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 prove the following theorems:

(1) If X has strong measure zero and if Y has strong first category, then their algebraic sum has property S0.

(2) If X has Hurewicz's covering property, then it has strong measure zero if, and only if, its algebraic sum with any first category set is a first category set.

(3) If X has strong measure zero and Hurewicz's covering property then its algebraic sum with any set in is a set in . ( is included in the class of sets always of first category, and includes the class of strong first category sets.)

These results extend: Fremlin and Miller's theorem that strong measure zero sets having Hurewicz's property have Rothberger's property, Galvin and Miller's theorem that the algebraic sum of a set with the γ-property and of a first category set is a first category set, and Bartoszyfński and Judah's characterization of -sets. They also characterize the property (*) introduced by Gerlits and Nagy in terms of older concepts.

Let be the collection of all sets which are finite Boolean combinations of recursively enumerable (r.e.) sets of numbers. Dale Myers asked [private correspondence] whether there exists a nonempty class of sets containing no member of . In this note we construct such a class. The motivation for Myers' question was his observation (reported in [1]) that the existence of such a class is equivalent to the assertion that there is a finite consistent set of tiles which has no m-trial tiling of the plane for any m (obeying the “origin constraint”). (For explanations of these terms and further results on tilings of the plane, cf. [1] and [5].) In addition to the application to tilings, the proof of our results gives some information on bi-immune sets and on complete extensions of first-order Peano arithmetic.

A class of sets may be roughly described as the class of infinite binary input tapes for which a fixed Turing machine fails to halt, or alternatively as the class of infinite branches of a recursive tree of finite binary sequences. (In these definitions, sets of numbers are identified with the corresponding binary sequences.) Precise definitions, as well as many results concerning such classes, may be found in [3] and [4].

Let denote the set of degrees ≤ 0′. A degree a ≤ 0′ is said to be complemented in if there exists a degree b ≤ 0′ such that b ∪ a = 0′ and b ∩ a = 0. R.W. Robinson (cf. [11]) showed that every degree a ≤ 0′ satisfying a″ = 0″ is complemented in and the author [8] showed that every degree a ≤ 0′ satisfying a′ = 0″ is complemented in . Also, in [2], R. L. Epstein showed that every r.e. degree is complemented in . In this paper we will show that in fact every degree ≤ 0′ is complemented in . We will further show that the same is true in the upper semilattice of degrees ≤ c, where c is any complete degree. This is in contrast to the situation in the upper semilattice of r.e. degrees in which, as Lachlan [6] has shown, no degree other than 0 and 0′ is complemented.

We use the same terminology and notations as in Part I of this paper [3], but numerals in square brackets refer to the references at the end of the present part. The word “space” will be used in the sense of “subspace of ŪF”. A. G. Hamilton [6] proved that any two α-bases of any α-space are recursively equivalent (see also [5]). This means that dimαV, introduced in [3] only for an isolic α-space V, can be defined for anyα-space V. Several results of [3] can therefore be strengthened. These and some other improvements are listed in §8. It is proved in §9 that every α-subspace of an isolic α-space is again an isolic α-space.

Let T1, T2 be countable first-order theories, Mi ⊨ Ti and any regular ultrafilter on λ ≥ ℵ0. A longstanding open problem of Keisler asks when T2 is more complex than T1, as measured by the fact that for any such λ, , if the ultrapower realizes all types over sets of size ≤ λ, then so must the ultrapower . In this paper, building on the author's prior work [12] [13] [14], we show that the relative complexity of first-order theories in Keisler's sense is reflected in the relative graph-theoretic complexity of sequences of hypergraphs associated to formulas of the theory. After reviewing prior work on Keisler's order, we present the new construction in the context of ultrapowers, give various applications to the open question of the unstable classification, and investigate the interaction between theories and regularizing sets. We show that there is a minimum unstable theory, a minimum TP2 theory, and that maximality is implied by the density of certain graph edges (between components arising from Szemerédi-regular decompositions) remaining bounded away from 0, 1. We also introduce and discuss flexible ultrafilters, a relevant class of regular ultrafilters which reflect the sensitivity of certain unstable (non low) theories to the sizes of regularizing sets, and prove that any ultrafilter which saturates the minimal TP2 theory is flexible.

Tense logics in the bimodal propositional language are investigated with respect to the Finite Model Property. In order to prove positive results techniques from investigations of modal logics above K4 are extended to tense logic. General negative results show the limits of the transfer.

Large cardinals arising from the existence of arbitrarily long end elementary extension chains over models of set theory are studied here. In particular, we show that the large cardinals obtained in this fashion (‘unfoldable cardinals’) lie in the boundary of the propositions consistent with ‘V = L’ and the existence of 0#. We also provide an ‘embedding characterisation’ of the unfoldable cardinals and study their preservation and destruction by various forcing constructions.

