We investigate the structure of the Medvedev lattice as a partial order. We prove that every interval in the lattice is either finite, in which case it is isomorphic to a finite Boolean algebra, or contains an antichain of size . the size of the lattice itself. We also prove that it is consistent with ZFC that the lattice has chains of size . and in fact that these big chains occur in every infinite interval. We also study embeddings of lattices and algebras. We show that large Boolean algebras can be embedded into the Medvedev lattice as upper semilattices, but that a Boolean algebra can be embedded as a lattice only if it is countable. Finally we discuss which of these results hold for the closely related Muchnik lattice.

We characterize the (κ, λ, < μ)-distributive law in Boolean algebras in terms of cut and choose games , when μ ≤ κ ≤ λ and κ<κ = κ. This builds on previous work to yield game-theoretic characterizations of distributive laws for almost all triples of cardinals κ, λ, μ with μ ≤ λ, under GCH. In the case when μ ≤ κ ≤ λ and κ<κ = κ, we show that it is necessary to consider whether the κ-stationarity of in the ground model is preserved by . In this vein, we develop the theory of κ-club and κ-stationary subsets of . We also construct Boolean algebras in which Player I wins but the (κ, ∞, κ)-d.1. holds, and, assuming GCH, construct Boolean algebras in which many games are undetermined.

Using a dictionary translating a variety of classical and modern covering properties into combinatorial properties of continuous images, we get a simple way to understand the interrelations between these properties in ZFC and in the realm of the trichotomy axiom for upward closed families of sets of natural numbers. While it is now known that the answer to the Hurewicz 1927 problem is positive, it is shown here that semifilter trichotomy implies a negative answer to a slightly stronger form of this problem.

An important technique in large cardinal set theory is that of extending an elementary embedding j: M → N between inner models to an elementary embedding j* : M[G] → N[G*] between generic extensions of them. This technique is crucial both in the study of large cardinal preservation and of internal consistency. In easy cases, such as when forcing to make the GCH hold while preserving a measurable cardinal (via a reverse Easton iteration of α-Cohen forcing for successor cardinals α), the generic G* is simply generated by the image of G. But in difficult cases, such as in Woodin's proof that a hypermeasurable is sufficient to obtain a failure of the GCH at a measurable, a preliminary version of G* must be constructed (possibly in a further generic extension of M[G]) and then modified to provide the required G*. In this article we use perfect trees to reduce some difficult cases to easy ones, using fusion as a substitute for distributivity. We apply our technique to provide a new proof of Woodin's theorem as well as the new result that global domination at inaccessibles (the statement that d(κ) is less than 2κ for inaccessible κ, where d(κ) is the dominating number at κ) is internally consistent, given the existence of 0#.

Recall that a subset X of an algebra A is irredundant iff x ∉ 〈X∖{x}〉 for all x ϵ X, where 〈X∖{x}) is the subalgebra generated by X∖{x}. By Zorn's lemma there is always a maximal irredundant set in an algebra. This gives rise to a natural cardinal function Irrmm(A) = min{∣X∣: X is a maximal irredundant subset of A}. The first half of this article is devoted to proving that there is an atomless Boolean algebra A of size 2ω for which Irrmm(A) = ω.

A subset X of a BA A is ideal independent iff x ∉ (X∖{x}〉id for all x ϵ X, where 〈X∖{x}〉id is the ideal generated by X∖{x}. Again, by Zorn's lemma there is always a maximal ideal independent subset of any Boolean algebra. We then consider two associated functions. A spectrum function

Sspect(A) = {∣X∣: X is a maximal ideal independent subset of A}

and the least element of this set, smm(A). We show that many sets of infinite cardinals can appear as Sspect(A). The relationship of Smm to similar “continuum cardinals” is investigated. It is shown that it is relatively consistent that Smm/fin) < 2ω.

We use the letter s here because of the relationship of ideal independence with the well-known cardinal invariant spread; see Monk [5]. Namely, sup{∣X∣: X is ideal independent in A} is the same as the spread of the Stone space Ult(A); the spread of a topological space X is the supremum of cardinalities of discrete subspaces.

There is a simple technique, due to Dragalin. for proving strong cut-elimination for intuitionistic sequent calculus, but the technique is constrained to certain choices of reduction rules, preventing equally natural alternatives. We consider such a natural, alternative set of reduction rules and show that the classical technique is inapplicable. Instead we develop another approach combining two of our favorite tools—Klop's ι-translation and perpetual reductions.

These tools are of independent interest and have proved useful in a variety of settings; it is therefore natural to investigate, as we do here, what they have to offer the field of sequent calculus.

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 say that A ≤LRB if every B-random number is A-random. Intuitively this means that if oracle A can identify some patterns on some real γ, oracle B can also find patterns on γ. In other words, B is at least as good as A for this purpose. We study the structure of the LR degrees globally and locally (i.e., restricted to the computably enumerable degrees) and their relationship with the Turing degrees. Among other results we show that whenever ∝ is not GL2 the LR degree of ∝ bounds degrees (so that, in particular, there exist LR degrees with uncountably many predecessors) and we give sample results which demonstrate how various techniques from the theory of the c.e. degrees can be used to prove results about the c.e. LR degrees.

We prove constructively that the weak König lemma and quantifier-free number–number choice imply that every pointwise continuous function from Cantor space into Baire space has a modulus of uniform continuity.

We give upper and lower bounds for the consistency strength of the failure of a combinatorial principle introduced by Jensen. Square on singular cardinals.

