Solutions to Exercises and Hints for

Solutions to Exercises and Hints for Investigations Chapter 2 Solutions to Exercises 2.1.5A[B=f; ; ; g,A\B=f; ; g,AnB=fg,BnA=;, AnC=f; g,CnA=fg,B\C=f; g,D[E=f; ; g, C[D[E=f; ; g,C\D\E=;,EnD=fg.

2.1.6(i) True (ii) False ifA=B(iii) True (iv) True (v) True.(iii) and (v) are false ifB=;; (iv) is false ifA=;.

2.2.9(i) Surjection (ii) Not a function (iii) Surjection (iv) Function (neither injection nor surjection) (v) Injection (vi) Not a function (vii) Bijection (viii) Function (neither injection nor surjection) 2.3.13(i) Strict order (ii) Equivalence (iii) Weak order (iv) Transitive (v) Symmetric and transitive (vi) Symmetric (vii) Strictly antisymmetric (viii) Strict order (ix) Equivalence (x) Symmetric.Chapter 3 Solutions to Exercises 3.2.11Ifn= 1 thenm+n=m+ 1 =S(m), but 16=S(m) for anym2N[Axiom 3.1.3]. If n6= 1 thenn=S(k) for somek2N[Corollary 3.1.6] and thenm+n=m+S(k) =S(m+k), but sincem+k2Nifm2Nandk2N, Axiom 3.1.3 implies that 16=S(m+k).

3.3.6Proof of Lemma 3.3.2:

(a) Forn= 1: 1n= 11 =n1.

(b) Inductive hypothesis: 1n=n1. Then: 1S(n) = (1n) + 1 [ Denition 3.3.1(b)] =S(1n) [Denition 3.2.1(a)] =S(n1) [Inductive hypothesis] =S(n) [Denition 3.3.1(a)]

=S(n)1 [Denition 3.3.1(a)]:

1 Solutions Manual for Number Systems A Path into Rigorous Mathematics, 1e by Anthony Kay (All Chapters) 1 / 4

2Solutions to Exercises and Hints for Investigations

Proof of Lemma 3.3.4:

(a) Forn= 1:

(m+ 1)n= (m+ 1)1 =m+ 1 [Denition 3.3.1(a)] =m1 + 1 [ Denition 3.3.1(a)]

=mn+n:

(b) Inductive hypothesis: (m+ 1)n=mn+n. Then

(m+ 1)S(n) = (m+ 1)n+ (m+ 1) [Denition 3.3.1(b)] = (mn+n) + (m+ 1) [Inductive hypothesis] = (mn+m) + (n+ 1) [Addition is associative and commutative]

=mS(n) +S(n) [ Denition 3.3.1(b) & Denition 3.2.1(a)]:

Proof of Theorem 3.3.5:

(a) Forn= 1: using Lemma 3.3.2,mn=m1 = 1m=nm.

(b) Inductive hypothesis:mn=nm. Then

S(m)n= (m+ 1)n[Denition 3.2.1(a)] =mn+n[Lemma 3.3.4] =nm+n[Inductive hypothesis]

=nS(m) [Denition 3.3.1(b)]:

3.3.11(a) Forp= 1:

m(np) =m(n1) =mn[Denition 3.3.1(a)] = (mn)1 [ Denition 3.3.1(a)]

= (mn)p:

(b) Inductive hypothesis:m(np) = (mn)p. Then

m(nS(p)) =m((np) +n) [ Denition 3.3.1(b)] =m(np) + (mn) [ Corollary 3.3.8] = (mn)p+ (mn) [ Inductive hypothesis]

= (mn)S(p) [ Denition 3.3.1(b)]:

3.4.3(a) Forn= 1: 1

n = 1 1 = 1 [Denition 3.4.1(a)].

(b) Inductive hypothesis: 1

n = 1. Then 1 S(n) = 11 n [Denition 3.4.1(b)] = 11 [Inductive hypothesis]

= 1:

3.4.6(a) Form= 1: using Denition 3.4.1(a), (np)

m = (np) 1 =np=n 1 p 1 =n m p m .

(b) Inductive hypothesis: (np)

m =n m p m . Then (np) S(m) = (np)(np) m [Denition 3.4.1(b)] = (np)(n m p m

• [Inductive hypothesis]

= (nn m )(pp m

• [ Multiplication is assoc. & comm.]

=n S(m) p S(m)

[Denition 3.4.1(b)]: 2 / 4

Solutions to Exercises and Hints for Investigations 3

3.4.8(a) Form= 1: using Denition 3.4.1(a),n

pm =n p1 =n p = (n p ) 1 = (n p ) m .

(b) Inductive hypothesis:n

pm = (n p ) m . Then n pS(m) =n pm+p [Denition 3.3.1(b)] =n pm n p [Theorem 3.4.4] = (n p ) m n p [Inductive hypothesis] =n p (n p ) m [Theorem 3.3.5] = (n p ) S(m)

[Denition 3.4.1(b)]:

3.5.6Ifn > mandm > k, then Denition 3.5.1 gives thatn=m+pandm=k+q for somep; q2N. Son= (k+q) +p=k+ (q+p) and sinceq+p2N, this satises the denition ofn > k. The proof with the

3.5.8 n+k > m+k)n+k= (m+k) +pfor somep2N )n+k= (m+p) +k )n=m+p[Theorem 3.2.10]

)n > m:

3.5.10Suppose9l2Nsuch thatS(n)< l < S(S(n)). Thenl6= 1, becauseS(n)<1 is impossible according to Theorems 3.5.3 and 3.5.4; so by Corollary 3.1.6,l=S(k) for some k2N. Thus we have S(n)< S(k)< S(S(n)) )n+ 1< k+ 1< S(n) + 1 )n < k < S(n) [Theorem 3.5.7]; which contradicts the inductive hypothesis. Hence@l2Nsuch thatS(n)< l < S(S(n)).

