It is shown that coherence conditions for monoidal categories concerning associativity are analogous to coherence conditions for symmetric strictly monoidal categories, where associativity arrows are identities. Mac Lane's pentagonal coherence condition for associativity is decomposed into conditions concerning commutativity, among which we have a condition analogous to naturality and a degenerate case of Mac Lane's hexagonal condition for commutativity. This decomposition is analogous to the derivation of the Yang-Baxter equation from Mac Lane's hexagon and the naturality of commutativity. The pentagon is reduced to an inductive definition of a kind of commutativity.

In the constructive theory of uniform spaces there occurs a technique of proof in which the application of a weak form of the law of excluded middle is circumvented by purely analytic means. The essence of this proof–technique is extracted and then applied in several different situations.

Hilbert and Ackermann ([1], p. 107) define a first order axiom system as one in which the axioms contain one or more predicate constants, but no predicate variables. Here “axiom” refers to the specific subject-matter axioms and not to the rules of the restricted predicate calculus (quantification theory), which rules are presupposed for each first-order system. It is pointed out by them that an exception could be made for the predicate of identity; for the axiom scheme for this predicate, namely

which has in (b) the variable predicate F, could nevertheless be replaced, in any given first-order system, by a finite set of axioms without predicate variables. Thus, for example, if Φ[x, y) is the one constant predicate of such a system then PId(b) could be replaced by

Thus one postulates, in addition to the reflexivity, symmetry, and transitivity of identity, the substitutivity of identical entities in each of the possible “atomic” contexts of a variable (occurrences in the primitive predicates). In this method of introducing identity it has to be taken as an additional primitive predicate and further axioms are consequently needed. In such a system having PId(a), (b1)−(b3) as axioms, the scheme PId(b) can be derived as a meta-theorem of the system, F(x) then being any formula of the system.

We prove that the statement “there is a k such that for every f there is a k-bounded diagonally nonrecursive function relative to f” does not imply weak König’s lemma over ${\rm{RC}}{{\rm{A}}_0} + {\rm{B\Sigma }}_2^0$. This answers a question posed by Simpson. A recursion-theoretic consequence is that the classic fact that every k-bounded diagonally nonrecursive function computes a 2-bounded diagonally nonrecursive function may fail in the absence of ${\rm{I\Sigma }}_2^0$.

Extending work of Puninski, Puninskaya and Toffalori in [5], we show that if V is an effectively given valuation domain then the theory of all V-modules is decidable if and only if there exists an algorithm which, given a, b ε V, answers whether a ε rad(bV). This was conjectured in [5] for valuation domains with dense value group, where it was proved for valuation domains with dense archimedean value group. The only ingredient missing from [5] to extend the result to valuation domains with dense value group or infinite residue field is an algorithm which decides inclusion for finite unions of Ziegler open sets. We go on to give an example of a valuation domain with infinite Krull dimension, which has decidable theory of modules with respect to one effective presentation and undecidable theory of modules with respect to another. We show that for this to occur infinite Krull dimension is necessary.

Let Msw denote the least iterable inner model with a strong cardinal above a Woodin cardinal. By [11], Msw has a fully iterable core model, ${K^{{M_{{\rm{sw}}}}}}$, and Msw is thus the least iterable extender model which has an iterable core model with a Woodin cardinal. In V, ${K^{{M_{{\rm{sw}}}}}}$ is an iterate of Msw via its iteration strategy Σ.

We here show that Msw has a bedrock which arises from ${K^{{M_{{\rm{sw}}}}}}$ by telling ${K^{{M_{{\rm{sw}}}}}}$ a specific fragment ${\rm{\bar{\Sigma }}}$ of its own iteration strategy, which in turn is a tail of Σ. Hence Msw is a generic extension of $L[{K^{{M_{{\rm{sw}}}}}},{\rm{\bar{\Sigma }}}]$, but the latter model is not a generic extension of any inner model properly contained in it.

These results generalize to models of the form Ms (x) for a cone of reals x, where Ms (x) denotes the least iterable inner model with a strong cardinal containing x. In particular, the least iterable inner model with a strong cardinal above two (or seven, or boundedly many) Woodin cardinals has a 2-small core model K with a Woodin cardinal and its bedrock is again of the form $L[K,{\rm{\bar{\Sigma }}}]$.

