12 1. PAIRS, RELATIONS, AND FUNCTIONS

write shorthand (Kathy, Pam). It does matter whether you write (Kathy, Pam)

or (Pam, Kathy), doesn't it?

Now we have the first challenge to our claim that all mathematics can be ex-

pressed in set-theoretical terms. Is it possible to have a set that would convey the

same information as the ordered pair (Kathy, Pam)? Of course, {Kathy, Pam} is

no good, because this is the same as {Pam, Kathy}. But there is a trick.

EXERCISE 3(G): Let a, b be any objects. Show that

{{a},{a,b}} = {{c},{c,d}} iff a = c and b = d.

We define (a, 6) = {{a}, {a, b}}, and call (a, b) an ordered pair as opposed to

the unordered pair {a, 6}. What we have done may look artificial. We could have

defined (a, b) the other way round, or perhaps in an entirely different way. And

besides, although Exercise 3 shows that our notion of ordered pair has the desired

properties, can we really say that {{a}, {a, b}} is the ordered pair (a, 6)? Well, in

what sense is (Kathy, Pam) the statement that "Kathy owes Pam some money?"

Only to the extent that you chose it as a symbol for this statement, or rather, for

the relationship concerning debt between Kathy and Pam. The symbol is appro-

priate, since it captures all the relevant information. In the same way, by defining

(a, b) as {{a}, {a, 6}}, we make an agreement on how we shall communicate certain

phenomena in the language of set theory. We are not making any ontological claims,

i.e., we do not stipulate that (a, b) really is {{a}, {a, b}} in some deep philosophical

sense.

Given three objects a,b,c, we define the ordered triple (a,b,c) by ((a,b),c).

More generally, for n 2, we define the ordered n-tuple of n objects a

0

,... , an_i

by (... ((oo, oi),...), a

n

_i). The Cartesian product of n sets A0,... , An-\ is the

set

AQ x • • • x An-i = {{do, •.. , a

n

-i) : °i € Ai for each i n}.

EXERCISE 4(PG): (a) Let A,B be nonempty sets. Show that ( J I M x B ) =

AuB.

(b) Show that in (a) the assumption that A and B are nonempty can be slightly

weakened, but not entirely omitted.

EXERCISE 5(PG): Show that two ordered triples (ao, a±, a2) and (b0, &i, 62) are

equal iff a* = bi for all i 3.

Let us go back to the monetary relationships of your friends Kathy, Pam, John

and Paul. Your list of who owes money to whom may look like this:

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

If F = {Kathy, Pam, John, Paul} is the set of your friends, then their "indebted-

ness relation" is a subset of F x F. More generally, if A is a set, then any subset

R C A x A will be called a binary relation on A. It does not matter whether or

not R represents anything as interesting as indebtedness.

The indebtedness relation may not carry enough information for you. You may

also want to know how much your friends owe each other. An appropriate list may