8.4 ARBITRARY COLLECTIONS OF SETS 291EXAMPLE 1 Let f: X -, Y. Prove that the image under f of the intersec-
tion of any collection of subsets of X is a subset of the intersection of
the images under f of the sets in the collection.
Solution Our first problem is to formulate in symbols the statement to be
proved. Let d represent the given collection of subsets of X. An in-
correct approach is to write d = (A,, A,, A,,... ) and to represent the
desired conclusion f(ng, A,) E f(Ai); this notation assumes the
collection to be countably infinite, which it may or may not be. Instead,
we write d = (A, I A E I}, where I is an arbitrary set. We must prove
fen,., A,) n,., f(~3 ~et y Efcn,., A,). hen y =m for some
x E n, , , A,. Since y = f(x) and x E A, for all A E I, then y E f(A3 for
all A E I; that is, y E n,, , f(A,), as desired.
Another important definition involving arbitrary collections of sets is a
generalization of the notion of the cartesian product of a finite number of
sets.
DEFINITION 3
Let {A,II E I) be an arbitrary collection of sets. We define the direct product
HAG, A, of the sets in the collection to be the set of all mappings f: I -r U, ., A,
such that f(A) E AA for each A E I.If I is a finite set, say, I = (1,2,... , n), then each element of the direct
product is essentially an n tuple (a,, a,,... , a,), where each ai E A,, corre-
sponding to the familiar cartesian product in that special case. Each func-
tion of the type noted in Definition 3 is called a choice function, since
defining it amounts to "choosing" an element from each of the sets A, in
the collection. Clearly if one of the sets in the collection is empty, no choice
function exists. It may seem self-evident that a choice function always exists
for an arbitrary collection of nonempty sets, but in fact this statement, like
the continuum hypothesis, can neither be proved nor disproved on the basis
of the usual axioms of set theory. It is common (although not uncontro-
versial) in modern-day mathematics to assume it as an axiom; the proofs of
many important theorems at the graduate and research levels depend on
this so-called axiom of choice. To recapitulate, the axiom of choice states
that if (A, I A E I)- is a family of nonempty sets, then n,, , A, is nonempty.
Stated differently, there exists a choice function, that is, a mapping f from
I into U,,, A, such that f(A) E A* for each A E I.
Exercises
- Let d = (~~11 E I} be a collection of subsets of a set X and let B G X. Prove: