80-110: The Nature of Mathematical Reasoning
Spring 1998
Final Exam: Sample Questions
Consider all the questions on the previous two tests and the sample questions on the previous two tests as candidates for final exam questions. Below are sample questions from the material covered since the last test.
1) Aristotles theory of syllogisms was lacking in expressive power. So is sentential logic. Explain how sentential logic is expressively weak, and give a clear example of two mathematical notions that cannot be expressed reasonably in sentential logic.
2) Suppose the domain of discourse is D = {2,4}, and you are given the following claims to evaluate, where the predicates used have their usual meaning:
$
x(2£x)"
x(2£x)Explain how you would evaluate the truth of these sentences, and whether they are true or false in D. Give a domain in which the first is true but the second false.
3) How are these two claims different?:
"
x$y(x < y)$
x"y(x < y)
4) Take a set A = {1,2,3} and a set B = {Katie, Robin, Emily}. Now draw two functions from A to B, one of which is 1-1 and one which is not.
5) Write out, explain, and justify Cantor’s definition of when |A|
£ |B|.6) What does it mean to say that a set is dense? Can a finite set be dense? Are all infinite sets dense?
7) Suppose you and a friend were proving that |Q|
£ |N| by showing that there is a function G1-1: Q ® N. Suppose you were trying to prove that the function: g(k,n) = 2k(2n+1) - 1 was 1-1, and you were this far in the proof:
Describe what you might do next.
8) What is the motivation for building a theory of infinite sets with simple axioms and definitions. How has it paid off?