14

1. PAIRS, RELATIONS, AND FUNCTIONS

EXERCISE 8(PG): Let A% = {0},Am = {0,{0}}. Using only braces and the

empty set symbol, list all elements of the sets A% x A^y and rhe{0,{0}} ^»-

As you can see, the two sets of Exercise 8 are not the same. However, both sets

A$ x A{$} and IIt€{0{0}}^

a r e cau"ed

"Cartesian products." Although the two sets

are formally different, there exists a canonical one-to-one map H from riie{0,{0}} ^

onto A$ x A{0} which is defined by H(f) = (/(0), /({0}))- Therefore, we shall use

the phrase "Cartesian product" in both of its meanings. In particular, the symbol

A2

may stand for A x A or for

2A.

In the rare cases where it matters, we shall

specify which of the two interpretations of this symbol is meant. For n 2, unless

specified otherwise, the symbol An refers to the set nA, where n = {0,1,... , n— l}. 2

Let us go back to the set F = {Kathy, Pam, John, Paul} of your friends. Let

D denote the indebtedness relation on F that was considered above. This relation

has the following property: If (x, y) G D, then (y, x) £ D. If a relation has this

property, then it is called asymmetric. In contrast, a relation R on a set X is

antisymmetric if for all x, y G X, (x,y) G R and (y,x) G R implies that x = y. A

relation R on a set X is symmetric if for all x, y G X, whenever (x,y) G R then also

(y,x) G R. An example of a symmetric relation on the set JF is the "same gender

relation" S: a pair (x, y) G S iff x and y are of the same gender. Thus

S = {(Kathy, Pam), (Pam, Kathy), (John, Paul), (Paul, John),

(Kathy, Kathy), (Pam, Pam), (John, John), (Paul, Paul)}.

This relation has two more interesting properties:

• It is reflexive, i.e., (x,x) G S for all x G F.

• It is transitive, i.e., if both (x,y) G S and (y,z) G S, then (x,z) G S.

A relation flona set X is irreflexive if (x, #) ^ it!. Note that a nonreflexive

relation is not necessarily irreflexive.

EXERCISE 9(G): Define a relation P on F by putting (x, y) e P itt x and y are

of opposite gender. Show that this relation is symmetric, but irreflexive and not

transitive.

A binary relation that is reflexive, symmetric and transitive is called an equiva-

lence relation. Here is an example of an equivalence relation on the set of all natural

numbers N:

(x, y) G CQ iff there are k,£,m G N such that m 6,

6k + m = x and 6£ H- m = y.

In other words, (x,y) G CQ if and only if these two numbers are congruent mod 6.

Given an equivalence relation R on a set X, we can form the set of equivalence

classes of R. For x G X, let the equivalence class of x be the set X/R = {y G X :

(x,y) G i?}. The element x is called a representative of the equivalence class X / R .

We also denote X/R = {#/# : x G X}. Note that the equivalence classes of the

relation CQ are the congruence classes mod 6, and the equivalence classes of the

"same gender relation" are the set of all females in the group and the set of all

males in the group.

2 This treatment of the natural numbers as sets will be discussed in Chapter 4.