Chapter 1
Order and Logic
The study of the semantics of logic programs rests on a certain amount of
order theory and logic, and it will be convenient to collect together here in
this first chapter those basic facts we need throughout the book to accomplish
this study.
1 At the same time, we establish some notation and terminology
which is common to all the chapters.
1.1 Ordered Sets and Fixed-Point Theorems
We start by presenting the minimum amount that we need of the theory
of ordered sets. In addition, we discuss certain important and well-known
fixed-point theorems applying to functions defined on ordered sets. In fact,
the first of these theorems has fundamental applications in the semantics of
computation in general, as well as in logic programming semantics.
Let D be a set. Recall that a binary relation [ on D is simply a subset [
of D × D. As usual, the symbol [ will be written infix, and hence we write
x [ y rather than (x, y) ∈ [, where x, y ∈ D. Furthermore, we write x c y
if x [ y and x = y. The relation [ on D is called reflexive if, for all x ∈ D,
we have x [ x; it is called antisymmetric if, for all x, y ∈ D, x [ y and y [ x
imply x = y; and it is called transitive if, for all x, y, z ∈ D, x [ y and y [ z
imply x [ z. We call [ a partial order if [ is reflexive, antisymmetric, and
transitive, and in that case we call the pair (D, [), or simply D when [ is
understood, a partially ordered set, a poset, or sometimes a partial order by
abuse of terminology. We may sometimes simply refer to a partially ordered
set (D, [) as an ordered set and to the relation [ as an ordering (on D).
Two elements x and y of a partially ordered set D are said to be comparable
if either x [ y or y [ x holds; otherwise, x and y are called incomparable.
A non-empty subset A ⊆ D is said to be totally ordered by [ or is called
a chain if any two elements of A are comparable with respect to [, that is,
given a, b ∈ A, we have a [ b or b [ a. A partial order [ on D is called a
total order if D itself is totally ordered by [. We call A an ω-chain if A is an
increasing sequence a 0 [ a 1 [ a 2 . . ., where ω denotes the first limit ordinal.
1 The text [Davey and Priestley, 2002] is a useful reference for the subject of ordered sets.
1
Order and Logic
The study of the semantics of logic programs rests on a certain amount of
order theory and logic, and it will be convenient to collect together here in
this first chapter those basic facts we need throughout the book to accomplish
this study.
1 At the same time, we establish some notation and terminology
which is common to all the chapters.
1.1 Ordered Sets and Fixed-Point Theorems
We start by presenting the minimum amount that we need of the theory
of ordered sets. In addition, we discuss certain important and well-known
fixed-point theorems applying to functions defined on ordered sets. In fact,
the first of these theorems has fundamental applications in the semantics of
computation in general, as well as in logic programming semantics.
Let D be a set. Recall that a binary relation [ on D is simply a subset [
of D × D. As usual, the symbol [ will be written infix, and hence we write
x [ y rather than (x, y) ∈ [, where x, y ∈ D. Furthermore, we write x c y
if x [ y and x = y. The relation [ on D is called reflexive if, for all x ∈ D,
we have x [ x; it is called antisymmetric if, for all x, y ∈ D, x [ y and y [ x
imply x = y; and it is called transitive if, for all x, y, z ∈ D, x [ y and y [ z
imply x [ z. We call [ a partial order if [ is reflexive, antisymmetric, and
transitive, and in that case we call the pair (D, [), or simply D when [ is
understood, a partially ordered set, a poset, or sometimes a partial order by
abuse of terminology. We may sometimes simply refer to a partially ordered
set (D, [) as an ordered set and to the relation [ as an ordering (on D).
Two elements x and y of a partially ordered set D are said to be comparable
if either x [ y or y [ x holds; otherwise, x and y are called incomparable.
A non-empty subset A ⊆ D is said to be totally ordered by [ or is called
a chain if any two elements of A are comparable with respect to [, that is,
given a, b ∈ A, we have a [ b or b [ a. A partial order [ on D is called a
total order if D itself is totally ordered by [. We call A an ω-chain if A is an
increasing sequence a 0 [ a 1 [ a 2 . . ., where ω denotes the first limit ordinal.
1 The text [Davey and Priestley, 2002] is a useful reference for the subject of ordered sets.
1