6Cardinals
II Logic and Set Theory
6.1 Definitions
We want to define
card
(
x
) (the cardinality, or size of
x
) in such a way that
card
(
x
) =
card
(
y
)
⇔ x ↔ y
. We can’t define
card
(
x
) =
{y
:
y ↔ x}
as it may
not be a set. So we want to pick a “representative” of the sets that biject with
x, like how we defined the ordinals.
So why not use the ordinals? By Choice, we know that all
x
is well-orderable.
So x ↔ α for some α. So we define:
Definition (Cardinality). The cardinality of a set
x
, written
card
(
x
), is the
least ordinal α such that x ↔ α.
Then we have (trivially) card(x) = card(y) ⇔ x ↔ y.
(What if we don’t have Choice, i.e. if we are in ZF? This will need a really
clever trick, called the Scott trick. In our universe of ZF, there is a huge of
blob of things that biject with
x
. We cannot take the whole blob (it won’t be a
set), or pick one of them (requires Choice). So we “chop off” the blob at fixed,
determined point, so we are left with a set.
Define the essential rank of
x
to be the least rank of all
y
such that
y ↔ x
.
Then set card(x) = {y ∈ V
essrank(x)
+
: y ↔ x}.)
So what cardinals are there? Clearly we have 1, 2, 3, ···. What else?
Definition (Initial ordinal). We say an ordinal α is initial if
(∀β < α)(¬β ↔ α),
i.e. it is the smallest ordinal of that cardinality.
Then 0
,
1
,
2
,
3
, ··· , ω, ω
1
, γ
(
X
) for any
X
are all initial. However,
ω
ω
is not
initial, as it bijects with ω (both are countable).
Can we find them all? Yes!
Definition (Omega ordinals). We define ω
α
for each α ∈ On by
(i) ω
0
= ω;
(ii) ω
α+1
= γ(ω
α
);
(iii) ω
λ
= sup{ω
α
: α < λ} for non-zero limit λ.
It is easy induction to show that each
ω
α
is initial. We can also show that
every initial
δ
(for
δ ≥ ω
) is an
ω
α
. We know that the
ω
α
are unbounded since,
say ω
α
≥ α for all α. So there is a least α with ω
α
≥ δ.
If
α
is a successor, then let
α
=
β
+
. Then
ω
β
< δ ≤ ω
α
. But there is no
initial ordinal between
ω
β
and
ω
α
=
γ
(
ω
β
), since
γ
(
X
) is defined as the least
ordinal that does not biject with X. So we must have δ = ω
α
.
If
α
is a limit, then since
ω
α
is defined as a supremum, by definition we
cannot have
δ < ω
α
, or else there is some
β < α
with
δ < ω
β
. So
ω
α
=
δ
as well.
Definition (Aleph number). Write ℵ
α
(“aleph-α”) for card(ω
α
).
Then from the argument above, we have
Theorem. The
ℵ
α
are the cardinals of all infinite sets (or, in ZF, the cardinals
of all infinite well-orderable sets). For example, card(ω) = ℵ
0
, card ω
1
= ℵ
1
.
We will use lower case letters to denote cardinalities and upper case for the
sets with that cardinality. e.g. card(N) = n.
Definition (Cardinal (in)equality). For cardinals
n
and
m
, write
m ≤ n
if
M
injects into
N
, where
card M
=
m, card N
=
n
. This clearly does not depend on
M and N.
So
m ≤ n
and
n ≤ m
implies
n
=
m
by Schr¨oder-Bernstein. Write
m < n
if
m ≤ n by m = n.
Example. card(P(ω)) > card(ω).
This ≤ is a partial order. Moreover, it is a total order (assuming AC).