Mathwizurd.com is created by David Witten, a mathematics and computer science student at Vanderbilt University. For more information, see the "About" page.

# Size of Sets

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

MathJax TeX Test Page 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

MathJax TeX Test Page 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

MathJax TeX Test Page 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.

MathJax TeX Test Page 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.