# Overview of basic results on cardinal arithmetic

Are there some good overviews of basic formulas about addition, multiplication and exponentiation of cardinals (preferably available online)?

$$\newcommand{\alnul}{\aleph_0}\newcommand{\mfr}[1]{\mathfrak{#1}}\newcommand{\Ra}{\Rightarrow}\newcommand{\card}[1]{\left|#1\right|}\newcommand{\powerset}[1]{\mathcal P(#1)}\newcommand{\Lra}{\Leftrightarrow}\newcommand{\Zobr}[3]{#1\colon#2\to#3}\newcommand{\alnul}{\aleph_0}\newcommand{\mfr}[1]{\mathfrak{#1}}\newcommand{\Ra}{\Rightarrow}\newcommand{\card}[1]{\left|#1\right|}\newcommand{\powerset}[1]{\mathcal P(#1)}\newcommand{\Lra}{\Leftrightarrow}\newcommand{\Zobr}[3]{#1\colon#2\to#3}$$I have no doubt that you there are many useful online resources for these, but many such identities are available here at MSE, together with their proofs.

I’ll give a list of some basic results on cardinal arithmetics and I’ll add links to results, which have proofs here at MSE. I am making this CW, so feel free to add more identities and pointers to further useful questions and answers.

In the identities bellow, $$aa$$, $$bb$$, $$cc$$ denote arbitrary cardinals, $$XX$$ is an arbitrary set, $$\alnul\alnul$$ is the cardinality of $$\mathbb N\mathbb N$$ and $$\mfr c=2^{\alnul}\mfr c=2^{\alnul}$$. Cardinality of a set $$XX$$ is denoted by $$\card X\card X$$ and $$\powerset X\powerset X$$ is the notation of the power set of $$XX$$.

Equality of cardinal numbers is defined as follows:
$$|A|=|B| \Lra \text{ there exists a bijection }\Zobr fAB.|A|=|B| \Lra \text{ there exists a bijection }\Zobr fAB.$$
Inequality of cardinal numbers is defined as follows:
$$|A|\le|B| \Lra \text{ there exists an injective function }\Zobr fAB.|A|\le|B| \Lra \text{ there exists an injective function }\Zobr fAB.$$
The definitions of the operations on cardinal numbers (addition, multiplication, exponentiation) can be found e.g. in this answer.

Validity of Axiom of Choice is assumed. If you want to learn about cardinals without AC, you can have a look e.g. at this question: Defining cardinality in the absence of choice

• $$a\le ba\le b$$ $$\land\land$$ $$b\le cb\le c$$ $$\Ra\Ra$$ $$a\le ca\le c$$

This follows from the fact that composition of two injective maps is injective

• $$a\le b \land b\le a \Ra a=ba\le b \land b\le a \Ra a=b$$

This is just a reformulation of Cantor-Bernstein’s theorem.

• For any two sets $$AA$$, $$BB$$ we have $$|A|\le|B||A|\le|B|$$ $$\lor\lor$$ $$|B|\le|A||B|\le|A|$$. I.e. any two sets/any two cardinal numbers are comparable.
• $$|A|\le|B| \Lra (\text{there exists a surjective function }\Zobr fBA \text{ or A is empty}).|A|\le|B| \Lra (\text{there exists a surjective function }\Zobr fBA \text{ or A is empty}).$$

There exists an injection from $X$ to $Y$ if and only if there exists a surjection from $Y$ to $X$.

Note: Proof of this result uses the Axiom of Choice.

• $$\card{\powerset X}=2^{\card X}\card{\powerset X}=2^{\card X}$$
• $$a+b=b+aa+b=b+a$$

This follows simply from commutativity of union: $$A\cup B=B\cup AA\cup B=B\cup A$$.

• $$a+(b+c)=(a+b)+ca+(b+c)=(a+b)+c$$

This follows from associativity of union: $$A\cup(B\cup C)=(A\cup B)\cup CA\cup(B\cup C)=(A\cup B)\cup C$$.

• $$b\le c \Ra a+b\le a+cb\le c \Ra a+b\le a+c$$

This is (after adding some details) basically the same thing as the implication $$B\subseteq CB\subseteq C$$ $$\Ra\Ra$$ $$A\cup B\subseteq A\cup CA\cup B\subseteq A\cup C$$. See Does $a \le b$ imply $a+c\le b+c$ for cardinal numbers?

• $$ab=baab=ba$$

A bijection $$A\times B\to B\times AA\times B\to B\times A$$ can be given by $$(x,y)\mapsto (y,x)(x,y)\mapsto (y,x)$$.

• $$a(bc)=(ab)ca(bc)=(ab)c$$

A bijection between $$A\times(B\times C)A\times(B\times C)$$ and $$(A\times B)\times C(A\times B)\times C$$ can be given by $$(x,(y,z))\mapsto ((x,y),z)(x,(y,z))\mapsto ((x,y),z)$$. See here: A bijection between $X \times (Y \times Z)$ and $(X \times Y) \times Z$

• $$a(b+c)=ab+aca(b+c)=ab+ac$$

This follows from the fact that $$A\times(B\cup C)=A\times B\cup A\times CA\times(B\cup C)=A\times B\cup A\times C$$.

• $$b\le c \Ra ab\le acb\le c \Ra ab\le ac$$
• $$a^2=a\cdot aa^2=a\cdot a$$

• $$a\le b \Ra a^c\le b^ca\le b \Ra a^c\le b^c$$

• $$a\le b \land c\ne 0 \Ra c^a\le c^ba\le b \land c\ne 0 \Ra c^a\le c^b$$

See e.g. this question.

Note that this is not true for $$c=0c=0$$, since $$0^0=10^0=1$$. (The set $$\emptyset^\emptyset=\{\emptyset\}\emptyset^\emptyset=\{\emptyset\}$$ has one element.) The set $$\emptyset^\emptyset\emptyset^\emptyset$$ and its cardinality is also discussed here.

• $$a^{b+c}=a^b\cdot a^ca^{b+c}=a^b\cdot a^c$$
• $$(a^b)^c=a^{bc}(a^b)^c=a^{bc}$$
• $$(ab)^c=a^c\cdot b^c(ab)^c=a^c\cdot b^c$$
• $$a^b\le 2^{ab}a^b\le 2^{ab}$$

• $$a<2^aa<2^a$$

This is Cantor's theorem. The question Is the class of subsets of integers countably infinite? deals with the special case $$a=\alnula=\alnul$$, but there are answers which discuss the more general result or can be easily generalized. See also Understanding the proof for $2^{\aleph_0} > \aleph_0$. This question asks about the general result: Cardinality of a set A is strictly less than the cardinality of the power set of A

• $$\alnul+\alnul=\alnul\alnul+\alnul=\alnul$$
• $$a\ge\alnul \Ra \alnul+a=aa\ge\alnul \Ra \alnul+a=a$$

• $$\alnul\cdot\alnul=\alnul\alnul\cdot\alnul=\alnul$$

The following result is, to some extent, related to the following:

• Union of countably many countable sets is countable.

It is worth mentioning that proof of this uses Axiom of Choice. See Prove that the union of countably many countable sets is countable.

• $$\alnul^{\alnul}=2^{\alnul}=\mfr c\alnul^{\alnul}=2^{\alnul}=\mfr c$$

See e.g. Is $\aleph_0^{\aleph_0}$ smaller than or equal to $2^{\aleph_0}$? or What is $\aleph_0$ powered to $\aleph_0$? or What's the cardinality of all sequences with coefficients in an infinite set? (One of the answers to this question also discusses powers of the form $$\aleph_\alpha^{\aleph_\beta}\aleph_\alpha^{\aleph_\beta}$$ in general.

• If $$aa$$ is infinite cardinal, then $$a^2=aa^2=a$$.

See e.g. About a paper of Zermelo

Note: Proof of this result uses the Axiom of Choice. See also: For every infinite $S$, $|S|=|S\times S|$ implies the Axiom of choice

• If $$bb$$, $$cc$$ are infinite cardinals, then $$b+c=bc=\max\{b,c\}b+c=bc=\max\{b,c\}$$.

Note: This is a consequence of the preceding result, so it relies on the Axiom of Choice too.