Recursive model theory involves the study of relationships between recursion theory and model theory. One direction this often takes is to study the effectiveness of various aspects of model theory. This paper examines such questions by examining some properties of recursive models; that is, models whose basic relations, functions, and constants are all uniformly recursive (and whose universe is the set of natural numbers). Somewhat more precisely:

Let be a model whose universe is N, and let (θ())i be an effective enumeration of all quantifier-free formulas of the language of . Then is recursive if {〈, i〉: satisfies (θ())i, in } is a recursive subset of N. (Here and throughout the paper, 〈 〉 denotes an effective pairing function, or an effective coding of sequences, as required.) Similarly, let (ϕ())i be an effective enumeration of all existential formulas of the language of . Then is existentially decidable if {〈, i〉: satisfies (ϕ())i in } is a recursive subset of N.

It is clear that if is recursive and is a model isomorphic to , then may lose many of the recursive properties of . In the simplest example, could easily fail to be a recursive model. But even if we require that be a recursive model, it could still fail to retain other recursive properties of . An example of the sort of property which can be studied in this vein is the following notion, introduced by Ash and Nerode in [2].

This work is an attempt to characterize the index sets of classes of recursively enumerable sets which are expressible in terms of open sets in the Baire topology on the power set of the set N of natural numbers, usual in recursion theory. Let be a class of subsets of N and be the set of indices of recursively enumerable sets Wх belonging to .

A well-known theorem of Rice and Myhill (cf. [5, p. 324, Rice-Shapiro Theorem]) states that is recursively enumerable if and only ifis a r.e. open set. In this case, note that if is not empty and does not contain all recursively enumerable sets, is a complete set. This theorem will be partially extended to classes which are boolean combinations of open sets by the following:

(i) There is a canonical boolean combination which represents, namely the shortest among boolean combinations which represent.

(ii) The recursive isomorphism type of depends on the length n of this canonical boolean combination (and trivial properties of ); for instance, is recursively isomorphic (in the particular case where is a boolean combination of recursive open sets) to an elementary set combination Yn or Un, constructed from {х ∣ х Wх) and depending on the length n. We can say also that is a complete set in the sense of Ershov's hierarchy [1] (in this particular case).

We characterize the expressive power of extensions of Dependence Logic and Independence Logic by monotone generalized quantifiers in terms of quantifier extensions of existential second-order logic.

This paper is concerned with n–localization property introduced by Newelski and Roslanowski in [10] and getting it for CS iterations of forcing notions.

Some negative results will be proved concerning the following for certain infinitary languages ℒ1 and ℒ2.

Definition. Beth(ℒ1, ℒ2) iff, for every sentence ϕ(R) of ℒ1, and n-place relation symbols R and S such that S does not occur in ϕ(R), if

then there is an ℒ2 formula θ(x1, …, xn) such that

and θ is built up using only those constant and relation symbols of ϕ other than R.

That is, Beth(ℒ1, ℒ2) iff for every implicit ℒ1 definition ϕ(R) of relations, there is a corresponding explicit ℒ2 definition θ. Beth(ℒωω, ℒωω) was proved by Beth.

Malitz proved that not Beth(ℒω1 ω1, ℒ∞∞) (hence not Beth (ℒ∞∞, ℒ∞∞)), but Beth (ℒ∞ω, ℒ∞∞). In §1, it is shown that Beth(ℒ∞ω, ℒ∞ω) is false. In §2, we strengthen this by showing that, for every cardinal κ, not Beth(ℒ∞ω, ℒ∞κ). In fact, not Beth (ℒκ+ω, ℒ∞κ) follows from property A(κ) defined in §2, and A(κ) is known for regular κ > ω (unpublished result of Morley).

More information on infinitary Beth and Craig theorems is given in [2] and [3]. We assume that the reader is acquainted with the languages ℒκλ which allow conjunctions over ≺κ formulas and quantifiers over ≺λ variables. Thus, we assume that the reader is acquainted with the back and forth argument for showing that two structures are ≡∞κ (ℒ∞κ-elementarily equivalent). Our notation is fairly standard.

