“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 point 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.
Notation: If x is not equal to y then we write x != y. For example, 0!=1.
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. (Hint: 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 one-to-one) if each element t belonging to the image f(S) is the image of exactly one s in S, i.e., given t in T, f(s)=t has exactly one solution, s in S.
In other words, if the condition f(s1)=f(s2) (for some s1, s2 in S) always forces s1=s2.
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 3-space 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 less than symbol < on the real line.
Definition: Let R be a relation on a set S. We call R an equivalence relation if
- any element s in S is related to itself (reflexive),
- if s is related to t (s,t belonging to S) then t is related to s (symmetry),
- if s1 is related to s2 and s2 is related to s3 then s1 is related to s3 (transitivity).
Example 3: 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 3: 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:
- S is the union of all the Si’s:
S = S1 union S2 union ... union Sk = U Si i - 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.) - the Si’s exhaust the collection of equivalence 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 x-y is an even number (i.e., an integer multiple of 2).
- Show that this is an equivalence relation,
- Find the sets Si in the above lemma which partition S,
- Find a “representative” of each equivalence class Si.
Yet Another Mathblog 