124 ELEMENTARY APPLICATIONS OF LOGIC Chapter 4
Using this definition, prove:
(a) (a, b) = (c, d) if and only if a = c and b = d
(b) (a, b) = (b, a) if and only if a = b- (Critique and complete.) Beginning with this exercise and continuing in Chap-
ter 5, exercises will occasionally appear under this heading. Each will consist of
three or more parts. Parts (a) and (b) will contain complete "proofs" of theorems,
one correct and in good form, the other having deficiencies. You are to identify
the faulty argument and rewrite it correctly. Each of the remaining parts will con-
tain the first several steps of a possible proof of a theorem. You should either
complete the proof, based on the suggested steps, or else judge the approach in-
appropriate and write a correct proof using a different approach:
(a) THEOREM If M and N are sets, then M n (N u M') E Mn N.
"Proof" Let x E M n (N u M'). To prove x E M n N, we must prove x E M
and - XEN. Since x~Mn(Nu M'), then xeM and XENU M' so that
x E M. Since x E N u M', then either x E N or x E M'. But we know already
that x E M so that x 4 M'. Hence x E N, as desired.
(b) THEOREM If A = {x E N 12x4 - 5x3 - 4x2 + 3x = 0) and B = (31, then
A = B.
"Proof" Since 2(3)4 - 5(3)3 - 4(3)2 + 3(3) = 162 - 135 - 36 + 9 = 0, so that 3
satisfies the equation defining A, we conclude A = B, as desired.
(c) THEOREM If A, B, and C are sets with A c B, then A n C c B n C.
Start of "Proof" Let x be an arbitrary element of A....
(d) THEOREM If X and Y are sets, then Y E X u (Y n X').
Start of "Proof" Let w E Y. We must prove that either w E Xor w E Y n X'. Suppose
wex....
(e) THEOREM If A and B are sets, then A n (B - A) = 0.
Start of "Proof" We use a mutual inclusion approach. To prove A n (B - A) c 0,
let x be an arbitrary element of A n (B - A). We must prove x E 0....
Infinite Unions and Intersections
One of the nice applications of the language of quantifiers to set theory is
in the definition of union and intersection of infinite collections, or families,
of sets. In particular, we-consider in this article collections of sets indexed
by the set N of all positive integers.DEFINITION 1
The collection of sets d = {A,, A,, A,,.. .) = {A~I~E N), containing a set A,
corresponding to each positive integer i (where some universal set U contains
each set A, in the collection) is called afamily (or collection) of sets indexed by the
set N of all positive integers. A positive integer i used to label a set A, in the
collection is called an index.