A cylindric algebra atom structure is said to be strongly representable if all atomic cylindric algebras with that atom structure are representable. This is equivalent to saying that the full complex algebra of the atom structure is a representable cylindric algebra. We show that for any finite n ≥ 3, the class of all strongly representable n-dimensional cylindric algebra atom structures is not closed under ultraproducts and is therefore not elementary.

Our proof is based on the following construction. From an arbitrary undirected, loop-free graph Γ, we construct an n-dimensional atom structure , and prove, for infinite Γ, that is a strongly representable cylindric algebra atom structure if and only if the chromatic number of Γ is infinite. A construction of Erdős shows that there are graphs Γk(k < ω) with infinite chromatic number, but having a non-principal ultraproduct ΠDΓk whose chromatic number is just two. It follows that is strongly representable (each k < ω) but is not.

In this paper we develop some basic features of Galois cohomology, specifically the connection between first Galois cohomology groups and principal homogeneous spaces, in a model-theoretic context. “Descent theory” also fits into our approach.

The model theory involved is elementary, and the reader is referred to [2]. It should be said that we make crucial use of Meq in our analysis. The reader is also referred to Poizat's seminal paper “Une theorie de Galois imaginaire” ([6]). Although our results do not depend on Poizat's work, it is in his paper that the model-theoretic context is suggested for a generalised treatment of Galois theory.

Nothing in this paper is particularly deep. We are concerned mainly with translating between the Galois cohomological language and the language of definable sets and definable families of definable sets. We will introduce (in a suitable context) the notion of a definable cocycle (from an automorphism group to a definable group G). The (classical) situation of profinite and continuous cocycles will be a special case. Kolchin's theory of constrained cohomology will be another special case, and our results yield a substantially simpler proof of his Theorem 5 from Chapter VII of [4]. In any case model-theorists will see that definable cocycles correspond to objects with which they are already quite familiar—commuting families of definable bijections.

We will prove that there exists a model of ZFC+“c =” in which every M ⊆ ℝ of cardinality less than continuum c is meager, and such that for every X ⊆ ℝ of cardinality c there exists a continuous function f : ℝ → ℝ with f[X] = [0, 1].

In particular in this model there is no magic set, i.e., a set M ⊆ ℝ such that the equation f[M] = g[M] implies f = g for every continuous nowhere constant functions f,g: ℝ → ℝ.

A number of specific cardinal numbers have been defined in terms of /fin or ωω. Some have been generalized to higher cardinals, and some even to arbitrary Boolean algebras. Here we study eight of these cardinals, defining their generalizations to higher cardinals, and then defining them for Boolean algebras. We then attempt to completely describe their relationships within each of several important classes of Boolean algebras.

The generalizations to higher cardinals might involve several cardinals instead of just one as in the case of ω, For example, the number a associated with maximal almost disjoint families of infinite sets of integers can be generalized to talk about maximal subsets of [κ]μ subject to the pairwise intersections having size less than ν. (For this multiple generalization of . see Monk [2001].) For brevity we do not consider such generalizations, restricting ourselves to just one cardinal. The set-theoretic generalizations then associate with each infinite cardinal κ some other cardinal λ, defined as the minimum of cardinals with a certain property.

The generalizations to Boolean algebras assign to each Boolean algebra some cardinal λ, also defined as the minimum of cardinals with a certain property.

For the theory of the original “continuum” cardinal numbers, see Douwen [1984]. Balcar and Simon [1989]. and Vaughan [1990].

I am grateful to Mati Rubin for some conversations concerning these functions for superatomic algebras, and to Bohuslav Balcar for information concerning the function h.

The notation for set theory is standard. For Boolean algebras we follow Koppelberg [1989], but recall at the appropriate place any somewhat unusual notation.

In [1] it was claimed that the word problem for free fields with infinite centre can be solved. In fact it was asserted that if K is a skew field with infinite central subfield C, then the word problem in the free field on a set X over K can be solved, relative to the word problem in K.

As G. M. Bergman has pointed out (in a letter to the author), it is necessary to specify rather more precisely what type of problem we assume to be soluble for K: We must be able to decide whether or not a given finite set in K is linearly dependent over its centre. This makes it desirable to prove that the free field has a corresponding property (and not merely a soluble word problem). This is done in §2; interestingly enough it depends only on the solubility of the word problem in the free field (cf. Lemma 2 and Theorem 1′ below).

Bergman also notes that the proof given in [1] does not apply when K is finite-dimensional over its centre; this oversight is rectified in §4, while §3 lifts the restriction on C (to be infinite). However, we have to assume C to be the precise centre of K, and not merely a central subfield, as claimed in [1].

I am grateful to G. M. Bergman for pointing out the various inaccuracies as well as suggesting remedies.

We prove new upper bound theorems on the consistency strengths of SPFA(θ), SPFA(θ-linked) and SPFA(θ+ -cc). Our results are in terms of (θ, Γ)-subcompactness, which is a new large cardinal notion that combines the ideas behind subcompactness and Γ-indescribability. Our upper bound for SPFA(ϲ-linked) has a corresponding lower bound, which is due to Neeman and appears in his follow-up to this paper. As a corollary, SPFA(ϲ-linked) and PFA(ϲ-linked) are each equiconsistent with the existence of a -indescribable cardinal. Our upper bound for SPFA(ϲ-c.c) is a -indescribable cardinal, which is consistent with V = L. Our upper bound for SPFA(ϲ+-linked) is a cardinals κ that is (κ+,)-subcompact, which is strictly weaker than κ+-supercompact. The axiom MM(ϲ) is a consequence of SPFA(ϲ+-linked) by a slight refinement of a theorem of Shelah. Our upper bound for SPFA(ϲ++-c.c.) is a cardinal κ that is (κ+, )-subcompact, which is also strictly weaker than κ+-supercompact.

Shelah has provided sufficient conditions for an ${\Bbb L}_{\omega _1 ,\omega } $-sentence ψ to have arbitrarily large models and for a Morley-like theorem to hold of ψ. These conditions involve structural and set-theoretic assumptions on all the ${\aleph _n}$’s. Using tools of Boney, Shelah, and the second author, we give assumptions on ${\aleph _0}$ and ${\aleph _1}$ which suffice when ψ is restricted to be universal:

Theorem.Assume${2^{{\aleph _0}}} < {2^{{\aleph _1}}}$. Let ψ be a universal ${\Bbb L}_{\omega _1 ,\omega } $-sentence.

1. (1) If ψ is categorical in${\aleph _0}$and$1 \leqslant {\Bbb L}\left( {\psi ,\aleph _1 } \right) < 2^{\aleph _1 } $, then ψ has arbitrarily large models and categoricity of ψ in some uncountable cardinal implies categoricity of ψ in all uncountable cardinals.

2. (2) If ψ is categorical in${\aleph _1}$, then ψ is categorical in all uncountable cardinals.

The theorem generalizes to the framework of ${\Bbb L}_{\omega _1 ,\omega } $-definable tame abstract elementary classes with primes.

We investigate which filters on ω can contain towers, that is, a modulo finite descending sequence without any pseudointersection (in ${[\omega ]^\omega }$). We prove the following results:

1. (1) Many classical examples of nice tall filters contain no towers (in ZFC).

2. (2) It is consistent that tall analytic P-filters contain towers of arbitrary regular height (simultaneously for many regular cardinals as well).

3. (3) It is consistent that all towers generate nonmeager filters (this answers a question of P. Borodulin-Nadzieja and D. Chodounský), in particular (consistently) Borel filters do not contain towers.

