234
Mathematical Aspects of Logic Programming Semantics
all x < x 0 , and the induction hypothesis leads to the conclusion that x 0 must
belong to B. This contradiction shows that B = A, as required.
•
A.1.13 Corollary Suppose that A is a well-ordered set and {p(a) | a ∈ A} is
a set of statements indexed by A. Suppose further that for all b ∈ A it follows
that p(b) is true if p(x) is true for all x < b. Then p(a) is true for all a ∈ A.
In fact, the form in which we will usually apply the principle of transfinite
induction is as follows.
A.1.14 Corollary Suppose that p(α) is a statement depending on the ordinal α. Suppose further that for all ordinals β, p(β) is true if p(γ) is true for
all γ < β. Then p(α) is true for all ordinals α.
When applying the principle of transfinite induction as a proof principle, as
formulated in Corollary A.1.14, it is usually convenient to split the argument
into two cases. The first of these is when β is assumed to be a successor ordinal,
and the second is when β is assumed to be a limit ordinal.
A.2 Basic Concepts from General Topology
We next turn to giving a brief overview of the general topology we need
at various points in our discussions.
3 In addition, we include here the proofs
of the results we stated without proof in our treatment of the Scott topology
in Chapter 3.
A.2.1 Definition A topology on a set X is a collection τ of subsets of X,
called the open sets of τ , satisfying the following properties.
(1) Any union of elements of τ belongs to τ .
(2) Any finite intersection of elements of τ belongs to τ .
(3) ∅ and X belong to τ .
The pair (X, τ ), or simply X by an abuse of notation, is called a topological
space.
A.2.2 Definition Given two topologies τ 1 and τ 2 on a set X, we say that τ 1
is weaker or coarser than τ 2 , or that τ 2 is stronger or finer than τ 1 , if τ 1 ⊆ τ 2 .
3 Our background references for the material we need from general topology are the books
[Kelley, 1975] and [Willard, 1970] to which we refer the reader for proofs of the results we
simply state.
Mathematical Aspects of Logic Programming Semantics
all x < x 0 , and the induction hypothesis leads to the conclusion that x 0 must
belong to B. This contradiction shows that B = A, as required.
•
A.1.13 Corollary Suppose that A is a well-ordered set and {p(a) | a ∈ A} is
a set of statements indexed by A. Suppose further that for all b ∈ A it follows
that p(b) is true if p(x) is true for all x < b. Then p(a) is true for all a ∈ A.
In fact, the form in which we will usually apply the principle of transfinite
induction is as follows.
A.1.14 Corollary Suppose that p(α) is a statement depending on the ordinal α. Suppose further that for all ordinals β, p(β) is true if p(γ) is true for
all γ < β. Then p(α) is true for all ordinals α.
When applying the principle of transfinite induction as a proof principle, as
formulated in Corollary A.1.14, it is usually convenient to split the argument
into two cases. The first of these is when β is assumed to be a successor ordinal,
and the second is when β is assumed to be a limit ordinal.
A.2 Basic Concepts from General Topology
We next turn to giving a brief overview of the general topology we need
at various points in our discussions.
3 In addition, we include here the proofs
of the results we stated without proof in our treatment of the Scott topology
in Chapter 3.
A.2.1 Definition A topology on a set X is a collection τ of subsets of X,
called the open sets of τ , satisfying the following properties.
(1) Any union of elements of τ belongs to τ .
(2) Any finite intersection of elements of τ belongs to τ .
(3) ∅ and X belong to τ .
The pair (X, τ ), or simply X by an abuse of notation, is called a topological
space.
A.2.2 Definition Given two topologies τ 1 and τ 2 on a set X, we say that τ 1
is weaker or coarser than τ 2 , or that τ 2 is stronger or finer than τ 1 , if τ 1 ⊆ τ 2 .
3 Our background references for the material we need from general topology are the books
[Kelley, 1975] and [Willard, 1970] to which we refer the reader for proofs of the results we
simply state.