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

CHAP. 14] ORDERED SETS AND LATTICES 345

(5) Every elementa∈S, other than a last element, has an immediate successor. For, letM(a)denote the set of

elements which strictly succeeda. Then the first element ofM(a)is the immediate successor ofa.

EXAMPLE 14.9

(a) The setZof integers with the usual order≤is linearly ordered and every element has an immediate successor

and an immediate predecessor, butZis not well-ordered. For example,Zitself has no first element. However,

any subset ofZwhich is bounded from below is well-ordered.

(b) The setQof rational numbers with the usual order≤is linearly ordered, but no element inQhas an immediate

successor or an immediate predecessor. For ifa,b∈Q, saya<b, then(a+b)/ 2 ∈Qand

a<

a+b

2

<b

(c) Consider the disjoint well-ordered sets

A={ 1 , 3 , 5 ,...,} and B={ 2 , 4 , 6 ,...}

Then the following ordered set

S={A;B}={ 1 , 3 , 5 ,...; 2 , 4 , 6 ,...}

is well-ordered. Note that, besides the first element 1, the element 2 does not have an immediate predecessor.

Notation: Here and subsequently, ifA,B,...are disjoint ordered sets, then{A;B;...}means the setA∪B∪...

ordered positionwise from left to right; that is, the elements in the same set keep their order, and any element in

a set on the left precedes any element in a set on its right. Thus every element inAprecedes every element inB,

and so on.

Transfinite Induction

First we restate the principle of mathematical induction. (See Section 1.8 and 11.3.)

Principle of Mathematical Induction: LetAbe a subset of the setNof positive integers with the following

two properties:

(i) 1∈A.

(ii) Ifk∈A, thenk+ 1 ∈A.

ThenA=N.

The above principle is one of Peano’s axioms for the natural numbers (positive integers)N. There is another

form which is sometimes more convenient to use. Namely:

PrincipleofMathematicalInduction(SecondForm): LetAbeasubsetofNwiththefollowingtwoproperties:

(i) 1∈A.

(ii) Ifjbelongs toAfor 1≤j<k, thenk∈A.

ThenA=N.

The second form of induction is equivalent to the fact thatNis well-ordered (Theorem 11.6). In fact, there
is a somewhat similar statement which is true for every well-ordered set.