Large Cardinals - Descriptive Set Theory

Inaccessible cardinals¶

The cardinality of $V_\alpha$ grows rather fast relative to ${}\alpha$ . For example,

|V_{\omega+\alpha}| = \beth_\alpha

(1)

where the beth function $\beth_\alpha$ is defined as

\begin{gather*} \beth_0 = \aleph_0 \\ \beth_{\alpha+1} = 2^{\beth_\alpha} \\ \beth_{\lambda} = \sup \{ \beth_\alpha \colon \alpha < \lambda\} \quad \text{ $\lambda$ limit} \end{gather*}

(2)

The existence of inaccessible cardinals ensures that the von-Neumann hierarchy is “long enough” for ${}\alpha$ to eventually “catch up” with the cardinality of $V_\alpha$ .

Recall the enumeration of all cardinals by means of the $\aleph$ -sequence:

\aleph_0 = \omega, \quad \aleph_{\alpha+1} = \aleph_\alpha^+, \quad \aleph_\lambda = \sup \{ \aleph_\xi \colon \xi<\lambda\} \; \text{ for limit } \lambda.

Here $\kappa^+$ is the least cardinal $> \kappa$ . Some cardinals are limits of short sequences of cardinals -- for example,

\aleph_\omega = \lim_n \aleph_n

is uncountable, but a limit of a countable sequence of smaller cardinals. Generally, cardinals who are a limit of a sequence of cardinals of length smaller than their cardinality are called singular. Non-singular cardinals are called regular:

\Op{reg}(\kappa): \iff \forall \alpha < \kappa \; \forall f \;( f: \alpha \to \kappa \; \to \; \sup_{\xi < \alpha} f(\xi) < \kappa).

In other words, a regular cardinal ${}\kappa$ cannot be reached by less then ${}\kappa$ -many steps. The first example of a regular cardinal is $\aleph_0$ .

On the other hand,

\aleph_\omega, \aleph_{\omega+\omega}, \aleph_{\aleph_{\omega}}, \aleph_{\aleph_{\aleph_\omega}}, \ldots

are singular and this suggests the question:

Are there regular cardinals of the form $\aleph_\lambda$ with $\lambda$ limit?

This is captured by the notion of inaccessibility.

Under the Generalized Continuum Hypothesis,

$(\mathsf{GCH}) \quad \forall \alpha \;\; 2^{\aleph_\alpha} = \aleph_{\alpha}^+$

weakly and strongly inaccessible cardinals coincide.

If $\kappa > \omega$ is inaccessible, then $\kappa = \aleph_\kappa$ . Moreover, we have

Proof

It suffices to show that $|V_\alpha| < \kappa$ for all $\alpha < \kappa$ . This follows by a straightforward induction, using the fact that ${}\kappa$ is strongly inaccessible.

This in turn implies we can bound the cardinality of elements of $V_\kappa$ .

Proof

( $\Rightarrow$ ) $x \in V_\kappa$ implies $|x| < |V_\kappa|$ . Apply Proposition 1.

( $\Leftarrow$ ) Since $x \subseteq V_\kappa$ , each $y \in x$ has rank $< \kappa$ . Since $|x| < \kappa$ , by regularity of ${}\kappa$ ,

\Op{rank}(x) = \sup\{\Op{rank}(y)+1 \colon y \in x\} < \kappa

(5)

which implies $x \in V_\kappa$ .

We have already seen that for limit $\alpha > \omega$ , $V_\alpha$ is a model of all $\ZFC$ axioms except Replacement.

Proof

We verify that $V_\kappa$ satisfies the axiom of Replacement. Suppose $x \in V_\kappa$ and $f:x \to V_\kappa$ is a function. Then $f[x] \subseteq V_\kappa$ , and by Proposition 2, $|f[x]| \leq |x| < \kappa$ . Applying the other direction of Proposition 2 to $f[x]$ , we obtain $f[x] \in V_\kappa$ , as desired.

Suppose an inaccessible cardinal exists, and let ${}\kappa$ be the least inaccessible.
It is not hard to verify that

V_\kappa \models \ZFC + \text{``there does not exist an inaccessible cardinal''}.

(6)

(You verify that being a inaccessible cardinal is absolute for $V_\kappa$ .) Therefore, the existence of an inaccessible cardinal is not provable from $\ZFC$ . This fact also follows from Gödel’s second incompleteness theorem.

Measurability¶

We have seen that (assuming the Axiom of Choice) there subsets of $\Real$ that are not Lebesgue measurable. Inspecting the proof, we see that we only use the following properties of Lebesgue measure:

${}\sigma$ -additivity,
translation invariance ( $\lambda(A) = \lambda(A+r)$ ),
$\lambda(A) > 0$ for some $A$ .

For spaces without an additive structures, instead of translation invariance, we can consider a non-triviality condition:

m(\{x\})=0 \quad \text{ for all $x$}

(7)

