Here we prove the following:

Theorem. For every N ≤ ω there is a complete theory Tn having exactly n nonisomorphic rigid models and no uncountable rigid models. Moreover, each non-rigid model admits a nontrivial automorphism.

The Tn are theories in the first-order predicate calculus and a rigid structure is a structure with no nontrivial endomorphisms, i.e., the only endomorphism of the structure into itself is the identity. The theorem answers a question of A. Ehrenfeucht.

For the most part we use standard model theoretic notation with Th denoting the set of sentences true in and meaning . A complete set of sentences is one of the form Th for some . The universe of a structure may be denoted by ∣∣. An n-ary relation on X is a set of n tuples (x0, …, xn−1) with each xi ∈ X. All the structures encounted here will be relational. If P is an n-ary relation then P ↾ Y, the restriction of P to Y, is {(x0, …, xn−1): (x0, …, xn−1) ∈ P and x0, …, xn−1Y}.

In this paper we investigate some of the recursion-theoretic problems which are suggested by the logical notion of independence.

A set S of natural numbers will be said to be k-independent (respectively, ∞-independent) if, roughly speaking, in every correct system there is a k-element set (respectively, an infinite set) of independent true sentences of the form x ∈ S. S will be said to be effectively independent (respectively, absolutely independent) if given any correct system we can generate an infinite set of independent (respectively, absolutely independent) true sentences of the form x ∈ S.

We prove that

(a) S is absolutely independent ⇔S is effectively independent ⇔S is productive;

(b) for every positive integer k there is a Π1 set which is k-independent but not (k + 1)-independent;

(c) there is a Π1 set which is k-independent for all k but not ∞-independent;

(d) there is a co-simple set which is ∞-independent.

We also give two new proofs of the theorem of Myhill [1] on the existence of an infinite set of Σ1 sentences which are absolutely independent relative to Peano arithmetic. The first proof uses the existence of an absolutely independent Π1 set of natural numbers, and the second uses a modification of the method of Gödel and Rosser.

In the early days of the development of Kripke-style semantics for modal logic a great deal of effort was devoted to showing that particular axiom systems were characterised by a class of models describable by a first-order condition on a binary relation. For a time the approach seemed all encompassing, but recent work by Thomason [6] and Fine [2] has shown it to be somewhat limited—there are logics not determined by any class of Kripke models at all. In fact it now seems that modal logic is basically second-order in nature, in that any system may be analysed in terms of structures having a nominated class of second-order individuals (subsets) that serve as interpretations of propositional variables (cf. [7]). The question has thus arisen as to how much of modal logic can be handled in a first-order way, and precisely which modal sentences are determined by first-order conditions on their models. In this paper we present a model-theoretic characterisation of this class of sentences, and show that it does not include the much discussed LMp → MLp.

Definition 1. A modal frame ℱ = 〈W, R〉 consists of a set W on which a binary relation R is defined. A valuation V on ℱ is a function that associates with each propositional variable p a subset V(p) of W (the set of points at which p is “true”).

The following is a classical result:

Theorem 1.1. A complete atomic Boolean algebra is isomorphic to a power set algebra [2, p. 70].

One of the consequences of [3] is: If M is a countable standard model of ZF and is a countable (in M) model of a complete ℵ0-categorical theory T, then there is a countable standard model N of ZF and a Λ ∈ N such that the Boolean algebra of definable (in T with parameters from ) subsets of is isomorphic to the power set algebra of Λ in N. In particular if and T the theory of equality with additional axioms asserting the existence of at least n distinct elements for each n < ω, then there is an N and Λ ∈ N with 〈PN(Λ), ⊆〉 isomorphic to the countable, atomic, incomplete Boolean algebra of the finite and cofinite subsets of ω.

From the above we see that some incomplete Boolean algebras can be realized as power sets in standard models of ZF.

Definition 1.1. A countable Boolean algebra 〈B, ≤〉 is a pseudo-power set if there is a countable standard model of ZF, N and a set Λ ∈ N such that

It is clear that a pseudo-power set is atomic.

The aim of this paper is to correct an error in the proof in [2] of a strengthened version of Hilbert's second ε-theorem.

Hilbert's original theorem says (effectively) that formulae of the form ∃xA → A(εxA) can be eliminated from deductions of ∈-free sentences B (i.e. those which do not contain the ε-symbol) from collections X of ε-free sentences. The extended version (Theorem III. 11 of [2]) says that, in addition, instances of Ackermann's schema can also be eliminated.

The error in [2] occurs in the proof of Theorem III.7 and is described as follows. If A′ is the formula obtained from A by replacing every occurrence of ∃yB by B(εyB) (or ∀yC by C(εyB) if B is of the form ¬ C), and if A is a Q3 or Q4-axiom then, contrary to the claim on p. 73 of [2], A′ is not necessarily an axiom of the same form. For example, if A is the Q3-axiom

where the rank of εx∃yD(x, y) is ≤ the rank of εyB (see p. 70) and where B is D(t,y), then A′ is

