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
To a set theorist, a function f : A —• B from a set A into a set B is simply
/ 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};
(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
Given {^4^ : i G / } , we can define the Cartesian product
11^ = {/
G 7
( I M : e J}) : Vi el{f(i) G Ai)}.
1If we talk about a relation without mentioning its arity, we always mean a binary relation.
Previous Page Next Page