CS486 Spring 1997 Final Exam
9:00 AM, Thursday, May 15, 1997 Thurston 202
This is a closed book exam. Please show all work in the examination booklet.

{

1. We define a transitive set as a set such that if then . Consider this second definition: is transitive iff for each and , we have . This definition explains use of the word ``transitive'' (say why).
   Show that the two definitions are equivalent.
   
2. 1. We proved the following version of Cantor's theorem in class. Write the argument as a sequent calculus proof and site at least two axioms of as needed. Recall that are all the functions from to and that , where , . The quantifiers range over sets. As background for this problem, recall Hint, consider the set
      
   2. Carry out enough detail in this proof to expose propositional reasoning, quantifier reasoning, and set theory reasoning (axioms). State rules used in each of these categories.
      
3. Consider these two definitions of the ``exists a unique such that quantifier,'' .
   Def. 1.
   Def. 2.
   Show that the definitions are equivalent using 1st-order quantifier rules and equality rules. Structure the argument using the best methods from the course.

4. The following statements are true but for various reasons, some are propositional truths (tautologies), some are valid in first-order logic and some are true in number theory. This order is a progression from most general (weakest theory) to most specific (strongest theory).
   1. Give the most general theory in which the statement is true.
      1. 
      2. 
      3. using def. 1 of from problem (3).
      4. using def. 2 of from (3).
      5. 
   2. Is the answer the same if magic is not allowed as an axiom?
      
5. Recall that Real Analysis (RA) is a theory whose axioms define an ordered field satisfying the completeness axiom.
   

   

   Recall that we also added the predicate meaning is a natural number with the axioms:

   1. Prove the Induction Axiom for from Completeness.
      
   2. Why is the Induction Axiom for true in ZF?
      
6. Define
   if then else fi
   Recall that is the ``consing'' of number onto list , sometimes also written .

   Prove in , using . Give examples of propositional, 1st-order, arithmetic and list reasoning steps.
   

7. State Gödel's theorem for a theory for which it holds. Why is it an interesting theorem? How does it relate to the unsolvability of the Halting Problem? Does the theorem say that there is a sentence whose truth is totally unknowable?

• About this document ...