230
Mathematical Aspects of Logic Programming Semantics
of X which has no least element, contradicting the hypothesis that (X, ≤ X )
is well-ordered.
•
Given two well-ordered sets (X, ≤ X ) and (Y, ≤ Y ), we call f : X → Y
monotonic if a ≤ X b implies f (a) ≤ Y f (b) for all a, b ∈ X. If f is also
injective, then f is called an embedding of X into Y . If f is both monotonic
and bijective, then f is called an order isomorphism between X and Y , and
in this case the two well-orderings X and Y are called isomorphic. Note that
all these definitions are consistent with the definitions concerning orderings
made in Chapter 1.
A.1.4 Definition Suppose that (X, ≤ X ) is a well-ordered set and that x 0 ∈
X. We call the set I = I(x 0 ) = {x ∈ X | x ≤ X x 0 } the initial segment of X
determined by x 0 . We call an initial segment I of X a proper initial segment
if I is a proper subset of X.
A.1.5 Definition Suppose that (X, ≤ X ) and (Y, ≤ Y ) are two well-ordered
sets. Then we write X ≤ Y if X is isomorphic to an initial segment of Y . We
write X < Y if X is isomorphic to a proper initial segment of Y .
A.1.6 Theorem For any two well-ordered sets X and Y , exactly one of the
following statements holds.
(a) X < Y .
(b) X > Y .
(c) X and Y are isomorphic.
Proof: We first prove the following statement.
(1) No well-ordered set (Z, ≤ Z ) is isomorphic to a proper initial segment of
itself.
To see this, suppose f : I → Z is an isomorphism, where I is a proper
initial segment of Z. Then we cannot have f (x) = x for all x ∈ I; otherwise, f
would not be surjective. Let x 0 be the least element of the set of those elements
x of I such that f (x) = x. Noting in particular that f (x 0 ) = x 0 , we see that
we cannot have f (x 0 ) < Z x 0 otherwise f (f (x 0 )) = f (x 0 ) by minimality of
x 0 , and this yields the contradiction that f is not injective. Hence it must
be the case that x 0 < Z f (x 0 ). Now let x 1 ∈ I be such that f (x 1 ) = x 0 .
Then x 1 = x 0 because f (x 0 ) = x 0 . If x 1 < Z x 0 , then by definition of x 0
again, we obtain x 0 = f (x 1 ) = x 1 < Z x 0 , which is impossible. If x 0 < Z x 1 ,
then f (x 1 ) = x 0 < Z f (x 0 ), which contradicts the monotonicity of f . Hence,
Statement (1) holds.
We will also need the following statement.
(2) Suppose the well-ordered sets (W, ≤ W ) and (Z, ≤ Z ) are isomorphic. Then
there is a unique isomorphism f : (W, ≤ W ) → (Z, ≤ Z ).
Mathematical Aspects of Logic Programming Semantics
of X which has no least element, contradicting the hypothesis that (X, ≤ X )
is well-ordered.
•
Given two well-ordered sets (X, ≤ X ) and (Y, ≤ Y ), we call f : X → Y
monotonic if a ≤ X b implies f (a) ≤ Y f (b) for all a, b ∈ X. If f is also
injective, then f is called an embedding of X into Y . If f is both monotonic
and bijective, then f is called an order isomorphism between X and Y , and
in this case the two well-orderings X and Y are called isomorphic. Note that
all these definitions are consistent with the definitions concerning orderings
made in Chapter 1.
A.1.4 Definition Suppose that (X, ≤ X ) is a well-ordered set and that x 0 ∈
X. We call the set I = I(x 0 ) = {x ∈ X | x ≤ X x 0 } the initial segment of X
determined by x 0 . We call an initial segment I of X a proper initial segment
if I is a proper subset of X.
A.1.5 Definition Suppose that (X, ≤ X ) and (Y, ≤ Y ) are two well-ordered
sets. Then we write X ≤ Y if X is isomorphic to an initial segment of Y . We
write X < Y if X is isomorphic to a proper initial segment of Y .
A.1.6 Theorem For any two well-ordered sets X and Y , exactly one of the
following statements holds.
(a) X < Y .
(b) X > Y .
(c) X and Y are isomorphic.
Proof: We first prove the following statement.
(1) No well-ordered set (Z, ≤ Z ) is isomorphic to a proper initial segment of
itself.
To see this, suppose f : I → Z is an isomorphism, where I is a proper
initial segment of Z. Then we cannot have f (x) = x for all x ∈ I; otherwise, f
would not be surjective. Let x 0 be the least element of the set of those elements
x of I such that f (x) = x. Noting in particular that f (x 0 ) = x 0 , we see that
we cannot have f (x 0 ) < Z x 0 otherwise f (f (x 0 )) = f (x 0 ) by minimality of
x 0 , and this yields the contradiction that f is not injective. Hence it must
be the case that x 0 < Z f (x 0 ). Now let x 1 ∈ I be such that f (x 1 ) = x 0 .
Then x 1 = x 0 because f (x 0 ) = x 0 . If x 1 < Z x 0 , then by definition of x 0
again, we obtain x 0 = f (x 1 ) = x 1 < Z x 0 , which is impossible. If x 0 < Z x 1 ,
then f (x 1 ) = x 0 < Z f (x 0 ), which contradicts the monotonicity of f . Hence,
Statement (1) holds.
We will also need the following statement.
(2) Suppose the well-ordered sets (W, ≤ W ) and (Z, ≤ Z ) are isomorphic. Then
there is a unique isomorphism f : (W, ≤ W ) → (Z, ≤ Z ).