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 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.
Previous Page Next Page