Homework 11, due Wednesday, April 19 section 7.1, exercises 1,7,8 section 7.2, exercises 5,6,8,11,13 Homework 12, due Monday, April 24 1. A relation (A,R,A) is said to be an equivalence relation (on A) if it is i. reflexive (Ax E A.x R x) ii. symmetric (Axy E A. (x R y -> y R x)) iii. transitive (Axyz E A. (x R y & y R z) -> x R z) Prove that (V,~=~,V) is an equivalence relation (on the class V of all sets; recall that we are allowed to liberalize the definition (A,R,B) to allow A and B to be classes all of whose members are sets; technicalities about sets and classes do NOT appear in the proof!) There are three things to show (for any sets A,B,C): A ~=~ A (A ~=~ B) -> (B ~=~ A) and ((A ~=~ B) & (B ~=~ C)) -> A ~=~ C One needs to prove that converses of bijections are bijections and that compositions of bijections are bijections. I will supply part of the proof in class (and later in the notes): I will prove that the converse of a bijection is a bijection (you will need to indicate how this is used in the proof of the result here, but that is easy!) 2. We define addition and multiplication as follows: for any natural numbers m and n, we define m+n as |(mx{0}) U (nx{1})| and m*n as |m x n|. I will do the proofs of the following theorems in class: i. for any natural numbers m and n, there is a natural number p such that p ~=~ (mx{0}) U (nx{1}) (i.e., m+n is well-defined). ii. m+0 = m iii. m+n' = (m+n)' This verifies that the natural numbers satisfy the axioms for addition in our formal arithmetic. Your mission is to prove the following theorems: i. for any natural numbers m and n, there is a natural number p such that p ~=~ mxn (i.e. m*n is well-defined) ii. m*0 = 0 iii. m*n' = m*n + m which will verify that the natural numbers satisfy the axioms for multiplication in our formal arithmetic. You are strongly encouraged to come by my office and talk to me about your proofs in progress.