Cardinality recap

The set of positive integers \(\mathbb{Z}^{+}\) is countably infinite.

The set of integers \(\mathbb{Z}\) is countably infinite and is a proper superset of \(\mathbb{Z}^{+}\). In fact, the set difference \[\mathbb{Z} \setminus \mathbb{Z}^{+} = \{ x \in \mathbb{Z} \mid x \notin \mathbb{Z}^+\} = \{ x \in \mathbb{Z} \mid x \leq 0 \}\] is countably infinite.

The set of rationals \(\mathbb{Q} = \left\{ \frac{p}{q} \mid p \in \mathbb{Z} \text{ and } q \in \mathbb{Z} \text{ and } q \neq 0 \right\}\) is countably infinite.

The set of real numbers \(\mathbb{R}\) is uncountable. In fact, the closed interval \(\{x \in \mathbb{R} ~|~ 0 \leq x \leq 1\}\), any other nonempty closed interval of real numbers whose endpoints are unequal, as well as the related intervals that exclude one or both of the endpoints are each uncountable. The set of irrational numbers \(\overline{\mathbb{Q}} = \mathbb{R} - \mathbb{Q} = \{ x \in \mathbb{R} \mid x \notin \mathbb{Q} \}\) is uncountable.

We can classify any set as

• Finite size. Fact: For each positive number \(n\), for any sets \(X\) and \(Y\) each size \(n\), there is a bijection between \(X\) and \(Y\).

• Countably Infinite. Fact: for any countably infinite sets \(X\) and \(Y\), there is a bijection between \(X\) and \(Y\).

• Uncountable. Examples: \(\mathcal{P}(\mathbb{N})\), the power set of any infinite set, the set of real numbers, any nonempty interval of real numbers. Fact: there are (many) examples of uncountable sets that do not have a bijection between them.

Finite sets definition

Definition: A finite set is one whose distinct elements can be counted by a natural number.

Cardinality motivation

Motivating question: when can we say one set is bigger than another?

Which is bigger?

• The set \(\{1,2,3\}\) or the set \(\{0,1,2,3\}\)?

• The set \(\{0, \pi, \sqrt{2} \}\) or the set \(\{\mathbb{N}, \mathbb{R}, \emptyset\}\)?

• The set \(\mathbb{N}\) or the set \(\mathbb{R}^+\)?

Which of the sets above are finite? infinite?

Cardinality rationale for functions

Key idea for cardinality: Counting distinct elements is a way of labelling elements with natural numbers. This is a function! In general, functions let us associate elements of one set with those of another. If the association is “good", we get a correspondence between the elements of the subsets which can relate the sizes of the sets.

Cardinality power sets

Recall: When \(U\) is a set, \(\mathcal{P}(U) = \{ X \mid X \subseteq U\}\)

Key idea: For finite sets, the power set of a set has strictly greater size than the set itself. Does this extend to infinite sets?

Definition: For two sets \(A, B\), we use the notation \(|A| < |B|\) to denote \((~|A| \leq |B| ~) \land \lnot (~|A| = |B|)\).

\[\begin{aligned} {4} &\emptyset = \{ \} \qquad &&\mathcal{P}(\emptyset) = \{ \emptyset \} \qquad &&|\emptyset| < |\mathcal{P}(\emptyset)| \\ &\{1 \} \qquad &&\mathcal{P}(\{1\}) = \{ \emptyset, \{1\} \} \qquad &&|\{1\}| < |\mathcal{P}(\{1\})| \\ &\{1,2 \} \qquad &&\mathcal{P}(\{1,2\}) = \{ \emptyset, \{1\}, \{2\}, \{1,2\} \} \qquad &&|\{1,2\}| < |\mathcal{P}(\{1,2\})| \\ \end{aligned}\]

\(\mathbb{N}\) and its power set

Example elements of \(\mathbb{N}\)

Example elements of \(\mathcal{P}(\mathbb{N})\)

Claim: \(| \mathbb{N} | \leq |\mathcal{P} ( \mathbb{N} ) |\)

Claim: There is an uncountable set. Example: \(\underline{\phantom{~~~\mathcal{P}(\mathbb{N})~~~}}\)

Proof: By definition of countable, since \(\underline{\phantom{~~~\mathcal{P}(\mathbb{N})~~~}}\) is not finite, to show is \(|\mathbb{N}| \neq |\mathcal{P}(\mathbb{N})|\) .

Rewriting using the definition of cardinality, to show is

Towards a proof by universal generalization, consider an arbitrary function \(f: \mathbb{N} \to\mathcal{P}(\mathbb{N})\).

To show: \(f\) is not a bijection. It’s enough to show that \(f\) is not onto.