which is not a Q3-axiom. In other words, the notion of rank as defined in [2] is inadequate for the proof of Theorem III.11.

In a recent paper [3] H. Gaifman investigated some model theoretic consequences of Matijasevič's theorem [5], and posed some further problems which naturally arise. We provide here partial answers to two of these problems, the results having been previously announced in the postscript of [3].

Firstly, it is shown in [3] that if M1 and M2 are models of the Peano axioms P and M1 ⊆ M2, then M1 is closed under the recursive functions of M2. The converse of this statement is false. Moreover, Gaifman asks: Is every initial segment of a model M of P which is closed under the recursive functions of M (or the ∑n-definable functions) also a model of P? We show that this is false and our method gives, en route, another proof of a theorem of Rabin [7] stating the P is not implied by any consistent set of ∑n sentences for any n.

Secondly, we partially answer a question posed on p. 129 of [3] by proving (some-what more than) every countable nonstandard model of P has an end extension in which a diophantine equation, not solvable in the original model, has a solution. We can, in fact, take the new model to be isomorphic to the original one. This generalises (apart from the countability restriction) a theorem of Rabin [6].

In [2] Bachmann showed how a hierarchy of normal functions on the countable ordinals Ω can be constructed using certain uncountable ordinals together with appropriate fundamental sequences for limit ordinals, as indexing ordinals for the hierarchy. This method, explained in more detail in §1 below, has been generalized by Pfeiffer [6] and Isles [4] to produce larger hierarchies. Using the hierarchies constructed in this way it is possible, as an immediate consequence of the definitions, to assign ω-sequences 〈αn〉n∈ω to limit ordinals α in an initial segment I of Ω such that . Indeed this was the motivation for Bachmann's original construction. However the initial segments I constructed in this way are of interest even without the fundamental sequences because they occur naturally as the proof-theoretic ordinals associated with particular formal theories. The fundamental sequences necessary for the Bachmann method are not intrinsically of interest proof-theoretically and only serve to obscure the definitions of the associated initial segments. Feferman and Weyhrauch [9] suggested an alternative definition for a sequence of functions on the countable ordinals. This definition was generalized by Aczel [1] who showed how the new functions corresponded to those in Bachmann's hierarchy. (Independently, Weyhrauch established the same results for an initial segment of the sequence of Bachmann functions, i.e. those functions indexed by α < εΩ+1.)

Takeuti [6] has suggested the need for higher axioms for set theory which are analogous to higher axioms of infinity, but which claim that power sets are in some sense large. In this paper we investigate a reflection axiom of this sort (Axiom T).

In §1, we introduce Axiom T and explore some related axioms. A technical lemma involving an elementary embedding is developed in §2 which allows us, in §3, to prove the relative consistency of Axiom T.

The reader is assumed to be familiar with ramified forcing languages and the usual techniques of forcing. A suitable treatment of these subjects is given by Takeuti and Zaring [7].

ZFC, GBC, ZF and GB are the set theories of Zermelo-Fraenkel and of Gödel-Bernays, with and without the axiom of choice (AC). CH is the continuum hypothesis.

For α an ordinal, define

For p1, p2 ∈ pα let p1 ≤ p2 mean that p1 ⊇ p2 (thus p1 is the stronger forcing condition). It is well known that Pα satisfies the countable chain condition [5].

This note is concerned with an aspect of the length of proof of formulas in recursively enumerable theories T adequate for recursive arithmetic. In particular, we consider the relative length of proof of formulas in the theories T and T(S), where F represents an r.e. set A in T and T(S) is the theory obtained from T by adjunction, as a new axiom, of a sentence S undecidable in T.

Throughout the sequel T is a consistent, r.e. theory with standard formalization [7] in which all recursive functions of one variable are definable, and in which there is a binary formula x ≤ satisfying the well-known conditions [7]:

Here is the constant term corresponding to the natural number n. Wn is the nth r.e. set in a standard enumeration of the r.e. sets. Also, we assume an a priori Gödel numbering of our formalism satisfying the usual conditions, so that all formulas are numbers ab initio.

In the more common applications of the theorem below, if F is a k-ary formula of T, is a natural number that measures in some way the length of the shortest proof of in T.

Sacks [2] has asked whether there exists a uniform solution to Post's problem, i.e. an enumeration operation W such that d < W(d) < d′ for every degree d. It is shown here that if such an operation W exists it cannot itself in a particular technical sense be uniform. In fact, the jump operation is characterized amongst such uniform enumeration operations by the condition: d < W(d) for all d. In addition, it is proved that the only other uniform enumeration operations such that d ≤ W(d) for all d are those which equal the identity operation above some fixed degree.

An algorithm has been described by S. Burris [3] which decides if a finite set of identities, whose function symbols are of rank at most 1, has a finite, nontrivial model. (By “nontrivial” it is meant that the universe of the model has at least two elements.) As a consequence of some results announced in the abstracts [2] and [8], it is clear that if the restriction on the ranks of function symbols is relaxed somewhat, then this finite model problem is no longer solvable by an algorithm, or at least not by a “recursive algorithm” as the term is used today.

