0.  Someone asked if 1 x n = n for any natural number. We have not formally defined multiplication. So let’s do it now:

Definition of multiplication of natural numbers is given inductively (in the form of a double induction, but here we focus only on a portion of this definition so that we get a sense of what the process looks like:

-  Base: 1 x 1 = 1

-  Inductions step:  1 x S(k) = S(1 x k).

Prove by using PMI that for all natural numbers n, 1 x n = n.

Note:  For each n, multiplication by n is defined as follows: n x 1 = n, and n x S(m) = n x m + n. And this process will be long and is not the focus of our course.

1.   More on ’basics’: suing equations and solutions to replace the operation subtraction.

Note:  First read the lecture slides to see we made a convention: for m < n, the unique k that satisfies m + k = n is denoted by n - m.  But we still refrain from allowing the operation ‘subtraction’ due to fact that this operation can lead to negative numbers, which are not natural numbers.

a) For natural numbers m < n prove if there exists a natural number k such that m + k = n, this k must be unique. (This can be read as follows: the equation m + x = n, if it has a solution, it must be unique.)

b) Prove, using Well Ordering Principle, that in part (a) there exists k e N such that m + k = n. (Carefully define a set S whose least element is such k and make sure to prove S  0.)

c) Next we like to extend the condition m < n to m < n.  That is, we like the equation n + x = n to have a solution.  Prove such a hypothetical solution, called z, cannot be a natural number.

d) Let’s assume S(z) = 1 (that is, 1 is the successor to this new “number").  This means z < 1.  Prove that this assumption fits the algebraic properties of the ordering relation: prove for any natural numbers n and m, z < m implies n + z < n + m.

Adding properties: Suppose we wish to extend all the properties of the natural numbers to include this new number z .  First we extend the equations m + x = m to include all m e N u {z}. Show that z + z = z . Also we consider the distributivity of the multiplication over the addition to hold for z as well.

e) Prove z + z = z, and use it to prove for any natural number n, z x n = z .

2.   Greek Constructions.

for this question one needs to use paper, a ruler (without considering and using the marks on it,) and a pair of compass. Obviously this question must be done manually and without the help of drawing software.

a)  Given a line segment AB present detailed steps of the construction of a line perpendicular to the line segment AB at the point B . Call this construction GC 1, and quote it as one step in the next two constructions to save space and time in your construction.

b)  Given below are two line segments, AB of length 1 and CD of length a (real) number r . Please read the details of Theorem 12.2.15, which is a rough sketch of the construction of ^r . Try to present all the steps of this sketchy instructions precisely, step by step and with proper documentation, as was done in the lecture. You don’t need to prove the constructed number is actually ^r as the proof in the textbook is complete.

A                                                   B,        C                                          D

Note:  Please keep practicing this question of a scrap sheet of paper, but eventually you will be presenting it on the presentation version of the PS, which has enough space for the construction.

c)  Carefully read 12.3.13, and use the sketch given there to construct an angle θ whose cos is the number r given in part (b). Use the unit 1 given in part (b), and present all the details of your construction line by line, numbered and documented.

d)   Use the line segment AB in part (b) to construct a regular hexagon (6 sided polygon with equal sides).  Make sure to prove why your construction is a regular hexagon.

e)  Start with the line segment AB in part (b) and on the extension of this line segment, construct a line segment of length ^5 - 1.

3.  This question is relevant to infinite hotel puzzle. Indeed this is the subject of chapter 10. So you can read 10.1 for more information. In fact you need to read 10.1 to see how we show a function is a bijection (so read definitions

10.1.4 - 10.1.8) but you may as well read all of the section, and for more hint on the following question read

10.2.4 and 10.2.5.

a) Design a bijection between the two sets

S = [-1, 1] n {2},    T = [0, 5] n [7, 8]

Prove your function is a bijection.

b) Apply your knowledge of Calculus to prove the sets are of same size:  S = (0, +o),    T = (0, 1)

W = (-1, 1)   U = (-o, +o)

4.   Mathematical Induction and Well Ordering Principle.

Note that we don’t allow division of natural numbers (because natural numbers, and similarly integers don’t satisfy the field properties). But there is a reasonable substitute for division which is possible among the integers and natural numbers:  the Quotient-Remainder formula.(A collection of numbers that satisfied the Quotient- Remainder formula is a rich algebraic structure known as Euclidean Domain.)  With the Quotient remainder formula one  perform very complicated and deep Algebra with integers and  natural  numbers.   Indeed all of chapters 3, 5 are based on this property. The statement of Q-R for the natural numbers is

AnAd 3!q 3!r such that 0 < r < d and   n = dq + r.

(Note, the notation 3! means “there is a unique".)