3.10 Cardinality[1YW]
[22B]For convenience we will use the symbol \(|A|\) to indicate cardinality of the set \(A\). This symbol is used as follows. Given two sets \(A,B\), we will write \(|A|= |B|\) if these sets are equipotents (or sometimes equinumerous), i.e. if there is a bijective function between \(A\) and \(B\); we will write \(|A|≤ |B|\) if there is an injective function from \(A\) to \(B\). We will also write \(|A|{\lt} |B|\) if there is an injective function from \(A\) to \(B\), but not a bijection. If we assume the axiom of choice to be true, then for every pair of sets we always have \(|A|≤ |B|\) or \(|B|≤ |A|\) (see 114).
[1Z9]If we now fix a family \(\mathcal F\) of sets of interest, we first define the relation \(A∼ B\iff | A|= | B|\) in it; it is easily shown that this is an equivalence relation; so we get that \(| A|≤ | B|\) is a total order in \({\mathcal F}/∼\).
This derives from the Proposition 82, since the relation
is reflexive and transitive, and by Cantor–Bernstein’s Theorem
In the following, let \(E_ 0=∅\), and let \(E_ n=\{ 1, \ldots n\} \) otherwise if \(n ≥ 1 \).
[1B1]By definition 1 “a set \( A \) is finite and has cardinality \(n\)” if it is equipotent to a set \(E_ n\) (for a choice of \(n ∈ ℕ\); note that there is at most one \(n\) for which this may hold, by the above Lemma). So when the set is finite, \(|A|\) is identified with the natural number of its elements; we will write \(|A|=n\). If a set isn’t finite, then it is infinite.
Note that the null map \(f: ∅ → ∅ \) is a bigection; and \(|A|=0 ⇔ A=∅\). The following exercise is a fundamental result.
[2GH]Prove that \(ℕ\) is infinite, and that \(|ℕ|{\gt}n, ∀ n∈ ℕ\). Hidden solution: [UNACCESSIBLE UUID ’2GJ’]
We recall Theorem 1.12.2 of the notes [ 2 ] , for convenience.
[02S] If \(A\) is infinite then \(|A|\ge |{\mathbb {N}}|\). In particular, \(|A|{\gt}n\) for any \(n\in {\mathbb {N}}\).
Finite sets
- E112
[02T] If \(A\) is a finite set and \(B⊆ A\), prove that \(B\) is finite.
Hidden solution: [UNACCESSIBLE UUID ’02V’]
- E112
[02W] Suppose we have a finite number \(m≥ \)1 of sets \(A_ 1,\ldots , A_ m\) all finite. Show that \(⋃_{j=1}^ m A_ j\) is a finite set. Hidden solution: [UNACCESSIBLE UUID ’02X’]
- E112
[02Y] Recall that \(A^ B\) is the set of all functions \(f:B→ A\). If \(A,B\) are finite non-empty sets show that \(| A^ B|=| A|^{| B|} \). What happens if one set, or both sets, are empty? Hidden solution: [UNACCESSIBLE UUID ’02Z’]
- E112
[22K]If \(A,B\) are finite non-empty sets, calculate the cardinality of the set of injective functions \(f:B\to A\) ; and the cardinality of the surjective ones. What happens if one, or both, of the two sets \(A,B\) are empty?
Comparison
- E112
[030]Prerequisites:13.Suppose \(A\) is not empty. We have \(| A|≤ | B|\) if and only if there is a surgective function \(f:B→ A\). (The ”if” implication necessitates the axiom of choice; See also 2.)
- E112
[031] Show that if \(| A_ 1|\le | A_ 2| \) and \(| B_ 1|\le | B_ 2| \) then \(| A_ 1\times {B_ 1}|\le | A_ 2\times {B_ 2}|\).
- E112
[032] Show that if \(| A_ 1|≤ | A_ 2| \) and \(| B_ 1|≤ | B_ 2| \) then \(| A_ 1^{B_ 1}|≤ | A_ 2^{B_ 2}|\) Hidden solution: [UNACCESSIBLE UUID ’033’]
- E112
[034] (Solved on 2021-11-04) Show that \(| (A^ B)^ C|=| A^{(B \times C)}|\). Hidden solution: [UNACCESSIBLE UUID ’035’]
- E112
[036] Let \(I\) be a family of indices and \(B_ i,A_ i\) sets, for \(i∈ I\), such that \(| A_ i|≤ | B_ i|\); suppose that the sets \(B_ i\) are pairwise disjoint. Show that
\[ \left|⋃_{i∈ I} A_ i\right| ≤ \left|⋃_{i∈ I} B_ i\right|~ . \](In your opinion, is it possible to prove this result without using the axiom of choice, at least in the case in which \(I\) is countable?) Hidden solution: [UNACCESSIBLE UUID ’037’]
- E112
[038] Let \(C\) be a set, \(I\) a family of indexes, and then \(B_ i\) sets, for \(i\in I\); suppose the sets \(B_ i\) are pairwise disjoint; define \({\mathcal B}=\bigcup _{i\in I} B_ i\) for convenience; then show that
\begin{eqnarray} \forall i, |B_ i|\le |C|& \Rightarrow & \left|{\mathcal B}\right| \le \left|I\times C\right| \label{eqn:B_ i_ cup_ le_ times_ C}\\ \forall i, |B_ i|\ge |C|& \Rightarrow & \left|{\mathcal B}\right| \ge \left|I\times C\right|~ ~ . \end{eqnarray}Hidden solution: [UNACCESSIBLE UUID ’039’]
where \({\mathcal B}=\prod _{i\in I} B_ i\). Hidden solution: [UNACCESSIBLE UUID ’03D’] [03F] Prerequisites:17.(Proposed on 2022-12) Show that cardinalities are always comparable: given two sets \(A,B\) either \(| A|\le | B|\) or \(| B|\le | A|\) holds. (Use Zorn’s lemma and the construction explained in the exercise 17). Hidden solution: [UNACCESSIBLE UUID ’03G’]
(Present as theorem 1.19 in the notes)
This statement is equivalent to the Axiom of Choice, see [ 21 ] .
Countable cardinality
[2DF]Recall that a set is ”countably infinite” if it has the same cardinality of \(ℕ\).
If \(A\) is countably infinite, there exists \(a:ℕ→ A\) bijective. Writing \(a_ n\) instead of \(a(n)\), we will therefore say that \(A=\{ a_{0},a_{1},a_ 2\ldots \} \) is an enumeration.
- E115
[03H] Found a polynomial \(p(x,y)\) which, seen as a function \(p:ℕ^ 2→ ℕ\) is bijective. It follows, iterating, that there is a polynomial \(q_ k\) in \(k\) variables \(q_ k:ℕ^ k→ℕ\) that is bijective. So \(ℕ^ k\) is countable. Hidden solution: [UNACCESSIBLE UUID ’03J’][UNACCESSIBLE UUID ’03K’]
- E115
[03M]Show that the sets \( {\mathbb {Z}}, {\mathbb {Q}}\) are countable. Hidden solution: [UNACCESSIBLE UUID ’03N’]
- E115
-
Let \(A_ 0.A_ 1\ldots A_ n\ldots \) sets of countable cardinality, for \(n\in {\mathbb {N}}\).
Show that \(B=\bigcup _{k=0}^\infty A_ k\) is countable.
Note that \(B\) is infinite-countable if for example there is at least one \(n\) for which \(A_ n\) is infinite-countable.
Hidden solution: [UNACCESSIBLE UUID ’03Q’]
- E115
[03R] We indicate with \({\mathcal P}_{\mathfrak f}(A)\) the set of subsets \(B⊆ A\) which are finite sets. This is called colloquially the set of finite parts.
Show that \({\mathcal P}_{\mathfrak f}(ℕ)\) is countably infinite.
Hidden solution: [UNACCESSIBLE UUID ’03S’]
This result applies in general, see 2.
Cardinality of the continuum
[03V]We will say that a set has cardinality of the continuum if it has the same cardinality as \(ℝ\).
[2F2] Cantor proved that \(|ℕ|{\lt} |ℝ|\). Cantor then (in 1878) formulated the continuum hypothesis CH: for any infinite set \(E⊆ ℝ\), either \(|E|= |ℝ|\) or \(|E|= |ℕ|\). For many year mathematicians tried to prove (or disprove) CH. It took decades to understand that this was not possible. We know know that, if ZF is consistent, then neither CH nor its negation can be proven as theorems in ZF (even using the Axiom of Choice). The second part of the statement was proved by Gödel nel 1939. The first part by Cohen in 1963. See Chap. 6 in [ 12 ] .
- E117
[03X](Proposed on 2022-12) Explain how you could explicitly construct a bijection between \([0,1)\) and \([0,1)^ 2\).
- E117
[03Y](Proposed on 2022-10-13) (Solved on 2022-10-27) Show with explicit constructions that the following sets have continuum cardinalities:
\[ [0,1],\quad [0,1),\quad (0,1),\quad (0,∞)~ ~ . \]Hidden solution: [UNACCESSIBLE UUID ’03Z’]
- E117
-
Show that the following sets have continuum cardinalities.
\[ ℝ^ n,\quad \{ 0,1\} ^{ℕ},\quad ℕ^{ℕ},\quad ℝ^{ℕ}~ ~ . \]Hidden solution: [UNACCESSIBLE UUID ’041’][UNACCESSIBLE UUID ’042’]
- E117
[043]Prerequisites:5,3.Let \(A_ t\) be sets with cardinality less than or equal to the continuum, for \(t∈ℝ\). Show that \(⋃_{t∈ℝ} A_ t\) has cardinality of the continuum. Hidden solution: [UNACCESSIBLE UUID ’044’]
- E117
[045]Let \({\mathcal A}\) be the set of subsets \(B⊆ ℝ\) which are countable sets; show that \({\mathcal A}\) has cardinality of the continuum. Hidden solution: [UNACCESSIBLE UUID ’046’]
In general
Let’s add some more general exercises.
- E117
[048]Show that \(|A|{\lt}|{\mathcal P}(A)|\). Hidden solution: [UNACCESSIBLE UUID ’049’]
- E117
[04B]Consider the set \(ℕ ^ℕ\) of functions \(f:ℕ→ℕ\); and the subset \(\mathcal A\) of \(f\) of functions that can be defined using an algorithm, written in a programming language of your choice (also assuming that the computer that is running this algorithm has potentially unlimited memory) and such that for each choice \(n∈ℕ\) in input the algorithm must finish and return \(f(n)\). Compare the cardinalities of \(ℕ ^ℕ\) and \(\mathcal A\).
[04D](Proposed on 2022-12) Calculate the cardinality of the set \({\mathcal F}\) of weakly decreasing functions \(f:ℕ→ℕ\). Hidden solution: [UNACCESSIBLE UUID ’04F’] [04G] Prerequisites:134.
A set \(A\) is called Dedekind–infinite if \(A\) is in bijection with a proper subset, that is if there is \(B⊂ A, B≠ A\) and \(h:A→ B\) bijection. Show that a set \(A\) is Dedekind–infinite if and only if there is an injective function \(g:ℕ→ A\). (This result does not require the axiom of choice.)
Hidden solution: [UNACCESSIBLE UUID ’04H’] [04J] Prerequisites:111.If \(A\) is infinite and \(B\) is countable, show that \(|A|=|A∪ B|\) using the existence of an injective function \(g:ℕ→ A\).
Hidden solution: [UNACCESSIBLE UUID ’04K’] [22M]Prerequisites:2,2.Similarly if \(A\) is infinite and \(B\) is finite show that \(|A|=|A⧵ B|\) using the fact that for every infinite set \(X\) there is an injective \(g:ℕ→ X\) function. Hidden solution: [UNACCESSIBLE UUID ’22N’] [04M] Prerequisites:111, 2. Show that a set \(A\) is Dedekind–infinity if and only if it is infinite (according to the definition seen at the beginning of the chapter).
Hidden solution: [UNACCESSIBLE UUID ’04N’]
Note: According to [ 10 ] , the previous equivalence cannot be proved using only the axioms of ZF (Zermelo–Fraenkel without the axiom of choice) ; the previous equivalence can be proved using the axioms of ZFC (Zermelo–Fraenkel with the axiom of choice); but its validity in ZF is weaker than the axiom of choice.
[UNACCESSIBLE UUID ’1ZC’] [04P] Prerequisites:2,17.Difficulty:*.(Proposed on 2022-12)
Let \(X\) an infinite set. Show that \(X\) can be partitioned in two sets \(X_ 1,X_ 2\) that have the same cardinality as \(X\). (Hint. consider subsets of \(X\) on which the property is valid, use Zorn) Hidden solution: [UNACCESSIBLE UUID ’04Q’] [04R] Prerequisites:2,1,3.Difficulty:*.(Solved on 2022-10-13
in parte)
Let \(A\) infinite. Show that \(|D× A|=|A|\) for every non-empty countable set \(D\) . 3
(A possible solution uses 2) Hidden solution: [UNACCESSIBLE UUID ’04S’]
(Another possible solution uses Zermelo’s theorem, 3 and 1; in this case 2 becomes a corollary of this result.) Hidden solution: [UNACCESSIBLE UUID ’04T’] [04V](Solved on 2022-10-27) Let \(A,B\) be infinite. Show that \(|A∪ B|=\max \{ |A|,|B|\} \). Hidden solution: [UNACCESSIBLE UUID ’04W’] [04X]Show that if \(A\) is an infinite set, and decomposes into the disjoint union of two sets \(A_ 1,A_ 2\) with \(|A_ 1|≤ |A_ 2|\) then \(|A|=|A_ 2|\). Hidden solution: [UNACCESSIBLE UUID ’04Y’] [04Z] Prerequisites:17, 2.Difficulty:**.(Proposed on 2022-10-13) (Solved on 2022-11-15)
Let \(A,B\) be infinite sets. Show that \(|A^ 2|=|A|\).
Use this result to show that if \(A,B\) are not empty and at least one is infinite then \(|A× B|=\max \{ |A|,|B|\} \).
Hidden solution: [UNACCESSIBLE UUID ’050’]
See also the note 118.
[27H]Historical notes.
The proposition ”\(|A^ 2|=|A|\) holds for every infinite set” is equivalent to the axiom of choice. This was demonstrated by Tarski [ 23 ] in 1928 ; the article is online and downloadable and contains other surprising equivalences. See also [ 21 ] Part 1 Section 7 page 140 assertion CN6.
Jan Mycielski [ 18 ] reports: «Tarski told me the following story. He tried to publish his theorem (stated above) in the Comptes Rendus Acad. Sci. Paris but Fréchet and Lebesgue refused to present it. Fréchet wrote that an implication between two well known propositions is not a new result. Lebesgue wrote that an implication between two false propositions is of no interest. And Tarski said that after this misadventure he never tried to publish in the Comptes Rendus».
This anecdote shows how in the past (before the works of Godel and Cohen [ 5 ] , even the most respected mathematician had a feeble grasp of the importance of the Axiom of Choice.
- E118
[051] Prerequisites:2.Let \(A\) be an infinite set. Let \(n∈ℕ\) with \(n≥ 1\). Show that \(|A^ n|=|A|\). Hidden solution: [UNACCESSIBLE UUID ’052’]
- E118
[053] Prerequisites:5, 1, 2.(Proposed on 2022-12) (Solved on 2023-01-24) Let \(A\) be an infinite set. Show that the set of finite parts \({\mathcal P}_{\mathfrak f}(A)\) has the same cardinality as \(A\). Hidden solution: [UNACCESSIBLE UUID ’054’]
- E118
[055] Prerequisites: 6, 2.(Solved on 2023-01-24) Let \(X\) be an infinite set, let \(∼\) be an equivalence relation on \(X\), let \(U=X/∼\) be the equivalence classes.
Suppose each class is finite, show that \(|U|=|X|\).
Suppose \(U\) is infinite and every class has cardinality at most \(|U|\), then \(|U|=|X|\).
Hidden solution: [UNACCESSIBLE UUID ’056’]
- E118
[057]Prerequisites:3,2,3.Difficulty:**.
Let \(V\) be a real vector space. Let \(A,B\) be two Hamel bases (see 3). Show that \(|A|=|B|\). (This result is known as ”Dimension theorem”)
More in general, let \(L,G⊆ V\), if the vectors in \(L\) are linearly independent, and \(G\) generates \(V\), show that \(|L|≤ |G|\).
Hidden solution: [UNACCESSIBLE UUID ’058’]
[UNACCESSIBLE UUID ’1ZB’] [UNACCESSIBLE UUID ’05B’] [UNACCESSIBLE UUID ’05C’][UNACCESSIBLE UUID ’05D’] [UNACCESSIBLE UUID ’05F’] [UNACCESSIBLE UUID ’05G’]
Power
Recall that \(A^ B\) is the set of all functions \(f:B→ A\). We will write \(|2^ A|\) to indicate the cardinality of the set of parts of \(A\).
- E118
[05J]Prerequisites:2.(Proposed on 2022-12) Let \(A,B\) be non-empty sets and such that \(A\) is infinite and \(2≤ |B|≤ |A|\) then \(|B^ A|=|2^ A|\). Hidden solution: [UNACCESSIBLE UUID ’05K’]
- E118
[05M]Let \(A,B\) be non-empty sets, suppose there is a \(C\) such that \(|B|=|2^ C|\) then \(|B^ A|=\max \{ |B|,|2^ A| \} \).
Hidden solution: [UNACCESSIBLE UUID ’05N’]
In general in case \(|B|{\gt}|A|\) the study of the cardinality of \(|B^ A|\) is very complex (even in seemingly simple cases like \(A=ℕ\)).