Homework No. 12

1. 1-1 Functions. (2 points)
Take a set A={alligator, bear, chimpanzee} and a set B={apple, banana, cherry}. Write down two functions from A to B, one of which is 1-1 and one which is not.

2. Cardinality. (4 points)
Prove: The cardinality of the even numbers is the same as the cardinality of the natural numbers.

3. The Non-Denumerability of the Continuum. (4 points)
Read Handouts #23 and #24.

• Explain the proof of the theorem: The interval of all real numbers between 0 and 1 is not denumerable, on pages 259-261, so that your fellow students who have not read the handout can understand it.
• State in one or two sentences the key idea behind this proof.
• State in one or two sentences what the importance of this proof is.

(Optional). Set theory.
If you are interested to know more about Russell's Paradox and modern set theory, read FOL, pages 216-224 (Sections 8.5-8.8). Attempt the following problem:

1. Page 220, Problem 26. (5 extra points)