Rewriting using the definition of onto, to show: \[\neg \forall B \in \mathcal{P}(\mathbb{N}) ~\exists a \in \mathbb{N} ~(~f(a) = B~)\] . By logical equivalence, we can write this as an existential statement: \[\underline{\phantom{\qquad\qquad\exists B \in \mathcal{P}(\mathbb{N}) ~\forall a \in \mathbb{N} ~(~f(a) \neq B~)\qquad\qquad}}\] In search of a witness, define the following collection of nonnegative integers: \[D_f = \{ n \in \mathbb{N} ~\mid~ n \notin f(n) \}\] . By definition of power set, since all elements of \(D_f\) are in \(\mathbb{N}\), \(D_f \in \mathcal{P}(\mathbb{N})\). It’s enough to prove the following Lemma:

Lemma: \(\forall a \in \mathbb{N} ~(~f(a) \neq D_f~)\).

Proof of lemma:

By the Lemma, we have proved that \(f\) is not onto, and since \(f\) was arbitrary, there are no onto functions from \(\mathbb{N}\) to \(\mathcal{P}(\mathbb{N})\). QED

Where does \(D_f\) come from? The idea is to build a set that would “disagree" with each of the images of \(f\) about some element.

Cardinality rationals reals

Comparing \(\mathbb{Q}\) and \(\mathbb{R}\)

Both \(\mathbb{Q}\) and \(\mathbb{R}\) have no greatest element.

Both \(\mathbb{Q}\) and \(\mathbb{R}\) have no least element.

The quantified statement \[\forall x \forall y (x < y \to \exists z ( x < z < y) )\] is true about both \(\mathbb{Q}\) and \(\mathbb{R}\).

Both \(\mathbb{Q}\) and \(\mathbb{R}\) are infinite. But, \(\mathbb{Q}\) is countably infinite whereas \(\mathbb{R}\) is uncountable.
The set of real numbers

\(\mathbb{Z} \subsetneq \mathbb{Q} \subsetneq \mathbb{R}\)

Order axioms (Rosen Appendix 1):

Completeness axioms (Rosen Appendix 1):

Each real number \(r \in \mathbb{R}\) is described by a function to give better and better approximations \[x_r: \mathbb{Z}^+ \to \{0,1\} \qquad \text{where $x_r(n ) = n^{th} $ bit in binary expansion of $r$}\]

Claim: \(\{ r \in \mathbb{R} ~\mid~ 0 \leq r ~\wedge~ r \leq 1 \}\) is uncountable.

Approach 1: Mimic proof that \(\mathcal{P}(\mathbb{Z}^+)\) is uncountable.

Proof: By definition of countable, since \(\{ r \in \mathbb{R} ~\mid~ 0 \leq r ~\wedge~ r \leq 1 \}\) is not finite, to show is \(|\mathbb{N}| \neq |\{ r \in \mathbb{R} ~\mid~ 0 \leq r ~\wedge~ r \leq 1 \}|\) .

To show is \(\forall f : \mathbb{Z}^+ \to \{ r \in \mathbb{R} ~\mid~ 0 \leq r ~\wedge~ r \leq 1 \} ~~(f \text{ is not a bijection})~~\). Towards a proof by universal generalization, consider an arbitrary function \(f: \mathbb{Z}^+ \to \{ r \in \mathbb{R} ~\mid~ 0 \leq r ~\wedge~ r \leq 1 \}\). To show: \(f\) is not a bijection. It’s enough to show that \(f\) is not onto. Rewriting using the definition of onto, to show: \[\exists x \in \{ r \in \mathbb{R} ~\mid~ 0 \leq r ~\wedge~ r \leq 1 \} ~\forall a \in \mathbb{N} ~(~f(a) \neq x~)\] In search of a witness, define the following real number by defining its binary expansion \[d_f = 0.b_1 b_2 b_3 \cdots\] where \(b_i = 1-b_{ii}\) where \(b_{jk}\) is the coefficient of \(2^{-k}\) in the binary expansion of \(f(j)\). Since¹ \(d_f \neq f(a)\) for any positive integer \(a\), \(f\) is not onto.

Approach 2: Nested closed interval property

To show \(f: \mathbb{N} \to \{ r \in \mathbb{R} ~\mid~ 0 \leq r ~\wedge~ r \leq 1 \}\) is not onto. Strategy: Build a sequence of nested closed intervals that each avoid some \(f(n)\). Then the real number that is in all of the intervals can’t be \(f(n)\) for any \(n\). Hence, \(f\) is not onto.

Consider the function \(f: \mathbb{N} \to \{ r \in \mathbb{R} ~\mid~ 0 \leq r ~\wedge~ r \leq 1 \}\) with \(f(n) = \frac{1+\sin(n)}{2}\)

Cardinality uncountable examples

• The power set of any countably infinite set is uncountable. For example: \[\mathcal{P}(\mathbb{N}), \mathcal{P}(\mathbb{Z^+}), \mathcal{P}(\mathbb{Z})\] are each uncountable.

• The closed interval \(\{x \in \mathbb{R} ~|~ 0 \leq x \leq 1\}\), any other nonempty closed interval of real numbers whose endpoints are unequal, as well as the related intervals that exclude one or both of the endpoints.

• The set of all real numbers \(\mathbb{R}\) is uncountable and the set of irrational real numbers \(\overline{\mathbb{Q}}\) is uncountable.