Next: Lecture Notes Up: Homework Assignments Previous: Homework 10

## Homework 11

```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