The set constructions I've considered so far --- things like , , --- have involved finite numbers of sets. It's often necessary to work with infinite collections of sets, and to do this, you need a way of naming thme and keeping track of them.
Let I be a set. A collection of sets indexed by I consists of a collection of sets , one set for each element .
Example. Let . A collection of sets indexed by I consists of four sets , , , and . For example,
Note that ; some of the sets in the collection may be identical.
Here's another collection of sets indexed by I:
Example. Let . A collection of sets indexed by I is an infinite collection of sets , , , ....
Here is a collection of sets indexed by I:
In general, if n is a positive integer, then .
Here's another collection of sets indexed by I:
In general, consists of the integers which are divisible by n.
Example. Let . Here's a collection of sets indexed by I:
Since is uncountable, I can't list the sets in this collection. Here are a couple of the sets:
Definition. Let I be a set, and let be a collection of sets indexed by I.
Notation. If you have a collection of sets indexed by the natural numbers
you usually write
for the union and intersection, respectively.
Example. Consider the following collection of sets indexed by :
This is a collection of intervals, which I've drawn below. They actually lie on top of one another on the x-axis; I've "pulled them up" so you can see them separately.
In this case,
The first statement is pretty clear, since all the intervals are contained in , and ; I won't write out the proof.
For the second statement, I have to show that contains no elements. I'll give a proof by contradiction.
Suppose on the contrary that . In particular, , so I know .
Choose a positive integer n such that ; I can do this because . Then , which contradicts .
This shows that there is no such element x, so the intersection is empty.
Example. Prove that .
A common technique in set equality proofs is to show that the left side is contained in the right side and the right side is contained in the left side. This is what I'll do here.
First, I'll do the easy inclusion --- the right side is contained in the left side. The only element of the right side is 0. For every , I have
Since this is true for all , it follows that . Therefore, .
Next, I have to show that . Let . I have to show that , i.e. that .
First, suppose . Since , there is an integer such that . (Since the numbers , , , ... approach 0, eventually they become less than any positive number.) Then , contrary to my assumption that . Therefore, is ruled out.
Next, suppose . Since , there is an integer such that . Then , contrary to my assumption that . Therefore, is ruled out.
Since I've ruled out and , it follows that . This is what I wanted to prove. Hence, .
This completes the proof that .
Example. Prove that .
First, I'll show that the left side is contained in the right side. Let . I have to show that .
Since , I know that for some . This means that
But --- the proof is
Therefore, . This means that . Hence, .
Next, I'll show that the right side is contained in the left side. Suppose . I have to show that .
Since , I have . Now , so for some I must have . Note that this automatically implies that . Since I already know , I have . This means that . Hence, . Therefore, .
This completes the proof that .
Definition. Let S and T be sets. The Cartesian product of S and T is the set consisting of all ordered pairs , where and .
Warning: is not the same as unless .
Example. Let and . Then
Notice that S and T are not subsets of . There are subset which "look like" S and T; for example, here's a subset that "looks like" S:
But this is not S: The elements of S are a, b, and c, whereas the elements of the subset U are pairs.
It's often useful to picture Cartesian products as points in a grid:
Example. consists of all pairs , where . Of course, this is the same thing as the the plane:
Copyright 2008 by Bruce Ikenaga