Countability

Countability is a fundamental concept in set theory and mathematics that deals with the size and nature of sets. The idea that there are different kinds of infinities can be quite counterintuitive at first. However, understanding these distinctions is crucial. It helps us determine whether a set is finite, countably infinite, or countably infinite, providing insight into concepts like discrete and continuous (after all this course is called discrete mathematics). This understanding significantly influences how we can classify and think about different problems, particularly in computer science.

This chapter is one where you can truly get creative with proofs, and sometimes you have to. That's what makes proofs so rewarding — sometimes it's just about finding that neat idea. It requires a lot of practice to build up intuition and ideas that you can adapt to different cases. But this is what makes it so enjoyable - really, trust us :). Every problem is more or less unique. That's what makes proofs really rewarding - sometimes it's just this neat idea. Oftentimes people think this makes this chapter harder because, after all, there is no recipe to approach every problem. It's just a lot of practice that builds up some intuition and ideas you might be able to use and alter in different cases. But this really makes it super fun. Because every problem is really different. Not unlike the basics of set theory, where proofs always go by showing double-sided inclusion.

The central aspect of this chapter is to decide whether a given set $A$ is countable or uncountable. More precisely you need to find an injection/bijection $\mathbb{N} \to A$ or find some other way to show that there is none.

Theory

The proofs for the following theorems can be found in the script and won't be recited here.

The first point provides us with major intuition about countability. The proof follows quite immediately from composing two bijections and obtaining a new one. This is a central idea. These properties can be combined with proof-patterns to prove uncountability or countability.

This is a rather extra theorem. Though, it's sort of intuitive. It somehow captures a notion of antisymmetry (however not in the sense that $A = B$, but only $A \sim B$). It will probably be rarely or might never be the case in this course that it is easier to show that these two injections exist than that a bijection $A \to B$ exists.

Important Countable Sets

This is a goto set to prove countability. Finding an injection to $\{0,1\}^*$ is often the base of a proof and combining this with Lemma 3.15 (Transitivity), we quickly obtain countability.

This is another very central theorem and in the case of certain involved set operations, should be considered as a starting point for proving that some complicated set is countable.

Just in case you are wondering: Why are they called semi-infinite? This is because they go on infinitely in one direction. This is often super useful. We can think about functions as infinite

This theorem is central and a thought about the uncountability of $\{0,1\}^{\infty}$ should be a possible starting point for any uncountability proof.

Computability

How to approach problems?

Countable or Uncountable

Determine whether the set you have is countable or uncountable. This requires you to first really understand what's going on in your set. Think about similar examples and similarities to known sets (often finding these similarities will directly lead you to the injection, which you have to find anyway).

Uncountablility Proofs

You can only start once you more or less understand what's going on in your set.

The following pattern is a common pattern and surely cannot be used in every case. However, oftentimes when having an uncountable set, you can find an injection from the set $\{0,1\}^{\infty}$, which is known to be uncountable. You could of course also use something like $\mathbb{R}$ or $[0,1]$, which might be easier sometimes. Also, the order below is not fixed and the proofs can look way different than the form below and still be correct. The purpose of these steps below is more to give you a structure of how one could approach problems involving proofs of uncountability.

Let $A$ be the set you want to prove to be uncountable.

1. Finding the injection

The first and probably most difficult step is to find an injection:

The intuition here is that you somehow have to encode all the information of a bitstring $b$ in its image $f(b)$. We want to sort of be able to reconstruct $b$ from $f(b)$ uniquely. More formally this is exactly the definition of an injection. Namely, for arbitrary $b, b' \in \{0,1\}^{\infty}$ we want to have:

This is just the definition of injectivity. You have to carefully think about this when choosing $f$, to then later prove that it is indeed the case. In this first step, the most important thing is, that you really precisely write down the definition of your function $f$ and how it maps the bitstring to elements of $A$.

2. Proving that your function is a function

Now that you thought about your function it should be clear to you that you have constructed something that is indeed a function. However you still have to prove or at least write some justification for why the following properties are fulfilled, because this is not obvious in many cases:

1. Does your function actually map to elements from $A$ and not something else? You defined your function to be a map from $\{0,1\}^{\infty}$ however, is it actually the case that for each $b\in \{0,1\}^{\infty}$, $f(b) \in A$?

2. Is your function actually a function? Argue why it is well-defined and totally-defined (definition of a function).

This step can in some cases already be quite demanding, in other cases it can also be quite short.

3. Proving injectivity

This is more or less the central part of your proof. Here you have to show that what you defined is actually injective. To do this, the definition of injectivity is basically everything we have to show. Two common ways are:

1. Let $b, b' \in \{0,1\}^{\infty}$ be arbitrary such that $b \neq b'$. Then we have