We prove that there is no sw-complete c.e. real, negatively answering a question in [6].

In [MPP] it was shown that in every reduct of = ‹ ℝ, +, ·, <› that properly expands ℳ = ‹ℝ, +, <, λa›a∈ℝ, all the bounded semi-algebraic (that is, -definable) sets are definable. Said differently, every such is an expansion of = ‹ℝ, +, <, λa, Bi›a∈ℝ, i∈I where {Bi}i∈I is the collection of all bounded semialgebraic sets and the λa's are scalar multiplication by a. In [PSS] (see Theorem 1.2 below) it was shown that the structure is a proper reduct of ; that is, one cannot define in it all the semialgebraic sets. In [Pe] we show that is the only reduct properly between ℳ and . As a first step towards this result, we investigate in this paper the definable sets in reducts such as . (We point out that ‘definable’ will always mean ‘definable with parameters’.)

Definition 1.1. Let X ⊆ ℝn. X is called semi-bounded if it is definable in the structure ‹ℝ, +, <, λa, B1, …, Bk›a∈ℝ, where the Bi's are bounded subsets of ℝn.

The main result of this paper (see Theorem 3.1) shows roughly that, in Ominimal expansions of that satisfy the partition condition (see Definition 2.3), every semibounded set can be partitioned into finitely many sets, each of which is of a form similar to a cylinder. Namely, these sets are obtained through the “stretching” of a bounded cell by finitely many linear vectors. As a corollary (see Theorem 1.4), we get different characterizations of semibounded sets, either in terms of their structure or in terms of their definability power.

The following result, by A. Pillay, P. Scowcroft and C. Steinhorn, was the main motivation for this paper. The theorem is formulated here in a slightly stronger form than originally, but the proof itself is essentially the original one. A short version of the proof is included in §4.

We prove that any 1-closed (see def 1.1) model of the Π2 consequences of PA satisfies ¬Cons PA which gives a proof of the second Gödel incompleteness theorem without the use of the Gödel diagonal lemma. We prove a few other theorems by the same method.

The structure of the Turing degrees of generic and n-generic sets has been studied fairly extensively, especially for n = 1 and n = 2. The original formulation of 1-generic set in terms of recursively enumerable sets of strings is due to D. Posner [11], and much work has since been done, particularly by C. G. Jockusch and C. T. Chong (see [5] and [6]).

In the enumeration degrees (see definition below), attention has previously been restricted to generic sets and functions. J. Case used genericity for many of the results in his thesis [1]. In this paper we develop a notion of 1-generic partial function, and study the structure and characteristics of such functions in the enumeration degrees. We find that the e-degree of a 1-generic function is quasi-minimal. However, there are no e-degrees minimal in the 1-generic e-degrees, since if a 1-generic function is recursively split into finitely or infinitely many parts the resulting functions are e-independent (in the sense defined by K. McEvoy [8]) and 1-generic. This result also shows that any recursively enumerable partial ordering can be embedded below any 1-generic degree.

Many results in the Turing degrees have direct parallels in the enumeration degrees. Applying the minimal Turing degree construction to the partial degrees (the e-degrees of partial functions) produces a total partial degree ae which is minimal-like; that is, all functions in degrees below ae have partial recursive extensions.

This paper considers Henkin’s proof of completeness of classical first-order logic and extends its scope to the realm of algebraizable logics in the sense of Blok and Pigozzi. Given a propositional logic L (for which we only need to assume that it has an algebraic semantics and a suitable disjunction) we axiomatize two natural first-order extensions L∀m and L∀ and prove that the former is complete with respect to all models over algebras from , while the latter is complete with respect to all models over relatively finitely subdirectly irreducible algebras. While the first completeness result is relatively straightforward, the second requires non-trivial modifications of Henkin’s proof by making use of the disjunction connective. As a byproduct, we also obtain a form of Skolemization provided that the algebraic semantics admits regular completions. The relatively modest assumptions on the propositional side allow for a wide generalization of previous approaches by Rasiowa, Sikorski, Hájek, Horn, and others and help to illuminate the “essentially first-order” steps in the classical Henkin’s proof.

