By Toby Bartels

**Empty set**: the set with no elements.
Originally denoted by the Scandivanian O with a slash through it
("Ø"),
it's now more commonly denoted as a numeral zero with a slash through it.
(Anyone who tells you it's a Greek Phi is just wrong.)
Of course, you could also say "{}".
I will say "Ø" on this crib sheet.

**Collection**: a set whose elements are themselves sets,
or possibly even sets with some extra structure (such as manifolds).
While an ordinary set just has elements,
a collection has elements' elements
(the elements of the sets which are its elements).
Since the elements of Ø are all sets (trivially),
Ø is also a collection, the empty collection.

**Subset**: a set which is part of another set.
If *X* and *Y* are sets,
then *Y* is a subset of *X*
if and only if, for all possible elements *x*,
*x* is an element of *X*
whenever *x* is an element of *Y*.
It's possible that
*X* has no elements other than those of *Y*;
then *X* = *Y*.
More often, however,
*X* will have additional elements which *Y* doesn't share.
Ø is a subset of every other set (as well as of itself).

**Power set**:
For every set *X*,
there is a collection ¶*X* of all the subsets of *X*.
Note that *X* will itself belong to ¶*X*, as will Ø.
This power set is usually denoted with some fancy form of the letter Pe,
not necessarily "¶".

**Union**:
If *C* is a collection of sets,
then the set of all of *C*'s elements' elements is
U*C*, the union of *C*.
That is, *x* in U*C* if and only if
*x* in *X* for some *X* in *C*.
The union is usually denoted by a big, thin lined curve in the shape of a U,
rather than by an actual letter U.
Notice that, if *C* is the empty collection Ø,
then U*C* is also Ø.
The union is most often encountered when *C* is rather small,
and then you can see "*X* U *Y*"
for U{*X*, *Y*},
"*X* U *Y* U *Z*"
for U{*X*, *Y*, *Z*},
or even
"*X*_{1} U ··· U
*X*_{n}"
for U{*X*_{1}, ..., *X*_{n}}.
(When it appears between symbols instead of in front of them,
the union symbol is slightly smaller.)
The last can also be written
"U_{i=1}^{n} *X*_{i}",
where the "*i* = 1" and "*n*"
should appear directly above and below the union symbol,
just like in a summation formula.

Exercise to see if you're paying attention:
What is U¶*X*, the union of the power set of *X*?

**Intersection**:
Recall that *x* in U*C* if and only if
*x* in *X* for *some* *X* in *C*.
Well, *x* in I*C* if and only if
*x* in *X* for *all* *X* in *C*.
The real symbol for intersection is upside down of the symbol for union,
never anything like the letter I.
All the notational variations listed for union above
apply to intersection the same way.

Intersection of the empty collection:
Theoretically, IØ would be the set of everything.
Aside from creating many interesting (but irrelevant to us) paradoxes,
this possibility may violate the spirit of the context you're working in.
For example,
suppose *C* is an arbitrary subcollection of ¶*X*.
Then we'd like U*C* and I*C* to be subsets of *X*.
This will always happen for the union,
and it will always happen for the intersection if *C* is nonempty.
In order to make IØ a subset of *X* as well,
define it to be *X*.
This will work out quite well in what follows.

Exercise to see if you're paying attention:
What is I¶*X*, the intersection of the power set of *X*?

Summary exercise that's a little deeper:
Start with ¶*X*.
The smallest subcollection of ¶*X* is the empty collection Ø,
while the largest subcollection of ¶*X* is ¶*X* itself.
Compare UØ, IØ, U¶*X*, and I¶*X*.
What do you think?

Exercise that links with the topology crib sheet:
Recall that
the formal definition of topology that Michael gave
consisted of a set *X*
along with a collection *T* of subsets of *X*,
such that *T* satisfied 3 conditions.
Making judicial use of the concept of the empty collection,
how can you reduce this to 2 conditions?

**Complement**:
If *Y* is a subset of *X*,
the complement of *Y* in *X* is
the set of all elements of *X* which are *not* in *Y*.
The complement of *Y* is denoted
"*Y*'", "*Y*^{c}",
"*Y*" with a bar over it,
or any of a number of different things.
If you want to make mention of *X* explicit,
say "*X* \ *Y*"
(which is sometimes incorrectly written with a minus sign).

Major theorem (de Morgan):
If *X* and *Y* are both subsets of some larger set,
then (*X* U *Y*)' = *X*' I *Y*'
and (*X* I *Y*)' = *X*' U *Y*'.
This works if you take unions and intersections of more or fewer than 2 sets,
too.
Exercise: How does this relate to the summary exercise above?
(This is kind of a trick question.)

OK, take a little breather now.

**Identity function**:
For every set *X*,
there is a special function
1_{X}: *X* -> *X*:
*x* |-> *x*.
This is the identity function on *X*.
The identity function is also called
"id_{X}"
or "*I*_{X}".

**Injection, monic, one to one**:
These are all the same thing.
A function *f*: *X* -> *Y* is one to one
if *f*(*x*) never equals *f*(*y*)
unless *x* = *y*.
Thus, if you're told what *f*(*x*) is,
then you automatically know what *x* is.
In other words, the equation *f*(*x*) = *y*
has at most 1 solution for *x*.
(Of course, it might not have any.)
Some people use the term "one to one" to mean one to one and onto.
You'll usually see "one-to-one" spelled with hyphens,
but I don't believe in hyphens.

**Surjection, epic, onto**:
These are all the same thing.
A function *f*: *X* -> *Y* is onto
if every *y* in *Y*
is *f*(*x*) for some *x* in *X*.
In other words, the equation *f*(*x*) = *y*
has at least 1 solution for *x*.
(Of course, it might have more than 1.)

**Range**:
If *f*: *X* -> *Y*,
then the range of *f* is the set
{*f*(*x*) | *x* in *X*},
that is the set of all elements of *Y*
which are *f*(*x*) for some *x* in *X*.
Note that the range of *f* is a subset of the codomain *Y*.
If *f* is not onto,
then we can shrink the codomain down to the range,
so that *f* becomes onto.
(Of course, it's a different *f* now,
since the codomain is different.)

**Image**:
If *f*: *X* -> *Y*
and *A* is a subset of *X*,
then the image *f*(*A*) of *A* under *f*
is {*f*(*x*) | *x* in *A*},
that is the set of all elements of *Y*
which are *f*(*x*) for some *x* in *A*.
In this way, *f* defines a function (also called "*f*")
from ¶*X* to ¶*Y*.
The image of Ø is Ø. The image of the domain is the range.
Sometimes people will say "the image of *f*"
to mean the image of the domain of *f*, that is the range,
especially in the sort of context
where they'd say "map" instead of "function".
For example,
I did this in the definition of embedding
on the topology crib sheet.

**Preimage**:
If *f*: *X* -> *Y*
and *A* is a subset of *Y*,
then the preimage *f*^{-1}(*A*)
of *A* under *f*
is {*x* | *f*(*x*) in *A*},
that is the set of all *x* in *X*
such that *f*(*x*) is an element of *A*.
In this way,
*f* defines a function (called "*f*^{-1}")
from ¶*Y* to ¶*X*.
The preimage of Ø is Ø.
The preimage of the codomain, or of the range,
or of anything between the range and the codomain,
is the domain.

Exercise:
If you start with the codomain, take the preimage, and then take the image,
you get the range, which is a subset of the codomain.
Is *f*(*f*^{-1}(*A*))
always a subset of *A*?
Is *f*^{-1}(*f*(*A*))
always a subset of *A*?
How about the other way around?

Related exercise:
Is there a formula for *f*(*A* U *B*)
in terms of *f*(*A*) and *f*(*B*)?
How about *f*(*A* I *B*)?
How about *f*^{-1}(*A* U *B*)?
How about *f*^{-1}(*A* I *B*)?

Related exercise:
If *f*: *X* -> *Y* is one to one or onto,
what does this say about *f*: ¶*X* -> ¶*Y*?
How about *f*^{-1}: ¶*Y* -> ¶*X*?

**Bijection**: a function which is both one to one and onto.
If *f* is a bijection,
then the equation *f*(*x*) = *y*
has *exactly* 1 solution for *x*.

**Inverse**:
Suppose *f*: *X* -> *Y* is a bijection.
If *y* in *Y*,
then there is a unique element *x* in *X*
such that *f*(*x*) = *y*.
Therefore, that equation defines a function from *Y* to *X*.
This function, like the preimage, is called "*f*^{-1}".
Notice that, if *f*: *X* -> *Y*
and *f*^{-1}: *Y* -> *X*
are inverses,
then so are *f*: ¶*X* -> ¶*Y*
and *f*^{-1}: ¶*Y* -> ¶*X*.

**Composition**:
If *f*: *X* -> *Y*
and *g*: *Y* -> *Z*,
then you can get from *X* to *Z*
by combining *f* and *g*
into a single function *g* ° *f*.
*g* ° *f* is defined to be
*x* |-> *g*(*f*(*x*)).
If *f*: *X* -> *Y*,
then 1_{Y} ° *f* =
*f* = *f* ° 1_{X}.
If you think of ° as multiplication,
now you know
where the notation "1" for identity functions comes from.
If *f* is also a bijection,
then *f* ° *f*^{-1} = 1_{Y}
and *f*^{-1} ° *f* = 1_{X}.
So, now you know
where the notation "^{-1}" for inverses comes from.

OK, take another little breather now.

**Sequence**:
a function whose domain is one of the sets above.
A sequence of 0 terms (or empty sequence)
is a function whose domain is Ø.
A sequence of *n* terms (or finite sequence of length *n*)
is a function whose domain is {1, ..., *n*}.
A sequence of infinity terms (or infinite sequence)
is a function whose domain is {1, 2, 3, ...}.
If *f* is a sequence,
write "*f*_{i}"
instead of "*f*(*i*)".
The sequence can be given explicitly in the form
"(*f*_{1}, *f*_{2}, *f*_{3}, ...)".
An **ordered pair** is simply a finite sequence of length 2.

**Family**:
A family is a function whose codomain is more important than its domain.
A sequence is a good example of a family,
since nothing is more obvious than the set {1, ..., *n*}.
As with a sequence, we use subscripts,
writing "*f*_{i}"
instead of "*f*(*i*)".
In fact, we usually don't even use a symbol like "*f*",
prefering instead to use, say, "*x*"
if the codomain is called "*X*".
In the next section,
I'll be working with families whose codomains are collections.
Since the elements of collections are sets,
such families are called "families of sets".
An **index set** is the domain of a family.
If *I* is an index set,
you may see notation like
"(*x*_{i} | *i* in *I*)"
being used for the family.
If the family is a sequence,
the notation might be
"(*x*_{i} |
*i* = 1, ..., *n*)".
For example, (*i*^{2} | *i* = 1, 2, 3, ...)
is a family of natural numbers
which maps every index number to its square.
Sometimes people will be sloppy
and use curly braces "{" and "}"
instead of parentheses "(" and ")".
Strictly speaking,
{*x*_{i} | *i* in *I*}
is the *range* of the family, not the family itself.
I will not be so sloppy here.

**Constant family**:
If *x* in *X* and *I* is another set,
we can make a constant family *c* whose index set is *I*.
Simply say that, for all *i* in *I*,
*c*_{i} = *x*.
Then whenever the notation "*c*_{i}"
might show up,
you can just replace it with "*x*" instead.
You can also express this family as
"(*x* | *i* in *I*)".
This is a very simple concept, but it's important.

Operations on families which you already know about:
If *x* is an infinite sequence of real numbers,
then *x* is actually a family whose index set is infinity.
Then the sum of the sequence is written
"+_{i=1}^{infinity} *x*_{i}"
(only with a large uppercase Greek Sigma instead of a plus sign
and with the subscripts and superscripts directly above and below the Sigma).
Similarly, the product of the sequence is written the same way,
only with a Pi instead of a Sigma.
So, addition and multiplication are actually
operations on *families* of real numbers.

Operations on families whose index set is 2:
If you think of 2 as the set {1, 2},
then 2 is just another possible index set for a family;
such a family is a finite sequence of length 2, or ordered pair.
But the notation for operations on such families is often different.
For example,
if you're given elements *x* and *y* of a set *X*,
then you automatically have the ordered pair (*x*, *y*),
a family of elements of *X*.
Rather than construct a name (such as "*z*") for this family
and then saying something like
"+_{i=1}^{2} *z*_{i}",
you can just say "*x* + *y*".
And notice that you use a different symbol in this case,
an actual plus sign instead of a Sigma.
That's a common circumstance with operations on families;
a large symbol is used for the operation on an arbitrary family,
with the elements of the family given by
either a formula or a variable with a subscript,
while a small symbol is used for the operation on an ordered pair,
placed between explicit expressions for the elements of the ordered pair.
(The small and large symbols are usually the same thing at different sizes,
but not always.
Indeed, for multiplication, the small symbol is blank!)

