Homework No. 3

1.  Write out the following two proofs, which were presented in class, as detailed and accurate as you can. State all your assumptions at the beginning and the conclusion at the end.  Justify every step you make. Also state the definitions that you are using. If you use variables, make sure to state what type they have, e.g., natural numbers, rational numbers.
 

1. The square root of 2 is irrational.

 
2. There are infinitely many prime numbers.

You may use the following lemmas without proving them:

• Lemma 1: For every natural number a, a² is even if and only if a is even.
• Lemma 2: For every rational number x, there are natural numbers a and b not both even, such that x=a/b.
• Lemma 3: If a set of numbers is finite, then it has a greatest element.
• Lemma 4: Every natural number is either prime, or has a prime as its divisor.

1. in base 60, and
2. in base 2.