4. (4) The statement “Every ultrafilter contains towers.” is independent of ZFC (this improves an older result of K. Kunen, J. van Mill, and C. F. Mills).

Furthermore, we study many possible logical (non)implications between the existence of towers in filters, inequalities between cardinal invariants of filters (${\rm{ad}}{{\rm{d}}^{\rm{*}}}\left( {\cal F} \right)$, ${\rm{co}}{{\rm{f}}^{\rm{*}}}\left( {\cal F} \right)$, ${\rm{no}}{{\rm{n}}^{\rm{*}}}\left( {\cal F} \right)$, and ${\rm{co}}{{\rm{v}}^{\rm{*}}}\left( {\cal F} \right)$), and the existence of Luzin type families (of size $\ge {\omega _2}$), that is, if ${\cal F}$ is a filter then ${\cal X} \subseteq {[\omega ]^\omega }$ is an ${\cal F}$-Luzin family if $\left\{ {X \in {\cal X}:|X \setminus F| = \omega } \right\}$ is countable for every $F \in {\cal F}$.

Given a supercompact cardinal κ and a regular cardinal λ < κ, we describe a type of forcing such that in the generic extension the cofinality of κ is λ, there is a very good scale at κ, a bad scale at κ, and SCH at κ fails. When creating our model we have great freedom in assigning the value of 2κ, and so we can make SCH hold or fail arbitrarily badly.

Horn [2] obtained a sufficient condition for an elementary class to be closed under direct product. Chang and Morel [1] showed that this is not a necessary condition. We will show that, if consideration is restricted to identity theory, that is, a first-order predicate calculus with equality but no other relation symbols or operation symbols, Horn's condition is necessary and sufficient.

A model for identity theory consists of a non-empty domain A, but no relations or operations except equality. If I is an index set, and for each is a model for identity theory, then the direct product of the is a model for identity theory and has domain A, the cartesian product of the Ai.

We consider the following question of Kunen:

Does Con(ZFC + ∃M a transitive inner model and a non-trivial elementary embedding j: M → V)

imply Con(ZFC + ∃ a measurable cardinal)?

We use core model theory to investigate consequences of the existence of such a j: M → V. We prove, amongst other things, the existence of such an embedding implies that the core model K is a model of “there exists a proper class of almost Ramsey cardinals”. Conversely, if On is Ramsey, then such a j. M are definable.

We construe this as a negative answer to the question above. We consider further the consequences of strengthening the closure assumption on j to having various classes of fixed points.

We prove here that the intuitionistic theory T0↾ + UMIDN. or even EETJ↾ + UMIDN, of Explicit Mathematics has the strength of –CA0. In Section 1 we give a double-negation translation for the classical second-order μ-calculus, which was shown in [Mö02] to have the strength of –CA0. In Section 2 we interpret the intuitionistic μ-calculus in the theory EETJ↾ + UMIDN. The question about the strength of monotone inductive definitions in T0 was asked by S. Feferman in 1982, and — assuming classical logic — was addressed by M. Rathjen.

In this paper we introduce a new property of families of functions on the Baire space, called pseudo-dominating, and apply the properties of these families to the study of cardinal characteristics of the continuum. We show that the minimum cardinality of a pseudo-dominating family is min {τ, ∂}. We derive two corollaries from the proof: τ ≥ min{∂, u} and min{∂, τ} = min{∂, τσ}. We show that if a dominating family is partitioned into fewer that s pieces, then one of the pieces is pseudo-dominating. We finally show that u < g implies that every unbounded family of functions is pseudo-dominating, and that the Filter Dichotomy principle is equivalent to every unbounded family of functions being finitely pseudo-dominating.

We prove that every rectangularly dense diagonal-free cylindric algebra is representable. As a corollary, we give finite, sound and complete axiomatizations for the finite-variable fragments of first order logic without equality and for multi-dimensional modal S5-logic.