Notes to Independence and Large Cardinals

1. It will be useful at this point to introduce some basic syntactic notions. The language of first-order arithmetic is the language consisting of the usual logical symbols (propositional connectives, quantifiers, and equality (=)) and the following non-logical symbols: The constant symbol 0, the unary successor function S, the binary operators + and ·, and the binary relation ≤. The terms are generated by starting with 0 and the variables and iteratively applying S, + and ·. A quantifier is bounded if it is of the form ∃x ≤ t or ∀x≤t where t is a term not involving x. A formula is a bounded formula (denoted Δ00) if all of its quantifiers are bounded. For n ≥ 0 the classes of formulas Σ0n and Π0n are defined as follows: Σ00 = Π00 = Δ00. Σ0n+1 is the set of formulas of the form ∃xφ where φ is Π0n and x is a (possibly empty) list of variables. Π0n+1 is the set of formulas of the form ∀xφ where φ is Σ0n and x is a (possibly empty) list of variables. The classes Σ0n, Π0n constitute the arithmetical hierarchy of formulas.

For a formal system T of arithmetic, a formula φ is (Π0n)^T if it is provably equivalent in T to a Π0n formula. Likewise, for (Σ0n)^T. A formula φ is (Δ0n)^T if it is provably equivalent in T to both a Σ0n formula and a Π0n formula. In many cases, when the context is clear, we shall drop reference to T.

A formal system T of arithmetic is Σ01-complete if it proves every true Σ01-statement. The system PA is Σ01-complete. The raises the question of whether PA can capture the truths at the next level of the arithmetical hierarchy, that is, the Π01 truths. The statement Con(PA) is a Π01-statement (informally it asserts “for all natural numbers n, n does not code a proof of a contradiction from the axioms of PA”). Thus, granting the consistency of PA, the incompleteness theorem shows that there is a Π01-truth that cannot be proved in PA.

2. A system T is Σ01 sound iff for every Σ01-statement φ, if T proves φ then φ is true.

3. In general, for a cardinal κ, a set x is of hereditarily cardinality of size less than κ, if x has size less than κ, all of the members of x have size less than κ, etc., in other words, the transitive closure of x has size less than κ. The set of all sets of hereditary cardinality less than κ is denoted H(κ). In particular, H(ω)=V_ω.

4. For a more detailed treatment of this notion see the next section. The interpretation of PA in ZFC-Infinity was established during the early days of set theory. The interpretation of ZFC-Infinity in PA was established by Ackermann (1937).

5. In descriptive set theory it is convenient to work with the “logician's reals”, that is, Baire space, ω^ω. This is the set of all infinite sequences of natural numbers (with the product topology (taking ω to be discrete)).

The projective sets of reals (or sets of k-tuples of reals) are obtained by starting with the closed subsets of (ω^ω)^k and iterating the operations of complement and projection. For A ⊆ (ω^ω)^k, the complement of A is simply (ω^ω)^k − A. For A ⊆ (ω^ω)^k+1, the projection of A is

p[A] = {⟨ x₁, … ,x_k ⟩ ∈ (ω^ω)^k | ∃ y, ⟨ x₁, … , x_k, y ⟩ ∈ A}.

(Think of the case where k+1=3. Here A is a subset of three-dimensional space and p[A] is the result of “projecting” A along the third axis onto the plane spanned by the first two axes.) We can now define the hierarchy of projective sets as follows: At the base level let Σ10 consist of the open subsets of (ω^ω)^k and let Π10 consist of the closed subsets of (ω^ω)^k. For each n such that 0 < n < ω, recursively define Π1n to consist of the complements of sets in Σ1n and Σ1n+1 to consist of the projections of sets in Π1n. The projective sets of (k-tuples of) reals are the sets appearing in this hierarchy. This hierarchy is also a proper hierarchy, as can be seen using universal sets and diagonalization.

It is a classical result of analysis (due to Luzin and Suslin in 1917) that the Σ11 sets are Lebesgue measurable.

6. There are a number of different ways of formalizing forcing. One can forgo talk of models and treat the independence results proof-theoretically. One can also give a model-theoretic treatment and here there are two approaches. The first approach starts with a countable transitive model M of a sufficiently large fragment of ZFC and then (working in V) one actually builds an outer model M[G] that satisfies a large fragment of set theory and the statement one wishes to show is independent. The second approach involves working with class-size Boolean-valued models. Cohen took the first approach but we have found it simpler to take the second in our treatment. (We caution the reader that set theorists often speak of V[G] as if there were a model larger than the universe of sets. When they do so they are either thinking of V as a countable model (like M above) or thinking of V[G] as a Boolean valued model (like V^B). See Kunen (1980), pp. 232–235 for further discussion.

7. For a precise definition see chapter 6 of Lindström (2003).

8. The above formulation of large cardinal axioms invokes classes but there are equivalent formulations in terms of sets. For example, in the case of a measurable cardinal κ there is a subset of P(κ) (namely, a κ-complete ultrafilter over κ) witnessing that κ is measurable.

9. It should be noted that in contrast to measurable and strong cardinals, Woodin cardinals are not characterized as the critical point of an embedding or collection of embeddings. In fact, a Woodin cardinal need not be measurable. However, if κ is a Woodin cardinal, then V_κ is a model of ZFC and V_κ satisfies that there is a proper class of strong cardinals.

10. It is still open whether large cardinal axioms at the level of Reinhardt and beyond are inconsistent in ZF alone (that is, without invoking AC). Should they turn out to be consistent then one would have a hierarchy of “choiceless” large cardinal axioms that would climb the hierarchy of interpretability beyond the large cardinal axioms formulated in the context of ZFC.

11. We should note that there are many large cardinal axioms that we have not discussed. The large cardinal axioms that have been investigated to date are for the most part known to be naturally well-ordered. However, there are some comparisons that remain open; for example, although it is known that a strongly compact cardinal is weaker than a supercompact cardinal it is not know how it compares with Woodin cardinals.