Chapter 7 Infinite Sets234
Problems for Section 7.3
Class Problems
Problem 7.27.
Forming a pair.a;b/of itemsaandbis a mathematical operation that we can
safely 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 pair.a;b/as a set.
(a)Explain why representing.a;b/byfa;bgwon’t work.(b)Explain why representing.a;b/byfa;fbggwon’t work either. Hint:What
pair doesff 1 g;f 2 ggrepresent?
(c)Define
pair.a;b/WWDfa;fa;bgg:Explain why representing.a;b/as pair.a;b/uniquely determinesaandb.Hint:
Sets can’t be indirect members of themselves:a 2 anever holds for any seta, and
neither cana 2 b 2 ahold for anyb.
Problem 7.28.
The axiom of choice says that ifsis a set whose members are nonempty sets that
arepairwise disjoint—that is no two sets inshave an element in common —then
there is a set,c, consisting of exactly one element from each set ins.
In formal logic, we could describeswith the formula,
pairwise-disjoint.s/
WWD8x 2 s:x¤;AND
8 x;y 2 s:x¤yIMPLIESx\yD;:Similarly we could describecwith the formula
choice-set.c;s/WWD 8x 2 s: 9 Šz: z 2 c\x:Here “ 9 Šz:” is fairly standard notation for “there exists auniquez.”
Now we can give the formal definition:
Definition(Axiom of Choice).
8 s:pairwise-disjoint.s/IMPLIES 9 c:choice-set.c;s/: