5
Order and Logic
iterates of a function f : D → D inductively as follows: f
0 (x) = x, and
f
n+1 (x) = f (f
n (x)) for all n ∈ N and x ∈ D.
1.1.7 Definition A function f : D → E between posets D and E is called
monotonic if, for all a, b ∈ D with a [ b, we have f (a) [ f (b). Furthermore,
f is called antitonic if, for all a, b ∈ D with a [ b, we have f (b) [ f (a). If
D and E are ω-complete partial orders, then a function f : D → E is called
ω-continuous if it is monotonic and f (A) = f ( A) for each ω-chain A in
D. Finally, if D and E are complete partial orders, then f is called (order )
continuous if, again, it is monotonic and, for every directed subset A of D, we
have f (A) = f ( A).
We note that if f is monotonic, then the image of any ω-chain under f
is an ω-chain, and similarly the image of any directed set under f is itself
a directed set. Therefore, the two suprema required in making the previous
definition always exist. Indeed, it is easy to see that, equivalently,
5 one may
define f to be continuous by requiring, for each directed set A, that f (A)
is a directed set and that f (A) = f ( A). In fact, if f is monotonic and
A is directed, then it is easily checked that the inequality f (A) [ f ( A)
always holds. Therefore, it follows that f is continuous if and only if it is
monotonic and f ( A) [ f (A) whenever A ⊆ D is directed. As a matter
of fact, preservation of suprema of chains is enough in defining continuity as
shown by the next result, which again we simply state.
6 We note finally that
if a function f between complete partial orders is continuous, then it is clear
that it is ω-continuous as a function between ω-complete partial orders.
1.1.8 Proposition A function f : D → E between complete partial orders is
continuous if and only if it is monotonic and f (A) = f ( A) for each chain
A in D.
We define ordinal powers of a monotonic function f on a complete partial
order (D, [) inductively as follows: f ↑ 0 = ⊥, f ↑ (α + 1) = f (f ↑ α) for any
ordinal α, and f ↑ α = {f ↑ β | β < α} if α is a limit ordinal. Noting that
(D, [) is chain complete, being a complete partial order, it is straightforward
using transfinite induction to see that f ↑ β [ f ↑ α whenever β ≤ α, and
hence that ordinal powers of f are well-defined. More generally, the same
comments apply to the ordinal powers f
α (x) for any x ∈ D which satisfies
x [ f (x): we define f
0 (x) = x, f
α+1 (x) = f (f
α (x)) for any ordinal α, and
f
α (x) = {f
β (x) | β < α} if α is a limit ordinal.
A fixed point of a function f : D → D is an element x ∈ D satisfying
f (x) = x. A pre-fixed point of a function f on a poset (D, [) is an element
y ∈ D satisfying f (y) [ y. Finally, a post-fixed point of f is an element y ∈ D
satisfying y [ f (y). The least fixed point, lfp(f ), of f is a fixed point x of f
5 This is the definition adopted in [Stoltenberg-Hansen et al., 1994].
6 A discussion of the various ways of formulating the notion of continuity is to be found
in [Markowsky, 1976].
Order and Logic
iterates of a function f : D → D inductively as follows: f
0 (x) = x, and
f
n+1 (x) = f (f
n (x)) for all n ∈ N and x ∈ D.
1.1.7 Definition A function f : D → E between posets D and E is called
monotonic if, for all a, b ∈ D with a [ b, we have f (a) [ f (b). Furthermore,
f is called antitonic if, for all a, b ∈ D with a [ b, we have f (b) [ f (a). If
D and E are ω-complete partial orders, then a function f : D → E is called
ω-continuous if it is monotonic and f (A) = f ( A) for each ω-chain A in
D. Finally, if D and E are complete partial orders, then f is called (order )
continuous if, again, it is monotonic and, for every directed subset A of D, we
have f (A) = f ( A).
We note that if f is monotonic, then the image of any ω-chain under f
is an ω-chain, and similarly the image of any directed set under f is itself
a directed set. Therefore, the two suprema required in making the previous
definition always exist. Indeed, it is easy to see that, equivalently,
5 one may
define f to be continuous by requiring, for each directed set A, that f (A)
is a directed set and that f (A) = f ( A). In fact, if f is monotonic and
A is directed, then it is easily checked that the inequality f (A) [ f ( A)
always holds. Therefore, it follows that f is continuous if and only if it is
monotonic and f ( A) [ f (A) whenever A ⊆ D is directed. As a matter
of fact, preservation of suprema of chains is enough in defining continuity as
shown by the next result, which again we simply state.
6 We note finally that
if a function f between complete partial orders is continuous, then it is clear
that it is ω-continuous as a function between ω-complete partial orders.
1.1.8 Proposition A function f : D → E between complete partial orders is
continuous if and only if it is monotonic and f (A) = f ( A) for each chain
A in D.
We define ordinal powers of a monotonic function f on a complete partial
order (D, [) inductively as follows: f ↑ 0 = ⊥, f ↑ (α + 1) = f (f ↑ α) for any
ordinal α, and f ↑ α = {f ↑ β | β < α} if α is a limit ordinal. Noting that
(D, [) is chain complete, being a complete partial order, it is straightforward
using transfinite induction to see that f ↑ β [ f ↑ α whenever β ≤ α, and
hence that ordinal powers of f are well-defined. More generally, the same
comments apply to the ordinal powers f
α (x) for any x ∈ D which satisfies
x [ f (x): we define f
0 (x) = x, f
α+1 (x) = f (f
α (x)) for any ordinal α, and
f
α (x) = {f
β (x) | β < α} if α is a limit ordinal.
A fixed point of a function f : D → D is an element x ∈ D satisfying
f (x) = x. A pre-fixed point of a function f on a poset (D, [) is an element
y ∈ D satisfying f (y) [ y. Finally, a post-fixed point of f is an element y ∈ D
satisfying y [ f (y). The least fixed point, lfp(f ), of f is a fixed point x of f
5 This is the definition adopted in [Stoltenberg-Hansen et al., 1994].
6 A discussion of the various ways of formulating the notion of continuity is to be found
in [Markowsky, 1976].