nLab
cardinal arithmetic

Context

Arithmetic

  • ,

  • ,

  • , , , , , , , , , , ,

  • ,

  • , ,

  • , , ,

,

    • ,

Contents

Idea

Cardinal arithmetic is an arithmetic with cardinals, which generalizes the ordinary arithmetic of natural numbers to non-finite numbers.

The idea is that on finite sets, whose cardinalities are natural numbers, the usual operations of arithmeticaddition, multiplication and exponentiation – are represented on finite sets by basic operations of set theory, namely forming disjoint union of sets, forming Cartesian product of sets and forming function sets of sets.

A\phantom{A}natural numbersA\phantom{A}A\phantom{A}finite setsA\phantom{A}
A\phantom{A}additionA\phantom{A}A\phantom{A}disjoint unionA\phantom{A}
A\phantom{A}multiplicationA\phantom{A}A\phantom{A}Cartesian productA\phantom{A}
A\phantom{A}exponentiationA\phantom{A}A\phantom{A}function setsA\phantom{A}

(Here passing from the left to the right column is an example of categorification, while passing from right to left is an example decategorification.)

But the operations on sets on the right directly generalize from finite sets to general sets, hence from sets whose cardinality is a natural number to infinite cardinals. Therefore cardinal arithmetic is also called a transfinite arithmetic.

Definitions

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.

Remarks

  • 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.

Properties

Theorem

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

Proof

Since ππ+π=2πππ\pi \leq \pi + \pi = 2 \cdot \pi \leq \pi \cdot \pi, it suffices to prove πππ\pi \cdot \pi \leq \pi. Establishing this is closely analogous to establishing one of the standard bijections ×\mathbb{N} \cong \mathbb{N} \times \mathbb{N} – not the one that enumerates along successive diagonals x+y=kx + y = k which are spheres in an L 1L^1 metric (and which involves additive structure), but one which enumerates along successive spheres in an L L^\infty metric (which involves only order structure).

With this hint in mind, regard π\pi as the least ordinal in its cardinality class (using the well-ordering theorem), and suppose π\pi is a minimal counterexample to the statement. Thus |α| 2=|α|{|\alpha|}^2 = {|\alpha|} for all ordinals α<π\alpha \lt \pi. Consider π 3=π×π×π\pi^3 = \pi \times \pi \times \pi in lexicographic order. This is a well-ordered set, as is the subset

S={(x,y,z)π 3:x=max(y,z)}S = \{(x, y, z) \in \pi^3: x = \max(y, z)\}

under the order inherited from π 3\pi^3. Clearly Sπ 2S \cong \pi^2 as sets. Under the supposition |π|<|π| 2{|\pi|} \lt {|\pi|}^2, the ordinal π\pi is isomorphic to one of the initial segments

S(a,b,c){(x,y,z)S:(x,y,z)<(a,b,c)}S(a, b, c) \coloneqq \{(x, y, z) \in S: (x, y, z) \lt (a, b, c)\}

of SS, say S(α,β,γ)S(\alpha, \beta, \gamma). But then (regarding α\alpha as an ordinal less than π\pi)

|π|=|S(α,β,γ)||S(α,α,α)|=|α| 2=|α|<|π|{|\pi|} = {|S(\alpha, \beta, \gamma)|} \leq {|S(\alpha, \alpha, \alpha)|} = {|\alpha|}^2 = {|\alpha|} \lt {|\pi|}

which gives a contradiction.

Remark

Conversely, if (relative to ZF or any other standard set theory) we assume that any infinite set can be put in bijection with its cartesian square, then every set can be well-ordered, a result originally due to Tarski. Details may be found at Hartogs number.

Corollary

If one of two non-zero cardinals κ,λ\kappa, \lambda is infinite, then

κ+λ=κλ=max{κ,λ}.\kappa + \lambda = \kappa \cdot \lambda = \max \{\kappa, \lambda\}.
Proof

Clearly, κκ+λ\kappa \leq \kappa + \lambda and λκ+λ\lambda \leq \kappa + \lambda, so max{κ,λ}κ+λ\max \{\kappa, \lambda\} \leq \kappa + \lambda, and similarly for multiplication instead of addition, assuming the cardinals are non-zero. Letting μ=max{κ,λ}\mu = \max \{\kappa, \lambda\}, we also have

κλμμ=μ\kappa \cdot \lambda \leq \mu \cdot \mu = \mu

and similarly for addition instead of multiplication.

References

Traditional lecture notes include

  • Alexandru Baltag, Axiomatix set theory lecture 8: Cardinal arithmetic (pdf)

  • Cardinal arithmetic (pdf)

See also

The point of view of categorification is amplified in

Last revised on August 9, 2018 at 11:09:01. See the history of this page for a list of all contributions to it.