1. PAIRS, RELATIONS, AND FUNCTION S 13

look like this:

(Kathy, Pam, 125), (Kathy, John, 63), (Paul, Pam, 87), (Paul, John, 14).

The new relation is a subset of the Cartesian product F x F x Z. Let us call such

relations 3~ary relations. It is now easy to imagine n-ary relations for even larger

n.

To a set theorist, a function f : A —• B from a set A into a set B is simply

a

relation1

/ C A x B such that for each a € A there is exactly one b G B such

that (a, 6) G / . It is common to write /(a) = b instead of (a, b) G / . The set

A is called the domain of f and is denoted by dom(f). Note that in particular,

the empty set is a function with empty domain. For CCA and D C B, we

write f[C] = {b e B : 3a G C (f(a) = 6)} for the ima^e of C under f, and

f~xD = {a e A : f(a) G .D} for the inverse image of D. The image of the whole

domain is called the range of f and is denoted by rng(f). The function / is onto

B o r a surjection, if its range is equal to B. It is one-to-one or an injection if

f(a) ^ /(a') whenever a^ a!. A function that is both a surjection and an injection

is called a bijection.

Note that if / is a function from A into B, and if J3 C C, then / is also a

function from ^4 into C. But if / : A — • B is a surjection, then / : A — C is no£ a

surjection, although the / in both cases is the same set! As you can see, the word

"surjection" is ambiguous. Therefore, we prefer to say that / maps A onto B, and

use the word "surjection" only sporadically, when no confusion can arise.

One handy use of functions is the indexing of families of sets. Suppose / is a

set, A is a family of sets, and / : / — A is a surjection. If we denote f(i) — Ai,

then A = {Ai : i G / } . Thus A becomes an indexed family of sets. Although the

sets A and {Ai : i G 1} are the same, most people find it more convenient to work

with indexed families. For instance, the symbols (}A and f]ieI Ai mean exactly

the same thing, and yet the former notation sometimes causes confusion.

EXERCISE 6(G): Let A be a nonempty family of subsets of a set X, and let B

be a nonempty family of subsets of a set Y. Moreover, let / be a function from X

into y . Show that

(a) r1\JB = \J{f-1B:B€B};

(b)

f-1C\B

=

n{f-1B:BeB};

(c) f-HY\B) - XXf-^B for each B € B.

EXERCISE 7(G): In the notation of the previous exercise, is it always true that

(a) fVA]=\J{f[A]:A€Ah

(b) f[r\A]=n{f[A}:AeAy,

(c) f[X\A] = Y\f[A] for each AeAl

Which inclusions always hold? What can be said if / is assumed to be onto? What

if it is assumed one-to-one?

Here is another use of indexed families: The set of all functions from A into B

is denoted by

AB.

Given {^4^ : i G / } , we can define the Cartesian product

11^ = {/

G 7

( I M : e J}) : Vi el{f(i) G Ai)}.

iei

1If we talk about a relation without mentioning its arity, we always mean a binary relation.