Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

24 RELATIONS [CHAP. 2

Fig. 2-1

There are two things worth noting in the above examples. First of allA×B=B×A. The Cartesian product
deals with ordered pairs, so naturally the order in which the sets are considered is important. Secondly, using
n(S)for the number of elements in a setS, we have:

n(A×B)= 6 = 2 ( 3 )=n(A)n(B)

In fact,n(A×B)=n(A)n(B)for any finite setsAandB. This follows from the observation that, for an ordered
pair(a, b)inA×B, there aren(A)possibilities fora, and for each of these there aren(B)possibilities forb.

The idea of a product of sets can be extended to any finite number of sets. For any setsA 1 ,A 2 ,...,An, the
set of all orderedn-tuples(a 1 ,a 2 ,...,an)wherea 1 ∈A 1 ,a 2 ∈A 2 ,...,an∈Anis called theproductof the sets
A 1 ,...,Anand is denoted by

A 1 ×A 2 ×···×An or

∏n

i= 1

A 1

Just as we writeA^2 instead ofA×A, so we writeAninstead ofA×A×···×A, where there arenfactors all
equal toA. For example,R^3 =R×R×Rdenotes the usual three-dimensional space.

2.3Relations

We begin with a definition.

Definition 2.1: LetAandBbe sets. Abinary relationor, simply,relationfromAtoBis a subset ofA×B.

SupposeRis a relation fromAtoB. ThenRis a set of ordered pairs where each first element comes from
Aand each second element comes fromB. That is, for each paira∈Aandb∈B, exactly one of the following
is true:

(i) (a, b)∈R;we then say “aisR-related tob”, writtenaRb.

(ii) (a, b) /∈R;we then say “ais notR-related tob”, writtena
Rb.

IfRis a relation from a setAto itself, that is, ifRis a subset ofA^2 =A×A, then we say thatRis a relationon A.

Thedomainof a relationRis the set of all first elements of the ordered pairs which belong toR, and the
rangeis the set of second elements.

Althoughn-ary relations, which involve orderedn-tuples, are introduced in Section 2.10, the term relation
shall then mean binary relation unless otherwise stated or implied.