Chapter 7 Infinite Sets236
(c)The Foundation axiom of set theory says that 2 is a well founded relation
on sets. Express the Foundation axiom as a formula of set theory. You may use
“member-minimal” and “isempty” in your formula as abbreviations for the formu-
las defined above.
(d)Explain why the Foundation axiom implies that no set is a member of itself.Homework Problems
Problem 7.30. (a)Explain how to write a formula, Subsetn.x;y 1 ;y 2 ;:::;yn/, of
set theory^8 that meansxfy 1 ;y 2 ;:::;yng.
(b)Now use the formula Subsetnto write a formula, Atmostn.x/, of set theory
that means thatxhas at mostnelements.
(c)Explain how to write a formula, Exactlyn, of set theory that means thatxhas
exactlynelements. Your formula should only be about twice the length of the
formula Atmostn.
(d)The obvious way to write a formula,Dn.y 1 ;:::;yn/, of set theory that means
thaty 1 ;:::;ynare distinct elements is to write anANDof subformulas “yi¤yj”
for 1 i < jn. Since there aren.n 1/=2such subformulas, this approach
leads to a formulaDnwhose length grows proportional ton^2. Describe how to
write such a formulaDn.y 1 ;:::;yn/whose length only grows proportional ton.
Hint:Use Subsetnand Exactlyn.
Exam Problems
Problem 7.31. (a)Explain how to write a formula Members.p;a;b/of set theory^9
that meanspDfa;bg.
Hint:Say that everything inpis eitheraorb. It’s OK to use subformulas of the
form “xDy,” since we can regard “xDy” as an abbreviation for a genuine set
theory formula.
Apair.a;b/is simply a sequence of length two whose first item isaand whose
second isb. Sequences are a basic mathematical data type we take for granted, but
when we’re trying to show how all of mathematics can be reduced to set theory, we
need a way to represent the ordered pair.a;b/as a set. One way that will work^10
(^8) See Section 7.3.2.
(^9) See Section 7.3.2.
(^10) Some similar ways that don’t work are described in problem 7.27.