Chapter 7 Infinite Sets238
That is:
Rule.Ordinal Induction
8 x:. 8 y 2 next.x/:P.y// IMPLIES P.next.x//;
8 S:. 8 x 2 S:P.x// IMPLIES P.S
x 2 Sx/
8 2 Ord:P./The intuitive justification for the Ordinal Induction Rule is similar to the justifi-
cation for strong induction. We will accept the soundness of the Ordinal Induction
Rule as a basic axiom.
(a)A setxisclosed under membershipif every element ofxis also a subset of
x, that is
8 y 2 x: yx:
Prove that every ordinalis closed under membership.
(b)A sequence
2nC 12 n22 12 0 (7.13)of ordinalsiis called amember-decreasingsequence starting at 0. Use Ordinal
Induction to prove that no ordinal starts an infinite member-decreasing sequence.^12
(^12) Do not assume the Foundation Axiom of ZFC (Section 7.3.2) which says that there isn’tanyset
that starts an infinite member-decreasing sequence. Even in versions of set theory in which the Foun-
dation Axiom does not hold, there cannot be any infinite member-decreasing sequence of ordinals.