334 CONSTRUCTION OF NUMBER SYSTEMS Chapter 10
We channel our efforts now toward verifying (a) and (b), relying heavily
on the induction postulate in both proofs.
X = (n~Nl(n,p)~s, for some PEN). We claim X = N:
1 E X, since (1, a(m)) E s,, by (i)'.
If n E X, then (n, p) E S, for some p E N, so that (a(n), a(p)) E s,,
by (ii)', and so a(n) E X. By the induction postulate, we con-
clude X = N, as desired.We first show 1 E Y. We know that (1, a(m)) E s,. Now
suppose (1, p) E s,, where p E N. If p # a(m), then the set
s, - ((1, p)) is a proper subset of s, containing the ordered
pair (1, a(m)); that is, satisfying (i)'. Furthermore, if (n, q) E
s, - ((1, p)), then (n, q) E S, and so (o(n), o(q)) E s,. Also,
(a@), 44)) # (1, p), since 1 4 im (a). Hence (49, ~(q)) E S, -
((1, p)). Thus s, - ((1, p)), a proper subset of s,, is a subset
of N x N satisfying both (i)' and (ii)', contradicting the fact
that s, is the smallest such subset. We conclude p = a(m).
We next suppose that n E Y, where n is an arbitrary element
of N. We must prove that o(n) E Y. By the result in (a),
we know that (n, y) E S, for some y E N. Hence our assump-
tion n E Y means that (n, y) E S, for exactly one y E N. Now
from (ii)' and the assumption (n, y) E S, follows the fact that
(o(n), a(y)) E s,. Hence we must prove only that if (a(n), t) E s,
for some t E N, then t = o(y). To do this, let us suppose there
is an element t E N, t # a(y), such that (a(n), t) E s,. As in the
proof of (a), consider the set s, - ((a(n), t)). Again, as in (a),
note that since 1 4 im (a), then a(n) # 1 so that s, - ((~(n), t))
is a proper subset of s, containing the ordered pair (1, a(m)),
so that (i)' is satisfied by s, - ((a(n), t)). To verify that s, -
((~(n), t)) satisfies (ii)', suppose that p E N and that (p, x) E
s, - ((a(n), t)); we must show that (o(p), o(x)) E s, -
((a(n), t)). Since (a(p), o(x)) E S, by (ii)', the only issue is
whether (a@), a(x)) equals (a(n), t); we claim, of course, that
it does not. There are two cases to consider, p = n and p # n.
In the first case the desired inequality is valid, since there is
only one y E N such that (n, y) E s,. For this y, (a(n), a(y)) E
s,, by (ii)', and does not equal (a(n), t), since t # a(y). As to
the second case, if p # n, then (o(p), a(x)) E S, and a(p) # a(n),
since a is one to one. Hence (a(p), a@)) # (a(n), t) and so
(o(p), o(x)) E S, - {(~(n), t)), again, as desired. Therefore s, -
((~(n), t)) satisfies (ii)', and again, we have a contradiction of
the fact that s, is the smallest subset of N x N satisfying both