An uncountable cardinal κ is called ${\omega _1}$-strongly compact if every κ-complete ultrafilter on any set I can be extended to an ${\omega _1}$-complete ultrafilter on I. We show that the first ${\omega _1}$-strongly compact cardinal, ${\kappa _0}$, cannot be a successor cardinal, and that its cofinality is at least the first measurable cardinal. We prove that the Singular Cardinal Hypothesis holds above ${\kappa _0}$. We show that the product of Lindelöf spaces is κ-Lindelöf if and only if $\kappa \ge {\kappa _0}$. Finally, we characterize ${\kappa _0}$ in terms of second order reflection for relational structures and we give some applications. For instance, we show that every first-countable nonmetrizable space has a nonmetrizable subspace of size less than ${\kappa _0}$.

Basic notation in this paper is as in [3]. From [5] and [9] the following additional notation is derived, ϕi is the partial recursive function with index i, Wi its range. ∅ is the empty set. ‘≡’ denotes isomorphism between sets, ‘≡m’ many-one equivalence, ‘≡T’ Turing equivalence, ‘≦1’ and ‘≦m’ signify one-one and many-one reducibility respectively. ‘Recursive’ is used throughout for ‘general recursive’.

We do a quantitative analysis of modal logic. For example, for each Kripke structure M, we study the least ordinal μ such that for each state of M, the beliefs up to level μ characterize the agents' beliefs (that is, there is only one way to extend these beliefs to higher levels). As another example, we show the equivalence of three conditions, that on the face of it look quite different, for what it means to say that the agents' beliefs have a countable description, or putting it another way, have a “countable amount of information”. The first condition says that the beliefs of the agents are those at a state of a countable Kripke structure. The second condition says that the beliefs of the agents can be described in an infinitary language, where conjunctions of arbitrary countable sets of formulas are allowed. The third condition says that countably many levels of belief are sufficient to capture all of the uncertainty of the agents (along with a technical condition). The fact that all of these conditions are equivalent shows the robustness of the concept of the agents' beliefs having a “countable description”.

We show that the class of strongly jump-traceable c.e. sets can be characterised as those which have sufficiently slow enumerations so they obey a class of well-behaved cost functions, called benign. This characterisation implies the containment of the class of strongly jump-traceable c.e. Turing degrees in a number of lowness classes, in particular the classes of the degrees which lie below incomplete random degrees, indeed all LR-hard random degrees, and all ω-c.e. random degrees. The last result implies recent results of Diamondstone's and Ng's regarding cupping with superlow c.e. degrees and thus gives a use of algorithmic randomness in the study of the c.e. Turing degrees.

Two real-valued deduction schemes are introduced, which agree on ⊢ ⊿ but not on Γ ⊢ ⊿, where Γ and ⊢ are finite sets of formulae. Using the first scheme we axiomatize real-valued equality so that it induces metrics on the domains of appropriate structures. We use the second scheme to reduce substitutivity of equals to uniform continuity, with respect to the metric equality, of interpretations of predicates in structures. This continuity extends from predicates to arbitrary formulae and the appropriate models have completions resembling analytic completions of metric spaces. We provide inference rules for the two deductions and discuss definability of each of them by means of the other.

We investigate the pair-splitting number which is a variation of splitting number, pair-reaping number which is a variation of reaping number and cardinal invariants of ideals on ω. We also study cardinal invariants of Fσ ideals and their upper bounds and lower bounds. As an application, we answer a question of S. Solecki by showing that the ideal of finitely chromatic graphs is not locally Katětov-minimal among ideals not satisfying Fatou's lemma.

Dobrinen and Simpson [4] introduced the notions of almost everywhere domination and uniform almost everywhere domination to study recursion theoretic analogues of results in set theory concerning domination in generic extensions of transitive models of ZFC and to study regularity properties of the Lebesgue measure on 2ω in reverse mathematics. In this article, we examine one of their conjectures concerning these notions.

Throughout this article, ≤T denotes Turing reducibility and μ denotes the Lebesgue (or “fair coin”) probability measure on 2ω given by

A property holds almost everywhere or for almost all X ∈ 2ω if it holds on a set of measure 1. For f, g ∈ ωω, f dominatesg if ∃m∀n < m(f(n) > g(n)).

(Dobrinen, Simpson). A set A ∈ 2ωis almost everywhere (a.e.) dominating if for almost all X ∈ 2ω and all functions g ≤TX, there is a function f ≤TA such that f dominates g. A is uniformly almost everywhere (u.a.e.) dominating if there is a function f ≤TA such that for almost all X ∈ 2ω and all functions g ≤TX, f dominates g.

There are several trivial but useful observations to make about these definitions. First, although these properties are stated for sets, they are also properties of Turing degrees. That is, a set is (u.)a.e. dominating if and only if every other set of the same degree is (u.)a.e. dominating. Second, both properties are closed upwards in the Turing degrees. Third, u.a.e. domination implies a.e. domination. Finally, if A is u.a.e. dominating, then there is a function f ≤TA which dominates every computable function.