A function is a triplet such that:
- is a set, called the domain of
- is a set, called the codomain of
- is a subset of , called the graph of
In addition the following two properties hold:
we write for the unique such that .
We say that is a function from to , which we write:
Let's consider the function from the reals to the reals which squares its argument. We could define it like this:
As you see in the definition of a function above, the domain and codomain are an integral part of the definition. In other words, even if the values of don't change, changing the domain or codomain changes the function.
Let's look at the following four functions.
is neither injective nor surjective (these terms will be defined later).
is not injective but surjective.
is injective but not surjective.
is injective and surjective
As you see, all four functions have the same mapping but all four are different. That's why just giving the mapping is insufficient; a function is only defined if its domain and codomain are known.
Image and preimage
For a set , we write for the set of subsets of .
Let . We will now define two related functions.
The image function:
The preimage function:
Note that the image and preimage are written respectively like and its inverse (if it exists). There is however no ambiguity because the domains are different. Note also that the image and preimage are not necessarily inverse of one another. (See the section on bijective functions below).
We define , which we call the image of .
For any , we call the support of .
Proposition: Let . Then
Let's take again the function:
Let's consider the following examples:
Let and . We define by , which we call the composition of and .
Let be a set. We define the identity function on A as
Definition: A function is injective if
Lemma: Consider a function and suppose . Then is injective if and only if there exists a function with .
Suppose is injective. As let's define as an arbitrary element of . We can then define a suitable function as follows:
It is now easy to verify that .
Suppose there is a function with . Then . is thus injective.
Definition: A function is surjective if
Lemma: Consider a function . Then is surjective if and only if there exists a function with .
Suppose is surjective. We can define a suitable function as follows:
It is now easy to verify that .
Suppose there is a function with . Then . Then . is thus surjective.
Definition: A function is bijective if
it is both injective and surjective.
Lemma: A function is bijective if and only if there exists a function with and . Furthermore it can be shown that such a is unique. We write it and call it the inverse of .
Left as an exercise.
Proposition: Consider a function . Then
- is injective iff
- is surjective iff
- is bijective iff the image and preimage of are inverse of each other
Example: If and are sets such that , there exists an obviously injective function , called the inclusion , such that for all .
Example: If is an equivalence relation on a set , there is an obviously surjective function , called the canonical projection onto , such that for all .
Theorem: Define the equivalence relation on such that if and only if . Then, if is any function, decomposes into the composition
where is the canonical projection, is the inclusion , and is the bijection for all .
Proof: The definition of immediately implies that , so we only have to prove that is well defined and a bijection. Let . Then . This shows that the value of is independent of the representative chosen from , and so it is well-defined.
For injectivity, we have , so is injective.
For surjectivity, let . Then there exists an such that , and so by definition of . Since is arbitrary in , this proves that is surjective.
Definition: Given a function , is a
(i) Monomorphism if given any two functions such that , then .
(ii) Epimorphism if given any two functions such that , then .
Theorem: A function between sets is
(i) a monomorphism if and only if it is injective.
(ii) an epimorphism if and only if it is surjective.
Proof: (i) Let be a monomorphism. Then, for any two functions , for all . This is the definition if injectivity. For the converse, if is injective, it has a left inverse . Thus, if for all , compose with on the left side to obtain , such that is a monomorphism.
(ii) Let be an epimorphism. Then, for any two functions , for all and . Assume , that is, that is not surjective. Then there exists at least one not in . For this choose two functions which coincide on but disagree on . However, we still have for all . This violates our assumtion that is an epimorphism. Consequentally, is surjective. For the converse, assume is surjective. Then the epimorphism property immediately follows.
Remark: The equivalence between monomorphism and injectivity, and between epimorphism and surjectivity is a special property of functions between sets. This not the case in general, and we will see examples of this when discussing structure-preserving functions between groups or rings in later sections.
Example: Given any two sets and , we have the canonical projections sending to , and sending to . These maps are obviously surjective.
In addition, we have the natural inclusions and which are obviously injective as stated above.
The projections and inclusions described above are special, in that they satisfy what are called universal properties. We will give the theorem below. The proof is left to the reader.
Theorem: Let be any sets.
(i) Let and . Then there exists a unique function such that and are simultaneously satisfied. is sometimes denoted .
(ii) Let and . Then there exists a unique function such that and are simultaneously satifsied.
The canonical projections onto quotients also satisfy a universal property.
Theorem: Define the equivalence relation on and let be any function such that for all . Then there exists a unique function such that , where is the canonical projection.