232
Mathematical Aspects of Logic Programming Semantics
define the ordering ≤ on the ordinals by α ≤ β if and only if A ≤ B, and we
note that ≤ is easily seen to be well-defined on the ordinals. Furthermore, by
Theorem A.1.6, the ordering ≤ is a partial order and, as we show next, is in
fact a well-order.
A.1.9 Lemma Let X be a linearly ordered partially ordered set which is not
well-ordered. Then X contains an infinite strictly descending sequence.
Proof: If X is not well-ordered, then there exists a subset X 0 of X which
does not contain a least element. Choose some x 0 ∈ X 0 , and note that X 1 =
{y ∈ X | y < x 0 } does not contain a least element. Now assume that some
x i ∈ X has been chosen such that the set X i+1 = {y ∈ X | y < x i } does
not contain a least element. Then we can choose x i+1 ∈ X i+1 arbitrarily and
obtain x i+1 < x i and also that X i+2 = {y ∈ X | y < x i+1 } does not contain
a least element. By the inductive argument just given, we obtain an infinite
strictly descending sequence (x n ), as required.
•
A.1.10 Proposition Every set of ordinals is itself well-ordered by ≤.
Proof: We begin by noting that if α and β are ordinals such that α ≤ β and
α = #A and β = #B, then we can assume without loss of generality that
A ⊆ B; we will make use of this observation in what follows.
Let X be a set of ordinals which is not well-ordered. Then, by Lemma
A.1.9, X contains an infinite descending sequence α 0 > α 1 > α 2 > . . . of
ordinals. For each i ∈ N, suppose that α i = #A i and that A i ⊃ A i+1 . Then
for each i ∈ N there exists a i ∈ A i \ A i+1 . Hence, {a i | i ∈ N} ⊆ A 0 is a subset
of A 0 without a least element, which is impossible.
•
It is common practice to identify any ordinal α with the set of all ordinals
β such that β < α; so, in these terms, β < α if and only if β ∈ α. We
will follow this practice in the following. In particular, when we speak of a
mapping f : X → α, where α is an ordinal, we mean, in fact, a mapping
f : X → {β | β < α}.
Ordinals fall into two classes. A successor ordinal is an ordinal α such that
there is a greatest ordinal β with β < α. In this case, α is called the successor
of β and may be denoted by β + 1; we also call β the predecessor of α and
may denote it by α − 1. Any ordinal which is not a successor ordinal is called
a limit ordinal .
Any ordinal has a successor. To see this, let α be an ordinal and identify
it with the set of ordinals {β | β < α}. Then α ∪ {α} is an ordinal above α
and indeed is the least ordinal above α and therefore is the successor α + 1 of
α.
We next give an example containing details of some familiar ordinals.
Mathematical Aspects of Logic Programming Semantics
define the ordering ≤ on the ordinals by α ≤ β if and only if A ≤ B, and we
note that ≤ is easily seen to be well-defined on the ordinals. Furthermore, by
Theorem A.1.6, the ordering ≤ is a partial order and, as we show next, is in
fact a well-order.
A.1.9 Lemma Let X be a linearly ordered partially ordered set which is not
well-ordered. Then X contains an infinite strictly descending sequence.
Proof: If X is not well-ordered, then there exists a subset X 0 of X which
does not contain a least element. Choose some x 0 ∈ X 0 , and note that X 1 =
{y ∈ X | y < x 0 } does not contain a least element. Now assume that some
x i ∈ X has been chosen such that the set X i+1 = {y ∈ X | y < x i } does
not contain a least element. Then we can choose x i+1 ∈ X i+1 arbitrarily and
obtain x i+1 < x i and also that X i+2 = {y ∈ X | y < x i+1 } does not contain
a least element. By the inductive argument just given, we obtain an infinite
strictly descending sequence (x n ), as required.
•
A.1.10 Proposition Every set of ordinals is itself well-ordered by ≤.
Proof: We begin by noting that if α and β are ordinals such that α ≤ β and
α = #A and β = #B, then we can assume without loss of generality that
A ⊆ B; we will make use of this observation in what follows.
Let X be a set of ordinals which is not well-ordered. Then, by Lemma
A.1.9, X contains an infinite descending sequence α 0 > α 1 > α 2 > . . . of
ordinals. For each i ∈ N, suppose that α i = #A i and that A i ⊃ A i+1 . Then
for each i ∈ N there exists a i ∈ A i \ A i+1 . Hence, {a i | i ∈ N} ⊆ A 0 is a subset
of A 0 without a least element, which is impossible.
•
It is common practice to identify any ordinal α with the set of all ordinals
β such that β < α; so, in these terms, β < α if and only if β ∈ α. We
will follow this practice in the following. In particular, when we speak of a
mapping f : X → α, where α is an ordinal, we mean, in fact, a mapping
f : X → {β | β < α}.
Ordinals fall into two classes. A successor ordinal is an ordinal α such that
there is a greatest ordinal β with β < α. In this case, α is called the successor
of β and may be denoted by β + 1; we also call β the predecessor of α and
may denote it by α − 1. Any ordinal which is not a successor ordinal is called
a limit ordinal .
Any ordinal has a successor. To see this, let α be an ordinal and identify
it with the set of ordinals {β | β < α}. Then α ∪ {α} is an ordinal above α
and indeed is the least ordinal above α and therefore is the successor α + 1 of
α.
We next give an example containing details of some familiar ordinals.