3.5.13

n > m)n=m+pfor somep2N )nk= (m+p)k )nk=mk+pk[Theorem 3.3.7]

)nk > mksincepk2N:

3.5.16First show thatn > m)n k > m k , by induction onk.

(a) Fork= 1:n > m)n

1 > m 1 )n k > m k .

(b) Inductive hypothesis:n > m)n

k > m k . Then n S(k) =nn k > nm k [Inductive hypothesis & Theorem 3.5.12] > mm k [Theorem 3.5.12 withn > m] =m S(k) ; son S(k) > m S(k) by transitivity, given thatn > m.

For the converse: given thatn > m)n

k > m k , it follows immediately that n < m)n k < m k . Alson=m)n k =m k . Hence by trichotomy,nm)n k m k .The contrapositive of this is thatn k > m k )n > m. 3 / 4

4Solutions to Exercises and Hints for Investigations 3.5.18First show thatn > m)k n > k m .Now,n > m)n=m+pfor somep2N[Denition 3.5.1]. Sok n =k m+p =k m k p [Theorem 3.4.4]. Then from Theorem 3.5.12, to show thatk n > k m we only need to verify thatk p >1.

Givenk >1: (a) Forp= 1,k

p =k 1 =k >1. (b) With the inductive hypothesisk p >1, we havek S(p) =kk p > k >1. Hencek p >1 for allk >1 andp2N.For the converse, an argument using trichotomy (as in the solution to Exercise 3.5.16) shows thatk n > k m )n > mwhenk >1.

3.6.11LetAbe a non-empty subset ofN, bounded above so thatUA, the set of upper bounds

ofA, is non-empty. HenceUAhas a least member [Theorem 3.6.9]; so letu:= minUA.

Ifu= 1, thena18a2A(sinceuis an upper bound forA). But then from Theorem 3.5.3,A=f1gso maxA= 1.Ifu6= 1, thenu=S(t) for somet2N. Ifu2A, thenusatises the conditions to be the greatest member ofA. So suppose thatu62A. Being an upper bound,ua8a2A; but ifu62A, thenu6=asou > a8a2A. Withu=S(t), this implies thatta8a2A [Corollary 3.5.11(iv)]. But thentis an upper bound forAandt < u, which contradicts the denition ofuas theleastupper bound ofA. Henceu2A, and in all cases maxAexists.

3.7.17There arenrows,ncolumns and 2 diagonals: a total of 2n+2 sums to be calculated.The least possible value for the sums is where all entries are 1, giving a sum ofn. The greatest possible value is where all entries are 3, giving a sum of 3n. Since 3n=n+ 2n, there are at most 2n+ 1 possible values of the sum; this requires a theorem that ifn=m+p, then

the cardinality of the setfk2N:mkngisp+ 1, which is easy to prove by induction

onp. Given this result, we have at most 2n+ 1 possible values for 2n+ 2 sums, so by the Pigeonhole Principle, at least one value of a sum must appear more than once; they are not all dierent.

3.7.24(i) WithM= 4, 2 M+1 = 2 5 = 32 and (M+ 1) 2 = 5 2 = 25, so 2 M+1 >(M+ 1) 2 .So the hypothesis 2 m > m 2 is anchored atm= 5, and we only need to considerm5 in the inductive step. Now, (S(m)) 2 = (m+ 1) 2 =m 2

• 2m+ 1, and since 1< m, we have

(S(m)) 2 < m 2

• 3m <2m

2 because 3m < m 2 whenm5. Also, 2 S(m) = 22 m >2m 2 [Inductive hypothesis]. Thus by transitivity, 2 S(m) >(S(m)) 2 .(ii) Form1, it is not necessarily true that 1< mor 3m < m 2 .

3.7.27Guest numbernalready in the hotel is moved to room 2n, for eachn2N. Passenger numbermfrom the bus can be accommodated in room 2m+ 1, for eachm2N.

3.8.4Letm=pn, sop=m+n[Denition 3.8.2]. Thenkp=k(m+n) =km+kn [Corollary 3.3.8], and sokm=kpkn[Denition 3.8.2], i.e.k(pn) =kpkn.Hints for Investigations 1.(i) 3^^3 = 7625597484987 and 2^^^3 = 65536.(iv) 2!2!c= 4 for allc2N.

2.(i) Considerm= 1 in particular.(ii) Do the addition, multiplication and exponentiation operations withmkandml, and withm k andm l , for xedm2Nand anyk; l2N.

3.What happens whenS(n) = 2?

4.How many words are there in the specication of the number in question?

• / 4