An inaccessible cardinal κ is supercompact when (κ, λ)-ITP holds for all λ ≥ κ. We prove that if there is a model of ZFC with infinitely many supercompact cardinals, then there is a model of ZFC where for every n ≥ 2 and μ ≥ ℕn, we have (ℕn, μ)-ITP.

Mr. Shen Yuting, in this Journal, vol. 18, no. 2 (June, 1953), stated a new paradox of intuitive set-theory. This paradox involves what Mr. Yuting calls the class of all grounded classes, that is, the family of all classes a for which there is no infinite sequence b such that … ϵ bn ϵ … ϵ b2ϵb1 ϵ a.

Now it is possible to state this paradox without employing any complex set-theoretical notions (like those of a natural number or an infinite sequence). For let a class x be called regular if and only if (k)(x ϵ k ⊃ (∃y)(y ϵ k · ~(∃z)(z ϵ k · z ϵ y))). Let Reg be the class of all regular classes. I shall show that Reg is neither regular nor non-regular.

Suppose, on the one hand, that Reg is regular. Then Reg ϵ Reg. Now Reg ϵ ẑ(z = Reg). Therefore, since Reg is regular, there is a y such that y ϵ ẑ(z = Reg) · ~(∃z)(z ϵ z(z = Reg) · z ϵ y). Hence ~(∃z)(z ϵ ẑ(z = Reg) · z ϵ Reg). But there is a z (namely Reg) such that z ϵ ẑ(z = Reg) · z ϵ Reg.

On the other hand, suppose that Reg is not regular. Then, for some k, Reg ϵ k · [1] (y)(y ϵ k ⊃ (∃z)(z ϵ k · z ϵ y)). It follows that, for some z, z ϵ k · z ϵ Reg. But this implies that (ϵy)(y ϵ k · ~(ϵw)(w ϵ k · w ϵ y)), which contradicts [1].

It can easily be shown, with the aid of the axiom of choice, that the regular classes are just Mr. Yuting's grounded classes.

We investigate relationships between versions of derivability conditions for provability predicates. We show several implications and non-implications between the conditions, and we discuss unprovability of consistency statements induced by derivability conditions. First, we classify already known versions of the second incompleteness theorem, and exhibit some new sets of conditions which are sufficient for unprovability of Hilbert–Bernays’ consistency statement. Secondly, we improve Buchholz’s schematic proof of provable $\Sigma_1$ -completeness. Then among other things, we show that Hilbert–Bernays’ conditions and Löb’s conditions are mutually incomparable. We also show that neither Hilbert–Bernays’ conditions nor Löb’s conditions accomplish Gödel’s original statement of the second incompleteness theorem.

We give strengthened versions of the Herwig–Lascar and Hodkinson–Otto extension theorems for partial automorphisms of finite structures. Such strengthenings yield several combinatorial and group-theoretic consequences for homogeneous structures. For instance, we establish a coherent form of the extension property for partial automorphisms for certain Fraïssé classes. We deduce from these results that the isometry group of the rational Urysohn space, the automorphism group of the Fraïssé limit of any Fraïssé class that is the class of all ${\cal F}$-free structures (in the Herwig–Lascar sense), and the automorphism group of any free homogeneous structure over a finite relational language all contain a dense locally finite subgroup. We also show that any free homogeneous structure admits ample generics.

We study a generalization of the splitting number s to uncountable cardinals. We prove that 𝔰(κ) > κ+ for a regular uncountable cardinal κ implies the existence of inner models with measurables of high Mitchell order. We prove that the assumption 𝔰(ℵω) > ℵω+1 has a considerable large cardinal strength as well.

The theory of (ℝ, <, +, ℤ, ℤa) is decidable if a is quadratic. If a is the golden ratio, (ℝ, <, +, ℤ, ℤa) defines multiplication by a. The results are established by using the Ostrowski numeration system based on the continued fraction expansion of a to define the above structures in monadic second order logic of one successor. The converse that (ℝ, <, +, ℤ, ℤa) defines monadic second order logic of one successor, will also be established.

i) We show for each context-free language L that by considering each word of L as a structure in a natural way, one turns L into a finite union of classes which satisfy a finitary analog of the characteristic properties of complete universal first order classes of structures equipped with elementary embeddings. We show this to hold for a much larger class of languages which we call free local languages, ii) We define local languages, a class of languages between free local and context-sensitive languages. Each local language L has a natural extension L ∞ to infinite words, and we prove a series of “pumping lemmas”, analogs for each local language L of the “uvxyz theorem” of context free languages: they relate the existence of large words in L or L ∞ to the existence of infinite “progressions” of words included in L, and they imply the decidability of various questions about L or L ∞. iii) We show that the pumping lemmas of ii) are independent from strong axioms, ranging from Peano arithmetic to ZF + Mahlo cardinals.

We hope that these results are useful for a model-theoretic approach to the theory of formal languages.

