# 4.6.D 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 AB, and are finite sets which are pairwise disjoint. (That is, ∩ ∩ =∩ = ∅.) 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) (∪ B) × A        i) $$A \times A \times B \times B$$

1. Suppose that and are finite sets which are not necessarily disjoint. What are all the possible values for |∪ 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 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 be a non-empty set, and let ∈ A. Let ∖ {x}. Let = {⊆ ∈ C}. Define : P(B) → by the

formula f(C)=C∪{x}. Show that 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 Ainto classes according to the value of (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 and are countably infinite sets. Show that ∪ is countably infinite.

b) Suppose that and are countable sets. Show that ∪ is countable.

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

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

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

13.Let and 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 to ∪ {⊥} and the set of partial functions from to B. (Partial functions were defined in Section 4.5. The symbol ‘⊥’ is sometimes used in theoretical computer science to represent the value ‘undefined.’)