Transfinite Induction and General Topology
231
In order to see this, suppose f, g : W → Z are isomorphisms. We show
f = g. Assume this is not the case, and let w 0 ∈ W be the ≤ W -least w
such that f (w) = g(w); suppose in fact that f (w 0 ) < Z g(w 0 ) for the sake
of argument. Let w 1 ∈ W be such that g(w 1 ) = f (w 0 ). Then w 1 = w 0 .
If w 1 < W w 0 , then by minimality of w 0 and monotonicity of f , we obtain
g(w 1 ) = f (w 1 ) < W f (w 0 ) = g(w 1 ), which is impossible. If w 0 < W w 1 , then
by monotonicity of g, we have f (w 0 ) < Z g(w 0 ) < Z g(w 1 ) = f (w 0 ), which is
also impossible. So Statement (2) holds.
We now turn to the proof of the theorem.
Define the relation R from X to Y by R(x, y) if and only if the initial
segments {w ∈ X | w ≤ X x} and {v ∈ Y | v ≤ Y y} are isomorphic, where
x ∈ X and y ∈ Y . First note that R(x, y 1 ) and R(x, y 2 ) implies y 1 = y 2 by
Statement (1). So R is a partial function. By symmetry, transitivity, and (1)
again, R is also injective.
We next show that dom(R) is an initial segment of X. Suppose x 2 ∈
dom(R), say, R(x 2 , y 2 ), and let x 1 < X x 2 . Let f be the isomorphism between
the initial segments corresponding to x 2 and y 2 . Then the initial segments
corresponding to x 1 and f (x 1 ) are also isomorphic, so R(x 1 , f (x 1 )), and hence
x 1 ∈ dom(R). We have also shown that R is order-preserving.
A similar argument shows that the range of R is an initial segment of Y .
Hence, R is an isomorphism from an initial segment I(x 0 ), say, of X to an
initial segment J(y 0 ), say, of Y ; thus, R(x 0 , y 0 ) holds.
Now consider the following cases. If I(x 0 ) = X, but J(y 0 ) = Y , then case
(a) holds. If I(x 0 ) = X, but J(y 0 ) = Y , then case (b) holds. If I(x 0 ) = X
and J(y 0 ) = Y , then case (c) holds. Suppose finally that I(x 0 ) = X and
J(y 0 ) = Y . Let x 1 be the first element of X \ I(x 0 ) and y 1 be the first element
of Y \ J(y 0 ); then x 1 is not in the domain of R (and y 1 is not in the range
of R). But clearly I(x 0 ) ∪ {x 1 } is the initial segment I(x 1 ) and J(y 0 ) ∪ {y 1 }
is the initial segment J(y 1 ), and, furthermore, I(x 1 ) and J(y 1 ) are clearly
isomorphic by an isomorphism which, by (2), must be an extension of R. We
therefore obtain the contradiction that x 1 is in the domain of R.
Hence, only one of (a), (b), (c) holds, as required.
•
Next, we state without proof a well-known theorem usually attributed to
E. Zermelo. This theorem has the consequence that any set is a carrier set for
some ordinal, see [Halmos, 1998] for details.
A.1.7 Theorem (The Well-Ordering Theorem) Every set can be wellordered.
A.1.8 Definition An ordinal or ordinal number is an equivalence class of a
well-ordering under the equivalence relation of isomorphism.
The ordinals themselves can be ordered as follows. First, for any wellordered set A, let #A denote the equivalence class of A under the equivalence
relation of isomorphism. Suppose that α = #A and β = #B are ordinals. We
231
In order to see this, suppose f, g : W → Z are isomorphisms. We show
f = g. Assume this is not the case, and let w 0 ∈ W be the ≤ W -least w
such that f (w) = g(w); suppose in fact that f (w 0 ) < Z g(w 0 ) for the sake
of argument. Let w 1 ∈ W be such that g(w 1 ) = f (w 0 ). Then w 1 = w 0 .
If w 1 < W w 0 , then by minimality of w 0 and monotonicity of f , we obtain
g(w 1 ) = f (w 1 ) < W f (w 0 ) = g(w 1 ), which is impossible. If w 0 < W w 1 , then
by monotonicity of g, we have f (w 0 ) < Z g(w 0 ) < Z g(w 1 ) = f (w 0 ), which is
also impossible. So Statement (2) holds.
We now turn to the proof of the theorem.
Define the relation R from X to Y by R(x, y) if and only if the initial
segments {w ∈ X | w ≤ X x} and {v ∈ Y | v ≤ Y y} are isomorphic, where
x ∈ X and y ∈ Y . First note that R(x, y 1 ) and R(x, y 2 ) implies y 1 = y 2 by
Statement (1). So R is a partial function. By symmetry, transitivity, and (1)
again, R is also injective.
We next show that dom(R) is an initial segment of X. Suppose x 2 ∈
dom(R), say, R(x 2 , y 2 ), and let x 1 < X x 2 . Let f be the isomorphism between
the initial segments corresponding to x 2 and y 2 . Then the initial segments
corresponding to x 1 and f (x 1 ) are also isomorphic, so R(x 1 , f (x 1 )), and hence
x 1 ∈ dom(R). We have also shown that R is order-preserving.
A similar argument shows that the range of R is an initial segment of Y .
Hence, R is an isomorphism from an initial segment I(x 0 ), say, of X to an
initial segment J(y 0 ), say, of Y ; thus, R(x 0 , y 0 ) holds.
Now consider the following cases. If I(x 0 ) = X, but J(y 0 ) = Y , then case
(a) holds. If I(x 0 ) = X, but J(y 0 ) = Y , then case (b) holds. If I(x 0 ) = X
and J(y 0 ) = Y , then case (c) holds. Suppose finally that I(x 0 ) = X and
J(y 0 ) = Y . Let x 1 be the first element of X \ I(x 0 ) and y 1 be the first element
of Y \ J(y 0 ); then x 1 is not in the domain of R (and y 1 is not in the range
of R). But clearly I(x 0 ) ∪ {x 1 } is the initial segment I(x 1 ) and J(y 0 ) ∪ {y 1 }
is the initial segment J(y 1 ), and, furthermore, I(x 1 ) and J(y 1 ) are clearly
isomorphic by an isomorphism which, by (2), must be an extension of R. We
therefore obtain the contradiction that x 1 is in the domain of R.
Hence, only one of (a), (b), (c) holds, as required.
•
Next, we state without proof a well-known theorem usually attributed to
E. Zermelo. This theorem has the consequence that any set is a carrier set for
some ordinal, see [Halmos, 1998] for details.
A.1.7 Theorem (The Well-Ordering Theorem) Every set can be wellordered.
A.1.8 Definition An ordinal or ordinal number is an equivalence class of a
well-ordering under the equivalence relation of isomorphism.
The ordinals themselves can be ordered as follows. First, for any wellordered set A, let #A denote the equivalence class of A under the equivalence
relation of isomorphism. Suppose that α = #A and β = #B are ordinals. We