80-110 The Nature of Mathematical Reasoning

Summer 2000

Dirk Schlimm

Homework No. 15

Monday, August 7, 2000
Due Thursday, August 10, 2000

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 #22 and #23.

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.

4. Preparation for final exam. (5 points)
Write a paragraph or two answering both of the following questions:

What is the difference between mathematical reasoning and other forms of reasoning, e.g., scientific, historical?
What is a proof?

(You probably have noticed that these are exactly the same questions as in Homework #1. By now, considering the amount of material you have learned in this course, your answers should be a bit different than what you've written 5 weeks ago. Answering this question gives you the opportunity to review the material and reflect about what we have discussed in this course.)

5. (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)