The purpose of this paper is to give structural results on graphs lying in the product of two hyperfinite sets X and Y, whose Y-sections are either all internal sets or all of “small” cardinality with respect to the saturation assumption imposed on our nonstandard universe. These results generalize those of [KKML] and [HeRo]. In [KKML] Keisler, Kunen, Miller and Leth proved, among other results, that any countably determined function in the product of two internal sets X and Y can be covered by countably many internal functions provided that the nonstandard universe is at least ℵ-saturated. This shows that any countably determined function can be represented as a union of countably many restrictions of internal functions to countably determined sets. On the other hand, Henson and Ross use in [HeRo] Choquet's capacitability theorem to prove that any Souslin function in the product of two internal sets X and Y is a.e. equal to an internal function. (Here “a.e.” refers to an arbitrary but fixed bounded Loeb measure.) Therefore, in our terminology, every Souslin function possesses an internal a.e. lifting.

After the introductory §0, where all the necessary terminology is introduced, we continue by presenting the structural result for graphs all of whose Y-sections are of cardinality ≤κ (provided that the nonstandard universe is ≤κ+-saturated) in §1. We show that, under the above saturation assumption, a κ-determined graph with all of the Y-sections of cardinality ≤κ is covered by κ-many internal functions. Therefore, any such graph is a union of κ-many κ-determined functions. In particular if the graph in question is Borel, Souslin, κ-Borel or κ-Souslin (or a member of one of the Borel, κ-Borel or projective hierarchies) then the corresponding constituting functions are of the same “complexity”. Thus, any Borel graph all of whose Y-sections are at most countable is a union of countably many Borel functions and, consequently, has Borel domain. In the setting of Polish topological spaces this was proved by Novikov (see [De]).

It was brought to our attention by M. Fitting that Beth's semantic tableau system using the intuitionistic propositional rules and the classical quantifier rules produces a correct but incomplete axiomatization of the logic CD of constant domains. The formula

where T is a truth constant, being an instance of a formula which is valid in all Kripke models with constant domains but which is not provable without cut.

From the Fitting formula one can immediately obtain that the sequent

although provable in the system GD outlined in [3], does not have a cut-free proof (in the system GD).

If the only problem with GD were the sequent S0, then we could extend GD to the system GD+ by adding the following (correct) rule:

Since the new rule still satisfies the subformula property a cut elimination theorem for GD+ would be a step in the right direction for a syntactical proof for the interpolation theorem for the logic of constant domains (cf. Gabbay [2]; see also §4). Unfortunately, one can show that the sequent

where P is a propositional parameter (or formula without x free) has a derivation in GD+, but does not have a cut-free derivation (in GD+). Of course, we could extend GD+ to GD++ by adding the following correct (and with the subformula property) rule:

But then we can find a sequent S2 which, although provable with cut in GD++, does not have a cut-free derivation in GD++.

Let A be a countable admissible set (as defined in [1], [3]). The language LA consists of all infinitary finite-quantifier formulas (identified with sets, as in [1]) that are elements of A. Notationally, LA = A ∩ Lω1ω. Then LA is a countable subset of Lω1ω, the language of all infinitary finite-quantifier formulas with all conjunctions countable. The set is the set of Lω1ω sentences defined in 2.2 below. The following theorem characterizes those A-Σ1 sets Φ of LA sentences that have uncountable models.

Main Theorem (3.1.). If Φ is an A-Σ1set of LA sentences, then the following are equivalent:

(a) Φ has an uncountable model,

(b) Φ has a model with a proper LA-elementary extension,

(c) for every , ⋀Φ → C is not valid.

This theorem was announced in [2] and is proved in §§3, 4, 5. Makkai's earlier [4, Theorem 1] implies that, if Φ determines countable structure up to Lω1ω-elementary equivalence, then (a) is equivalent to (c′) for all , ⋀Φ → C is not valid.

The requirement in 3.1 that Φ is A-Σ1 is essential when the set ω of all natural numbers is an element of A. For by the example of [2], then there is a set Φ LA sentences such that (b) holds and (a) fails; it is easier to show that, if ω ϵ A, there is a set Φ of LA sentences such that (c) holds and (b) fails.

La première partie de cet article ([10], que nous désignerons par (I) dans la suite) était consacrée à la théorie élémentaire TX des algèbres de Boole munies d'idéaux distingués indéxés dans un ensemble X. On a vu que les idéaux définissables dans un modèle de Tx forment la sous-algèbre engendrée par les idéaux distingués de l'algèbre de Heyting des idéaux de munie de l'opérateur sa défini par sa(K) = {a: a/K est sans atome}, et que la théorie de peut être caractérisée par la structure composée de l'algèbre de Heyting des idéaux définissables munie de l'opérateur sa et des idéaux distingués, et par l'application qui à tout K de fait correspondre le nombre d'atomes de /K, pris dans N ⋃ {∞}.

