# 3.6.4: A final note on infinities

We have seen that |R| is strictly larger than |N|. We end this section with what might look like a simple question: Is there a subset of R that is neither in one-to-one correspondence with N nor with R? That is, is the cardinality of R the next largest cardinality after the cardinality of N, or are there other cardinalities intermediate between them? This problem was unsolved for quite a while, and the solution, when it was found, proved to be completely unexpected. It was shown that both ‘yes’ and ‘no’ are consistent answers to this question! That is, the logical structure built on the system of axioms that had been accepted as the basis of set theory was not extensive enough to answer the question. The question is ‘undecidable’ in that system. We will come back to ‘undecidability’ in Chapter 5.

It is possible to extend the system of axioms underlying set theory in various ways. In some extensions, the answer is yes. In others, the answer is no. You might object, “Yes, but which answer is true for the real real numbers?” Unfortunately, it’s not even clear whether this question makes sense, since in the world of mathematics, the real numbers are just part of a structure built from a system of axioms. And it’s not at all clear whether the ‘real numbers’ exist in some sense in the real world. If all this sounds like it’s a bit of a philosophical muddle, it is. That’s the state of things today at the foundation of mathematics, and it has implications for the foundations of computer science, as we’ll see in the next chapter.

Exercises

1. Suppose that A, B, and C are finite sets which are pairwise disjoint. (That is, A B = A C =B C = ∅.) Express the cardinality of each of the following sets in terms of |A|, |B|, and |C|. Which of your answers depend on the fact that the sets are pairwise disjoint?

a) P(AB) b) $$A \times\left(B^{C}\right)$$ c)P(A)×P(C)

d) $$A^{B \times C}$$ e) $$(A \times B)^{C}$$ f) $$\mathcal{P}\left(A^{B}\right)$$

g) $$(A \cup B)^{C}$$ h) (A B) × A i) $$A \times A \times B \times B$$

1. Suppose that A and B are finite sets which are not necessarily disjoint. What are all the possible values for |A B| ?
2. Let’s say that an ‘identifier’ consists of one or two characters. The fist character is one of the twenty-six letters (A, B, ..., C). The second character, if there is one, is either a letter or one of the ten digits (0, 1, ..., 9). How many different identifiers are there? Explain your answer in terms of unions and cross products.
3. Suppose that there are five books that you might bring along to read on your vacation. In how many different ways can you decide which books to bring, assuming that you want to bring at least one? Why?
4. Show that the cardinality of a finite set is well-defined. That is, show that if f is a bijective function from a set $$A$$ to $$N_{n},$$ and if $$g$$ is a bijective function from $$A$$ to $$N_{m},$$ then $$n=m$$.
5. Finish the proof of Theorem 4.7 by proving the following statement: Let A be a non-empty set, and let x A. Let B = A ∖ {x}. Let X = {C A | x C}. Define f : P(B) → X by the

formula f(C)=C∪{x}. Show that f is a bijective function.

6. Use induction on the cardinality of $$B$$ to show that for any finite sets $$A$$ and $$B,\left|A^{B}\right|=|A|^{B |}$$ (Hint: For the case where B B, and divide AB into classes according to the value of f (x).)
7. Let $$A$$ and $$B$$ be finite sets with $$|A|=n$$ and $$|B|=m$$ . List the elements of $$B$$ as $$B=\left\{b_{0}, b_{1}, \ldots, b_{m-1}\right\}$$ Define the function $$\mathcal{F} : A^{B} \rightarrow A \times A \times \cdots \times A,$$ where $$A$$ occurs $$m$$ times in the cross product, by $$\mathcal{F}(f)=\left(f\left(b_{0}\right), f\left(b_{1}\right), \ldots, f\left(b_{m-1}\right)\right) .$$ Show that $$\mathcal{F}$$ is a one-to-one correspondence.
8. Show that Z, the set of integers, is countable by finding a one-to-one correspondence between

N and Z.

9. Show that the set N × N is countable.
10. Complete the proof of Theorem 2.9 as follows:

a) Suppose that A and B are countably infinite sets. Show that A B is countably infinite.

b) Suppose that A and B are countable sets. Show that A B is countable.

12. Prove that each of the following statements is true. In each case, use a proof by contradiction.

a) Let X be a countably infinite set, and let N be a finite subset of X. Then X N is count-

ably infinite.
b)Let A be an infinite set, and let X be a subset of A. Then at least one of the sets X and A X is infinite.
c) Every subset of a finite set is finite.

13.Let A and B be sets and let ⊥ be an entity that is not a member of B. Show that there is a one-to-one correspondence between the set of functions from A to B ∪ {⊥} and the set of partial functions from A to B. (Partial functions were defined in Section 4.5. The symbol ‘⊥’ is sometimes used in theoretical computer science to represent the value ‘undefined.’)