Consider the following, famously described situation:
There is a group of barbers who shave faces of only those men who do not shave themselves. Within this group, suppose there is a barber who does not shave himself - call him Bertrand. By definition, since Bertrand is within the group previously described, he must shave himself; but if Bertrand shaved himself, he wouldn't be a part of this group of barbers. Could this be possible (Baldwin)?
Consider the same situation, now just described utilizing sets and set builder notation:
Let B = {S:S ∉ S}
i: Suppose B∈B. But for any set S∈B, S∉S ⇒ B∉B. Thus, B∈B ⇒ B∉B.
ii: So suppose B∉B. Since for any set S, S∉S ⇒ S∈B, then given B∉B ⇒ B∈B.
The way this double implication is formed implies the following to be true: B∈B iff B∉B, which makes no sense at all - yet arguments i and ii are valid given the defined set B.
After proposing the puzzle, Russell determined the causation for the paradox was that a description of sets of numbers was being confused with a description of sets of sets of numbers. The reason this confusion was happening was because sets were being poorly defined as sets of "everything" (Kiersz). As an attempt to stop the paradox from happening, and overall better set theory, Russell introduced the following hierarchy: numbers, sets of numbers, sets of sets of numbers, etc. Additionally, Russell brought forth the realization that sets are defined to broadly, which led to the convention of set theory axioms being introduced and decided upon. Ultimately, this axiomatic set theory is the result of this paradox being introduced and has led us to the careful construction of definitions of sets that we use today.
Galileo's Paradox
Galileo is one of the leading mathematicians in the works of infinity, and he is so from introducing the following paradox relating to the mapping of infinite sets.
In his work, Galileo considered the following sets:
A = {1, 2, 3, 4, 5, ...} and B = {1, 4, 9, 16, 25, ...}
In other words, he worked with the set of natural numbers, and the set of the squared values of the natural numbers. Commonly, the way a mapping was formed between these two sets was in a way such that each value in A mapped to its equivalent value in B. For example, the elements 1, 4, and 9 in A mapped to the elements 1, 4, and 9 in B respectively. Thus, one can see that with this mapping, A has more elements than B since there exists elements in A that do not have a corresponding value in B, but every value in B is mapped to by a value in A.
Contrastingly, Galileo considered the following mapping between A and B:
A...B
1 ↔ 1
2 ↔ 4
3 ↔ 9
4 ↔ 16
Thus, he mapped each natural number in A to its corresponding squared value in set B, which created a one-to-one mapping between the sets. This implied that the sets contain the same number of elements, which is paradoxical because the previous mapping showed that A obviously has more elements in it; resulting in the idea that there are different sizes of infinity.
Galileo applied this paradox to show that two line segments of different length contain the same number of points; a further explanation of this relation to line segments can be seen here. Cantor, whom you will read about later, applied this idea of different sized infinite sets to prove that there are more elements in the set of all real numbers than there are in the set of all natural numbers.
The Infinite Hotel Paradox
To further build on paradoxes of infinity, as mentioned previously through Galileo's Paradox, watch the following video by Jeff Dekofsky describing a diligent night manager with unremarkable problem solving skills and his infinite hotel.
