346 ORDERED SETS AND LATTICES [CHAP. 14
Principle of Transfinite Induction: LetAbe a subset of a well-ordered setSwith the following two properties:
(i) a 0 ∈A.
(ii) Ifs(a)⊆A, thena∈A.ThenA=S.
Herea 0 is the first element ofS, ands(a), called theinitial segmentofa, is defined to be the set of all
elements ofSwhich strictly precedea.
Axiom of Choice, Well-Ordering Theorem
Let{Ai|i∈I}be a collection of nonempty disjoint sets. We assume everyAi⊆X.Afunctionf:{Ai}→X
is called achoice functioniff(Ai)=ai∈Ai. In other words,f“chooses” a pointai∈Aifor each setAi.
The axiom of choice lies at the foundations of mathematics and, in particular, the theory of sets. This
“innocent looking” axiom, which follows, has as a consequence some of the most powerful and important results
in mathematics.
Axiom of Choice: There exists a choice function for any nonempty collection of nonempty disjoint sets.
One of the consequences of the axiom of choice is the following theorem, which is attributed to Zermelo.Well-Ordering Theorem: Every setScan be well-ordered.
The proof of this theorem lies beyond the scope of this text. Moreover, since all of our structures are finite
or countable, we will not need to use this theorem. Ordinary mathematical induction suffices.
14.8Lattices
There are two ways to define a latticeL. One way is to defineLin terms of a partially ordered set. Specifically,
a latticeLmay be defined as a partially ordered set in which inf(a, b)and sup(a, b)exist for any pair of elements
a,b∈L. Another way is to define a latticeLaxiomatically. This we do below.
Axioms Defining a Lattice
LetLbe a nonempty set closed under two binary operations calledmeetandjoin, denoted respectively by
∧and∨. ThenLis calledlatticeif the following axioms hold wherea,b,care elements inL:
[L 1 ] Commutative law:
( 1 a) a∧b=b∧a( 1 b) a∨b=b∨a[L 2 ] Associative law:
( 2 a) (a∧b)∧c=a∧(b∧c) ( 2 b) (a∨b)∨c=a∨(b∨c)[L 3 ] Absorption law:
( 3 a) a∧(a∨b)=a( 3 b) a∨(a∧b)=aWe will sometimes denote the lattice by(L,∧,∨)when we want to show which operations are involved.
Duality and the Idempotent Law
Thedualof any statement in a lattice(L,∧,∨)is defined to be the statement that is obtained by interchanging
∧and∨. For example, the dual of
a∧(b∨a)=a∨a is a∨(b∧a)=a∧a