Exercises from Section 1.2.1

Tord M. Johnson

March 9, 2024

1. [05] Explain how to modify the idea of a proof by mathematical induction, in case we want to prove some statement P(n) for all nonnegative integers—that is, for n = 0,1,2, instead of for n = 1,2,3,.

We may modify the idea of a proof by mathematical induction in the case we want to prove some statement for all nonnegative integers as follows:

Let P(n) be some statement about the integer n. In order to prove that P(n) is true for all nonnegative integers n:

a.
Give a proof that P(0) is true.
b.
Give a proof that “if all of P(0),P(1),,P(n) are true, then P(n + 1) is also true”; this proof should be valid for any nonnegative integer n.

2. [15] There must be something wrong with the following proof. What is it? “Theorem. Let a be any positive number. For all positive integers n we have an1 = 1. Proof. If n = 1, an1 = a11 = a0 = 1. And by induction, assuming that the theorem is true for 1,2,,n, we have

a(n+1)1 = an = an1 × an1 a(n1)1 = 1 × 1 1 = 1;

so the theorem is true for n + 1 as well.”

The proof, in particular during the induction step, makes an assumption about a(n1)1, instead of an1, requiring the case for both n = 1 and n = 2 to be proved, which has not been done. Otherwise, if a(n1)1 = a(11)1 = a1 = 1, the theorem would indeed be true.

3. [18] The following proof by induction seems correct, but for some reason the equation for n = 6 gives 1 2 + 1 6 + 1 12 + 1 20 + 1 30 = 5 6 on the left-hand side, and 3 2 1 6 = 4 3 on the right-hand side. Can you find a mistake? “Theorem.

1 1 × 2 + 1 2 × 3 + + 1 (n 1) × n = 3 2 1 n.

Proof. We use induction on n. For n = 1, clearly 32 1n = 1(1 × 2); and, assuming that the theorem is true for n,

1 1 × 2 + + 1 (n 1) × n + 1 n × (n + 1) = 3 2 1 n + 1 n(n + 1) = 3 2 1 n + ( 1 n 1 n + 1) = 3 2 1 n + 1.”

The proof, in particular during the base step for n = 1, fails to prove that 3 2 1 1 = 1 (11)×1 or that 3 2 1 1 = 0, the former which is in fact undefined.

4. [20] Prove that, in addition to Eq. (3), Fibonacci numbers satisfy Fn ϕn2.

Proposition. For ϕ = 1+5 2 and all positive integers n, Fibonacci numbers satisify Fn ϕn2.

Proof. If n = 1, Fn = 1 2 3 = 2 1+2 > 2 1+5 = 1 ϕ = ϕ1 = ϕ12 = ϕn2.

Then, assuming Fn ϕn2 for all positive integers n, we must show that Fn+1 ϕ(n+1)2 = ϕn1. If n = 2, Fn = 1 ϕ0 = ϕ22 = ϕn2. Otherwise, if n > 2:

Fn+1 = Fn + Fn1 ϕn2 + ϕn3 = ϕn+1 + ϕn ϕ3 = ϕn1(ϕ + 1 ϕ2 ) = ϕn1( 1 ϕ + 1 ϕ2) > ϕn1(2) since 1ϕ < 1 > ϕn1

which we needed to show. □

5. [21] A prime number is an integer > 1 that has no exact divisors other than 1 and itself. Using this definition and mathematical induction, prove that every integer > 1 may be written as a product of one or more prime numbers. (A prime number is considered to be the “product” of a single prime, namely itself.)

Proposition. Every integer n > 1 may be written as a product of one or more prime numbers.

Proof. If n = 2, then n is prime.

Then, assuming every integer n > 1 may be written as a product of one or more prime numbers, we must show that n + 1 may be as well. In the case that n + 1 is prime, this is trivially true. Otherwise, in the case that n + 1 is composite, there must exist two factors p and q such that n + 1 = pq where 1 < p,q < n + 1; but by hypothesis, p and q are the products of one or more prime numbers, and so their product is such, as we needed to show. □

6. [20] Prove that if Eqs. (6) hold just before step E4, they hold afterwards also.

