§1. Introduction. This paper considers several complexity questions regarding Borel automorphisms of a Polish space. Recall that a Borel automorphism is a bijection of the space with itself whose graph is a Borel set (equivalently, the inverse image of any Borel set is Borel). Since the inverse of a Borel automorphism is another Borel automorphism, as is the composition of two Borel automorphisms, the set of Borel automorphisms of a given Polish space forms a group under the operation of composition. We can also consider the class of automorphisms of all Polish spaces. We will be primarily concerned here with the following notion of equivalence:

Definition 1.1. Two Borel automorphisms f and g of the Polish spaces X and Y are said to be Borel isomorphic, f ≅ g, if they are conjugate, i.e. there is a Borel bijection φ: X → Y such that φ ∘ f = g ∘ φ.

We restrict ourselves to automorphisms of uncountable Polish spaces, as the Borel automorphisms of a countable space are simply the permutations of the space. Since any two uncountable Polish spaces are Borel isomorphic, any Borel automorphism is Borel isomorphic to some automorphism of a fixed space. Hence, up to Borel isomorphism we can fix a Polish space and represent any Borel automorphism as an automorphism of this space. We will use the Cantor space 2ω (with the product topology) as our representative space.

We isolate a forcing which increases the value of while preserving ω1 under the assumption that there is a precipitous ideal on ω1 and a measurable cardinal.

We show that if I is a precipitous ideal on ω1 and if θ > ω1 is a regular cardinal, then there is a forcing ℙ = ℙ(I, θ) which preserves the stationarity of all I-positive sets such that in Vℙ, ⟨Hθ; ∈, I⟩ is a generic iterate of a countable structure ⟨M; ∈, Ī⟩. This shows that if the nonstationary ideal on ω1 is precipitous and exists, then there is a stationary set preserving forcing which increases . Moreover, if Bounded Martin's Maximum holds and the nonstationary ideal on ω1 is precipitous, then .

We give several new characterizations of the continuous enumeration degrees. The main one proves that an enumeration degree is continuous if and only if it is not half of a nontrivial relativized $\mathcal {K}$ -pair. This leads to a structural dichotomy in the enumeration degrees.

Many philosophers take set-theoretic discourse to be about objects of a special sort, namely sets; correlatively, they regard truth in such discourse as quite like truth in discourse about nonmathematical objects. There is a thin “disquotational” way of construing this construal; but that may candy-coat a philosophically substantive semantic theory: the Mathematical-Object theory of the basis for the distribution of truth and falsehood to sentences containing set-theoretic expressions. This theory asserts that truth and falsity for sentences containing set-theoretic expressions are grounded in semantic facts (about the relation between language and the world) of the sort modelled by the usual model-theoretic semantics for an uninterpreted formal first-order language. For example, it would maintain that ‘{ } ∈ {{ }}” is true in virtue of the set-theoretic fact that the empty set is a member of its singleton, and the semantic facts that ‘{ }’ designates the empty set,‘{{ }}’ designates its singleton, and ‘∈’ applies to an ordered pair of objects iff that pair's first component is a member of its second component.

Now this theory may come so naturally as to seem trivial. My purpose here is to loosen its grip by “modelling” an alternative account of the alethic underpinnings of set-theoretic discourse. According to the Alternative theory, the point of having set-theoretic expressions (‘set’ and ‘∈’ will do) in a language is not to permit its speakers to talk about some special objects under a special relation; rather it is to clothe a higher-order language in lower-order garments.

In [3] Kemeny made the following conjecture: Suppose *Z is a nonstandard model of the ring of integers Z. Let

and let F be the subgroup of those cosets ā which contain an element of infinite height in *Z. Kemeny then asked if the ring R = {a: ā ∈ F} is also a nonstandard model of Z. If so then Goldbach's conjecture is false because Kemeny also shows in [3] that Goldbach's conjecture fails in R.

The papers [1] and [5] by Gandy and Mendelson show that R is not a nonstandard model of Z but we give here a simpler proof based on Mendelson's paper. Suppose R is a nonstandard model of Z. Then each positive number in R is a sum of four squares. Choose a in R so that a is a positive element of R of infinite height in *Z. Then since a is infinite in *Z, a − 1 is positive. Thus , xi ∈ R for i = 1, …, 4. Now each xi must be of the form ai + ni, where ai has infinite height in *Z and ni, ∈ Z.

This paper gives some simple existence results on prime and atomic models over sets. It also contains an example in which there is no prime model over a certain set even though there is an atomic model over the set. The existence results are “local” in that they deal with just one set rather than all sets contained in models of some theory. For contrast, see the “global” results in [6] or [7, p. 200].

Throughout the paper, L is a countable language, and T is a complete L-theory with infinite models. There is a “large” model of T that contains the set X and any other sets and models to be used in a particular construction of a prime or atomic model over X.

A model is said to be prime over X if and every elementary monomorphism on X can be extended to an elementary embedding on all of . This notion is used in a variety of ways in model theory. It aids in distinguishing between models that are not isomorphic, as in Vaught [10]. It also aids in showing that certain models are isomorphic, as in Baldwin and Lachlan [1].

We show that every reduct of a stable. CM-trivial theory of finite U-rank is CM-trivial.

Let $\left\langle {{W_n}:n \in \omega } \right\rangle$ be a canonical enumeration of recursively enumerable sets, and suppose T is a recursively enumerable extension of PA (Peano Arithmetic) in the same language. Woodin (2011) showed that there exists an index $e \in \omega$ (that depends on T) with the property that if${\cal M}$ is a countable model of T and for some${\cal M}$-finite set s, ${\cal M}$ satisfies ${W_e} \subseteq s$, then${\cal M}$ has an end extension${\cal N}$ that satisfies T + We = s.

