80-110 The Nature of Mathematical Reasoning
Homework No. 3
Friday, July 7, 2000
Due Monday, July 10, 2000
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.
The square root of 2 is irrational.
There are infinitely many prime numbers.
You may use the following lemmas without proving them:
2. Determine the representation of 1978
Lemma 1: For every natural number a, a2 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.
- in base 60, and
- in base 2.