Let L be a countable language including the unary relation symbol U. Let and be L-structures such that is a proper elementary U-extension of ; i.e., , and . Under what conditions will have a proper elementary U-extension? In [2], it was shown that this is not always the case, even if and are countable. However, the examples given are completely artificial, and it still seems that in most cases will have a proper elementary U-extension.

Lascar asked whether will necessarily have a proper elementary U-extension whenever it contains an infinite set of indiscernibles over . This paper gives a counterexample for Lascar's question. The example is produced by modifying one of the examples in [2], using an idea of Marcus [5].

Models containing an infinite set of indiscernibles can often be “stretched” to produce larger models that share some desired nonelementary property with the original [1], [6]. However, the mere presence of indiscernibles in a model does not guarantee that it can be used in this way.

If the model is not completely determined by the indiscernibles, the nonelementary property may not carry over to larger models. An example of this is given in [3]. The example for Lascar's question is further evidence that models with indiscernibles need not be “elastic”.

We prove that every model of T = Th(ω, <,…) (T countable) has an end extension; and that every countable theory with an infinite order and Skolem functions has nonisomorphic countable models; and that if every model of T has an end extension, then every ∣T∣-universal model of T has an end extension definable with parameters.

We construct a model of Peano arithmetic in an uncountable language which has no elementary end extension. This answers a question of Gaifman and contrasts with the well-known theorem of MacDowell and Specker which states that every model of Peano arithmetic in a countable language has an elementary end extension. The construction employs forcing in a nonstandard model.

In his celebrated paper of 1931 [7], Kurt Gödel proved the existence of sentences undecidable in the axiomatized theory of numbers. Gödel's proof is constructive and such a sentence may actually be written out. Of course, if we follow Gödel's original procedure the formula will be of enormous length.

Forty-five years have passed since the appearance of Gödel's pioneering work. During this time enormous progress has been made in mathematical logic and recursive function theory. Many different mathematical problems have been proved recursively unsolvable. Theoretically each such result is capable of producing an explicit undecidable number theoretic predicate. We have only to carry out a suitable arithmetization. Until recently, however, techniques were not available for carrying out these arithmetizations with sufficient efficiency.

In this article we construct an explicit undecidable arithmetical formula, F(x, n), in prenex normal form. The formula is explicit in the sense that it is written out in its entirety with no abbreviations. The formula is undecidable in the recursive sense that there exists no algorithm to decide, for given values of n, whether or not F(n, n) is true or false. Moreover F(n, n) is undecidable in the formal (axiomatic) sense of Gödel [7]. Given any of the usual axiomatic theories to which Gödel's Incompleteness Theorem applies, there exists a value of n such that F(n, n) is unprovable and irrefutable. Thus Gödel's Incompleteness Theorem can be “focused” into the formula F(n, n). Thus some substitution instance of F(n, n) is undecidable in Peano arithmetic, ZF set theory, etc.

We show it is consistent with ZFC that the Hanf number of Ellentuck's Souslin logic should be exactly .

Given I, a reasonable countable set of Turing degrees, can we find some sort of canonical strict upper bound on I? If I = {a ∣ a ≤ b}, the upper bound on I which springs to mind is b′. But what if I is closed under jump? This question arises naturally out of the question which motivates a large part of hierarchy theory: Is there a canonical increasing function from a countable ordinal, preferably a large one, into D, the set of Turing degrees? If d is to be such a function, it is natural to require that d(α + 1) = d(α)′; but how should d(λ) depend on d ↾ λ, where λ is a limit ordinal?

For any I ⊆ D, let MI, = ⋃I. Towards making the above questions precise, we introduce ideals of Turing degrees.

Definition 1. I ⊆ D is an ideal iff I is closed under jump and join, and I is downward-closed, i.e., if a ≤ b & b ϵ I then a ϵ I.

The following definition reflects the hierarchy-theoretic motivation for this paper.

Definition 2. For I ⊆ D and A ⊆ ω, I is an A-hierarchy ideal iff for some countable ordinal α, MI = Lα[A]∩ ωω.

All hierarchy ideals are ideals, but not conversely.

Early in the game Spector knocked out the best sort of canonicity for upper bounds on ideals, proving that no set of degrees closed under jump has a least upper bound.

Gödel has called to my attention that p. 773 is misleading in regard to the discovery of the finite axiomatization and its place in his proof of the consistency of GCH. For the version in [1940], as he says on p. 1, “The system Σ of axioms for set theory which we adopt [a finite one] … is essentially due to P. Bernays …”. However, it is not at all necessary to use a finite axiom system. Gödel considers the more suggestive proof to be the one in [1939], which uses infinitely many axioms.

His main achievement regarding the consistency of GCH, he says, really is that he first introduced the concept of constructible sets into set theory defining it as in [1939], proved that the axioms of set theory (including the axiom of choice) hold for it, and conjectured that the continuum hypothesis also will hold. He told these things to von Neumann during his stay at Princeton in 1935. The discovery of the proof of this conjecture On the basis of his definition is not too difficult. Gödel gave the proof (also for GCH) not until three years later because he had fallen ill in the meantime. This proof was using a submodel of the constructible sets in the lowest case countable, similar to the one commonly given today.