The generalized measure problem asks whether there exists a set $M$ together with a measure function

\begin{gather*} m: \mathcal{P}(M) \to [0,\infty), \end{gather*}

(8)

so that the following conditions are met:

(M1) $\quad$ $m(M) =1$
(M2) $\quad$ $\forall x \in M \; m(\{x\})=0$
(M3) $\quad$ if $(A_i)_{i < \omega}$ is a countable sequence of disjoint sets $\subseteq M$ , then

m\left(\bigcup_{i<\omega} A_i\right ) = \sum_{i<\omega} m(A_i)

The structure of the set $M$ does not play any role here, so we can replace it by a cardinal ${}\kappa$ outright. One can also consider strengthening ${}\sigma$ -additivity to ${}\kappa$ -additivity:

If $\gamma < \kappa$ and $(A_\xi)_{\xi< \gamma}$ is a sequence of disjoint subsets of ${}\kappa$ , then
$m(\bigcup_{\xi<\gamma} A_\xi) = \sum_{\xi<\gamma} m(A_\xi).$

A transfinite sum $\sum_{\xi<\gamma}$ is given as the supremum of all sums over finite subsequences:

\sum_{\xi<\gamma} m(A_\xi) = \sup \left \{ \sum_{\xi \in F} m(A_\xi) \colon F \subseteq \gamma \text{ finite}\right \}.

(9)

Hence, $\omega_1$ -additive is the same as ${}\sigma$ -additive.

Proof

Suppose $m$ is a measure on ${}\kappa$ that is not ${}\kappa$ -additive. Then, for some $\gamma < \kappa$ , there exists a sequence $(A_\xi)_{ \xi< \gamma}$ of disjoint subsets of ${}\kappa$ so that

m(\bigcup_{\xi<\gamma} A_\xi) \ne \sum_{\xi<\gamma} m(A_\xi).

(10)

Since a measure is always ${}\sigma$ -additive, $\gamma > \omega$ has to hold, and there can be at most countably many $A_\xi$ with $m(A_\xi)>0$ .

We can drop those $A_\xi$ , and by the ${}\sigma$ -additivity of $m$ for the remaining $\xi$ it has to hold that $m(A_\xi)=0$ while $m \left(\bigcup_{\xi<\gamma} A_\xi \right) = r >0$ .

By putting

\overline{m}(X) = \frac{m(\bigcup_{\xi \in X} A_\xi)}{r}

we obtain a measure on $\gamma < \kappa$ , contradicting the minimality of ${}\kappa$ .

Measurable cardinals¶

If $m$ is a measure on ${}\kappa$ , the associated ideal

\mathcal{I}_m = \{x\subseteq \kappa \colon m(x) = 0 \}

(11)

is a ${}\sigma$ -ideal, or, complementing the notion of $\omega_1$ -additivity, a $\omega_1$ -complete ideal.

The corresponding filter

\mathcal{F}_m = \{x\subseteq \kappa \colon m(x) = 1\}

(12)

is then $\omega_1$ -complete, too.

A measure $m$ is two-valued if it only assumes the values 0 and 1. In this case the corresponding filter $\mathcal{F}_m$ is an ultrafilter (and $\mathcal{I}_m$ is a prime ideal).

Conversely, if $U$ is $\omega_1$ -complete, non-principal ultrafilter on ${}\kappa$ , we can define a two-valued measure $m: \mathcal{P}(\kappa) \to \{0,1\}$ on ${}\kappa$ by letting

m(x) = \begin{cases} 1 & \text{if } x \in U, \\ 0 & \text{otherwise}. \end{cases}

(13)

In the following, we will see that measurability implies inaccessibility.

Proof

Since $U$ is non-principal, no singleton set $\{x\}$ can be in $U$ (for this would imply $\kappa\setminus \{x\} \notin U$ and therefore no subset of it would be in $U$ either, contradicting the non-principality of $U$ ).

If $X \in U$ and $|X| < \kappa$ , then $X$ is the union of $< \kappa$ many singletons. Since $\neg U$ is a ${}\kappa$ -complete prime ideal, this implies $X \in \neg U$ , contradiction.

Proof

If ${}\kappa$ were singular, it would be the union of $<\kappa$ -many sets of cardinality $<\kappa$ . Applying Lemma 1 leads to a contradiction.

Proof

By Proposition 3, any measurable cardinal is regular. Assume for a contradiction there exists $\gamma < \kappa$ with $2^\gamma \geq \kappa$ . As $2^\gamma \geq \kappa$ , there exists a set $S$ of functions $f: \gamma \to \{0,1\}$ with $|S| = \kappa$ . Let $U$ be a ${}\kappa$ -complete, non-principal ultrafilter on $S$ .

For $\alpha < \gamma, i \in \{0,1\}$ , let

X_{\alpha,i} = \{ f \in S \colon f(\alpha) = i\}

(14)

and let $g(\alpha) = i$ if and only if $X_{\alpha,i} \in U$ . Since $U$ is an ultrafilter, $g$ is well-defined on $\gamma$ .

