"I think mathematics is a vast territory. The outskirts of
mathematics are the outskirts of mathematical civilization. There
are certain subjects that people learn about and gather together.
Then there is a sort of inevitable development in those fields.
You get to a pont where a certain theorem is bound to be proved,
independent of any particular individual, because it is just in the
path of development."
William P. Thurston
MORE MATHEMATICAL PEOPLE, NY, 1990, p332
"Chance favors the prepared mind."
Pasteur, Louis
FUNCTIONS ON FINITE SETS
This section will introduce some frequently used terms.
Let S and T be finite sets.
Definition: A "function" f from S to T is a rule which
associates to each element s of S exactly one element t of T.
We will use the following notations for this:
f : S > T ("f is a function from S to T"),
f : s > t ("f sends s in S to t in T"),
t = f(s) ("t is the image of s under f").
A function is also called a "map", "mapping", or "transformation".
We call S the "domain" of f, T the "range" of f, and the set
f(S) = {f(s) in T  s in S}
the "image" of f. The Venn diagram depicting this setup is:


 * *
 * *
 * *
 * S *
 * *
 * * + + +
 * * + +
 * * * + +
 + * * T +
 + * * +
 + * * +
 + * f(S) * +
 * * +
 + * * * +
 + + + +


The "graph" of a function f : S > T is the subset
{ (s,f(s))  s in S} subset SxT .
Is every subset of SxT the graph of some function
from S to T? In general, no. Let
p : SxT > S
(s,t) > s
be projection onto the 1st component. The following fact classifies
exactly which subsets of SxT can arise as the graph of a function
from S to T.
LEMMA: Let X subset SxT. X is the graph of a function from S to T
if and only if, for all (s1,t1) in X and (s2,t2) in X, whenever
t1 <> t2 we also have s1 <> s2.
(This does follow from the definition of a function. As an exercise
you may want to convince yourself of this.)
DEFINITION: If the image of the function f : S > T is all of T,
i.e., if f(S) = T, then we call f "surjective" (or "onto").
Equivalently, a function f from S to T is surjective if each t in T
is the image of some s in S under f. Occasionally, you see the
following special notation for surjective functions:
f : S >> T ("f maps S surjectively onto T").
Exercise: State a general rule which determines those subsets
X of SxT which are the graph of some surjective function from S to T.
(Use the projection onto the second component,
pr2 : SxT > T
(s,t) > t
in your rule.)
Question: Suppose that S < T. Is there a surjective
function f : S > T? Explain.
DEFINITION: A function f : S > T is called "injective" (or
"onetoone") if each element t belonging to the image f(S)
is the image of exactly one s in S.
In other words, if the condition f(s1)=f(s2) (for some s1, s2 in S)
always forces s1=s2. Sometimes the "hook arrow" notation is used
to denote an injective function
f : S '> T.
(This doesn't come out well when typed, unfortunately).
Question: Suppose that S > T. Is there an injective
function f : S > T? Explain.
Exercise: Suppose that S = T. Show that a function
f : S > T is surjective if and only if it is injective.
DEFINITION: A function f : S > T is called a "bijection"
if it is both injective and surjective.
Equivalently, a bijection from S to T is a function for which
each t in T is the image of exactly one s in S.
Exercise: Give an algorithm for determining if a given subset X
of SxT is the graph of a bijection from S to T.
Example: Let C be the cube in 3space having vertices at the points
O=(0,0,0), P1=(1,0,0), P2=(0,1,0), P3=(0,0,1), P4=(1,1,0), P5=(1,0,1),
P6=(0,1,1), P7=(1,1,1). Let V = {O,P1,...,P7} be the set of the 8
vertices of C and let F be the set of the 6 faces of C. Let r be
the rotation of a point (x,y,z) by 180 degrees about the passing
through the points (1/2,1/2,0), (1/2,1/2,1). Note that
r:R3 > R3 is a function which sends the cube C onto itself.
The cube C is pictured as follows:


 z
 
 
 P3 _________
 / /
 /  / 
 /_ ______/ 
    
  O _______________ y
  /  /P2
  /  /
 /________/
 P1 / 
 /
 x


This function r induces two functions
f1 : V > V, f2 : F > F,
where f1 is the function which sends a vertex v of C to its image
r(v) under r (which is again a vertex). Similarly, f2 is the
function which sends a face f of C to its image r(f) under r (which
is again a face). Both f1 and f2 are bijections.
Exercise: Finish the labeling of the vertices and the faces in the
above picture and describe f1 and f2 explicitly by filling out the
tables
V  f1(V) F  f2(F)
 
 
 
 
 
 
 


Theorem: If f : S > T is a bijection then there exists a function
f^(1) : T > S defined by the following property: for s in S
and t in T, we have
f^(1)(t)=s if and only if f(s)=t.
Exercise: Prove this.
DEFINITION: The function f^(1) in the above theorem is called the
"inverse function" of f.
Relations
A relation on a set is a generalization of the concept of
a function from S to itself.
Definition: Let S be a set. If R is a subset of SxS
then we call R a "relation on S"..
If (x,y) in R then we say that x is "related" to y.
This is a very general notion. There are lots and lots
of relations in mathematics  inequality symbols, functions,
subset symbols are all common examples of relations.
Example 1: Let S be any set and let f be a function from
S to itself. This function gives rise to the relation R
on S defined by the graph of f:
R = { (x,y) in SxS  y = f(x), for x in S }.
(It is through this correspondence that we may regard a
function as a relation.)
Example 2: Let S be the set of all subsets of {1,2,...,n}.
Let R be defined by
R = { (S1,S2)  S1 subset S2, S1 in S, S2 in S }.
Note that R is a relation.
Exercise: Find a relation corresponding to the symbol <
on the real line.
Definition: Let R be a relation on a set S. We call R an
"equivalence relation" if
(a) any element s in S is related to itself ("reflexive"),
(b) if s is related to t (s,t belonging to S) then t
is related to s ("symmetry"),
(c) if s1 is related to s2 and s2 is related to s3
then s1 is related to s3 ("transitivity").
Example" The equality symbol = provides an equivalence relation
on the real line: let E = {(x,x)  x real}. This is an
equivalence relation on the real line: note x=y if and only if
(x,y) belongs to E.
Notation: If R is an equivalence relation on S then we often
write "x~y" in place of "(x,y) in R", for simplicity. (Often one
replaces the ~ sign by the "equivalence" sign  like an equals
sign but with 3 horizontal lines instead of 2  but this does not
come out in ascii mode.)
Exercise 1: (a) Let f(x)=x^2, let S be the real line, and
let R be the corresponding relation as in Example 1. Is R
an equivalence relation?
(b) Let f(x)=2x, let S be the real line, and let R be the
corresponding relation as in Example 1. Is R an equivalence
relation?
Exercise 2: Let R be the corresponding relation as in
Example 2. Is R an equivalence relation?
Let R be an equivalence relation on a set S. For
s in S, we call the subset
[s] = { t in S  s~t }
the "equivalence class" of s in S.
Exercise: Show that for any s1 and s2 in S, we have either
(a) [s1] = [s2], or
(b) [s1] is disjoint from [s2].
As a consequence of this exercise, we see that if R is an equivalence
relation on a set S then the equivalence classes of R partition S
into disjoint subsets. We state this as a separate lemma for future
reference (we also assume S is finite for simplicity):
Lemma: If S is a finite set and R is an equivalence relation on S
then there are subsets
S1 subset S, S2 subset S, ..., Sk subset S,
satisfying the following properties:
(1) S is the union of all the Si's:
S = S1 union S2 union ... union Sk = U Si
i
(2) the Si's are disjoint: for 1 <= i <= k, 1 <= j <= k, if
i <> j then Si intersect Sj = EMPTY,
(These last two properties say that the Si's "partition" S.)
(3) the Si's exhaust the collection of equivalenvce classes of R:
for each 1 <= i <= k, there is an si in S such that
Si = [si].
(This element si is called a "representative" of the equivalence class
Si.)
Exercise: Let S be the set Z of all integers. Let R be the relation
defined by (x,y) in R if and only if xy is an even number (i.e., an
integer multiple of 2).
(1) Show that this is an equivalence relation,
(2) Find the sets Si in the above lemma which partition S,
(3) Find a "representative" of each equivalence class Si.