80-110 The Nature of Mathematical Reasoning

Tuesday, August 8 2000

Quiz 9

Name: _______________________________

1. Who is the founder of modern set theory?

2. Georg Cantor (1845-1918)

3. What does it mean for a function f:A->B to be 1-1 (one-to-one, injective)?

4. No two different elements of the set A are mapped to the same element in B.

5. Explain the difference between "forall x exists y ( x < y )" and "exists x forall y ( x < y )", where the variables range over the natural numbers, and < stands for "is less than".

6. "forall x exists y ( x < y )" is true if for all numbers there exists a greater number. This can be true only with infinite sets and it certainly the case for the natural numbers.

"exists x forall y ( x < y )" is true if there is one number such that all numbers are greater than it. This sentence is false, since no number is greater than itself. If would be true if the relation were "greater or equal", because in this case there is a number such that all numbers are greater or equal, namely 1.

7. Name one non-classical logic.

8. Intuitionistic logic, Modal logic, Linear logic, Fuzzy logic, etc.

9. What does a recursive definition consist of?

10. (a) A base clause, which defines the basic elements of the set.
(b) One or more inductive clauses: they tell us how to generate complex elements from parts.
(c) And a final clause which states that all elements are either basic elements or generated by the inductive clause.