Here we generalize Woodin’s theorem to all recursively enumerable extensions T of the fragment ${{\rm{I}\rm{\Sigma }}_1}$ of PA, and remove the countability restriction on ${\cal M}$ when T extends PA. We also derive model-theoretic consequences of a classic fixed-point construction of Kripke (1962) and compare them with Woodin’s theorem.

The principle (*) of Sierpinski is the assertion that there is a family of functions $\left\{ {{\varphi _n}:{\omega _1} \to {\omega _1}|n \in \omega } \right\}$ such that for every $I \in {[{\omega _1}]^{{\omega _1}}}$ there is n ε ω such that ${\varphi _n}[I] = {\omega _1}$. We prove that this principle holds if there is a nonmeager set of size ω1 answering question of Arnold W. Miller. Combining our result with a theorem of Miller it then follows that (*) is equivalent to $non\left( {\cal M} \right) = {\omega _1}$. Miller also proved that the principle of Sierpinki is equivalent to the existence of a weak version of a Luzin set, we will construct a model where all of these sets are meager yet $non\left( {\cal M} \right) = {\omega _1}$.

A formula α of modal LPC is a de re modality iff it contains a free individual variable within the scope of a modal operator; otherwise α is de dicto.1 We shall say that de re modalities are eliminable in a system S of modal LPC iff there is a transformation R on wffs of S such that R(α) is de dicto and ├sα ≡ R(α). We shall show that where S is LPC + S5 + Pr2 then de re modalities are not eliminable in S.

For given Boolean algebras $\mathbb {A}$ and $\mathbb {B}$ we endow the space $\mathcal {H}(\mathbb {A},\mathbb {B})$ of all Boolean homomorphisms from $\mathbb {A}$ to $\mathbb {B}$ with various topologies and study convergence properties of sequences in $\mathcal {H}(\mathbb {A},\mathbb {B})$ . We are in particular interested in the situation when $\mathbb {B}$ is a measure algebra as in this case we obtain a natural tool for studying topological convergence properties of sequences of ultrafilters on $\mathbb {A}$ in random extensions of the set-theoretical universe. This appears to have strong connections with Dow and Fremlin’s result stating that there are Efimov spaces in the random model. We also investigate relations between topologies on $\mathcal {H}(\mathbb {A},\mathbb {B})$ for a Boolean algebra $\mathbb {B}$ carrying a strictly positive measure and convergence properties of sequences of measures on $\mathbb {A}$ .

In studying mathematical logic, Boolean algebras can play an important role in the organization of syntactic properties of first-order theories. In this paper we are concerned with syntactical questions about the complete theories of Boolean algebras, Tarski [12] and Ershov [4]. We give a syntactic characterization of the languages introduced in [4] by Ershov in terms of number of alternations of quantifiers and show that extensions with respect to these natural languages are equivalent to extensions with respect to ∀k(L−1) ⋃ ∃k(L−1) for specified, k. The main motivation for this paper was to examine a generalized notion of model completeness of A. Robinson [14], called k-model completeness, and to find real mathematical structures having these properties in a nontrivial way; this turns out to be realized in the very natural setting of Boolean algebras and our results are very definitive about these notions in that setting. Also, we point out here the connections of these notions with those examined by Chang in [2] and observe that the syntactic properties of the complete theories of Boolean algebras have much in common with those properties enjoyed by ∀n-axiomatizable theories which are categorical for “some” infinite cardinal. Finally, a complete characterization of the model companions of the complete theories of Boolean algebras is given with respect to Ershov's languages [4].

We compare the strength of polychromatic and monochromatic Ramsey theory in several set-theoretic domains. We show that the rainbow Ramsey theorem does not follow from ZF, nor does the rainbow Ramsey theorem imply Ramsey's theorem over ZF. Extending the classical result of Erdős and Rado we show that the axiom of choice precludes the natural infinite exponent partition relations for polychromatic Ramsey theory. We introduce rainbow Ramsey ultrafilters, a polychromatic analogue of the usual Ramsey ultrafilters. We investigate the relationship of rainbow Ramsey ultrafilters with various special classes of ultrafilters, showing for example that every rainbow Ramsey ultrafilter is nowhere dense but rainbow Ramsey ultrafilters need not be rapid. This entails comparison of the polychromatic and monochromatic Ramsey theorems as combinatorial principles on ω.

The purpose of the present paper is to dispel such mystery as may be traceable to use of the ill-chosen term ‘ω-inconsistency’ and to a certain application of the term ‘axiom of infinity’. The application of ‘axiom of infinity’ which I have in mind is made by Rosser in his penetrating studies of the system of my New foundations. Let me begin with a synopsis of that system, which I shall call NF.

NF assumes as primitive just the membership connective ‘ϵ’, the truth functions, and quantification over a single style of variables ‘x’, ‘y’, etc. without type distinctions. The axioms, superimposed on standard quantification theory, comprise the axiom of extensionality ‘(x)(x ϵ y · = · x ϵ z) · y ϵ w · ⊃· z ϵ w’ and the axioms of abstraction, these latter being all sentences of the form ‘(∃y)(x)(x ϵ y · = Fx)’ in which the sentence supplanting ‘Fx’ is stratified (i.e., adaptable to type theory by some assignment of types to variables).