## 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 Σ0*n* and
Π0*n* are defined as follows:
Σ00 = Π00 = Δ00.
Σ0*n*+1 is the set of
formulas of the form ∃**x**φ where φ is
Π0*n* and **x** is a (possibly empty) list of variables.
Π0*n*+1 is the set of formulas of the form ∀**x**φ where φ is Σ0*n* and **x** is a
(possibly empty) list of variables. The classes Σ0*n*,
Π0*n* constitute the *arithmetical hierarchy of
formulas*.

For a formal system *T* of arithmetic, a formula φ is
(Π0*n*)^{T} if it is provably equivalent in *T* to a Π0*n*
formula. Likewise, for (Σ0*n*)^{T}. A formula φ is
(Δ0*n*)^{T} if it is provably equivalent in *T* to both a
Σ0*n* formula and a Π0*n* 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_{1}, … ,x_{k}⟩ ∈ (ω^{ω})^{k}| ∃ y, ⟨ x_{1}, … ,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
1*n* to consist of the complements of sets in 1*n* and
1*n*+1 to consist of the projections of sets in 1*n*.
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.