Proposition. In Algorithm E, given am + bn = d am + bn = c = qd + r prior to step E4, afterwards we have am + bn = d am + bn = c.

Proof.

Assume am + bn = d am + bn = c = qd + r.

But:

am + bn = d am + bn = c = qd + riffam + bn = d am + bn = qd + r iff am + bn = d am + bn = q(am + bn) + r iff am + bn = d am + bn = qam + qbn + r iff am + bn = d am + bn qam qbn = r iff am + bn = d (a qa)m + (b qb)n = r iff (a qa)m + (b qb)n = r am + bn = d

Then, given (a qa)m + (b qb)n = r am + bn = d, in executing step E4:

c d (a qa)m + (b qb)n = r am + bn = c d r (a qa)m + (b qb)n = d am + bn = c t a (t qa)m + (b qb)n = d am + bn = c a a (t qa)m + (b qb)n = d am + bn = c a t qa am + (b qb)n = d am + bn = c t b am + (t qb)n = d am + bn = c b b am + (t qb)n = d am + bn = c b t qb am + bn = d am + bn = c

as we needed to show. □

7. [23] Formulate and prove by induction a rule for the sums 12, 22 12, 32 22 + 12, 42 32 + 22 12, 52 42 + 32 22 + 12, etc.

Proposition. Let Sn = 12 if n = 1 or n2 + (1)Sn1 if n > 1 otherwise, for all positive integers n. That is, let Sn be a sum in the sequence 12, 22 12, 32 22 + 12, 42 32 + 22 12, 52 42 + 32 22 + 12, etc. For all positive integers n, Sn = 1kn(1)nkk2.

Proof. For n = 1, we have Sn = 12 = (1)012 = 1k1(1)1kk2 = 1kn(1)nkk2.

Then, assuming for all positive integers n 1 if Sn = 1kn(1)nkk2, we must prove that Sn+1 = 1kn+1(1)(n+1)kk2.

But:

Sn+1 = (n + 1)2 + (1)S n = (n + 1)2 + (1) 1kn(1)nkk2 = (n + 1)2 + 1kn(1)(n+1)kk2 = (1)(n+1)(n+1)(n + 1)2 + 1kn(1)(n+1)kk2 = 1kn+1(1)(n+1)kk2

as was to be shown.

8. [25] (a) Prove the following theorem of Nicomachus (A.D. c. 100) by induction: 13 = 1, 23 = 3 + 5, 33 = 7 + 9 + 11, 43 = 13 + 15 + 17 + 19, etc. (b) Use this result to prove the remarkable formula 13 + 23 + + n3 = (1 + 2 + + n)2.

[Note: An attractive geometric interpretation of this forumula, suggested by Warren Lushbaugh, is shown in Fig. 5; see Math. Gagzette 49 (1965), 200. The idea is related to Nicomachus’s theorem and Fig. 3. Other “look-see” proofs can be found in books by Martin Gardner, Knotted Doughnuts (New York: Freeman, 1986), Chapter 16; J. H. Conway and R. K. Guy, The Book of Numbers (New York: Copernicus, 1996), Chapter 2.]

a.
We shall prove a theorem of Nicomachus.

Proposition. For all positive integers n, n3 = 1knn2 n + 2k 1.

Proof. If n = 1, n3 = 13 = 1 = 12 1 + 2 1 = 1knn2 n + 2k 1.

Then, assuming n3 = 1knn2 n + 2k 1 for all positive integers n, we must show that (n + 1)3 = 1kn+1(n + 1)2 (n + 1) + 2k 1. But:

