nLab
cardinal arithmetic

Contents

Idea

arithmetic with cardinals. a kind of transfinite arithmetic

Definition

For SS a set, write |S|{|S|} for its cardinality. Then the standard operations in the category Set induce arithmetic operations on cardinal numbers:

For S 1S_1 and S 2S_2 two sets, the sum of their cardinalities is the cardinality of their disjoint union, the coproduct in SetSet:

|S 1|+|S 2||S 1⨿S 2|. {|S_1|} + {|S_2|} \coloneqq {|S_1 \amalg S_2|} \,.

More generally, given any family (S i) i:I(S_i)_{i: I} of sets indexed by a set II, the sum of their cardinalities is the cardinality of their disjoint union:

i:I|S i|| i:IS i|. \sum_{i: I} {|S_i|} \coloneqq {|\coprod_{i: I} S_i|} \,.

Likewise, the product of their cardinalities is the cardinality of their cartesian product, the product in SetSet:

|S 1||S 2||S 1×S 2|. {|S_1|} \, {|S_2|} \coloneqq {|S_1 \times S_2|} \,.

More generally again, given any family (S i) i:I(S_i)_{i: I} of sets indexed by a set II, the product of their cardinalities is the cardinality of their cartesian product:

i:I|S i|| i:IS i|. \prod_{i: I} {|S_i|} \coloneqq {|\prod_{i: I} S_i|} \,.

Also, the exponential of one cardinality raised to the power of the other is the cardinality of their function set, the exponential object in SetSet:

|S 1| |S 2||Set(S 2,S 1)|. {|S_1|}^{|S_2|} \coloneqq {|Set(S_2,S_1)|} \,.

In particular, we have 2 |S|2^{|S|}, which (assuming the law of excluded middle) is the cardinality of the power set P(S)P(S). In constructive (but not predicative) mathematics, the cardinality of the power set is Ω |S|\Omega^{|S|}, where Ω\Omega is the cardinality of the set of truth values.

The usual way to define an ordering on cardinal numbers is that |S 1||S 2|{|S_1|} \leq {|S_2|} if there exists an injection from S 1S_1 to S 2S_2:

(|S 1||S 2|):((S 1S 2)). ({|S_1|} \leq {|S_2|}) \;:\Leftrightarrow\; (\exists (S_1 \hookrightarrow S_2)) \,.

Classically, this is almost equivalent to the existence of a surjection S 2S 1S_2 \to S_1, except when S 1S_1 is empty. Even restricting to inhabited sets, these are not equivalent conditions in constructive mathematics, so one may instead define that |S 1||S 2|{|S_1|} \leq {|S_2|} if there exists a subset XX of S 2S_2 and a surjection XS 1X \to S_1. Another alternative is to require that S 1S_1 (or XX) be a decidable subset of S 2S_2. All of these definitions are equivalent using excluded middle.

This order relation is antisymmetric (and therefore a partial order) by the Cantor–Schroeder–Bernstein theorem (proved by Cantor using the well-ordering theorem, then proved by Schroeder and Bernstein without it). That is, if S 1S 2S_1 \hookrightarrow S_2 and S 2S 1S_2 \hookrightarrow S_1 exist, then a bijection S 1S 2S_1 \cong S_2 exists. This theorem is not constructively valid, however.

The well-ordered cardinals are well-ordered by the ordering <\lt on ordinal numbers. Assuming the axiom of choice, this agrees with the previous order in the sense that κλ\kappa \leq \lambda iff κ<λ\kappa \lt \lambda or κ=λ\kappa = \lambda. Another definition is to define that κ<λ\kappa \lt \lambda if κ +λ\kappa^+ \leq \lambda, using the successor operation below.

The successor of a well-ordered cardinal κ\kappa is the smallest well-ordered cardinal larger than κ\kappa. Note that (except for finite cardinals), this is different from κ\kappa's successor as an ordinal number. We can also take successors of arbitrary cardinals using the operation of Hartog's number?, although this won't quite have the properties that we want of a successor without the axiom of choice.

Properties

  • It is traditional to write 0{}_0 for the first infinite cardinal? (the cardinality of the natural numbers), 1\aleph_1 for the next (the first uncountable cardinality), and so on. In this way every cardinal (assuming choice) is labeled μ\aleph_\mu for a unique ordinal number μ\mu, with ( μ)) += μ +(\aleph_\mu))^+ = \aleph_{\mu^+}.

  • For every cardinal π\pi, we have 2 π>π2^\pi \gt \pi (this is sometimes called Cantor's theorem). The question of whether 2 0= 12^{\aleph_0} = \aleph_{1} (or more generally whether 2 μ= μ +2^{\aleph_\mu} = \aleph_{\mu^+}) is called Cantor’s continuum problem; the assertion that this is the case is called the (generalized) continuum hypothesis. It is known that the continuum hypothesis is undecidable in ZFC.

  • For every transfinite cardinal π\pi we have (using the axiom of choice) π+π=π\pi + \pi = \pi and ππ=π\pi \cdot \pi = \pi, so addition and multiplication are idempotent.

References

Lecture notes include

  • Cardinal arithmetic (pdf)
Created on May 24, 2017 03:26:43 by Urs Schreiber (46.183.103.17)