# Size of Sets

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

# Uncountable

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

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.

# 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.