Bridge to Abstract Mathematics: Mathematical Proof and Structures

7.1 RELATIONS 229

DEFINITION 1

(a) We say that two ordered pairs of objects (a, b) and (y, z) are equal,

denoted (a, b) = (y, z), if and only if a = y and b = z.

(b) Given sets A and B, we say that an object x is an element of the cartesian

product A x B if and only if there exist a E A and b E B such that x = (a, b).

In the following theorems we gather properties of cartesian product,
some of which were listed as exercises earlier in the text, and provide proofs
in selected cases.

THEOREM 1

Let W, X, Y, and Z be arbitrary sets. Then:

(a) (XuY)xZ=(XxZ)u(YxZ)

(b) (XnY)xZ=(XxZ)n(YxZ)

(c) (X-Y)xZ=(XxZ)-(YXZ)

(d) (WxX)n(YxZ)=(Wn Y) x(XnZ)

(e) (Wx X)u(YxZ)=(Wu Y) x (XuZ)

(f) If WsXand Y=Z,then Wx YsXxZ.

Partial proof All except (f) are statements of set equality and so may be

proved by a mutual inclusion approach. In some cases, such as (a) and

(b), it is possible to write a string of valid biconditional statements (as

in Example 10, Article 4.1). We will take the latter approach to prove (a).

(a) An object a is an element of (X u Y) x Z -

a = (x, z) for some objects x E X u Y and z E Z e

a = (x, z) where either x E X or x E Y, and z E Z o

a = (x, z) where either x E X and z E 2, or x E Y and z E Z -

either a E X x Z or a E Y x Z e>

(c) We will prove that (X x 2) - (Y x 2) G (X - Y) x 2, leaving the

reverse inclusion to you. Suppose a E (X x Z) - (Y x 2). Since a E X x 2,

then a = (x, z) where x E X and z E Z. To show a E (X - Y) x Z, we need

show only that x E X - Y. We proceed indirectly. If x 4 X - Y, then since

x E X, we would have x E X n Y, due to the theorem X = (X n Y) u

(Xn Y')=(Xn Y)u(X- Y),sothatx~Y. Butthenx~Yandz~Zso

that a = (x, z) E Y x 2. But this contradicts the assumption a E (X x 2) -

(Y x 2). 0

THEOREM 2

Let A, B, and C be arbitrary sets. Then:

(a) Ax@=@xA=@

(6) If A x B = A x C and A # 0, then B = C.