Therefore, $f$ is injective.
As you can see, this is just the direct method of proving that $f$ fulfills the definition.

2. Let $b, b' \in \{0,1\}^{\infty}$ be arbitrary such that $f(b) = f(b')$. Then we have

Therefore, we have proven indirectly that $f$ is injective.
As you can see, this is just the contraposition of the definition of the injectivity of $f$ (see proof pattern of indirect proof).

The difficulty in this step is to provide precise and detailed justifications.

4. Punchline

Now we can actually apply definition 3.42 to obtain $\{0,1\}^{\infty} \preceq A$. However, it is not immediate how this implies that $A$ is uncountable, as we need to show that not $A \preceq \mathbb{N}$. There are multiple ways how one could argue this. An easy way is to assume that $A$ is countable ($A \preceq \mathbb{N}$) and that $\{0,1\}^{\infty} \preceq A$. Then we obtain with Lemma 3.15 (Transitivity) that $\{0,1\}^{\infty} \preceq \mathbb{N}$, which is false as proven in lecture via Cantor's diagonalization argument (we obtain a contradiction). Therefore, $A$ must be uncountable.

See the exercise "This seems odd" for an application of this pattern.

Tricks

Often you can try out some handy tricks when tackling countability exercises. Many students think that you should skip countability problems in the exam, but if you have a good overview over the theorems, lemmas and corollaries, equipped with some techniques, experience and tricks, the idea to some of those problems can get to you pretty fast. Often you can combine those with constructing a specific injection.

The Complement Trick

To prove that a given set $A$ is uncountable, find an uncountable set $B$ such that $A \subseteq B$ and prove that $B \setminus A$ is countable.

Intuitively this corresponds to, instead of directly proving that a set $A$ is uncountable, proving that it is part of a huge set, in which the complement of $A$ is very small (countable). Then this means $A$ is very big, because if it was not $B$ would not be very big. Translating this into a more formal language:

In the following we prove the validity of this pattern: Assume towards a contradiction that $A$ is countable. $A \cup (B \setminus A)$ is countable by Theorem 3.22. But notice that $A \cup (B \setminus A) = B$. Hence we have that $B$ is countable, a contradiction.

For a simple application of this pattern we prove that $[0,1] \setminus \mathbb{Q}$ is uncountable. Consider $[0,1]$ (which we know is uncountable). By definition we have $[0,1] \setminus \mathbb{Q} \subseteq [0,1]$. We have that $[0,1] \setminus ([0,1] \setminus \mathbb{Q}) = \mathbb{Q} \cap [0,1]$. Now we know that $\mathbb{Q} \cap [0,1] \subseteq \mathbb{Q}$ and by Lemma 3.15 (iii) hence $\mathbb{Q} \cap [0,1] \preceq \mathbb{Q}$ and by transitivity of $\preceq$ we have that $\mathbb{Q} \cap [0,1] \preceq \mathbb{N}$ which means that $\mathbb{Q} \cap [0,1]$ is countable. Now we can directly use the complement trick (which you would have to prove in an exam) to conclude that $[0,1] \setminus \mathbb{Q}$ is uncountable.

If you see a countability problem where a direct proof of uncountability doesn't come to mind, you can think about the complement, at many times this is much easier :)

Fundamental Theorem of Arithmetic

Often when working with natural numbers, one can apply the fundamental theorem of arithmetic (i.e. that every natural number $\geq 1$ can be uniquely factored into a product of prime powers).

For example, one can very easily create an injection $f : \mathbb{N} \times \mathbb{N} \to \mathbb{N}, (a,b) \mapsto 2^a3^b$. If we have $f((a,b)) = f((c,d))$, then $2^a3^b = 2^c3^d$. Since for every number the exponents of primes in the prime factorization are unique we have that $(a,b) = (c,d)$ which means that $f$ is injective.

This can expedite many injection constructions, but can also lead to some problems if applied incorrectly as shown in the following:

One could allege that the following is an injection: $f : \{0,1\}^\infty \to \mathbb{N}, b \mapsto n$ where $n = \prod_{i} {p_i}^{b_i}$ where where $p_i$ corresponds to the $i$'th prime. Now we could "prove" the same way as above that this is an injection. But this would mean that $\{0,1\}^\infty$ is countable which is not the case, right? The issue here is that $\prod_i {p_i}^{b_i}$ does not necessarily converge. If $b_i = 1$ for distinctly infinite $i \in \mathbb{N}$ the product will be infinity which is not in $\mathbb{N}$, so $f$ is not a function. Often this can constitute a trap when using the fundamental theorem of arithmetic to construct an injection to $\mathbb{N}$.

Exercises