[Understanding Analysis by Stephen Abbott] - [Chapter 1 The Real Numbers]

1-1 Correspondence

The term cardinality is used in mathematics to refer to the size of a set.

Definition 1.5.1 A function $f : A \to B$ is one-to-one $(1-1$) if $a_1 \neq a_2$ in $A$ implies that $f(a_1) \neq f(a_2)$ in $B$. The function is onto if, given any $b in B$, it is possible to find an element $a \in A$ for which $f(a) = b$

A function $f : A \to B$ that is both $(1-1)$ and onto provides us with exactly what we mean by a $(1-1)$ correspondence between two sets. The property of being $(1-1)$ means that no two elements of $A$ correspond to the same element of $B$, and the property of being onto ensures that every element of $B$ corresponds to something in $A$

Definition 1.5.2 The set $A$ has the same cardinality as $B$ if there exists $f : A \to B$ that is $1-1$ and onto. In this case, we write $A \sim B$

Countable Sets

Definition 1.5.5 A set $A$ is countable if $N \sim A$. An infinite set that is not countable is called an uncountable set.

Theorem 1.5.6

The set $Q$ is countable.
The set $R$ is uncountable.

Proof.

Set $A_1 = \{0\}$ and for each $n \leqslant 2$, let $A_n$ be the set given by $$ A_n = \{\pm\frac{p}{q} : \text{where } p, q \in N \text{ are in lowest terms with } p + q = n\} $$
The crucial observation is that each $A_n$ is finite and every rational number appears in exactly on of these sets. Our $1-1$ correspondence with $N$ is then achieved by consecutively listing the elements in each $A_n$

The fact that this line of reasoning applies to any rational number $p/q$ is our proof that the set $A_n$ were constructed to be disjoint so that no rational number appears twice.
The second part proof is done by contradiction. Assume that there does exist a $1-1$, onto function $f : N \to R$. Again, what this suggests is that it is possible to enumerate the element of $R$. If we let $x_1 = f(1)$, $x_2 = f(2)$, and so on, then our assumption that $f$ is onto means that we can write $$ R = \{x_1, x_2, x_3, x_4,...\} \tag{1}\label{1} $$ and be confident that every real number appears somewhere on the list. We will now use the Nested Interval Property to produce a real number that is not there.
Let $I_1$ be a closed interval that does not contain $x_1$. Next let $I_2$ be a closed interval, contained in $I_1$, which does not contain $x_2$. The existence of such an $I_2$ is easy to verify. Certainly $I_1$ contains two smaller disjoint closed intervals, and $x_2$ can only be in one of these. In general, given an interval $I_n$, construct $I_{n+1}$ to satisfy
1. $I_{n+1} \subseteq I_n$
2. $x_{n+1} \notin I_{n+1}$
We now consider the intersection $\bigcap_{n=1}^\infty I_n$. If $x_{n_0}$ is some real number from the list $\eqref{1}$, then we have $x_0 \notin I_{n_0}$, and it follows that $$ x_{n_0} \notin \bigcap_{n=1}^\infty I_n $$

Now, we are assuming that the list in $\eqref{1}$ contains every real number, and this leads to the conclusion that $$ \bigcap_{n=1}^\infty I_n = \emptyset $$

However, the Nested Interval Property (NIP) asserts that $\bigcap_{n=1}^\infty I_n \neq \emptyset $. By NIP, there is at least one $x \in \bigcap_{n=1}^\infty I_n$ that, consequently cannot be on the list in \eqref{1}. This contradiction means that such an enumeration of $R$ is impossible, and we conclude that $R$ is an uncountable set.

What exactly should be make of this discovery? It is an important exercise to show that any subset of a countable set must be either countable or finite. If a set can be arranged into a single list, then deleting some elements from this list results in another (shorter, and potentially terminating) list. This means that countable sets are smaller type of infinite set. Anything smaller is either still countable or finite.

The cardinality of $R$ is, informally speaking, a larger type of infinity. The real numbers so outnumber the natural numbers that there is no way to map $N$ onto $R$. The set $Q$, on the other hand, is countable. By imitating the demonstration that $N ~ Z$, we can prove that the union of two countable sets must be countable. Because $R = Q \cup \I$, it follows that $I$ cannot be countable otherwise $R$ would be. The inescapable conclusion is that, despite the fact that we have encountered so few of them, the irrational numbers form a far greater subset of $R$ than $Q$.

Theorem 1.5.7 If $A \subseteq B$ and $B$ is countable, then $A$ is either countable or finite.

Theorem 1.5.8

If $A_1, A_2,...A_m$ are each countable sets, then the union $A_1 \cup A_2 \cup ...\cup A_m$ is countable
If $A_n$ is a countable set for each $n \in N$, then $\bigcap_{n=1}^\infty A_n$ is countable.

Tags

[Understanding Analysis by Stephen Abbott] - [Chapter 1 The Real Numbers] - [1.5 Cardinality]

1-1 Correspondence

Countable Sets