next up previous
Next: About this document

Homework #4
Due Thursday, September 17

  1. The Well-Ordering Property of Natural Numbers states: ``Every nonempty subset S of the natural numbers has a smallest element.''
    1. Use the Axiom of Induction to prove the Well-Ordering Property. Suggestion: Let S be any subset of the natural numbers tex2html_wrap_inline17 . Assume that S has no smallest element. Let M be the complement of S. Prove that M equals tex2html_wrap_inline17 and hence that S must be empty.
    2. Use the Well-Ordering Property to prove the Axiom of Induction. Suggestion: Let M be any subset of tex2html_wrap_inline17 satisfying I and II of the Axiom of Induction. Let S be the complement of M. Prove that S is empty and hence that M must be tex2html_wrap_inline17 .
  2. Suppose there are m people, m-1 black hats and m red hats. Assume individuals tex2html_wrap_inline55 are given red hats and individuals tex2html_wrap_inline57 are given black hats. Each person in order ( tex2html_wrap_inline59 ) is asked in turn whether or not he/she can deduce the color of his/her hat. Prove by induction on n that person n can correctly deduce that his/her hat is red.
  3. Induction problems #8, 10 (you can use the result of 9), 18.
  4. Be sure you know how to do induction problems #2, 3, 4, 6, 9, 11, 12, but do not hand them in.

Carl Lee
Thu Sep 10 08:15:17 EDT 1998