If A and B are subsets of natural numbers we say that A is recursively equivalent to B (denoted A ≃ B) if there is a one-one partial recursive function which maps A onto B, and that A is recursively isomorphic to B (denoted A ≅ B) if there is a one-one total recursive function which maps A onto B and Ā (the complement of A) onto B#x00AF;.

This paper contains a proof–theoretic account of unification in intermediate logics. It is shown that many existing results can be extended to fragments that at least contain implication and conjunction. For such fragments, the connection between valuations and most general unifiers is clarified, and it is shown how from the closure of a formula under the Visser rules a proof of the formula under a projective unifier can be obtained. This implies that in the logics considered, for the n-unification type to be finitary it suffices that the m-th Visser rule is admissible for a sufficiently large m. At the end of the paper it is shown how these results imply several well-known results from the literature.

We consider locally o-minimal structures possessing tame topological properties shared by models of DCTC and uniformly locally o-minimal expansions of the second kind of densely linearly ordered abelian groups. We derive basic properties of dimension of a set definable in the structures including the addition property, which is the dimension equality for definable maps whose fibers are equi-dimensional. A decomposition theorem into quasi-special submanifolds is also demonstrated.

It is known that we can introduce in number theory (for example, the system Z of Hilbert-Bernays) by induction schemata certain predicates of natural numbers which cannot be expressed explicitly within the framework of number theory. The question arises how we can define these predicates in some richer system, without employing induction schemata. In this paper a general notion of definability by induction (relative to number theory), which seems to apply to all the known predicates of this kind, is introduced; and it is proved that in a system L1 which forms an extension of number theory all predicates which are definable by induction (hereafter to be abbreviated d.i.) according to the definition are explicitly expressible.

In order to define such predicates and prove theorems answering to their induction schemata, we have to allow certain impredicative classes in L1. However, if we want merely to prove that for each constant number the special case of the induction schema for a predicate d.i. is provable, we do not have to assume the existence of impredicative classes. A certain weaker system L2, in which only predicative classes of natural numbers are allowed, is sufficient for the purpose. It is noted that a truth definition for number theory can be obtained in L2. Consistency proofs for number theory do not seem to be formalizable in L2, although they can, it is observed, be formalized in L1.

In general, given any ordinary formal system (say Zermelo set theory), it is possible to define by induction schemata, in the same manner as in number theory, certain predicates which are not explicitly definable in the system. Here again, by extending the system in an analogous fashion, these predicates become expressible in the resulting system. The crucial predicate instrumental to obtaining a truth definition for a given system is taken as an example.

In this paper we consider a fonnal system of second-order Peano arithmetic with a rule of inference stronger than the ω-rule [3]. We also consider the relation to a class of models for analysis (i.e. second-order arithmetic) which lies between the class of ω-models and the class of β-models [5].

The notation used is largely that of [3] and [5]. We assume that the reader has some familiarity with at least the ideas of the former. The formal system (A) of Peano arithmetic employed in [3] includes the comprehension axioms and the second-order induction axiom.

This paper is a continuation of [27], where we provide the background and the basic tools for studying the structural properties of classes of models over languages without equality. In the context of such languages, it is natural to make distinction between two kinds of classes, the so-called abstruct classes, which correspond to those closed under isomorphic copies in the presence of equality, and the reduced classes, i.e., those obtained by factoring structures by their largest congruences. The generic problem described in [27] is to investigate under what conditions this reduction process does not alter the metatheory of a class.

Here we focus our attention on a concrete aspect of this generic problem that we import from universal algebra, namely the existence and description of free models. As in [27], we can find here again the basic notion of protoalgebraicity, which was originally introduced in [7] as the weakest condition to guarantee that the reduction process behaves reasonably well from an algebraic point of view. Our concern, however, takes us to handle a further notion, that of semialgebraicity, which corresponds to the notion of equivalential logic of [18]; semialgebraicity turns out to be the property which ensures that freeness is fully preserved by the reduction process.

Hrushovski's generalization of the Fraisse construction has provided a rich source of examples in model theory, model theoretic algebra and random graph theory. The construction assigns to a dimension function δ and a class K of finite (finitely generated) models a countable ‘generic’ structure. We investigate here some of the simplest possible cases of this construction. The class K will be a class of finite graphs; the dimension, δ(A), of a finite graph A will be the cardinality of A minus the number of edges of A. Finally and significantly we restrict to classes which are δ-invariant. A class of finite graphs is δ-invariant if membership of a graph in the class is determined (as specified below) by the dimension and cardinality of the graph, and dimension and cardinality of all its subgraphs. Note that a generic graph constructed as in Hrushovski's example of a new strongly minimal set does not arise from a δ-invariant class.

