An example of an uncountable set
Let B be the set of all infinite sequences of bits (0s and 1s).
Theorem: B is uncountable.
Proof. Assume, for a contradiction, that B is countable, i.e. its elements
can be listed: b1, b2, b3, b4, … Let nbi denote the nth bit of bi.
b1 = 1b1 2b1 3b1 4b1 5b1 6b1 7b1 8b1 . . .
b2 = 1b2 2b2 3b2 4b2 5b2 6b2 7b2 8b2 . . .
b3 = 1b3 2b3 3b3 4b3 5b3 6b3 7b3 8b3 . . .
b4 = 1b3 2b3 3b3 4b3 5b3 6b3 7b3 8b3 . . .
Let c be the sequence of bits such that its 1st bit is 1-1b1, its second bit
is 1- 2b2, …, its nth bit is 1- nbn, …
Notice that then c is different from each bi. Hence c is not in the above
list, so not all the elements of B are listed. - Contradiction.