Cardinality

Size of Sets

Cardinality is defined as the number of elements in a set. 

The set $\{1,2,3,4,5\}$ has cardinality 5. What about the set $\{a,b,c,d,e\}$? Well, we can map each element in the first set to an element in the second set $$\begin{cases}1 \to a\\2 \to b \\ 3 \to c \\ 4 \to d \\5 \to e\end{cases}$$ If we can do this, then the two sets have the same cardinality. What if the sets are infinite? Consider the natural numbers below: $$\{0,1,2,3,4,5\dots\}$$ The cardinality of that set is called $\aleph_0$ (Aleph null). This is called countable infinity, because every element can be counted one at a time, and each element is associated with a natural number. What about $\{0, 2, 4, 6, 8, 10 \dots\}$? What's the cardinality of that set? It turns out, it's still $\aleph_0$. Let's try to map them. $$\begin{cases}0 \to 0\\1 \to 2 \\ 2 \to 4 \\ 3 \to 6 \\4 \to 8\end{cases}$$ So, any set that can be mapped to the naturals is countable. Let's explore the uncountables.

Uncountable

Is there anything that cannot be counted? Surely there must be some set of numbers that is a magnitude greater than the natural numbers. There is! Let's look at all possible decimals from 0 to 1. We will represent them as binary numbers beginning with the digit after the decimal.

First, let's assume they are countable, so we write $$S_1 = \{1, 1, 1, 1, 1, \dots \}$$ $$S_2 = \{1, 0, 0, 1, 0, \dots \}$$ $$S_3 = \{1, 1, 0, 0, 1, \dots \}$$ $$S_4 = \{1, 0, 1, 1, 1, \dots \}$$ $$S_5 = \{1, 1, 1, 0, 0, \dots \}$$ $$\dots$$ Now, let's take a diagonal from these sets. $$S_1 = \{\textbf{1}, 1, 1, 1, 1, \dots \}$$ $$S_2 = \{1, \textbf{0}, 0, 1, 0, \dots \}$$ $$S_3 = \{1, 1, \textbf{0}, 0, 1, \dots \}$$ $$S_4 = \{1, 0, 1, \textbf{1}, 1, \dots \}$$ $$S_5 = \{1, 1, 1, 0, \textbf{0}, \dots \}$$ This set becomes $\{1, 0, 0, 1, 0, \dots\}$. This set itself isn't necessarily special. As you can see, it is possible that it is exactly the same as $S_2$. However, when we flip each bit in the sequence, we get a new sequence. How do we know? We can prove it.

Proof

First, let's re-establish what we're trying to prove. We're trying to show that this set X isn't in $S_1$ to $S_n$.
Second, let's re-establish what the set is. The set is the set such that nth element is not in $S_n$. Now, we do a proof by contradiction. We say this set X equals $S_i$ for some $i$. This means that the i'th element is the i'th element of $S_i$. However, we know this is false. X is the set $X_i s.t. X_i \neq S_{ii}$ Therefore, X will differ at some point with some binary number. So, X doesn't equal an arbitrary $S_i$, and X is not in the set of all binary numbers. This means that there is a binary number that was never counted. Therefore, the decimals from 0 to 1 are uncountable.

Cardinality of the Decimals

As we showed above, decimals could be represented by a set of 1s and 0s. 

As we showed above, decimals could be represented by a set of 1s and 0s. Each position has 2 options: 0 or 1, and there are $\aleph_0$. Therefore, the number of decimals is $$2 \times 2 \times \dots \left(\aleph_0 \text{ times}\right) = 2^{\aleph_0}$$

Continuum Hypothesis

In 1900, Hilbert published a list of 23 problems that he wanted to either prove or disprove. One of the more famous problems is the continuum hypothesis which states there is no set with a cardinality between that of the integers and the real numbers.