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.

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.

Musical chairs analogy

Analogy: Musical chairs

What does this say about the number of chairs and the number of people?

Injective functions visually

Informally, a function being one-to-one means “no duplicate images”.

Cardinality lower bound definition

Definition: For nonempty sets \(A, B\), we say that the cardinality of \(A\) is no bigger than the cardinality of \(B\), and write \(|A| \leq |B|\), to mean there is a one-to-one function with domain \(A\) and codomain \(B\). Also, we define \(|\emptyset| \leq |B|\) for all sets \(B\).

Injective cardinality musical chairs

In the analogy: The function \(sitter: \{ Chair1, Chair2\} \to \{ Person\sun, Person\smiley, Person\frownie \}\) given by \(sitter(Chair1) = Person\sun\), \(sitter(Chair2) = Person\smiley\), is one-to-one and witnesses that \[| \{ Chair1, Chair2\} | \leq |\{ Person\sun, Person\smiley, Person\frownie \}|\]

Cardinality upper bound definition

Definition: For nonempty sets \(A, B\), we say that the cardinality of \(A\) is no smaller than the cardinality of \(B\), and write \(|A| \geq |B|\), to mean there is an onto function with domain \(A\) and codomain \(B\). Also, we define \(|A| \geq |\emptyset|\) for all sets \(A\).

Surjective cardinality musical chairs

In the analogy: The function \(triedToSit: \{ Person\sun, Person\smiley, Person\frownie \} \to \{ Chair1, Chair2\}\) given by \(triedToSit(Person\sun) = Chair1\), \(triedToSit(Person\smiley) = Chair2\), \(triedToSit(Person\frownie) = Chair2\), is onto and witnesses that \[|\{ Person\sun, Person\smiley, Person\frownie \}| \geq | \{ Chair1, Chair2\} |\]

Cardinality properties

Properties of cardinality \[\begin{aligned} &\forall A ~ (~ |A| = |A| ~)\\ &\forall A ~ \forall B ~(~ |A| = |B| ~\to ~ |B| = |A|~)\\ &\forall A ~ \forall B ~ \forall C~ (~ (|A| = |B| ~\wedge~ |B| = |C|) ~\to ~ |A| = |C|~) \end{aligned}\]

Extra practice with proofs: Use the definitions of bijections to prove these properties.

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}\)