(n + 1)3 = n3 + 3n2 + 3n + 1 = 3n2 + 3n + 1 + n3 = 3n2 + 3n + 1 + 1knn2 n + 2k 1 = 3n2 + 3n + 1 + n(n2 n) + 1kn2k 1 = 3n2 + 3n + 1 + n3 n2 + 1kn2k 1 = 2n2 + 3n + 1 + n3 + 1kn2k 1 = n3 + 2n2 + 3n + 1 + 1kn2k 1 = n3 + 2n2 + n + 2n + 1 + 1kn2k 1 = (n + 1)(n2 + n) + 2n + 1 + 1kn2k 1 = (n + 1)(n2 + 2n + 1 n 1) + 2n + 1 + 1kn2k 1 = (n + 1)((n + 1)2 (n + 1)) + 2(n + 1) 1 + 1kn2k 1 = (n + 1)((n + 1)2 (n + 1)) + 1kn+12k 1 = 1kn+1(n + 1)2 (n + 1) + 2k 1

as we needed to show. □

b.
We shall use the proof above to prove another formula.

Proposition. For all positive integers n, 1knk3 = ( 1knk)2.

Proof. We have that for all positive integers n, n3 = 1knn2 n + 2k 1.

First, we will show that 1jn 1kjj2 j + 2k 1 = 1kn2+n 2 2k 1.

In the case that n = 1:

1jn 1kjj2 j + 2k 1 = 1j1 1kjj2 j + 2k 1 = 1k112 1 + 2k 1 = 1 = 1k12k 1 = 1k12+1 2 2k 1 = 1kn2+n 2 2k 1

Then, assuming that 1jn 1kjj2 j + 2k 1 = 1kn2+n 2 2k 1 for all positive integers n, we must first show that 1jn+1 1kjj2 j + 2k 1 = 1k(n+1)2+n+1 2 2k 1. But:

1jn+1 1kjj2 j + 2k 1 = ( 1jn 1kjj2 j + 2k 1) + 1kn+1(n + 1)2 (n + 1) + 2k 1 = ( 1kn2+n 2 2k 1) + 1kn+1(n + 1)2 (n + 1) + 2k 1 = ( 1kn2+n 2 2k 1) + 1k+1(n+1)2+(n+1) 2 n+1k = ( 1kn2+n 2 2k 1) + n2+n 2 +1k+1 2 (n+1)2+(n+1) 2 k = ( 1kn2+n 2 2k 1) + n2+n 2 +1k(n+1)2+(n+1) 2 2k 1 = ( 1k(n+1)2+(n+1) 2 2k 1)

as was to be shown.

Second, and finally, we note that:

1knk3 = 1jn 1kjj2 j + 2k 1 = 1kn2+n 2 2k 1 = (n2 + n 2 )2 the sum of n2+n 2  odd integers = (n(n + 1) 2 )2 = ( 1knk)2

as we needed to show. □

9. [20] Prove by induction that if 0 < a < 1, then (1 a)n 1 na.

Proposition. For all positive integers n, if 0 < a < 1, then (1 a)n 1 na.

Proof. If n = 1, then (1 a)n = (1 a)1 = 1 a = 1 (1)a = 1 na.

Then, assuming that (1 a)n 1 na for all positive integers n, we must show that (1 a)n+1 1 (n + 1)a. But:

(1 a)n+1 = (1 a)(1 a)n (1 a)(a na) = 1 na a + na2 1 na a = 1 (n + 1)a

as we needed to show. □

10. [M22] Prove by induction that if n 10, then 2n > n3.

Proposition. For all integers n 10, 2n > n3.

Proof. If n = 10, then 2n = 210 = 1024 > 1000 = 103 = n3.

Also note that if n 10, then (1 + 1 n)3 (1 + 1 10)3 < 2.

Then, assuming 2n > n3 for all integers n 10, we must show that 2n+1 > (n + 1)3. But:

2n+1 = (2)2n > (2)n3 > (1 + 1 n)3n3 = (n + 1)3

as we needed to show. □

11. [M30] Find and prove a simple formula for the sum

13 14 + 4 33 34 + 4 + 53 54 + 4 + (1)n(2n + 1)3 (2n + 1)4 + 4 .

When we enumerate the first five terms and cumulative sums of the sequence Sn = (1)n1(2n1)3 (2n1)4+4 :

nSn 1knSk




1 1/5 1/5
2 -27/85 -2/17
3 125/629 3/37
4 -343/2405 -4/65
5 729/6565 5/101

