230 RELATIONS: EQUIVALENCE RELATIONS AND PARTIAL ORDERINGS Chapter 7
(c) If A x B = B x A, A # 0, B # a, then A = B
(d) If A x B = 0, then either A = 0 or B = 0Proof (a) Suppose x E A x 0. Then there exist objects a E A and 6 E 0
such that x = (a, 6). But the statement "there exists 6 E 0" is false, so
we have arrived at a contradiction.
(b) Recall Example 9, Article 5.2.
(c) To prove A G B, let x E A; we must prove x E B. Since B # 0,
there must exist y E B. Since x E A and y E B, then (x, y) E A x B. Since
A x B = B x A, then (x, y) E B x A. But this implies, among other
things, that x E B, as desired. The proof is completed by proving B c A
in an analogous fashion.
(d) Suppose the conclusion is false; that is, suppose A # 0 and
B # 0. Then there exist a E A and b E B. But then (a, 6) E A x B, con-
tradicting the hypothesis A x B = @. 0
Note that (a) and (d) of Theorem 2 are converses of each other. Part (b)
may be thought of as a cancellation property; (c) states that the cartesian
product is a highly noncommutative operation.
DEFINITION 2
Let A and B be sets. A relation from A to 6 is any subset R of A x B. If A = 6, we
say that R is a relation on A.The concept "relation" is extraordinarily general. Examples of relations
are very easy to come by. On the other hand, we should not expect, in the
absence of any assumptions about specific properties of a relation, that
many general statements, that is, theorems, can be proved about relations.
As we will soon see, it is only when we look at specific types of relations
that any mathematically interesting theory begins to develop. Since a rela-
tion is among other things a set, specific relations may be described by
either the roster method or the rule method. As was the case in describing
general sets, a rule describing a relation must have the property that, given
an ordered pair (x, y), we must be able to determine, by the rule, whether
or not (x, y) lies in the relation. Relati~ns having infinitely many ordered
pairs must, of course, be described by the rule method. A number of rela-
tions are presented in the following examples.EXAMPLE 1 Let A = {1,2, 3) and B = {w,x, y,z). Then R, = {(l,x),
(2, Y), (3,4), R2 = ((2, w), (2, x), (2, Y), (2941, and R, = {(I, z), (2, 4,
(3, z)} are relations from A to B. The set R, = {(x, I), (x, 3)) is a rela-
tion from B to A. The entire set A x B is itself a relation from A to
B, as is the empty set 0. The relation R2 may be described by the rule
method, namely, R, = ((2,b)lb~ B} or R, = ((a, b)la = 2 and b~ B}.'You should write a description of R,, by using the rule method. 0