Not All Infinities Are Born Equal

The reader is probably familiar with the notion of countable and uncountable sets. Though, most students are only familiar with the use of cantor’s diagonalization argument to prove countability of things like \mathbb{Q}. As is the spirit of this blog, I’d like to talk about proving these sorts of things with an alternate argument.


We begin with a notion of the cardinality of sets, and use this to define a countable set. The goal here is to show that, for an infinite set, injectivity into \mathbb{N} is enough to prove countability. We proceed to prove that finite cartesian products of countable sets are countable, as well as countable unions of countable sets, using this lemma.

Formally,
Let A and B be sets. We say that A and B have the same cardinality if there is a bijective mappings f: A \to B.

We definite countability as follows:

Definition 1:
A set A is finite if it has the same cardinality to a finite subset \{1,\ldots,n\} \subset \mathbb{N}. A set A is countable if there is a bijective mapping f: A \to \mathbb{N}.

If A is finite or countable, we say A is at most countable. 

Often, one may see \aleph_0 used to represent a countable cardinality, and \aleph_1 used to represent the cardinality of \mathbb{R}.

In the definition, we may relax the requirement that f be bijective through the following lemma:

Lemma 1:
If A is infinite, and f: A \to \mathbb{N} is injective, then A is countable.

Proof:

Let \eta_1 = \min \limits_{x \in A} \{f(x)\}

\eta_2 = \min \limits_{x \in A} \{f(x) \setminus \{\eta_1\}\}

\vdots

\eta_k = \min \limits_{x \in A} \{f(x) \setminus \{\eta_1,\eta_2, \ldots, \eta_k\}\}

Since f is injective, for each a_i \in A, there is a unique \eta_i \in \mathbb{N} with f(a_i) = \eta_i.

Define g(a_i) = i. Clearly g is bijective. Thus, given an injective f, the map g \circ f: A \to \mathbb{N} \to \mathbb{N} is bijective. Thus, A is countable.

With this lemma, we may prove that \mathbb{Q} is countable. This is of vital importance in the study of analysis, as this gives \mathbb{R} a countable dense subset (making it  a separable space).

Theorem 1: \mathbb{Q} is countable.

Proof:

Recall \mathbb{Q} := \{\frac{s}{r} \, ; \, s \in \mathbb{N}, r \in \mathbb{N}\}. By the lemma, we need define an injective f: \mathbb{Q} \to \mathbb{N}. We may use a trick involving primes. Let p_1,p_2 be prime numbers greater than 1. Define f(\frac{s}{r}) = p_1^sp_2^r. WE see that f is injective (check this), so we may order the co-domain of f and construct a mapping g as in the lemma.

Using the same trick with primes, we may prove a finite cartesian product of countable sets is countable. Therefore, say, \mathbb{Q}^n or \mathbb{Q} \times \mathbb{N} are countable.

Theorem 2:
If \{A_i\}_{i \in I_n} is a finite set of countable sets, A = \prod \limits_{i \in I_n} A_i is countable.

Proof:

Let p_1,\ldots,p_n be prime numbers greater than 1. Since each A_i is countable, there are injective mappings f_i: A_i \to \mathbb{N}. For an a \in A, define f(a) = p_1^{f(a_1)}p_2^{f(a_2)} \cdots p_k^{f(a_k)}

If a \neq b, f(a) \neq f(b) since this will only happen if f(a_i) = f(b_i). Thus, A is countable.

Moreover, given a countable union of countable sets, said union is countable. This will be useful for proving various properties about infinite subsets of $latex\mathbb{R}&s=1$.

Let I be countable, and \{A_i\}_{i \in I} be a set of countable sets. Then, A = \bigcup \limits_{i \in I} A_i is countable.

Proof:

Since I is countable, there is a mapping g: I \to \mathbb{N}. Since each A_i is countable, there are mappings f_i: A_i \to \mathbb{N}. We need find a mapping h: \bigcup \limits_{i \in I} A_i \to \mathbb{N} that is injective.

Define for each x \in A, an indice \alpha(x) = \min \limits_{i \in I} \{g(i) : x \in A_i \}. Let p_1,p_2 be primes greater than 1. Then the mapping h(x) = p_1^{f_{\alpha(x)}(x)}p_2^{\alpha(x)} is injective.To see h is injective, consider x \neq y. Then, either \alpha_1 = \alpha_2 or \alpha_1 \neq \alpha_2. In either case, we use the injectivity of f and g to see that h is injective at x. Thus, A is countable.

An interesting lemma involving all binary strings is given as well. That is, the set of binary strings is uncountable.

Lemma 2:
The set A:= \{(a_0,a_1 \ldots) \, ; \, a_i \in \{0,1\}\} is uncountable.

Suppose A is countable. Then we may split A into countably many members, so that we can define

X_1 = (a_1^1,a_2^2, \ldots)

\vdots

X_k = (a_0^k, a_1^k, \ldots )

Now we may if we find an element not in the collection \{X_j\}_{j \in \mathbb{N}}, then A is not countable. Consider b = (b_0, b_1, \ldots) where

b_j=\left\{  \begin{array}{lr}  0 & : a_j =1 \\  0 & : a_j =0  \end{array}  \right.

Clearly b \in A, but b \neq X_k for any k \in \mathbb{N}. Thus, we have a contradiction.

As a corollary to this lemma, we have the nice fact:
\mathbb{R} is not countable. To prove this just note that A \subset \mathbb{R}^+ \subset \mathbb{R}, so that \mathbb{R} cannot be countable.

I think I’ll stop here, as that’s about all I really need to say about countability basics. I’d recommend seeing how these arguments can be used to prove different facts about countable sets. For example, use the lemma above to prove (a,b) is uncountable. As usual, any inquiries can be sent to erdosninth@gmail.com.

Cheers,

J.T.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s