7.4. Does All This Really Work? 237
is to represent.a;b/as
pair.a;b/WWDfa;fa;bgg:
(b)Explain how to write a formula Pair.p;a;b/, of set theory^11 that meanspD
pair.a;b/.
Hint:Now it’s OK to use subformulas of the form “Members.p;a;b/.”
(c)Explain how to write a formula Second.p;b/, of set theory that meanspis a
pair whose second item isb.
Problems for Section 7.4
Homework Problems
Problem 7.32.
For any setx, define next.x/to be the set consisting of all the elements ofx, along
withxitself:
next.x/WWDx[fxg:
So by definition,
x 2 next.x/andxnext.x/: (7.12)
Now we give a recursive definition of a collection, Ord, of sets calledordinals
that provide a way to count infinite sets. Namely,
Definition.
;2Ord;
if 2 Ord;then next./ 2 Ord;
ifSOrd;then[
2 S 2 Ord:There is a method for proving things about ordinals that follows directly from
the way they are defined. Namely, letP.x/be some property of sets. TheOrdinal
Induction Rulesays that to prove thatP./is true for all ordinals, you need only
show two things
IfPholds for all the members of next.x/, then it holds for next.x/, and ifPholds for all members of some setS, then it holds for their union.(^11) See Section 7.3.2.