Operations on families *of sets* which you already know about:
If *X* is a family of sets with index set *I*,
then the union
U_{i in I} *X*_{i}
of the family
is simply the union of the range of *X* as a function.
There is also the abbreviated notation
"U_{i} *X*_{i}",
and of course
"U_{i=1}^{n} *X*_{i}"
for sequences,
which you may recognise from the paragraph on unions from before.
(So, I was secretly already talking about families!)
Of course, you can do the exact same things for intersection,
although you'll want to make *X*
a family of *subsets* of a given set *Y*,
so that you can define the intersection of the empty family
(the family whose index set is Ø),
which will be *Y*, of course.
Note that, because the union and intersection of a family of sets
doesn't depend on
how often the sets appear, or the order they appear in, or so on,
I could define
union and intersection of simple *collections* of sets earlier.
But this won't work for the concepts I introduce in the next section,
which is why we need families.

Prepare for the next section by taking another little breather.

Deep but easy exercise to see if you're paying attention: What is the disjoint union of the empty family of sets?

Another deep exercise:
If *m* and *n* are
extended whole numbers being thought of as sets,
what does the disjoint union of the sets
have to do with the ordinary sum of the numbers?

Binary **Cartesian product**:
If *X* and *Y* are sets,
consider the constant family of sets
whose index set is *Y* and whose constant value is *X*.
Then you can form the disjoint union
+_{y in Y} *X*,
which is
{(*x*, *y*) |
*x* in *X*, *y* in *Y*}.
In other words, it's the set of all ordered pairs
which can be made from
an element of *X* and an element of *Y*.
With any luck, you've seen this before.
There is a special notation for this, of course:
"*X* × *Y*".

Another deep exercise:
If *m* and *n* are
extended whole numbers being thought of as sets,
what does the Cartesian product of the sets
have to do with the ordinary product of the numbers?

Generic Cartesian product:
The binary Cartesian product × is an operation on an ordered pair.
Can we extend this to an operation on an arbitrary family?
Yes!
If *X* is a family of sets with index set *I*,
then the Cartesian product
×_{i in I} *X*_{i}
is a set of *families*:
the set of all families *x* with index set *I*
such that *x*_{i}
in *X*_{i}.
(We can take U_{i} *X*_{i}
for the codomain of the families.)
Of course, that should really be a large uppercase Greek Pi
instead of "×".

Deep but easy exercise to see if you're paying attention: What is the Cartesian product of the empty family of sets? (No, it's not empty!)

Exercise to see if I'm lying to you:
If *X* is a family with index set 2,
is the generic Cartesian product
×_{i = 1}^{2} *X*_{i}
really the same as the binary Cartesian product
*X*_{1} × *X*_{2}?
If not, what is the relationship between them?

**Exponentiation of sets**:
If *X* and *Y* are sets,
consider the constant family of sets
whose index set is *Y* and whose constant value is *X*.
Then you can form the Cartesian product
×_{y in Y} *X*,
which is the set of all families *f* with index set *Y*
such that *f*_{y} in *X*.
Or, more prosaically, it's the set of all functions
*f*: *Y* -> *X*.
There's a special notation for this: "*X*^{Y}".
If *n* is an extended whole number,
interpret *n* as a set to get *X*^{n}.
Thus, *X*^{infinity} is
the set of infinite sequences of elements of *X*,
*X*^{n} is
the set of finite sequences of length *n* of elements of *X*,
and *X*^{0} is
the set of empty sequences in *X* (there is exactly 1).
You're familiar with this in the case where
*X* is the set **R** of real numbers.

Last deep exercise:
If *m* and *n* are
extended whole numbers being thought of as sets,
what does the power *m*^{n} of the sets
have to do with the ordinary power of the numbers?

OK, I'm done, so take a breather. You deserve it.

Go back to Oz's crib sheet.

This web page was written between 2000 and 2002 by Toby Bartels. Toby reserves no legal rights to it.

The permanent URI of this web page
is
`http://tobybartels.name/Oz/sets/`

.