Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

356 ORDERED SETS AND LATTICES [CHAP. 14

precedesb 0 and hence does not belong toB. Thus everyx∈s(b 0 )belongs toA; hences(b 0 )⊆A. By (ii),b 0 ∈A.

This contradicts the assumption thatb 0 ∈S\A. Thus the original assumption thatA=Sis not true. ThereforeA=S.

14.19. LetSbe a well-ordered set with first elementa 0. Definealimit elementofS.

An elementb∈S is a limit element ifb=a 0 andbhas no immediate predecessor.

14.20. Consider the setN={ 1 , 2 , 3 ,...}of positive integers. Every number inNcan be written uniquely as a
product of a nonnegative power of 2 times an odd number. Supposea,a′∈Nand

a= 2 r( 2 s+ 1 ) and a′= 2 r

′

( 2 s′+ 1 )

wherer,r′ands,s′are nonnegative integers. Define:

a≺a′ ifr<r′ or ifr=r′buts<s′.

(a) Insert the correct symbol,≺or., between each pair of numbers:

(i)5 ___ 14; (ii)6 ___ 9; (iii)3 ___ 20; (iv)14 ___ 21

(b) LetS=(N,≺). Show thatSis well-ordered.

(c) DoesShave any limit elements?

(a) The elements ofNcan be listed as in Fig. 14-14. The first row consists of the odd numbers, the second row of

2 times the odd numbers, the third row of 2^2 =4 times the odd numbers, and so on. Thena≺a′if a is in higher

row then,a′or ifaanda′are in the same row butacomes beforea′in the row. Accordingly:

(i) 5 ≺ 14 ; (ii) 6. 9 ; (iii) 3. 20 ; (iv) 14. 20.

Fig. 14-14

(b) LetAbe a subset ofS. The rows are well-ordered. Letr 0 denote the minimum row of elements inA.Inr 0

there may be many elements ofA. The columns are well-ordered, so lets 0 denote the minimum column of the

elements ofAin rowr 0. Thenx=(r 0 ,s 0 )is the first element ofA. ThusSis well-ordered.

(c) As indicated by Fig. 14-14, every power of 2, that is, 1, 2, 4, 8,..., has no immediate predecessor. Thus each,

other than 1, is a limit element ofS.

14.21. LetSbe a well-ordered set. Letf:S→Sbe a similarity mapping ofSintoS. Prove that, for every
a∈S, we havea
f(a).
LetD={x|f(x)≺x}.IfDis empty, then the statement is true. SupposeD=
. SinceDis well-ordered,D
has a first element, sayd 0. Sinced 0 ∈D, we havef(d 0 )≺d 0. Since f is a similarity mapping:

f(d 0 )≺d 0 implies f(f(d 0 ))≺f(d 0 )

Thusf(d 0 )also belongs toD. Butf(d 0 )≺d 0 andf(d 0 )∈Dcontradicts the fact thatd 0 is the first element of

D. Hence the original assumption thatD=
leads to a contradiction. ThereforeDis empty and the statement

is true.