Normal function
Encyclopedia
In axiomatic set theory, a function f : Ord
→ Ord is called normal (or a normal function) iff
it is continuous (with respect to the order topology
) and strictly monotonically increasing
. This is equivalent to the following two conditions:
More important examples of normal functions are given by the aleph number
s
which connect ordinal and cardinal number
s, and by the beth number
s
.
Proof: If not, choose γ minimal such that f(γ) < γ. Since f is strictly monotonically increasing, f(f(γ)) < f(γ), contradicting minimality of γ.
Furthermore, for any non-empty set S of ordinals, we have
Proof: "≥" follows from the monotonicity of f and the definition of the supremum
. For "≤", set δ = sup S and consider three cases:
Every normal function f has arbitrarily large fixed points; see the fixed-point lemma for normal functions
for a proof.
One can create a normal function g : Ord → Ord, called the derivative of f, where g(α) is the α-th fixed point of f.
Ordinal number
In set theory, an ordinal number, or just ordinal, is the order type of a well-ordered set. They are usually identified with hereditarily transitive sets. Ordinals are an extension of the natural numbers different from integers and from cardinals...
→ Ord is called normal (or a normal function) iff
IFF
IFF, Iff or iff may refer to:Technology/Science:* Identification friend or foe, an electronic radio-based identification system using transponders...
it is continuous (with respect to the order topology
Order topology
In mathematics, an order topology is a certain topology that can be defined on any totally ordered set. It is a natural generalization of the topology of the real numbers to arbitrary totally ordered sets...
) and strictly monotonically increasing
Monotonic function
In mathematics, a monotonic function is a function that preserves the given order. This concept first arose in calculus, and was later generalized to the more abstract setting of order theory....
. This is equivalent to the following two conditions:
- For every limit ordinal γ (i.e. γ is neither zero nor a successor), f(γ) = supSupremumIn mathematics, given a subset S of a totally or partially ordered set T, the supremum of S, if it exists, is the least element of T that is greater than or equal to every element of S. Consequently, the supremum is also referred to as the least upper bound . If the supremum exists, it is unique...
{f(ν) : ν < γ}. - For all ordinals α < β, f(α) < f(β).
Examples
A simple normal function is given by f(α) = 1 + α; note however that f(α) = α + 1 is not normal. If β is a fixed ordinal, then the functions f(α) = β + α, f(α) = β × α and f(α) = βα (for β > 1) are all normal.More important examples of normal functions are given by the aleph number
Aleph number
In set theory, a discipline within mathematics, the aleph numbers are a sequence of numbers used to represent the cardinality of infinite sets. They are named after the symbol used to denote them, the Hebrew letter aleph...
s
which connect ordinal and cardinal numberCardinal number
In mathematics, cardinal numbers, or cardinals for short, are a generalization of the natural numbers used to measure the cardinality of sets. The cardinality of a finite set is a natural number – the number of elements in the set. The transfinite cardinal numbers describe the sizes of infinite...
s, and by the beth number
Beth number
In mathematics, the infinite cardinal numbers are represented by the Hebrew letter \aleph indexed with a subscript that runs over the ordinal numbers...
s
.Properties
If f is normal, then for any ordinal α,- f(α) ≥ α.
Proof: If not, choose γ minimal such that f(γ) < γ. Since f is strictly monotonically increasing, f(f(γ)) < f(γ), contradicting minimality of γ.
Furthermore, for any non-empty set S of ordinals, we have
- f(sup S) = sup f(S).
Proof: "≥" follows from the monotonicity of f and the definition of the supremum
Supremum
In mathematics, given a subset S of a totally or partially ordered set T, the supremum of S, if it exists, is the least element of T that is greater than or equal to every element of S. Consequently, the supremum is also referred to as the least upper bound . If the supremum exists, it is unique...
. For "≤", set δ = sup S and consider three cases:
- if δ = 0, then S = {0} and sup f(S) = f(0);
- if δ = ν + 1 is a successorSuccessor ordinalIn set theory, the successor of an ordinal number α is the smallest ordinal number greater than α. An ordinal number that is a successor is called a successor ordinal...
, then there exists s in S with ν < s, so that δ ≤ s. Therefore, f(δ) ≤ f(s), which implies f(δ) ≤ sup f(S); - if δ is a nonzero limit, pick any ν < δ, and an s in S such that ν < s (possible since δ = sup S). Therefore f(ν) < f(s) so that f(ν) < sup f(S), yielding f(δ) = sup {f(ν) : ν < δ} ≤ sup f(S), as desired.
Every normal function f has arbitrarily large fixed points; see the fixed-point lemma for normal functions
Fixed-point lemma for normal functions
The fixed-point lemma for normal functions is a basic result in axiomatic set theory stating that any normal function has arbitrarily large fixed points...
for a proof.
One can create a normal function g : Ord → Ord, called the derivative of f, where g(α) is the α-th fixed point of f.