233
Transfinite Induction and General Topology
A.1.11 Example It is easy to see that any finite set A = {a 1 , . . . , a n }, containing n elements, can be well-ordered in essentially one way. Thus, if A
and B are any well-ordered sets containing n elements, then A and B are
isomorphic. Standard notation for the finite ordinals, together with canonical
representatives for them, is as follows: 0 = #∅, 1 = #{∅}, 2 = #{∅, {∅}},
3 = #{∅, {∅}, {∅, {∅}}}, etc. Thus, we are using the same symbols 0, 1, 2, 3, . . .
to denote natural numbers and ordinal numbers (as well as cardinal numbers),
but the context in which they occur will determine their meaning. Often, we
consider an ordinal to be the set of all its predecessors, as already noted, in
which case we view the ordinal n as the set {0, 1, . . . , n − 1} for each n. Furthermore, 0 is the least ordinal, 1 is the successor of 0, 2 is the successor of 1,
etc. Thus, we have 0 < 1 < 2 < 3 < · · · as ordinals.
Turning now to ordinals determined by infinite sets, we note first that infinite sets can be well-ordered in more than one way. For example, the set N
of natural numbers can be well-ordered by writing it as {1, 3, 5, . . . ; 2, 4, 6, . . .}
and ordering it from left to right. The resulting well-order is clearly not isomorphic to N well-ordered by the usual order on N. Indeed, the first infinite ordinal or least infinite ordinal , denoted by ω, is the ordinal determined
by N in its usual order, that is, ω = #N. Thus, ω is the first limit ordinal. The successor of ω is ω + 1 = {0, 1, 2, . . . , ω}, the successor of which
is ω + 2 = (ω + 1) + 1 = {0, 1, 2, . . . , ω, ω + 1}, etc. The next, or second,
limit ordinal is denoted by ω2 = {0, 1, 2, . . . , ω, ω + 1, ω + 2, . . . , ω + n, . . .}
etc. In this way, the ordinals form a transfinite sequence, and indeed any
non-finite ordinal is sometimes called a transfinite number. Thus, we have
0 < 1 < 2 < 3 < · · · < ω < ω + 1 < ω + 2 < · · · < ω2 < ω2 + 1 < ω2 + 2 <
· · · < ω3 < · · · < ωn < · · · < ωω = ω
2 < ω
2 + 1 < ω
2 + 2 < · · · as ordinal numbers. Note also that all the ordinals we have so far displayed in this
example are determined by countable sets. The first uncountable ordinal is
denoted by ω 1 and as a set is the uncountable well-ordered set containing all
the countable ordinals.
•
We are now in a position to consider the principle of transfinite induction.
The reader may note that it is an extension, from N to arbitrary well-ordered
sets, of the well-known strong form
2 of the principle of mathematical induction.
A.1.12 Theorem (Principle of Transfinite Induction) Suppose that A
is any well-ordered set and B is a subset of A which satisfies the statement
that a ∈ B whenever x ∈ B for all x < a. Then B = A.
Proof: If B = A, then A \ B = ∅. By well-ordering of A and therefore of any
subset B of A, A \ B has a first element x 0 , say. But now we have x ∈ B for
2 Also known as course of values induction.
Transfinite Induction and General Topology
A.1.11 Example It is easy to see that any finite set A = {a 1 , . . . , a n }, containing n elements, can be well-ordered in essentially one way. Thus, if A
and B are any well-ordered sets containing n elements, then A and B are
isomorphic. Standard notation for the finite ordinals, together with canonical
representatives for them, is as follows: 0 = #∅, 1 = #{∅}, 2 = #{∅, {∅}},
3 = #{∅, {∅}, {∅, {∅}}}, etc. Thus, we are using the same symbols 0, 1, 2, 3, . . .
to denote natural numbers and ordinal numbers (as well as cardinal numbers),
but the context in which they occur will determine their meaning. Often, we
consider an ordinal to be the set of all its predecessors, as already noted, in
which case we view the ordinal n as the set {0, 1, . . . , n − 1} for each n. Furthermore, 0 is the least ordinal, 1 is the successor of 0, 2 is the successor of 1,
etc. Thus, we have 0 < 1 < 2 < 3 < · · · as ordinals.
Turning now to ordinals determined by infinite sets, we note first that infinite sets can be well-ordered in more than one way. For example, the set N
of natural numbers can be well-ordered by writing it as {1, 3, 5, . . . ; 2, 4, 6, . . .}
and ordering it from left to right. The resulting well-order is clearly not isomorphic to N well-ordered by the usual order on N. Indeed, the first infinite ordinal or least infinite ordinal , denoted by ω, is the ordinal determined
by N in its usual order, that is, ω = #N. Thus, ω is the first limit ordinal. The successor of ω is ω + 1 = {0, 1, 2, . . . , ω}, the successor of which
is ω + 2 = (ω + 1) + 1 = {0, 1, 2, . . . , ω, ω + 1}, etc. The next, or second,
limit ordinal is denoted by ω2 = {0, 1, 2, . . . , ω, ω + 1, ω + 2, . . . , ω + n, . . .}
etc. In this way, the ordinals form a transfinite sequence, and indeed any
non-finite ordinal is sometimes called a transfinite number. Thus, we have
0 < 1 < 2 < 3 < · · · < ω < ω + 1 < ω + 2 < · · · < ω2 < ω2 + 1 < ω2 + 2 <
· · · < ω3 < · · · < ωn < · · · < ωω = ω
2 < ω
2 + 1 < ω
2 + 2 < · · · as ordinal numbers. Note also that all the ordinals we have so far displayed in this
example are determined by countable sets. The first uncountable ordinal is
denoted by ω 1 and as a set is the uncountable well-ordered set containing all
the countable ordinals.
•
We are now in a position to consider the principle of transfinite induction.
The reader may note that it is an extension, from N to arbitrary well-ordered
sets, of the well-known strong form
2 of the principle of mathematical induction.
A.1.12 Theorem (Principle of Transfinite Induction) Suppose that A
is any well-ordered set and B is a subset of A which satisfies the statement
that a ∈ B whenever x ∈ B for all x < a. Then B = A.
Proof: If B = A, then A \ B = ∅. By well-ordering of A and therefore of any
subset B of A, A \ B has a first element x 0 , say. But now we have x ∈ B for
2 Also known as course of values induction.