Henceforth, when we write , we will consider that “ is a function from to ”.
As is seen from the definition, a function is a relation mapping each element in the domain to a unique element in the codomain. So, the notation is generally used instead of the notations and and read “ maps to ” or “ maps to ”. The notation is read “ of ”. Each element of the domain is called an “argument” and for each in the domain, the corresponding unique element in the codomain is called “the function value at ”, “output for an element ” or “the image ” under the function . The set defined as is called the “image” or the “range” of . Sometimes a function is called a “map” or a “mapping”.
EXAMPLE1 (Identity function): Let be a set. The function over defined as is called the “identity function” of .
EXAMPLE2 (Constant function): Let and be two non-empty set and be a constant in . The function from to defined as is called a “constant function”.
EXAMPLE3 (Inclusion function): Let be a set and . The function from to defined as is called an “inclusion function”.
EXAMPLE4 (Restriction and extension): Let and . The function from to defined as is called a “restriction” of . Besides, is called an “extension” of .
EXAMPLE5 (Characteristic function): Let be a set and . The function from to defined as
is called the “characteristic function” of .
DEFINITION2: Let . If , then the functions and are called “equal functions”.
DEFINITION3: Let . If it holds for , then is called an “injective function”, an “injection” or an “one to one function”. Since the condition of being an injection is equivalent to the condition , the last condition can be used as the definition of injection. As is seen from the definition, an injection is a function mapping two distinct arguments to two distinct images.
DEFINITION4: Let . If it holds , then is called a “surjective function”, a “surjection” or an “onto function”. A function is a surjection if and only if its image equal to its codomain.
DEFINITION5: A function is called a “bijective function”, a “bijection” or a “one to one correspondence” if it is both injective and surjective. The identity function of a set in Example1 can be given as an example.
EXAMPLE6: Let’s examine the following three functions , and :
is injective because it separately maps the elements of to the elements of . However, for in , there is no an element in satisfying .
is surjective because each element of is the image of at least one element in . However, is not injective because but .
As is seen from the above figure, the function is both injective and surjective i.e., is a bijection.
The above three examples show us a function is injective if and only if any two arrows leaving from the domain don’t arrive the same images in the codomain, and a function is surjective if and only if for each element in the codomain, there exists at least one arrow leaving from the domain such that the arrow arrives this element. Unfortunately, these necessary and sufficient conditions cannot be used for a function whose domain or codomain has infinitely many elements because an infinite set cannot be displayed by the Venn diagram. There are many different ways for testing whether a function whose domain or codomain has infinitely many elements is injective (or surjective) or not. Let’s give some examples concerning the infinite sets:
EXAMPLE7: Let , , , . is injective because .
Choose for any in . Then, . Hence is surjective. Since is both injective and surjective, it is a bijection.
EXAMPLE8: Let , .
is not injective because but .
is not surjective because there is no an element in such that for in .
EXAMPLE9: Consider the above function as . Actually, the function is the same as the above function. Its codomain is only changed. Under the given conditions, we will investigate whether this function is injective (surjective) or not:
Let . Since , it has the square root . Choose . Since , then is surjective. As above, is not injective because but for in the domain.
EXAMPLE10: This time, we consider the function as . Then, similar to example9, one can prove that is surjective. Now, we will investigate is whether injective or not: Take in .
So, is injective.
Depending on the domain and the codomain of a function, the injectivity or the surjectivity can be changed. When the injectivity or the surjectivity of the function is asked, one should ask this question: What are the domain and the codomain of this function.
PROPOSITION1: Let and be two sets with elements and . Then,
is injective if and only if it is surjective.
The above proposition is available for the finite sets. Over the infinite sets, an injective function doesn’t have to be surjective and a surjective function doesn’t have to be injective. The function from to is injective. However, it is not surjective because it is positive-valued.
are called the image of under and the preimage or the inverse image of under , respectively. As is seen from the definition, is formed the images of the elements of and is formed the elements in whose images are in . Particularly, if it is chosen by , then is range and denoted by . It is clear that , , and .
EXAMPLE11: , , , , , , , and . Then,
PROPOSITION2: Let and be two sets, , and . Then,
COROLLARY1: Let and be two sets, , and . Then,
The property "b" in the proposition3 and its corollary attracts our attention. Although there are the equalities in the properties "a", "c" and "d", we can only say that is a subset of . It is interesting. Since is a subset of , it may be equal. According to proposition1, there are two probabilities: and . The identity function of a set is an example for the second probability. Is there any example for the first probability? The following example is the answer of this question:
EXAMPLE12: Choose , , , and define as . It is clear that is a function. Since , then . On the other hand, since , then . As is seen, .
There are many examples for the two probabilities. Is there any criterion determining whether the left side is equal to the right side or not? The following proposition is the answer this question:
PROPOSITION4: Let . Then,
PROPOSITION5: Let . Then,
PROPOSITION6: Let . Then,
a) is injective ,
b) is surjective ,
c) is bijective .
DEFINITION7: Let and . The function defined as is called the composition of the functions and . (Note that the codomain of is equal to the domain of )
EXAMPLE13: Choose , and . Then, .
Let and be two functions with suitably chosen domains and codomains. Is equal to ? We will answer this question by the help of an example:
EXAMPLE14: Choose , and . Since
then . We have just obtained an example about . Is the proposition always true? The answer of this question is "no". For example, if we choose and , then
I.e., When we choose and , it holds . Consequently, if and are two functions with suitably chosen domains and codomains, then there are two probabilities: and .
PROPOSITION7: Let . Then, and .
PROPOSITION8: Let , and . Then, .
PROPOSITION9: Let and . Then,
a) If and are injective, then is also injective.
b) If and are surjective, then is also surjective.
c) If is injective, then is also injective.
d) If is surjective, then is also surjective.
DEFINITION8: Let .
i) If there exists at least one function such that , then the function is called a right inverse of .
ii) If there exists at least one function such that , then the function is called a left inverse of .
The definitions (i) and (ii) can be given by the follows:
i*) If there exists at least one function such that , then the function is called a right inverse of .
ii*) If there exists at least one function such that , then the function is called a left inverse of .
PROPOSITION10: Let . Then,
a) There exists at least one right inverse of is surjective.
b) There exists at least one left inverse of is injective.
EXAMPLE15: Choose by . If we define as
then it holds because , . So, has a left inverse.
Since the function given in example15 is injective, then it has a left inverse. However, according to proposition10, it has no a right inverse because it is not surjective. Example15 shows that a function can have a left inverse although it has no a right inverse.
EXAMPLE16: Choose by . Since it is surjective, then it has a right inverse. Define as . Since , , then is a right inverse of . According to proposition10, has no a left inverse because it is not injective.
PROPOSITION11: Let , and . Then,
a) If is injective and , then (an injective function has the left cancellation property)
b) If is surjective and , then (a surjective function has the right cancellation property)
Now, let's introduce the inverse function:
Let . Assume that and are left and right inverses of , respectively. Then,
. I.e., if a function has both left and right inverses, then these are equal to each other. A function being both left inverse and right inverse of is called an inverse of . Now, let's give the definition of "inverse", more properly:
DEFINITION9: Let . If there exists a function such as and , then the function is called an inverse of . Besides, is called invertible.
PROPOSITION12: Let . Then, has an inverse if and only if is bijective.
PROOF: The proof of this proposition can be directly obtained from Proposition10.
EXAMPLE17: If we choose by , then the function defined by is an inverse of because
EXAMPLE18: If we choose by , then the function defined by is an inverse of because
EXAMPLE19: If we choose by then the function defined by is an inverse of because
Let the functions be two inverses of the function . Then is a left inverse of and is a right inverse of . We have shown that a left inverse and a right inverse of a function are equal to each other. So, . Consequently, If there exists an inverse of a function, then it is unique. This unique inverse is denoted by .
PROPOSITION13: Let , . Then,
a) If is invertible, then is also invertible and . Besides, is bijective.
b) If and are invertible, then is invertible and .
THEOREM1: Let be a non-empty set and . Then is a group with the identity element . is commutative if and only if .
DEFINITION10: Let be a non-empty set and . Then we can define as,
, , and
Where is a natural number.