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 . 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 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 and be sets. We say that and have the same cardinality if there is a bijective mappings .

We definite countability as follows:

Definition 1:

A set is finite if it has the same cardinality to a finite subset . A set iscountableif there is a bijective mapping .If is finite or countable, we say is

at most countable.

Often, one may see used to represent a countable cardinality, and used to represent the cardinality of .

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

Lemma 1:

If is infinite, and is injective, then is countable.

Proof:Let

Since is injective, for each , there is a unique with .

Define . Clearly is bijective. Thus, given an injective , the map is bijective. Thus, is countable.

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

Theorem 1:is countable.

Proof:Recall . By the lemma, we need define an injective . We may use a trick involving primes. Let be prime numbers greater than . Define . WE see that is injective (check this), so we may order the co-domain of and construct a mapping as in the lemma.

Using the same trick with primes, we may prove a finite cartesian product of countable sets is countable. Therefore, say, or are countable.

Theorem 2:

If is a finite set of countable sets, is countable.

Proof:Let be prime numbers greater than . Since each is countable, there are injective mappings . For an , define

If , since this will only happen if . Thus, 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 be countable, and be a set of countable sets. Then, is countable.

Proof:Since is countable, there is a mapping . Since each is countable, there are mappings . We need find a mapping that is injective.

Define for each , an indice . Let be primes greater than . Then the mapping is injective.To see is injective, consider . Then, either or . In either case, we use the injectivity of and to see that is injective at . Thus, 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 is uncountable.Suppose is countable. Then we may split into countably many members, so that we can define

Now we may if we find an element not in the collection , then is not countable. Consider where

Clearly , but for any . Thus, we have a contradiction.

As a corollary to this lemma, we have the nice fact:

is not countable. To prove this just note that , so that 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 is uncountable. As usual, any inquiries can be sent to erdosninth@gmail.com.

Cheers,

J.T.