Many classical statements of set theory are settled by the existence of generic elementary embeddings that are analogous the elementary embeddings posited by large cardinals. [2] The embeddings analogous to measurable cardinals are determined by uniform, κ-complete precipitous ideals on cardinals κ. Stronger embeddings, analogous to those originating from supercompact or huge cardinals are encoded by normal fine ideals on sets such as [κ]<λ or [κ]λ.

The embeddings generated from these ideals are limited in ways analogous to conventional large cardinals. Explicitly, if j: V → M is a generic elementary embedding with critical point κ and λ supnЄωjn(κ) and the forcing yielding j is λ-saturated then j“λ+ ∉ M. (See [2].)

Ideals that yield embeddings that are analogous to strongly compact cardinals have more puzzling behavior and the analogy is not as straightforward. Some natural ideal properties of this kind have been shown to be inconsistent:

Theorem 1 (Kunen). There is no ω2-saturated, countably complete uniform ideal on any cardinal in the interval [ℵω, ℵω).

Generic embeddings that arise from countably complete, ω2-saturated ideals have the property that sup . So the Kunen result is striking in that it apparently allows strong ideals to exist above the conventional large cardinal limitations. The main result of this paper is that it is consistent (relative to a huge cardinal) that such ideals exist.

Extending Gödel's Dialectica interpretation, we provide a functional interpretation of classical theories of positive arithmetic inductive definitions, reducing them to theories of finite-type functionals defined using transfinite recursion on well-founded trees.

We obtain an almost everywhere quantifier elimination for (the noncritical fragment of) the logic with probability quantifiers, introduced by the first author in [10]. This logic has quantifiers like ∃≥3/4y which says that “for at least 3/4 of all y”. These results improve upon the 0-1 law for a fragment of this logic obtained by Knyazev [11]. Our improvements are:

1. We deal with the quantifier ∃≥ry, where y is a tuple of variables.

2. We remove the closedness restriction, which requires that the variables in y occur in all atomic subformulas of the quantifier scope.

3. Instead of the unbiased measure where each model with universe n has the same probability, we work with any measure generated by independent atomic probabilities PR for each predicate symbol R.

4. We extend the results to parametric classes of finite models (for example, the classes of bipartite graphs, undirected graphs, and oriented graphs).

5. We extend the results to a natural (noncritical) fragment of the infinitary logic with probability quantifiers.

6. We allow each PR, as well as each r in the probability quantifier (∃≥ry), to depend on the size of the universe.

We show that the ℵ0-categorical structures produced by Hrushovski's predimension construction with a control function fit neatly into Shelah's SOPn hierarchy: if they are not simple, then they have SOP3 and NSOP4. We also show that structures produced without using a control function can be undecidable and have SOP.

In 1985 the second author showed that if there is a proper class of measurable Woodin cardinals and and are generic extensions of V satisfying CH then and agree on all Σ12-statements. In terms of the strong logic Ω-logic this can be reformulated by saying that under the above large cardinal assumption ZFC + CH is Ω-complete for Σ12. Moreover, CH is the unique Σ12-statement with this feature in the sense that any other Σ12-statement with this feature is Ω-equivalent to CH over ZFC. It is natural to look for other strengthenings of ZFC that have an even greater degree of Ω-completeness. For example, one can ask for recursively enumerable axioms A such that relative to large cardinal axioms ZFC + A is Ω-complete for all of third-order arithmetic. Going further, for each specifiable segment Vλ of the universe of sets (for example, one might take Vλ to be the least level that satisfies there is a proper class of huge cardinals), one can ask for recursively enumerable axioms A such that relative to large cardinal axioms ZFC + A is Ω-complete for the theory of Vλ. If such theories exist, extend one another, and are unique in the sense that any other such theory B with the same level of Ω-completeness as A is actually Ω-equivalent to A over ZFC, then this would show that there is a unique Ω-complete picture of the successive fragments of the universe of sets and it would make for a very strong case for axioms complementing large cardinal axioms. In this paper we show that uniqueness must fail. In particular, we show that if there is one such theory that Ω-implies CH then there is another that Ω-implies ¬-CH.

We develop canonical rules capable of axiomatizing all systems of multiple-conclusion rules over K4 or IPC, by extension of the method of canonical formulas by Zakharyaschev [37]. We use the framework to give an alternative proof of the known analysis of admissible rules in basic transitive logics, which additionally yields the following dichotomy: any canonical rule is either admissible in the logic, or it is equivalent to an assumption-free rule. Other applications of canonical rules include a generalization of the Blok–Esakia theorem and the theory of modal companions to systems of multiple-conclusion rules or (unitary structural global) consequence relations, and a characterization of splittings in the lattices of consequence relations over monomodal or superintuitionistic logics with the finite model property.