In this paper we prove a sharp form of this negative result; showing, by the way, that Burris' result is in a sense the best possible result in the positive direction. Our main result is that in a first order language whose only function or relation symbol is a 2-place function symbol (the language of groupoids), the set of identities that have no nontrivial model, is recursively inseparable from the set of identities such that the sentence has a finite model. As a corollary, we have that each of the following problems, restricted to sentences defined in the language of groupoids, is algorithmically unsolvable: (1) to decide if an identity has a finite nontrivial model; (2) to decide if an identity has a nontrivial model; (3) to decide if a universal sentence has a finite model; (4) to decide if a universal sentence has a model. We note that the undecidability of (2) was proved earlier by McNulty [13, Theorem 3.6(i)], improving results obtained by Murskiǐ [14] and by Perkins [17]. The other parts of the corollary seem to be new.

Consider modal propositional formulae, constructed using proposition-letters, connectives and the modal operators □ and ⋄. The semantic structures are frames, i.e., pairs <W, R> with R ⊆ W2. Let F, V be variables ranging respectively over frames and functions from the set of proposition-letters into the powerset of W. Then the relation

may be defined, for arbitrary formulae α, following the Kripke truth-definition. From this relation we may further define

Now, to every modal formula α there corresponds some property Pα of R. A particular example is obtained by considering the well-known translation of modal formulae into formulae of monadic second-order logic with a single binary first-order predicate. For these particular Pα we have

for all F and w ∈ W. These formulae Pα are, however, rather intractable and more convenient ones can often be found. An especially interesting case occurs when Pα may be taken to be some first-order formula. For example, it can be seen that

for all F and w ∈ W. It is customary to talk about a related correspondence, namely when for all F we have

Note that this correspondence holds whenever the first one above holds.

Our unexplained notation is that of Rogers [4]. Let P ⊆ 2N × 2N. We call a sequence <An: n ∈ N> of subsets of N a P-sequence iff ∀n(An+1 = the unique B such that P(An, B)).

Theorem. Let P ⊆ 2N × 2N be arithmetical. Then there is no P-sequence <An: n ∈ N> such that ∀n(A′n+1 ≤T An).

This theorem improves a result of Friedman [2] who showed that for no arithmetical P is there a P-sequence <An: n ∈ N> such that An + 1 is a code for an ω-model of the relative arithmetic comprehension schema, and An + 1 is present in the model coded by An, for all n. Other related results are those of Harrison [3], who showed there is a sequence <An: n ∈ N> such that ∀n<A′n + 1 ≤T An>, and of Enderton and Putnam [1], who showed there is no sequence <An: n ∈ N> with ∀n(A′n + 1 ≤T An) and A0 hyperarithmetic.

Our theorem is closely connected to Gödel's second incompleteness theorem. Its proof is a recursion theoretic parallel to the proof of Gödel's theorem. In §2 we draw a version of Gödel's theorem as a corollary to ours.

Much effort has been spent to prove that the reduced product operation preserves, and sometimes even strengthens the L-equivalence of structures, where L is some infinitary language. A similar result is suggested by the following well-known fact:

Assume D is a nonprincipal ultrafilter on ω and, for n Є ω, Cn is a set. If the ultra-product ΠωCn/D is infinite, it has a cardinality ≥ Hence, by Łos' theorem, (i) if and φ(x) is a first-order formula, then iff where Q is the unary quantifier “there are many.”

We shall prove some generalizations of (i). In particular, we show

(ii) if D is a nonprincipal ultrafilter over I = ω, and then where L(Q) is the language obtained from the first-order language by adding the quantifier Q.

(ii) remains true, if D is an ω-regular or an atomless filter over a set I.

Lipner [7] proved that if is regular, then the L(Q)-equivalence is preserved under direct products. We show that the assumption “ is regular” is necessary.

The concept of a topos as a system, or world in which mathematics could be defined and interpreted, was developed by F. W. Lawvere and M. Tierney. Much of their work is embodied in the lecture notes Elementary toposes by A. Kock and G. C. Wraith [6].

In an early paper Lawvere set forth a set of axioms for approximately such a system [8]. The topos constructed there is a set-like category that includes among its axioms an axiom of infinity and an axiom of choice.

In its final form an elementary topos is freed from any such axioms.

The most prominent example of an elementary topos is a set theory with the usual Zermelo-Fraenkel or Godel-Bernays set of axioms.

In this paper I have tried to determine what, if any, is the effect of an axiom of choice introduced in a topos, and how are some of the set-theoretic equivalents of such an axiom related in topos theory.

Since the set-theoretic membership relation ∈, the notions of an “empty” set and a “power” set are definable in topos theory, it makes sense to talk about a “choice map” that picks a single element out of every nonempty object, provided that these objects can be somehow collected into a single object or “family.” In other words, an analogue of the usual choice axiom can be formulated in elementary topos language; this is axiom AC2 of the text.