Chapter 5 Infinite Sets110
Problem 5.14.
For any sets,A, andB, letŒA!Bçbe the set of total functions fromAtoB.
Prove that ifAis not empty andBhas more than one element, thenNOT.Asurj
ŒA!Bç/.
Hint:Suppose thatis a function fromAtoŒA!Bçmapping each element
a 2 Ato a functionaWA!B. Pick any two elements ofB; call them 0 and 1.
Then define
diag.a/WWD(
0 ifa.a/D1;
1 otherwise:Problems for Section 5.4
Class Problems
Problem 5.15.
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/WWD 8x 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/:The only issue here is that Set Theory is technically supposed to be expressed
in terms ofpureformulas in the language of sets, which means formula that uses
only the membership relation, 2 , propositional connectives, the two quantifies 8
and 9 , and variables ranging over all sets. Verify that the Axiom of Choice can be
expressed as a pure formula, by explaining how to replace all impure subformulas
above with equivalent pure formulas.
For example, the formulaxDycould be replaced with the pure formula 8 z:z 2
xIFFz 2 y.