we conjecture that 1kn(1)k1(2k1)3 (2k1)4+4 = (1)n1n 4n2+1 .

Proposition. For all positive integers n, 1kn(1)k1(2k1)3 (2k1)4+4 = (1)n1n 4n2+1 .

Proof. If n = 1, 1kn(1)k1(2k1)3 (2k1)4+4 = (1)0(21)3 (21)4+4 = 1 5 = (1)0(1) 4(1)2+1 = (1)n1n 4n2+1 .

Then, assuming 1kn(1)k1(2k1)3 (2k1)4+4 = (1)n1n 4n2+1 for all positive integers n, we must show that 1kn+1(1)k1(2k1)3 (2k1)4+4 = (1)n(n+1) 4(n+1)2+1 . But:

1kn+1(1)k1(2k 1)3 (2k 1)4 + 4 = ( 1kn(1)k1(2k 1)3 (2k 1)4 + 4 ) + (1)n(2(n + 1) 1)3 (2(n + 1) 1)4 + 4 = (1)n1n 4n2 + 1 + (1)n(2(n + 1) 1)3 (2(n + 1) 1)4 + 4 = (1)n1n((2n + 1)4 + 4) + (1)n(2n + 1)3(4n2 + 1) (4n2 + 1)((2n + 1)4 + 4) = (1)n1n((2n + 1)4 + 4) + (1)n(2n + 1)3(4n2 + 1) (4(n + 1)2 + 1)(4n2 + 1)2 = (1)n n((2n + 1)4 + 4) + (1)n(2n + 1)3(4n2 + 1) (4(n + 1)2 + 1)(4n2 + 1)2 = (1)n(n((2n + 1)4 + 4) + (2n + 1)3(4n2 + 1)) (4(n + 1)2 + 1)(4n2 + 1)2 = (1)n(n + 1)(4n2 + 1)2 (4(n + 1)2 + 1)(4n2 + 1)2 = (1)n(n + 1) 4(n + 1)2 + 1

as we needed to show. □

12. [M25] Show how Algorithm E can be generalized as stated in the text so that it will accept input values of the form u + v2, where u and v are integers, and the computations can still be done in an elementary way (that is, without using the infinite decimal expansion of 2). Prove that the computation will not terminate, however, if m = 1 and n = 2.

Algorithm E can be generalized to accept input values of the form u + v2 for integers u and v, using repeated subtraction instead of division. The algorithm relies on the fact that u + v2 = u + v2u u = 0 v v = 0, our test for a zero remainder; and on the fact that (u u) + (v v)2 < 0(u u) + (v )2 < 0.

Algorithm F (Generalized Euclid’s algorithm). Given two numbers m = mr + mi2 and n = nr + ni2 with integers mr,mi,nr,ni, we compute their greatest common divisor d = dr + di2 with integers dr,di, and we also compute two integers a and b such that am + bn = d.

F1a.
[Initialize.] Set a b 1, a b 0, (cr,ci) (mr,mi), (dr,di) (nr,ni), y z 1.
F1b1.
[Initialize c = |m|.] Set v 0.
F1b2.
If (v + 1)2 2ci2, v v + 1, and go to step F1b2. Otherwise, if ci < 0, v (v + 1). (Afterwards, we have v = ci2.)
F1b3.
If cr + v < 0, y 1, (cr,ci) (cr,ci).
F1c1.
[Initialize d = |n|.] Set v 0.
F1c2.
If (v + 1)2 2di2, v v + 1, and go to step F1c2. Otherwise, if di < 0, v (v + 1). (Afterwards, we have v = di2.)
F1c3.
If dr + v < 0, z 1, (dr,di) (dr,di).
F2a.
[Divide.] Let q 0, (er,ei) (cr,ci).
F2b1.
Let (er,ei) (er dr,ei di) and v 0.
F2b2.
If (v + 1)2 2ei2, v v + 1 and go to step F2b2. Otherwise, if ei < 0, v (v + 1). (Afterwards, we have v = ei2.)
F2c.
If er + v 0, q q + 1 and go to step F2b1.
F2d.
Let (rr,ri) (cr qdr,ci qdi). (We have cr + ci2 = qd + rr + ri2 and 0 rr + ri2 < d.)
F3.
[Remainder zero?] If (rr,ri) = (0,0), let a ya, b zb and the algorithm terminates; we have in this case am + bn = d as desired.
F4.
[Recycle.] Set (cr,ci) (dr,di), (dr,di) (rr,ri), t a,a a,a t qa, t b,b b,b t qb, and go back to F2a.

Unfortunately, Algorithm F will not terminate given inputs m = 1,n = 2. If it did terminate, we would have rr + ri2 = 0 = cr + ci2 q(dr + di2) = (cr qdr) + (ci qdi2), or equivalently, 2 = qdrcr ciqdi ; that is, we would find 2 to be rational, which cannot be. We can be assured that ciqdi in this case, since 1q2 for any rational q. Hence, the algorithm will not terminate.

________________________________________________________________________________

Note: ... For further information, see “quadratic Euclidean domains” in number theory textbooks.

13. [M23] Extend Algorithm E by adding a new variable T and adding the operation “T T + 1” at the beginning of each step. (Thus, T is like a clock, counting the number of steps executed.) Assume that T is initially zero, so that assertion A1 in Fig. 4 becomes “m > 0, n > 0, T = 0.” The additional condition “T = 1” should similarly be appended to A2. Show how to append additional conditions to the assertions in such a way that any one of A1,A2,,A6 implies T 3n, and such that the inductive proof can still be carried out. (Hence the computation must terminate in at most 3n steps.)

Initially, we are given the following algorithm with various assertions.

Algorithm E (Extended Euclid’s algorithm). Given two positive integers m and n, we compute their greatest common divisor d, and we also compute two not-necessarily-positive integers a and b such that am + bn = d.

A1.
[Precondition.] m > 0, n > 0.
E1.
[Initialize.] Set a b 1, a b 0, c m, d n.
A2.
[E1 postcondition.] c = m > 0, d = n > 0, a = b = 0, a = b = 1.
A6.
[E4 postcondition.] am + bn = d, am + bn = c, d > 0, gcd (c,d) = gcd (m,n).
E2.
[Divide.] Let q and r be the quotient and remainder, respectively, of c divided by d. (We have c = qd + r and 0 r < d.)
A3.
[E2 postcondition.] am + bn = d, am + bn = c = qd + r, 0 r < d, gcd (c,d) = gcd (m,n).
E3.
[Remainder zero?] If r = 0, the algorithm terminates; we have in this case am + bn = d as desired.
A4.
[E3 postcondition, r = 0.] am + bn = d = gcd (m,n).
A5.
[E3 postcondition, r0.] am + bn = d, am + bn = c = qd + r, 0 < r < d, gcd (c,d) = gcd (m,n).
E4.
[Recycle.] Set c d, d r, t a, a a, a t qa, t b, b b, b t qb, and go back to E2.

We can augment this with a step variable T to show that T 3n.

Algorithm G (Extended Euclid’s algorithm with steps). Given two positive integers m and n, we compute their greatest common divisor d, and we also compute two not-necessarily-positive integers a and b such that am + bn = d, as well as steps T to show that T 3n.

G0.
[Initialze steps.] T 0.
B1.
[Precondition, G0 postcondition.] m > 0, n > 0, T = 0.
G1.
[Initialize.] Set a b 1, a b 0, c m, d n, T T + 1.
B2.
[G1 postcondition.] c = m > 0, d = n > 0, a = b = 0, a = b = 1, T = 1.
B6.
[G4 postcondition.] am + bn = d, am + bn = c, d > 0, gcd (c,d) = gcd (m,n), T 3(n d) + 1.
G2.
[Divide.] Let q and r be the quotient and remainder, respectively, of c divided by d. Also set T T + 1. (We have c = qd + r and 0 r < d.)
B3.
[G2 postcondition.] am + bn = d, am + bn = c = qd + r, 0 r < d, gcd (c,d) = gcd (m,n), T 3(n d) + 2.
G3.
[Remainder zero?] Set T T + 1. If r = 0, the algorithm terminates; we have in this case am + bn = d and T 3n as desired.
B4.
[G3 postcondition, r = 0.] am + bn = d = gcd (m,n), d > 0, T 3(n d) + 3.
B5.
[G3 postcondition, r0.] am + bn = d, am + bn = c = qd + r, 0 < r < d, gcd (c,d) = gcd (m,n), d > 0, T 3(n d) + 3.
G4.
[Recycle.] Set c d, d r, t a, a a, a t qa, t b, b b, b t qb, T T + 1, and go back to G2.

