Bridge to Abstract Mathematics: Mathematical Proof and Structures

116 ELEMENTARY APPLICATIONS OF LOGIC Chapter 4

DEFINITION 1

Let A and B be sets:

(a) We say that A equals B (denoted A = 6) if and only if the statement

(Vx) ( (x E A) t, (x E B) ) is true.

(b) We say that A is a subset of B (A G B) if and only if the statement

(Vx) ( (x E A) + (x E B) ) is true.

PROVING SET INCLUSION

EXAMPLE 1 Prove that 0 G A for any set A [Fact 1 (7), Article 1.41.

Solution Let A be an arbitrary set. By definition, @ G A has the meaning

(Vx)[(x E a) -+ (x E A)]. But the predicate x E @ is false for any object

x, so that the conditional (x E 0) -+ (x E A) is true for any x, regard-

less of the truth value of the predicate x E A. Hence the statement

(Vx)[(x E 0) -+ (X E A)] is true, so that 0 c A is true, as claimed.

EXAMPLE 2 Prove that A c A for any set A [Fact 1 (2), Article 1.41.

Solution Let A be an arbitrary set. By definition, A r A has the meaning

(Vx)[(x E A) -+ (x E A)]. But the predicate (x E A) -+ (x E A) has the form

p -+ p for any substitution of a particular object for x and so is true for

any such substitution, since p -+ p is a tautology [Theorem 2(a), Article

2.31. Hence the statement (Vx)[(x E A) + (x E A)] is true, as is (conse-

quently) the statement A c A.

EXAMPLE 3 Prove that, for any sets A and B, A = B if and only if A E B

and B G A [Fact 1(4), Article 1.4).

Solution The definition of A = B is (Vx)[(x E A) * (x E B)], whereas A E B

is defined by (Vx)[(x E A) -+ (x E B)]. Therefore our theorem asserts

that (Vx)[(x E A) - (x E B)] is logically equivalent to the conjunction

(Vx)[(x E A) + (x E B)] A (Vx)[(x E B) -+ (x E A)]. Using the tautology

/

(p - q) ++ [(p -+ q) A (q -+ p)] [Theorem l(m), Article 2.31, and the

theorem (Vx)(p(x) A q(x)) c* (Vx)(p(x)) A (Vx)(q(x)) of the predicate cal-

culus [Theorem l(~), Article 3.31, we observe (Vx)[(x E A) - (x E B)]

* (Vx)[((x E A) -+ (x E-B)) A ((x E B) -+ (x E A))]

++ (Vx)[(x E A) -+ (x E B)] A (Vx)[(x E B) + (x E A)], as desired.

Each of the results in Examples 1 through 3 is an important foundational

result in set theory. Each can be paraphrased in a form that is perhaps

more easily remembered than the formal statement. The first states "the

empty set is a subset of every set," the second is "every set is a subset of it-

self," while the third has the meaning "two sets are equal if and only if each

is a subset of the other."