I will not get too heavy into the details here nor will I define everything precisely. I just want to give you a flavor of some really deep ideas.

Remember in our section on Cantor we made the following definitions for two sets A and B.

card(A) = card(B) if there is a 1-1 and onto map from A to B. card(A) ≤ card(B) is there is a 1-1 map from A to B (there may or may not be a 1-1*and onto*map from A to B) card(A) < card(B) if card(A) ≤ card(B) but card(A) is not equal to card(B) (as defined above).

Recall these two theorems of Cantor which we proved earlier.

card(N) = card(Q) card(N) < card(R)For two real numbers x and y we know that if x≤y and y≤x then x = y (no other possibilities). As it turns out the notion of cardinality also enjoys this same property.

**Theorem (Cantor-Schroder-Bernstein):** *If card(A) ≤ card(B) and card(B)≤card(A), then card(A) = card(B).*

If A and B are finite sets then this is just comparing ordinary numbers. It is when A and B are infinite sets (perhaps one of those wildly infinite sets like P(P(P(N))))) that this becomes amazing.

What other similar properties of real numbers does cardinality enjoy. For example, if x and y are two real numbers we either have x≤y or y≤x. Does this comparability theorem also work for cardinality?

**Question:** If A and B are any two sets, do we have either card(A)≤card(B) or card(B)≤card(A).

The fact that this is not obvious is a bit weird but if you think about it in terms of 1-1 and onto functions it becomes more apparent that there is something to show here. Just think about it. Given two sets A and B (this only becomes interesting if the sets are infinite), is it clear that either there is a 1-1 function from A to B or there is a 1-1 function from B to A?

As it turns out, there is no answer to this question – literally. To answer the above question (called the comparability theorem for sets) you need the Axiom of Choice.

**Axiom of Choice (informal version):** *Let C be an infinite collection of non-empty sets. Then we can choose an element from each member of the collection C.*

To be clear, choosing an element of each member of a collection of sets is not always a problem.

- If S is a collection of non-empty sets of natural numbers, the AOC is not needed since we just choose the smallest member of each set.
- If S is a collection of open intervals, the AOC is not needed since we just choose the midpoint of each open interval.
- If S is a collection of subsets of real numbers, we need the AOC.
- If S is a collection of pairs of shoes, the AOC is not needed since we just choose the left shoe from each pair.
- If S is a collection of pairs of socks, the AOC is needed.

Here is what is amazing thing about the AOC. You can not prove it (using the basic tools of logic which are known as the Zermello-Fraenkel set theory axioms) either true or false. You either have to accept it as true or not accept it at all. This is the work of Goedel and Cohen. What is interesting about the AOC of choice is that, to the uninitiated, it seems obvious – pick a member of each set and don’t make a federal case about it! However, there are many statements which are logically equivalent to the AOC which seem, on their surface, false.

For example, AOC is logically equivalent to the well-ordering principle which says that every set can be “ordered” in such a way that every non-empty set has a “smallest” element. For the natural numbers, with the usual ordering ≤, this is clearly true. For the real numbers, with the same ordering, this is not true. Can you think of a subset of the real numbers with no smallest element? If you believe in the AOC then there is some *other* ordering of the reals such that every non-empty subset of the reals has a smallest element (with respect to this strange ordering). This seems unbelievable – but nevertheless, if you accept the AOC you need to accept this.

As another example, the AOC is equivalent to the statement that for every infinite set A, we have card(A) = card({(a, a’): a, a’ belong to A}. For the natural numbers and the real numbers is this true – though it takes some work to do this. What about for A = P(R)? Again, if you believe the AOC, you must believe this.

The AOC of choice also implies (but not equivalent to) the Banach-Tarski paradox: a solid ball in 3-dimensional space can be split into a finite number of non-overlapping pieces, which can then be put back together in a different way to yield *two* identical copies of the original ball. This is clearly unbelievable! However, if you accept the AOC, you must accept this.

You should enjoy this AOC dilemma. It is one of the few opportunities in mathematics where you have a *choice* on what you want to believe. As it turns out, when we cover the work of Goedel, we will have many other opportunities.