QUESTIONS AND PROBLEMS 557that C £ C. For an object ÷ to belong to C, it no longer suffices that ÷ £
÷; it must also be true that ÷ æ A for some class A, an assumption not made
for the case when ÷ is C. A complete set of axioms for set theory avoiding all
known paradoxes was worked out by Paul Bernays (1888-1977) and Adolf Fraenkel
(1891-1965). It forms part of the basic education of mathematicians today. It is
generally accepted because mathematics can be deduced from it. However, it is
very far from what Cantor had hoped to create: a clear, concise, and therefore
obviously consistent foundation for mathematics. The axioms of set theory are
extremely complicated and nonintuitive, and far less obvious than many things
deduced from them. Moreover, their consistency is not only not obvious, it is even
unprovable. In fact, one textbook of set theory, Introduction to Set Theory, by
J. Donald Monk (McGraw-Hill, New York, 1969), p. 22, asserts of these axioms:
"Naturally no inconsistency has been found, and we have faith that the axioms are,
in fact, consistent"! (Emphasis added.)
Questions and problems
19.1. Bertrand Russell pointed out that some applications of the axiom of choice
are easier to avoid than others. For instance, given an infinite collection of pairs of
shoes, describe a way of choosing one shoe from each pair. Could you do the same
for an infinite set of pairs of socks?
19.2. Prove that C = {÷ : ÷ £ ÷} is a proper class, not a set, that is, it is not an
element of any class.
19.3. Suppose that the only allowable way of forming new formulas from old ones
is to connect them by an implication sign; that is, given that A and  are well
formed, [A B] is well formed, and conversely, if A and  are not both well
formed, then neither is [A => B). Suppose also that the only basic well-formed
formulas are p, q, and r. Show that
]p => r] [[p => q] =• r]is well formed but[[Ñ => Ë => [r =>]]
is not. Describe a general algorithm for determining whether a finite sequence of
symbols is well formed.
19.4. Consider the following theorem. There exists an irrational number that
becomes rational when raised to an irrational power. Proof: Consider the number
ι- \/2
è = v3. If this number is rational, we have an example of such a number. If it
is irrational, the equation è^^2 = y/3 = 3 provides an example of such a number.
Is this proof intuitionistically valid?
19.5. Show that any two distinct Fermat numbers 2^2 ™ +1 and 2^2 " + 1, m < n, are
relatively prime. (Use mathematical induction on n.) Apply this result to deduce
that there are infinitely many primes. Would this proof of the infinitude of the
primes be considered valid by an intuitionist?
19.6. Suppose that you prove a theorem by assuming that it is false and deriving
a contradiction. What you have then proved is that either the axioms you started
with are inconsistent or the assumption that the theorem is false is itself false.