Nous montrons maintenant que les structures possibles peuvent être définies de façon axiomatique en introduisant une classe équationnelle d'algèbres de Heyting munies d'une opération unaire, dites sa-algèbres de Heyting (en abrégé sa-AH), et en prouvant que cette classe est constituée des algèbres pouvant être plongées dans l'algèbre de Heyting des idéaux d'une algèbre de Boole, munie de l'opérateur sa. Ainsi les sont, à isomorphisme près, les sa-AH engendrées par des éléments distingués indéxés dans X; on en déduit une classification des extensions complètes de Tx en montrant que les applications qui peuvent être associées à une structure de la forme pour caractériser la théorie d'un modèle sont déterminées par leur restriction à une partie M() définie uniformément, sur laquelle elles prennent des valeurs dans (N − {0}) ⋃ {∞}, et que réciproquement toute application de M() dans (N − {0}) ⋃ {∞} est une telle restriction.

We employ an infinite-signature Hrushovski amalgamation construction to yield two results in Recursive Model Theory. The first result, that there exists a strongly minimal theory whose only recursively presentable models are the prime and saturated models, adds a new spectrum to the list of known possible spectra. The second result, that there exists a strongly minimal theory in a finite language whose only recursively presentable model is saturated, gives the second non-trivial example of a spectrum produced in a finite language.

We describe punctual categoricity in several natural classes, including binary relational structures and mono-unary functional structures. We prove that every punctually categorical structure in a finite unary language is ${\text {PA}}(0')$-categorical, and we show that this upper bound is tight. We also construct an example of a punctually categorical structure whose degree of categoricity is $0''$. We also prove that, with a bit of work, the latter result can be pushed beyond $\Delta ^1_1$, thus showing that punctually categorical structures can possess arbitrarily complex automorphism orbits.

As a consequence, it follows that binary relational structures and unary structures are not universal with respect to primitive recursive interpretations; equivalently, in these classes every rich enough interpretation technique must necessarily involve unbounded existential quantification or infinite disjunction. In contrast, it is well-known that both classes are universal for Turing computability.

§1. Introduction. Let M be a totally ordered set. A (Dedekind) cut p of M is a couple (pL, pR) of subsets pL, pR of M such that pL ⋃ pR = M and pL < pR, i.e., a < b for all a ∈ pL, b ∈ pR. In this article we are looking for model completeness results of o-minimal structures M expanded by a set pL for a cut p of M. This means the following. Let M be an o-minimal structure in the language L and suppose M is model complete. Let D be a new unary predicate and let p be a cut of (the underlying ordered set of) M. Then we are looking for a natural, definable expansion of the L(D)-structure (M, pL) which is model complete.

The first result in this direction is a theorem of Cherlin and Dickmann (cf. [Ch-Dic]) which says that a real closed field expanded by a convex valuation ring has a model complete theory. This statement translates into the cuts language as follows. If Z is a subset of an ordered set M we write Z+ for the cut p with pR = {a ∈ M ∣ a > Z} and Z− for the cut q with qL = {a ∈ M ∣ a < Z}.

We classify ultrafilters on ω with respect to sequential contours (see [4]. [5]) of different ranks. In this way we obtain an ω1 sequence of disjoint classes. We prove that non-emptiness of for successor α ≥ 2 is equivalent to the existence of P-point. We investigate relations between P-hierarchy and ordinal ultrafilters (introduced by J. E. Baumgartner in [1]). we prove that it is relatively consistent with ZFC that the successor classes (for α ≥ 2) of P-hierarchy and ordinal ultrafilters intersect but are not the same.

For a group G definable in a first order structure M we develop basic topological dynamics in the category of definable G-flows. In particular, we give a description of the universal definable G-ambit and of the semigroup operation on it. We find a natural epimorphism from the Ellis group of this flow to the definable Bohr compactification of G, that is to the quotient ${G^{\rm{*}}}/G_M^{{\rm{*}}00}$ (where G* is the interpretation of G in a monster model). More generally, we obtain these results locally, i.e., in the category of Δ-definable G-flows for any fixed set Δ of formulas of an appropriate form. In particular, we define local connected components $G_{{\rm{\Delta }},M}^{{\rm{*}}00}$ and $G_{{\rm{\Delta }},M}^{{\rm{*}}000}$, and show that ${G^{\rm{*}}}/G_{{\rm{\Delta }},M}^{{\rm{*}}00}$ is the Δ-definable Bohr compactification of G. We also note that some deeper arguments from [14] can be adapted to our context, showing for example that our epimorphism from the Ellis group to the Δ-definable Bohr compactification factors naturally yielding a continuous epimorphism from the Δ-definable generalized Bohr compactification to the Δ-definable Bohr compactification of G. Finally, we propose to view certain topological-dynamic and model-theoretic invariants as Polish structures which leads to some observations and questions.

We show that every nonzero Δ20, e-degree bounds a minimal pair. On the other hand, there exist Σ20, e-degrees which bound no minimal pair.

We give the first systematic study of strong isomorphism reductions, a notion of reduction more appropriate than polynomial time reduction when, for example, comparing the computational complexity of the isomorphim problem for different classes of structures. We show that the partial ordering of its degrees is quite rich. We analyze its relationship to a further type of reduction between classes of structures based on purely comparing for every n the number of nonisomorphic structures of cardinality at most n in both classes. Furthermore, in a more general setting we address the question of the existence of a maximal element in the partial ordering of the degrees.