We give an example of an imaginary defined in certain valued fields with analytic structure which cannot be coded in the ‘geometric’ sorts which suffice to code all imaginaries in the corresponding algebraic setting.

Using techniques developed by Hamkins, Reitz and the second author, we determine the modal logic of inner models.

We develop several aspects of local and global stability in continuous first order logic. In particular, we study type-definable groups and genericity.

We study the strengths of various notions of higher randomness: (i) strong ${\rm{\Pi }}_1^1$randomness is separated from ${\rm{\Pi }}_1^1$randomness; (ii) the hyperdegrees of ${\rm{\Pi }}_1^1$random reals are closed downwards (except for the trivial degree); (iii) the reals z in $NC{R_{{\rm{\Pi }}_1^1}}$ are precisely those satisfying $z \in {L_{\omega _1^z}}$ and (iv) lowness for ${\rm{\Delta }}_1^1$randomness is strictly weaker than that for ${\rm{\Pi }}_1^1$randomness.

We show that if A and are automorphic via Φ then the structures (A) and () are Δ30-isomorphic via an isomorphism Ψ induced by Φ. Then we use this result to classify completely the orbits of hhsimple sets.

A truth for λ is a pair 〈Q, ψ〉 so that Q ⊆ Hλ, ψ is a first order formula with one free variable, and there exists B ⊆ Hλ+ such that (Hλ+; ∈, B) ⊨ ψ[Q]. A cardinal λ is , indescribable just in case that for every truth 〈Q, ψ〈 for λ, there exists < λ so that is a cardinal and 〈Q ∩ , ψ) is a truth for . More generally, an interval of cardinals [κ, λ] with κ ≤ λ is indescribable if for every truth 〈Q, ψ〈 for λ, there exists , and π: → Hλ so that is a cardinal, is a truth for , and π is elementary from () into (H; ∈, κ, Q) with id.

We prove that the restriction of the proper forcing axiom to ϲ-linked posets requires a indescribable cardinal in L, and that the restriction of the proper forcing axiom to ϲ+-linked posets, in a proper forcing extension of a fine structural model, requires a indescribable 1-gap [κ, κ+]. These results show that the respective forward directions obtained in Hierarchies of Forcing Axioms I by Neeman and Schimmerling are optimal.

The relativized weak pigeonhole principle states that if at least 2n out of n2 pigeons fly into n holes, then some hole must be doubly occupied. We prove that every DNF-refutation of the CNF encoding of this principle requires size $2^{\left( {{\rm{log\ }}n} \right)^{3/2 - \varepsilon } } $ for every ε﹥0 and every sufficiently large n. By reducing it to the standard weak pigeonhole principle with 2n pigeons and n holes, we also show that this lower bound is essentially tight in that there exist DNF-refutations of size $2^{\left( {{\rm{log\ }}n} \right)^{O\left( 1 \right)} } $ even in R(log). For the lower bound proof we need to discuss the existence of unbalanced low-degree bipartite expanders satisfying a certain robustness condition.

In [16], the algebraico-tree-theoretic simplicity hierarchical structure of J. H. Conway’s ordered field ${\bf{No}}$ of surreal numbers was brought to the fore and employed to provide necessary and sufficient conditions for an ordered field to be isomorphic to an initial subfield of ${\bf{No}}$, i.e., a subfield of ${\bf{No}}$ that is an initial subtree of ${\bf{No}}$. In this sequel to [16], analogous results for ordered abelian groups and ordered domains are established which in turn are employed to characterize the convex subgroups and convex subdomains of initial subfields of ${\bf{No}}$ that are themselves initial. It is further shown that an initial subdomain of ${\bf{No}}$ is discrete if and only if it is a subdomain of ${\bf{No}}$’s canonical integer part ${\bf{Oz}}$ of omnific integers. Finally, making use of class models the results of [16] are extended by showing that the theories of nontrivial divisible ordered abelian groups and real-closed ordered fields are the sole theories of nontrivial densely ordered abelian groups and ordered fields all of whose models are isomorphic to initial subgroups and initial subfields of ${\bf{No}}$.

We introduce the notion of pseudoalgebraicity to study atomic models of first order theories (equivalently models of a complete sentence of ${L_{{\omega _1},\omega }}$). Theorem: Let T be any complete first-order theory in a countable language with an atomic model. If the pseudominimal types are not dense, then there are 2ℵ0 pairwise nonisomorphic atomic models of T, each of size ℵ1.

In [3], [4], and [5] Joyce Friedman formulated and investigated certain rules which constitute a semi-decision procedure for wffs of first order predicate calculus in closed prenex normal form with prefixes of the form ∀x1 … ∀xκ∃y1 … ∃ym∀z1 … ∀zn. Given such a wff QM, where Q is the prefix and M is the matrix in conjunctive normal form, Friedman's rules can be used, in effect, to construct a matrix M* which is obtained from M by deleting certain conjuncts of M.

We prove that Standardization fails in every nontrivial universe definable in the nonstandard set theory BST, and that a natural characterization of the standard universe is both consistent with and independent of BST. As a consequence we obtain a formulation of nonstandard class theory in the ∈-language.

If is an analytic family of pairwise eventually different functions then the following strong maximality condition fails: For any countable , no member of which is covered by finitely many functions from , there is such that for all there are infinitely many integers k such that f(k) = h(k). However if V = L then there exists a coanalytic family of pairwise eventually different functions satisfying this strong maximality condition.

We prove that the property “P doesn't make the old reals Lebesgue null” is preserved under countable support iterations of proper forcings, under the additional assumption that the forcings are nep (a generalization of Suslin proper) in an absolute way. We also give some results for general Suslin ccc ideals.

Extending some results of Malykhin, we prove several independence results about base properties of βω / ω and its powers, especially the Noetherian type Nt(βω / ω), the least κ for which βω / ω has a base that is κ-like with respect to containment. For example, Nt(βω / ω) is at least s, but can consistently be ω1, c, c+, or strictly between ω1 and c. Nt(βω / ω) is also consistently less than the additivity of the meager ideal. Nt(βω / ω) is closely related to the existence of special kinds of splitting families.

We show that many singular cardinals λ above a strongly compact cardinal have regular ultrafilters D that violate the finite square principle introduced in [3]. For such ultrafilters D and cardinals λ there are models of size λ for which Mλ/D is not λ++-universal and elementarily equivalent models M and N of size λ for which Mλ/D and Nλ/D are non-isomorphic. The question of the existence of such ultrafilters and models was raised in [1].

Let ε stand for the set of all numbers (i.e., nonnegative integers), V for the class of all sets (i.e., subcollections of ε) and for the family of all functions (i.e., mappings from a subset of ε into ε). If ƒ is a function, we write δƒ and ρƒ for its domain and range respectively. The relation of inclusion is denoted by ⊂ and that of proper inclusion by ⊆.

In a previous paper [9] a demonstrably consistent type-free system of combinatory logic CΔ was presented. This system contained a moderately strong exten-sionality principle, the usual equations of combinatory logic, Boolean propositional connectives, unrestricted quantifiers, an unrestricted abstraction principle (“comprehension axiom”), and a limited principle of excluded middle. It also contained elementary arithmetic in its entirety, avoiding arithmetical Gödel incompleteness [14] by being ω-complete. CΔ probably can be shown to contain certain important parts of mathematical analysis, such as the theory of continuous functions, which are contained by the somewhat similar (but nonextensional) system K′ [6], [7]. A stronger system CΓ, having these same properties and more, will be formulated in the present paper. Elsewhere [13] it will be shown that the system Q of my book, Elements of combinatory logic (Yale University Press, New Haven and London, 1974), referred to below as ECL, is essentially a subsystem of CΓ, so that the consistency of CΓ guarantees that of Q.

CΓ will be stronger than both CΔ and Q in having an operator ‘ɿ’ (inverted Greek iota) which denotes the inverse of equality in the sense that ‘ɿ(= a) = a’ is a theorem of the system. Thus ‘ɿ’ denotes a function or operator which operates on a unit class to give the only member of that class. (Here ‘=a’ denotes the unit class whose only member is denoted by ‘a’.) If uninverted Greek iota, ‘ι’, is used as an abbreviation for ‘=’, the above equation could be written as ‘ɿ(ιa) = a’. Here ‘ιa’ is analogous to Bertrand Russell's well-known notation ‘ιa’, denoting a unit class. This same operator ‘ɿ’ makes it possible to transform one-many or many-one relations into the corresponding functions or operators, a kind of transformation not usually available in systems of combinatory logic [1], [2]. It also provides a method for restricting functions by restricting the corresponding relations.

In well-known papers ([A-K1], [A-K2], and [E]) J. Ax, S. Kochen, and J. Ershov prove a transfer theorem for henselian valued fields. Here we prove an analogue for henselian valued and ordered fields. The orders for which this result apply are the usual orders and also the higher level orders introduced by E. Becker in [Bl] and [B2]. With certain restrictions, two henselian valued and ordered fields are elementarily equivalent if and only if their value groups (with a little bit more structure) and their residually ordered residue fields (a henselian valued and ordered field induces in a natural way an order in its residue field) are elementarily equivalent. Similar results are proved for elementary embeddings and ∀-extensions (extensions where the structure is existentially closed).

We study cut-elimination in first-order classical logic. We construct a sequence of polynomial-length proofs having a non-elementary number of different cut-free normal forms. These normal forms are different in a strong sense: they not only represent different Herbrand-disjunctions but also differ in their prepositional structure.

This result illustrates that the constructive content of a proof in classical logic is not uniquely determined but rather depends on the chosen method for extracting it.

An equation to compute the dp-rank of any abelian group is given. It is also shown that its dp-rank, or more generally that of any one-based group, agrees with its Vapnik–Chervonenkis density. Furthermore, strong abelian groups are characterised to be precisely those abelian groups A such that there are only finitely many primes p such that the group A / pA is infinite and for every prime p, there are only finitely many natural numbers n such that $\left( {p^n A} \right)[p]/\left( {p^{n + 1} A} \right)[p]$ is infinite.

Finally, it is shown that an infinite stable field of finite dp-rank is algebraically closed.