6Cardinals
II Logic and Set Theory
6.2 Cardinal arithmetic
Definition (Cardinal addition, multiplication and exponentiation). For cardinals
m, n
, write
m
+
n
for
card
(
M ⊔N
);
mn
for
card
(
M ×N
); and
m
n
for
card
(
M
N
),
where
M
N
=
{f
:
f is a function N → M }
. Note that this coincides with our
usual definition of X
n
for finite n.
Example. R ↔ P(ω) ↔ 2
ω
. So card(R) = card(P
ω
) = 2
ℵ
0
.
Similarly, define
X
i∈I
m
i
= card
G
i∈I
M
i
!
.
Example. How many sequences of reals are there? A real sequence is a function
from ω → R. We have
card(R
ω
) = (2
ℵ
0
)
ℵ
0
= 2
ℵ
0
×ℵ
0
= 2
ℵ
0
= card(R)
Note that we used facts like
Proposition.
(i) m + n = n + m since N ⊔M ↔ N ⊔N with the obvious bijection.
(ii) mn = nm using the obvious bijection
(iii)
(
m
n
)
p
=
m
np
as (
M
N
)
P
↔ M
N×P
since both objects take in a
P
and an
N and returns an M.
It is important to note that cardinal exponentiation is different from ordinal
exponentiation. For example,
ω
ω
(ordinal exponentiation) is countable, but
ℵ
ℵ
0
0
≥ 2
ℵ
0
> ℵ
0
(cardinal exponentiation).
From IA Numbers and sets, we know that
ℵ
0
ℵ
0
=
ℵ
0
. What about
ℵ
1
ℵ
1
?
Or ℵ
3
ℵ
0
?
It turns out that cardinal sums and multiplications are utterly boring:
Theorem. For every ordinal α,
ℵ
α
ℵ
α
= ℵ
α
.
This is the best we could ever ask for. What can be simpler?
Proof.
Since the Alephs are defined by induction, it makes sense to prove it by
induction.
In the following proof, there is a small part that doesn’t work nicely with
α = 0. But α = 0 case (ie ℵ
0
ℵ
0
= ℵ
0
) is already done. So assume α = 0.
Induct on
α
. We want
ω
α
× ω
α
to biject with
ω
α
, i.e. well-order
ω
α
× ω
α
to
an ordering of length ω
α
.
Using the ordinal product clearly doesn’t work. The ordinal product counts
the product in rows, so we have many copies of
ω
α
. When we proved
ℵ
0
ℵ
0
=
ℵ
0
,
we counted them diagonally. But counting diagonally here doesn’t look very
nice, since we will have to “jump over” infinities. Instead, we count in squares
ω
α
ω
α
We set (
x, y
)
<
(
x
′
, y
′
) if either
max
(
x, y
)
< max
(
x
′
, y
′
) (this says that (
x
′
, y
′
)
is in a bigger square), or, (say
max
(
x, y
) =
max
(
x
′
, y
′
) =
β
and
y
′
=
β, y < β
or
x
=
x
′
=
β, y < y
′
or
y
=
y
′
=
β, x < x
′
) (nonsense used to order things in the
same square — utterly unimportant).
How do we show that this has order type
ω
α
? We show that any initial
segment has order type < ω
α
.
For any proper initial segment I
(x,y)
, we have
I
(x,y)
⊆ β × β
for some β < ω
α
, since ω
α
is a limit, with wlog β infinite. So
β × β ↔ β
by induction hypothesis (their cardinality is less that ω
α
). So
card(β × β) < card(ω
α
).
Hence
I
(x,y)
has order type
< ω
α
. Thus the order type of our well-order is
≤ ω
α
.
So
ω
α
× ω
α
injects into
ω
α
. Since trivially
ω
α
injects into
ω
α
× ω
α
, we have
ω
α
× ω
α
↔ ω
α
.
So why did we say cardinal arithmetic is boring? We have
Corollary. Let α ≤ β. Then
ℵ
α
+ ℵ
β
= ℵ
α
ℵ
β
= ℵ
β
.
Proof.
ℵ
β
≤ ℵ
α
+ ℵ
β
≤ ℵ
β
+ ℵ
β
= 2ℵ
β
≤ ℵ
β
× ℵ
β
= ℵ
β
,
So done
Example. X ⊔ X bijects with X, for infinite X (in ZFC).
However, cardinal exponentiation is very hard. For example, is 2
ℵ
0
=
ℵ
1
?
This is the continuum hypothesis, and cannot be proved or disproved in ZFC!
Even today, not all implications among values of
ℵ
ℵ
β
α
are known, i.e. we don’t
know whether they are true, false or independent!