Since $\gamma < \kappa$ and $U$ is ${}\kappa$ -complete,

X = \bigcap_{\alpha < \gamma} X_{\alpha, g(\alpha)}

(15)

is in $U$ . But $|X| \leq 1$ , since the only function possibly in $X$ is $g$ . This contradicts Lemma 1.

Thus, if ${}\kappa$ is real-valued measurable but not measurable, then the continuum $2^{\aleph_0}$ has to be very large.

Partition properties¶

Another concept of largeness is related to the existence of large homogeneous sets for partitions.

For given set $S$ and $n \in \Nat$ , let

[S]^n := \{ X \subseteq S \colon \: |X| = n \}

be the set of all $n$ -element subsets of $S$ . For cardinals $\kappa, \lambda$ , we define

\kappa \to (\lambda)^n_k

to mean that any partition $F: [S]^n \to \{1, \dots, k\}$ with $|S| = \kappa$ has an $F$ -homogeneous subset of cardinality $\lambda$ , that is, a set $H$ , $|H| = \lambda$ , such that

F|_{[H]^n} \equiv \text{ constant}.

Ramsey’s theorem (1929/39) says that for any $n,k \in \Nat$ ,

\aleph_0 \to (\aleph_0)^n_k.

Do there exist uncountable cardinals with similar properties?

A cardinal ${}\kappa$ is weakly compact if it is uncountable and $\kappa \to (\kappa)^2_2$ holds.

Measurable cardinals have even stronger homogeneity properties. Let $[S]^{<\omega}$ be the set of all finite subsets of $S$ . If $F: [S]^{<\omega} \to I$ is a partition, then $H \subseteq S$ is $F$ -homogenenous if

F|_{[H]^n} \equiv \text{ constant}

for all $n \in \Nat$ .

In general, any cardinal that satisfies the statement of the theorem is called Ramsey.

To prove Theorem 4, we introduce normal ultrafilters.

Let us assume as a convention that a filter on a cardinal ${}\kappa$ always contains the end-segments $\{\xi \colon \alpha \leq \xi < \kappa\}$ .

Proof (Rowbottom’s Theorem)

Let $U$ be a normal filter over ${}\kappa$ . We show that for every $n$ , for any $g: [\kappa]^n \to \gamma$ with $\gamma < \kappa$ , there is a set $H_n \in U$ such that $g \Rest{[H_n]^n} \equiv \text{const}$ . The intersection of the $H_n$ is again in $U$ and satisfies the statement of the the theorem.

We proceed by induction. The case $n=1$ follows from the ${}\kappa$ -completeness of $U$ . Now assume $g:[\kappa]^{n+1} \to \gamma$ , with $\gamma < \kappa$ .

For each $S \in [\kappa]^n$ , define $g_S : \kappa \to \gamma$ by

g_S(\alpha) = \begin{cases} g(S \cup \{\alpha\}) & \text{ if } \max S < \alpha \\ 0 & \text{otherwise} \end{cases}

(17)

By ${}\kappa$ -completeness of $U$ , $g_S$ is constant on a set $Y_S \in U$ , say

g_S\Rest{Y_S} \equiv \delta_S < \gamma.

(18)

We now define a function $h: [\kappa]^n \to \gamma$ by letting

h(S) = \delta_S.

(19)

By induction hypothesis, $h$ is constant on a set $Z \subseteq \kappa$ in $U$ (and hence of size ${}\kappa$ ), say $h\Rest{[Z]^n} \equiv \delta < \kappa$ .

For each $\alpha < \kappa$ , let

Y_\alpha = \bigcap \{Y_S \colon \max S \leq \alpha\}

(20)

By ${}\kappa$ -completeness, $Y_\alpha \in U$ , and by normality

H = Z \cap \Delta_{\alpha < \kappa} Y_\alpha \in U

(21)

By Lemma 1, $H$ has cardinality ${}\kappa$ .

We claim that $g$ is constant on $[H]^{n+1}$ : Let $T \in [H]^{n+1}$ . Write $T$ as $S \cup \{\alpha\}$ with $\max S < \alpha$ . Then

\begin{align*} \alpha \in H & \Rightarrow & \alpha \in \Delta_{\gamma < \kappa} Y_\gamma \\ & \Rightarrow & \alpha \in \bigcap_{\beta < \alpha} Y_\beta \\ & \Rightarrow & \alpha \in Y_{\max S} \\ & \Rightarrow & \alpha \in Y_S \\ & \Rightarrow & g_S(\alpha) = \delta_S \end{align*}

(22)

On the other hand, $S \subseteq H$ implies $S \subseteq Z$ and hence by definition of $Z$ , $h(S) = \delta_S = \delta$ , so $g(T) = g_S(\alpha) = \delta_S = \delta$ .

Axiomatic set theory

Models of Set Theory

Constructibility

The Constructible Universe