The new assertions may be derived as shown below, given n > 0.

Summary PreconditionStep Postcondition






{}G0 {B1} {}T 0 {T = 0}
{B1}G1 {B2} {T = 0}
{T + 1 = 1}T T + 1 {T = 1}
{B2}G2 {B3} {n = d T = 1}
{T 3(n d) + 1}
{T + 1 3(n d) + 2}T T + 1 {T 3(n d) + 2}
{B3}G3 {B4} {d > 0 T 3(n d) + 2}
{d > 0 T + 1 3(n d) + 3}T T + 1 {d > 0 T 3(n d) + 3}
{T 3n}
{B3}G3 {B5} {d > 0 T 3(n d) + 2}
{d > 0 T + 1 3(n d) + 3}T T + 1 {d > 0 T 3(n d) + 3}
{B5}G4 {B6} {d > 0 T 3(n d) + 3}
{T 3(n d)}
{T + 1 3(n d) + 1}T T + 1 {T 3(n d) + 1}
{B6}G2 {B3} {T 3(n d) + 1}
{T + 1 3(n d) + 2}T T + 1 {T 3(n d) + 2}

14. [50] (R. W. Floyd.) Prepare a computer program that accepts, as input, programs in some programming language together with optional assertions, and that attempts to fill in the remaining assertions necessary to make a proof that the computer program is valid. (For example, strive to get a program that is able to prove the validity of Algorithm E, given only assertions A1, A4, and A6. See the papers by R. W. Floyd and J. C. King in the IFIP Congress proceedings, 1971, for further discussion.)

n.a.

15. [HM28] (Generalized induction.) The text shows how to prove statements P(n) that depend on a single integer n, but it does not describe how to prove statements P(m,n) depending on two integers. In these circumstances a proof is often given by some sort of “double induction,” which frequently seems confusing. Actually, there is an important principle more general than simple induction that applies not only to this case but also to situations in which statements are to be proved about uncoutnable sets—for example, P(x) for all real x. This general principle is called well-ordering.

Let “ ” be a relation on a set S, satisifying the following properties:

i.
Given x, y, and z in S, if x y and y z, then x z.
ii.
Given x and y in S, exactly one of the following three possibilities is true: x y, x = y, or y x.
iii.
If A is any nonempty subset of S, there is an element x in A with x y (that is, x y or x = y) for all y in A.

This relation is said to be a well-ordering of S. For example, it is clear that the positive integers are well-ordered by the ordinary “less than” relation, <.

a.
Show that the set of all integers is not well-ordered by <.
b.
Define a well-ordering relation on the set of all integers.
c.
Is the set of all nonnegative real numbers well-ordered by <?
d.
(Lexicographic order.) Let S be well-ordered by , and for n > 0 let Tn be the set of all n-tuples (x1,x2,,xn) of elements xj in S. Define (x1,x2,,xn) (y1,y2,,yn) if there is some k, 1 k n, such that xj = yj for 1 j < k, but xk yk in S. Is a well-ordering of Tn?
e.
Continuing part (d), let T = n1Tn; define (x1,x2,,xm) (y1,y2,,yn) if xj = yj for 1 j < k and xk yk, for some k min (m,n), or if m < n and xj = yj for 1 j m. Is a well-ordering of T?
f.
Show that is a well-ordering of S if and only if it satisifies (i) and (ii) above and there is no infinite sequence x1,x2,x3, with xj+1 xj for all j 1.
g.
Let S be well-ordered by , and let P(x) be a statement about the element x of S. Show that if P(x) can be proved under the assumption that P(y) is true for all y x, then P(x) is true for all x in S.