We show, under the assumption that factoring is hard, that a model of PV exists in which the polynomial hierarchy does not collapse to the linear hierarchy; that a model of exists in which NP is not in the second level of the linear hierarchy; and that a model of exists in which the polynomial hierarchy collapses to the linear hierarchy.

Our methods are model-theoretic. We use the assumption about factoring to get a model in which the weak pigeonhole principle fails in a certain way, and then work with this failure to obtain our results.

As a corollary of one of the proofs, we also show that in the failure of WPHP (for definable relations) implies that the strict version of PH does not collapse to a finite level.

I investigate versions of the Maximality Principles for the classes of forcings which are <κ-closed, <κ-directed-closed, or of the form Col(κ, <λ). These principles come in many variants, depending on the parameters which are allowed, I shall write MPΓ (A) for the maximality principle for forcings in Γ, with parameters from A. The main results of this paper are:

• The principles have many consequences, such as <κ-closed-generic (Hκ) absoluteness, and imply, e.g., that ◊κ holds. I give an application to the automorphism tower problem, showing that there are Souslin trees which are able to realize any equivalence relation, and hence that there are groups whose automorphism tower is highly sensitive to forcing.

• The principles can be separated into a hierarchy which is strict, for many κ.

• Some of the principles can be combined, in the sense that they can hold at many different κ simultaneously.

The possibilities of combining the principles are limited, though: While it is consistent that MP<κ-closed(Hκ +) holds at all regular κ below any fixed α, the “global” maximality principle, stating that MP<κ-closed (Hκ ∪ {κ} ) holds at every regular κ, is inconsistent. In contrast to this, it is equiconsistent with ZFC that the maximality principle for directed-closed forcings without any parameters holds at every regular cardinal. It is also consistent that every local statement with parameters from Hκ⊦ that's provably <κ-closed-forceably necessary is true, for all regular κ.

We call a logic regular for a semantics when the satisfaction predicate for at least one of its nontheorems is closed under double negation. Such intuitionistic theories as second-order Heyting arithmetic HAS and the intuitionistic set theory IZF prove completeness for no regular logics, no matter how simple or complicated. Any extensions of those theories proving completeness for regular logics are classical, i.e., they derive the tertium non datur. When an intuitionistic metatheory features anticlassical principles or recognizes that a logic regular for a semantics is nonclassical, it proves explicitly that the logic is incomplete with respect to that semantics. Logics regular relative to Tarski, Beth and Kripke semantics form a large collection that includes propositional and predicate intuitionistic, intermediate and classical logics. These results are corollaries of a single theorem. A variant of its proof yields a generalization of the Gödel-Kreisel Theorem linking weak completeness for intuitionistic predicate logic to Markov's Principle.

We consider a modal language for affine planes, with two sorts of formulas (for points and lines) and three modal boxes. To evaluate formulas, we regard an affine plane as a Kripke frame with two sorts (points and lines) and three modal accessibility relations, namely the point-line and line-point incidence relations and the parallelism relation between lines. We show that the modal logic of affine planes in this language is not finitely axiomatisable.

We study the minimal complexity of tilings of a plane with a given tile set. We note that every tile set admits either no tiling or some tiling with Kolmogorov complexity of its (n × n)-squares. We construct tile sets for which this bound is tight: all (n × n)-squares in all tilings have complexity Ω(n). This adds a quantitative angle to classical results on non-recursivity of tilings—that we also develop in terms of Turing degrees of unsolvability.

In this paper we show that there is a pair of superhigh r.e. degree that forms a minimal pair. An analysis of the proof shows that a critical ingredient is the growth rates of certain order functions. This leads us to investigate certain high r.e. degrees, which resemble ∅′ very closely in terms of ∅′-jump traceability. In particular, we will construct an ultrahigh degree which is cappable.

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.

We provide a short proof that if κ is a regular cardinal with κ < c, then

for any ordinal α < min{, κ}. In particular,

for any ordinal α < . This generalizes an unpublished result of E. Szemerédi that Martin's axiom implies that

for any cardinal κ with κ < c.

We prove that there are groups in the constructible universe whose automorphism towers are highly malleable by forcing. This is a consequence of the fact that, under a suitable diamond hypothesis, there are sufficiently many highly rigid non-isomorphic Souslin trees whose isomorphism relation can be precisely controlled by forcing.

In response to a question of Farah, “How many Boolean algebras are there?” [Far04], one of us (Oliver) proved that there are continuum-many nonisomorphic Boolean algebras of the form with I a Borel ideal on the natural numbers, and in fact that this result could be improved simultaneously in two directions:

(i) “Borel ideal” may be improved to “analytic P-ideal”

(ii) “continuum-many” may be improved to “E0-many”; that is, E0 is Borel reducible to the isomorphism relation on quotients by analytic P-ideals.

See [Oli04].

In [AdKechOO], Adams and Kechris showed that the relation of equality on Borel sets (and therefore, any Borel equivalence relation whatsoever) is Borel reducible to the equivalence relation of Borel bireducibility. (In somewhat finer terms, they showed that the partial order of inclusion on Borel sets is Borel reducible to the quasi-order of Borel reducibility.) Their technique was to find a collection of, in some sense, strongly mutually ergodic equivalence relations, indexed by reals, and then assign to each Borel set B a sort of “direct sum” of the equivalence relations corresponding to the reals in B. Then if B1, ⊆ B2 it was easy to see that the equivalence relation thus induced by B1 was Borel reducible to the one induced by B2, whereas in the opposite case, taking x to be some element of B / B2, it was possible to show that the equivalence relation corresponding to x, which was part of the equivalence relation induced by B1, was not Borel reducible to the equivalence relation corresponding to B2.