##
80-110 The Nature of Mathematical Reasoning

**Spring 2001**
*Dirk Schlimm*

# Homework No. 12

Thursday, April 19, 2001

Due Tuesday, April 24, 2001

**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:

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