[Notes: Part (g) is the generalization of simple induction that was promised; in the case S = positive integers, it is just the simple case of mathematical induction treated in the text. In that case we are asked to prove that P(1) is true if P(y) is true for all positive integers y < 1; this is the same as saying we should prove P(1), since P(y) certainly is (vacuously) true for all such y. Consequently, one finds that in many situations P(1) need not be proved using a special argument.

Part (d), in connection with part (g), gives us a powerful method of n-tuple induction for proving statements P(m1,,mn) about n positive integers m1,,mn.

Part (f) has further application to computer algorithms: If we can map each state x of a computation into an element f(x) belonging to a well-ordered set S, in such a way that every step of the computation takes a state x intoa state y with f(y) f(x), then the algorithm must terminate. This principle generalizes the argument about strictly decreasing values of n, by which we proved the termination of Algorithm 1.1E.]

Answers are enumerated below.

a.
We can show that the set of all integers is not well-ordered by < by considering the violation of condition (iii) with the nonempty (improper) subset , which has no least element.
b.
We may define a well-ordering relation on the set of all integers as
x y = { |x| = |y|if  x = y > 0 |x| < |y|otherwise (12)

To see that satisifes condition (i), assume x y and y z. We must show that x z. By hypothesis, x = y > 0 |x| < |y| and y = z > 0 |y| < |z|.

Case I. [ x = y > 0 and y = z > 0.] This case is impossible, as it requires both y > 0 and y < 0, and so need not be considered.

Case II. [ x = y > 0 and |y| < |z|.] In this case, since x = y > 0, we have |y| = y = x = |x|. But |y| = |x| < |z| and so x z as we needed to show in this case.

Case III. [|x| < |y| and y = z > 0.] In this case, since y = z > 0, we have |y| = y = z = |z|. But |x| < |y| = |z| and so x z as we needed to show in this case.

Case IV. [|x| < |y| and |y| < |z|.] In this case, clearly, as < is transitive, |x| < |z|, and so x z as we needed to show in this case.

To see that satisifies condition (ii) we must show that for arbitrary x and y, x y, x = y, or y x. If x = y, xy, |x| |y|, and |y| |x|; if x = y > 0, then |x| = |y| and x y; if y = x > 0, then |y| = |x| and y x; otherwise, either |x| < |y| or |y| < |x| in which case x y or y x, respectively.

To see that satisifies condition (iii), we must show that any nonempty subset of has a least element under . Let S be such a subset, so that S and let T = {t |(s S)(t s)}. We must show that S has a least element. In the case that 0 S, clearly 0 is such an element. Otherwise, in the case that 0S, T, and there must exist an element u T such that u + 1T but u + 1 S. Clearly, u + 1 is the least element under in S, as we needed to show.

c.
The set of all nonnegative real numbers is not well-ordered by <, as condition (iii) is violated with the nonempty subset of positive reals, which has no least nonnegative real number.
d.
Lexicographic order is a well-ordering of Tn for n > 0.

To see that satisfies condition (i), assume (x1,x2,,xn) (y1,y2,,yn) and (y1,y2,,yn) (z1,z2,,zn). We must show that (x1,x2,,xn) (z1,z2,,zn). For n = 1, we have (x1) (y1) and (y1) (z1). Since S is well-ordered by , is transitive, and so (x1) (z1). Then, assuming (x1,x2,,xk) (y1,y2,,yk) (y1,y2,,yk) (z1,z2,,zk)(x1,x2,,xk) (z1,z2,,zk) for some k 1, we must show that (x1,x2,,xk+1) (y1,y2,,yk+1) (y1,y2,,yk+1) (z1,z2,,zk+1)(x1,x2,,xk+1) (z1,z2,,zk+1). But since S is well-ordered by and therefore transitive, (xk+1) (yk+1) (yk+1) (zk+1)(xk+1) (zk+1); clearly then, with our induction hypothesis, (x1,x2,,xk+1) (z1,z2,,zk+1).

To see that satisifies condition (ii) we must show for arbitrary n that (x1,x2,,xn) (y1,y2,,yn), (x1,x2,,xn) = (y1,y2,,yn), or (y1,y2,,yn) (x1,x2,,xn). Clearly the condition is satisfied for n = 1 since S is well-ordered. Then, assuming (x1,x2,,xk) (y1,y2,,yk), (x1,x2,,xk) = (y1,y2,,yk), or (y1,y2,,yk) (x1,x2,,xk) for some k 1; we must show that (x1,x2,,xk+1) (y1,y2,,yk+1), (x1,x2,,xk+1) = (y1,y2,,yk+1), or (y1,y2,,yk+1) (x1,x2,,xk+1).

Case I. [(x1,x2,,xk) (y1,y2,,yk) and (xk+1) (yk+1).] Clearly (x1,x2,,xk+1) (y1,y2,,yk+1).

Case II. [(x1,x2,,xk) = (y1,y2,,yk) and (xk+1) (yk+1).] (x1,x2,,xk+1) (y1,y2,,yk+1) by definition.

Case III. [(y1,y2,,yk) (x1,x2,,xk) and (xk+1) (yk+1).] In this case, we have (y1,y2,,yk+1) (x1,x2,,xk+1).

Case IV. [(x1,x2,,xk) (y1,y2,,yk) and (xk+1) = (yk+1).] In this case, we have (x1,x2,,xk+1) (y1,y2,,yk+1).

Case V. [(x1,x2,,xk) = (y1,y2,,yk) and (xk+1) = (yk+1).] In this case, we have (x1,x2,,xk+1) = (y1,y2,,yk+1).

Case VI. [(y1,y2,,yk) (x1,x2,,xk) and (yk+1) = (xk+1).] In this case, we have (y1,y2,,yk+1) (x1,x2,,xk+1).

Case VII. [(x1,x2,,xk) (y1,y2,,yk) and (yk+1) (xk+1).] In this case, we have (x1,x2,,xk+1) (y1,y2,,yk+1).

Case VIII. [(x1,x2,,xk) = (y1,y2,,yk) and (yk+1) (xk+1).] In this case, we have (y1,y2,,yk+1) (x1,x2,,xk+1).

Case IX. [(y1,y2,,yk) (x1,x2,,xk) and (yk+1) (xk+1).] In this case, we have (y1,y2,,yk+1) (x1,x2,,xk+1).

To see that satisfies condition (iii) we must show that for arbitrary n, Tn has a least element under . For n = 1, clearly this is true as S is well-ordered under . Then, assuming Tk has a least element, we must show that so does Tk+1. But if both Tk and S have least elements, (t1,t2,,tk) and (s1) respectively, then clearly Tk+1 does too; namely, (t1,t2,,tk,s1).

e.
Continuing part (d), if we let T = n1Tn and define (x1,x2,,xm) (y1,y2,,yn) if xj = yj for 1 j < k and xk yk, for some k min (m,n), or if m < n and xj = yj for 1 j m; then is not a well-ordering of T, as condition (ii) can be violated. Consider {a,b} with a b. Then, (b) (a,b), (b)(a,b), and (a,b) (b).
f.
We need to show that is a well-ordering of S if and only if it satisifies conditions (i) and (ii) and there is no infinite sequence x1,x2,x3, with xj+1 xj for all j 1. That is, we must show the equivalence of condition (iii), that S has a least element, and the nonexistence of an infinite descending sequence xj such that xj+1 xj for all j 1. If S has a least element, then clearly, there is an s S such that for any x S, x s unless s = x. Conversely, if no such sequence exists, there is some s such that x s for all x S, and this s is precisely the least element of S.
g.
Let S be well-ordered by , and let P(x) be a statement about the element x of S. We must show that if P(x) can be proved under the assumption that P(y) is true for all y x, then P(x) is true for all x in S.

Suppose not. That is, suppose there is some p such that P(p) does not hold, despite the fact that for all y x, P(y)P(x). If P(y) holds for all y p, then by hypothesis, P(p) holds. This is a condraction. Hence, P(x) holds for all x S.