MATtours of discrete mathematics

Paradoxes

Some logical paradoxes about set theory led to refinements in the early years of the twentieth century. One of the most famous paradoxes is called Russell's paradox, after its inventor, the philosopher Bertrand Russell. There are some special sets that are actually elements of themselves, such as the set of all sets and the set of all ideas. Most garden-variety sets, though, are not elements of themselves. But what about the set of all of those garden-variety sets? Is that set special or not? If it is special, then it's an element of itself, so it's one of the garden-variety sets that are those elements. But if the set of all garden-variety sets is itself a garden-variety set, then it's an element of itself, so it's special.

Russell's paradox led to several refinements of set theory, including one that excluded sets from being elements of themselves. In our definitions of intersection and union, we referred to collections of sets; by this refinement, those collections are not sets themselves.

Set theory also has been embroiled in paradoxes that aren't logically contradictory but can boggle the mind nevertheless. It makes sense, for example, to say that two sets are the same size if their elements can be paired up exactly in some list. So the sets {a, b, c} and {1, 2, 3} are the same size since you can pair up their elements:

a 1
b 2
c 3

By this reasoning, the set of positive integers is the same size as the set of positive even integers, because you can pair them up like this:

1 2
2 4
3 6
4 8
5 10
6 12
7 14
etc.

That might make sense, since each set has infinitely many elements; after all, infinity equals infinity. In fact, you can even find a way to pair up all integers and all rational numbers (fractions).

But how can you pair up all positive integers and real numbers between 0 and 1—that is, all decimals, including infinite and non-repeating decimals? Imagine such a list. It might begin like this:

1 0.549354935493. . . .
2 0.112111211112. . . .
3 0.949583648593. . . .
4 0.237584930587 . . . .
5 0.444044404440. . . .
6 0.345678938546. . . .

But there are lots of real numbers between 0 and 1 that won't appear on this list. For example, any number beginning 0.121111 certainly doesn't appear among the first six terms. It isn't the number corresponding to 1, because it doesn't have a 5 right after the decimal point. And it isn't the number corresponding to 2, since it doesn't have a 1 in the second place after the decimal point. And it isn't the number corresponding to 3, since it's third digit after the decimal point isn't 9. And so on. In fact, you can continue to append digits to 0.121111 in a way that the nth digit differs from the nth digit after the decimal point in the number listed beside integer n. Then you can be sure that the resulting number won't appear anywhere on the list.

This reasoning holds for any list you might make. So there's no way to pair up all positive integers and all real numbers between 0 and 1. That is, the infinite set containing all real numbers between 0 and 1 is "bigger than" the infinite set containing all positive integers. Informally, some infinities are bigger than others.

So it makes sense to talk about the size, or cardinality, of infinite sets as well as finite sets. Two sets have the same cardinality if there's a bijection between them. So some sets have the same cardinality as the set of integers, and other sets have the same cardinality as the set of real numbers. The former, along with finite sets, are called countable, or denumerable sets. All other sets are said to be uncountable or non-denumerable.