next up previous
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
your proofs in progress.



Randall Holmes
2000-05-05