We show there are countably many δ-invariant (strong) amalgamation classes of finite graphs which are closed under subgraph and describe the countable generic models for these classes. This analysis provides ω-stable generic graphs with an array of saturation and model completeness properties which belies the similarity of their construction. In particular, we answer a question of Baizhanov (unpublished) and Baldwin [5] and show that this construction can yield an ω-stable generic which is not saturated. Further, we exhibit some ω-stable generic graphs that are not model complete.

In a 1969 paper, Quine coined the term ‘limits of decision”. This term evidently refers to limits on the logical vocabulary of a logic, beyond which satisfiability is no longer decidable. In the same paper, Quine showed that not only monadic formulas, but homogeneous k -adic formulas for arbitrary k lie on the decidable side of the limits of decision. But the precise location of the limits of decision has remained an open question. The present paper answers that question. It addresses the question of decidability of those sublogics of first-order logic that are defined in terms of their logical vocabularies. A complete answer is obtained, thus locating exactly Quine's limits of decision.

We consider the arithmetic complexity of index sets of uniformly computably enumerable families learnable under different learning criteria. We determine the exact complexity of these sets for the standard notions of finite learning, learning in the limit, behaviorally correct learning and anomalous learning in the limit. In proving the ${\rm{\Sigma }}_5^0$-completeness result for behaviorally correct learning we prove a result of independent interest; if a uniformly computably enumerable family is not learnable, then for any computable learner there is a ${\rm{\Delta }}_2^0$ enumeration witnessing failure.

We investigate computability theoretic and descriptive set theoretic contents of various kinds of analytic choice principles by performing a detailed analysis of the Medvedev lattice of $\Sigma ^1_1$ -closed sets. Among others, we solve an open problem on the Weihrauch degree of the parallelization of the $\Sigma ^1_1$ -choice principle on the integers. Harrington’s unpublished result on a jump hierarchy along a pseudo-well-ordering plays a key role in solving this problem.

Under a sharp version of the assumption I∆0 ⊢ ¬ ∆0H we characterize models of I∆0 + BΣ1 having a proper end extension to a model of I∆0.

In [WP] Wilkie and Paris study the relationship between the existence of a proper end extension of a model and its “fullness”, which is related to a certain weak overspill principle (we recall the definition of fullness in §3). Let M be a countable nonstandard model of I∆0 + BΣ1. Under the hypothesis I∆0 ⊢ ¬ ∆0H they prove the following (Corollaries 7 and 8):

The following are equivalent:

1. 1) M has a proper end extension to a model of I∆0 + BΣ1.

2. 2) M is (I∆0 + BΣ1)-full.

Moreover, assuming that there is no t ∈ M such that for v ∈ M, 2[t/v]exists if and only if v < N, the following are equivalent:

1. 1) M has a proper end extension to a model of I∆0.

2. 2) M is I∆0-full.

Wilkie and Paris ask whether the assumption on the structure of the model can be eliminated from the second equivalence.

We eliminate it, but we sharpen the assumption I∆0 ⊢ ¬ ∆0H. So we partially answer their question.

Let K be a function field of one variable over a constant field C of finite transcendence degree over ℂ. Let M/K be a finite extension and let W be a set of primes of K such that all but finitely many primes of W do not split in the extension M/K. Then there exists a set W′ of K-primes such that Hilbert's Tenth Problem is not decidable over OK,W′ = {x ϵ K∣ordþx ≥ 0, ∀þ ∉ W′}, and the set (W′ ∖ W)∪{W ∖ W′) is finite.

Let K be a function field of one variable over a constant field C finitely generated over ℚ. Let M/K be a finite extension and let W be a set of primes of K such that all but finitely many primes of W do not split in the extension M/K and the degree of all the primes in W is bounded by b ϵ ℕ. Then there exists a set W′ of K-primes such that ℤ has a Diophantine definition over OK,W′, and the set (W′ ∖ W)∪(W ∖ W′) is finite.

We study local strengthenings of the simplicity condition. In particular, we define and study a local Lascar rank, as well as short, low. supershort and superlow theories. An example of a low non supershort theory is given.