376 ANSWERS AND SOLUTIONS TO SELECTED EXERCISES
- (a) Proof Suppose 0 is not finite, that is, 0 is infinite. Then there exists
a proper subset X of (25 such that X E 0. But the statement X c 0 implies
3x E 0 such that x E 0X. The statement "3x E (21" is a contradiction. O - (c) Proof By the hypotheses, there exists a one-to-one mapping f of A, onto
B, and there exist bijections g and h of A, onto A, and B, onto B,,
respectively. We must produce a one-to-one mapping F of A, onto B,. To
do this, let F = k-' 0 f 0 g. Clearly F is a mapping from A, into B,. Since
h-', f, and g are all one to one, F is one to one [recall Theorem 2(a),
Article 8.21, as required. 0
This result says that the relation 5 is a well-defined relation on equivalence
classes of sets identified with one another by the equivalence relation r.
Viewing < as a relation on equivalence classes of sets, rather than on sets,
Schroeder-Bernstein says that if [A] 5 [B] and if [B] < [A], then [A] = [B],
the requirement for antisymmetry.
Article 8.4
- (c) Proof x
n(U,,,~,)ox~Bandx,,,~,oxandx,
for some A E I o [this step follows from the logical principle stated in Exercise
Il(c),Article3.3]x~BnA,forsomeI~Iox~~,~,(BnA,). - (b) Proof x E f - '(B,) if and only if f(x) E n, ., B, 9 f(x) E n, ,, B, for all
~EJOXE f-l(B,)for allp~~-xi n,., f-'(B,). 0
Article 9.1
- (b) Proof Suppose y and z are both multiplicative inverses of a nonzero
x E F. Then y = 1. y = (yx)y = (zx)y = z(xy) = z - 1 = z, so that y = z, as
required. - (b) False; in the field (R, +, -), - 1 = (- I)-', but - 1 # 1. (c) False; in
the field Z,, 1 = - 1, since 1 + 1 = 0. - (a) False; a = 2 has no square root in the field (Q, +, .). Also, in the field
(Z,, +, a), 0, 1, 2, and 4 are the only squares.
Article 9.2
- (a) Proof We proceed by induction on n. Let S consist of precisely those
positive integers for which the desired result is true. We claim S = N.
(i) 1 E S since x E F, x # 0, implies x2 E 9, by Theorem l(c). (ii) Assume
m E S. To prove m + 1 E S, let x E S, x # 0; we must show x~(~+') E 9. NOW
x~(~+~) = xZm+, = x~~x~, where we note that xZm E 9 by induction hypothesis,
whereas x2 E 9 by Theorem l(c). Hence the product is in 9, by (b) of
Definition 1. 0 - (b) (v) Proof Assume x, y, a E F with x I y and a I 0. To prove ax 2 ay,
we must prove that either ax - ay E 9 or ax = ay. By hypothesis, we have
that either y- x~9 or y= x and either -a~9 or a =O. Now ifa =O or