The work [11] deals with questions of first-order definability in algebraic function fields. In particular, it exhibits new cases in which the field of constant functions is definable, and it investigates the phenomenon of definable transcendental elements. We fix some of its proofs and make additional observations concerning definable closure in these fields.

We prove that if μ is a regular cardinal and ℙ is a μ-centered forcing poset, then ℙ forces that (I[μ++[)V generates I[μ++] modulo clubs. Using this result, we construct models in which the approachability property fails at the successor of a singular cardinal. We also construct models in which the properties of being internally club and internally approachable are distinct for sets of size the successor of a singular cardinal.

A box type is an n-type of an o-minimal structure which is uniquely determined by the projections to the coordinate axes. We characterize heirs of box types of a polynomially bounded o-minimal structure M. From this, we deduce various structure theorems for subsets of Mk, definable in the expansion of M by all convex subsets of the line. We show that after naming constants, is model complete provided M is model complete.

A classical theorem in computability is that every promptly simple set can be cupped in the Turing degrees to some complete set by a low c.e. set. A related question due to A. Nies is whether every promptly simple set can be cupped by a superlow c.e. set, i.e. one whose Turing jump is truth-table reducible to the halting problem ∅′. A negative answer to this question is provided by giving an explicit construction of a promptly simple set that is not superlow cuppable. This problem relates to effective randomness and various lowness notions.

In partial answer to a question posed by Arnie Miller [4] and X. Caicedo [2] we obtain sufficient conditions for an ℒω1,ω theory to have an independent axiomatization. As a consequence we obtain two corollaries: The first, assuming Vaught's Conjecture, every ℒω1,ω theory in a countable language has an independent axiomatization. The second, this time outright in ZFC, every intersection of a family of Borel sets can be formed as the intersection of a family of independent Borel sets.

In this paper, we investigate the extent to which techniques used in [10], [2], and [3]—developed to prove coloring theorems at successors of singular cardinals of uncountable cofinality—can be extended to cover the countable cofinality case.

The Rainbow Ramsey Theorem is essentially an “anti-Ramsey” theorem which states that certain types of colorings must be injective on a large subset (rather than constant on a large subset). Surprisingly, this version follows easily from Ramsey's Theorem, even in the weak system RCA0 of reverse mathematics. We answer the question of the converse implication for pairs, showing that the Rainbow Ramsey Theorem for pairs is in fact strictly weaker than Ramsey's Theorem for pairs over RCA0. The separation involves techniques from the theory of randomness by showing that every 2-random bounds an ω-model of the Rainbow Ramsey Theorem for pairs. These results also provide as a corollary a new proof of Martin's theorem that the hyperimmune degrees have measure one.

We use the Low Basis Theorem of Jockusch and Soare to show that all computable algebraic fields are d-computably categorical for a particular Turing degree d with d′ = 0″, but that not all such fields are 0′-computably categorical. We also prove related results about algebraic fields with splitting algorithms, and fields of finite transcendence degree over ℚ.

We solve a longstanding question of Rosenstein, and make progress toward solving a long-standing open problem in the area of computable linear orderings by showing that every computable η-like linear ordering without an infinite strongly η-like interval has a computable copy without nontrivial computable self-embedding.

The precise characterization of those computable linear orderings which have computable copies without nontrivial computable self-embedding remains open.

We study the strictness of the modal μ-calculus hierarchy over some restricted classes of transition systems. First, we prove that over transitive systems the hierarchy collapses to the alternation-free fragment. In order to do this the finite model theorem for transitive transition systems is proved. Further, we verify that if symmetry is added to transitivity the hierarchy collapses to the purely modal fragment. Finally, we show that the hierarchy is strict over reflexive frames. By proving the finite model theorem for reflexive systems the same results holds for finite models.

In this paper we develop a method for finding, under general conditions, explicit and highly uniform rates of convergence for the Picard iteration sequences for selfmaps on bounded metric spaces from ineffective proofs of convergence to a unique fixed point. We are able to extract full rates of convergence by extending the use of a logical metatheorem recently proved by Kohlenbach. In recent case studies we were able to find such explicit rates of convergence in two concrete cases. Our novel method now provides an explanation in logical terms for these findings. This amounts, loosely speaking, to general conditions under which we in this specific setting can transform a ∀∃∀-sentence into a ∀∃-sentence via an argument involving product spaces. This reduction in logical complexity allows us to use the existing machinery to extract quantitative bounds of the sort we need.

It is shown that there is a formula σ(g) in the first-order language of group theory with the following property: for every finite group G, the largest soluble normal subgroup of G consists precisely of the elements g of G such that σ(g) holds.