View source for Abstract Algebra/Functions

{{TOC right}}
==Definition==   
A function <math>\operatorname{f}</math> is a triplet <math>(A, B, G)</math> such that:
* <math>A</math> is a set, called the domain of <math>\operatorname{f}</math>
* <math>B</math> is a set, called the codomain of <math>\operatorname{f}</math>
* <math>G</math> is a subset of <math>A \times B</math>, called the graph of <math>\operatorname{f}</math>
In addition the following two properties hold:
# <math>\forall x \in A, \exists y \in B \mid (x,y) \in G</math>.
# <math>\forall x \in A, y \in B, y' \in B\mbox{, then } (x,y) \in G \mbox{ and } (x,y') \in G \Rightarrow y=y'</math>.

<math>\forall x \in A</math> we write <math>\operatorname{f}(x)</math> for the unique <math>y \in B</math> such that <math>(x,y) \in G</math>.

We say that <math>\operatorname{f}</math> is a function from <math>A</math> to <math>B</math>, which we write:
:<math>\operatorname{f}:A \rightarrow B</math>

===Example===
Let's consider the function from the reals to the reals which squares its argument. We could define it like this:
:<math>\operatorname{f}:\mathbb{R} \rightarrow \mathbb{R}</math>
:<math>\operatorname{f}:x \mapsto x^2</math>

===Remark===
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 <math>\operatorname{f}(x)</math> don't change, changing the domain or codomain changes the function.

Let's look at the following four functions.

The function:
:<math>\operatorname{f_1}:\mathbb{R} \rightarrow \mathbb{R}</math>
:<math>\operatorname{f_1}:x \mapsto x^2</math>
is neither injective nor surjective (these terms will be defined later).

The function:
:<math>\operatorname{f_2}:\mathbb{R} \rightarrow \mathbb{R}_{\geq 0}</math>
:<math>\operatorname{f_2}:x \mapsto x^2</math>
is not injective but surjective.

The function:
:<math>\operatorname{f_3}:\mathbb{R}_{\geq 0} \rightarrow \mathbb{R}</math>
:<math>\operatorname{f_3}:x \mapsto x^2</math>
is injective but not surjective.

The function:
:<math>\operatorname{f_4}:\mathbb{R}_{\geq 0} \rightarrow \mathbb{R}_{\geq 0}</math>
:<math>\operatorname{f_4}:x \mapsto x^2</math>
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 <math>E</math>, we write <math>\mathcal{P}(E)</math> for the set of subsets of <math>E</math>.

Let <math>\operatorname{f}:A \rightarrow B</math>. We will now define two related functions.

The '''image''' function:
:<math>\operatorname{f}:\mathcal{P}(A) \rightarrow \mathcal{P}(B),S \subseteq A \mapsto \{\operatorname{f}(x) \mid x \in S\}</math>

The '''preimage''' function:
:<math>\operatorname{f^{-1}}:\mathcal{P}(B) \rightarrow \mathcal{P}(A),T \subseteq B \mapsto \{x \in A \mid \operatorname{f}(x) \in T\}</math>

Note that the image and preimage are written respectively like <math>\operatorname{f}</math> 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 <math>\operatorname{Im}_{\operatorname{f}}:=\operatorname{f}(A)</math>, which we call the '''image''' of <math>\operatorname{f}</math>.

For any <math>y \in B</math>, we call <math>\operatorname{f^{-1}}(\{y\})</math> the '''support''' of <math>y</math>.

'''Proposition''': Let <math>\operatorname{f}:A \rightarrow B</math>. Then
# <math>\forall S \subseteq A, S \subseteq f^{-1}(f(S))</math>
# <math>\forall T \subseteq B, f(f^{-1}(T)) \subseteq T</math>

===Example===
Let's take again the function:
:<math>\operatorname{f}:\mathbb{R} \rightarrow \mathbb{R}</math>
:<math>\operatorname{f}:x \mapsto x^2</math>

Let's consider the following examples:
:<math>\operatorname{f^{-1}}(\{4\})=\{-2,2\}</math>
:<math>\operatorname{f^{-1}}(\mathbb{R}_{< 0}) = \emptyset</math>
:<math>\operatorname{f}(\mathbb{R}_{\geq 0}) = \mathbb{R}_{\geq 0}</math>

==Further definitions==
Let <math>\operatorname{f}:B \rightarrow C</math> and <math>\operatorname{g}:A \rightarrow B</math>. We define <math>\operatorname{f} \circ \operatorname{g}:A \rightarrow C</math> by <math>(\operatorname{f} \circ \operatorname{g})(x) := \operatorname{f}(\operatorname{g}(x))</math>, which we call the '''composition''' of <math>\operatorname{f}</math> and <math>\operatorname{g}</math>.

Let <math>A</math> be a set. We define the '''identity function''' on A as
:<math>\operatorname{id_A}:A \rightarrow A, x \mapsto x</math>

==Properties==

'''Definition''': A function <math>\operatorname{f}:A \rightarrow B</math> is '''injective''' if
:<math>\forall x \in A, x' \in A, \operatorname{f}(x) = \operatorname{f}(x') \Rightarrow x = x'</math>

'''Lemma''': Consider a function <math>\operatorname{f}:A \rightarrow B</math> and suppose <math>A \neq \emptyset</math>. Then <math>\operatorname{f}</math> is injective if and only if there exists a function <math>\operatorname{g}:B \rightarrow A</math> with <math>\operatorname{g} \circ \operatorname{f} = \operatorname{id_A}</math>.
<br />
''Proof'':
<br />
<math>'\Rightarrow'</math>:
<br />
Suppose <math>\operatorname{f}</math> is injective. As <math>A \neq \emptyset</math> let's define <math>m</math> as an arbitrary element of <math>A</math>. We can then define a suitable function <math>\operatorname{g}:B \rightarrow A</math> as follows:
:<math>
\operatorname{g}(y):= \left\{
\begin{array}{ll}
\mbox{the unique } x \in A \mid \operatorname{f}(x) = y & \text{, if } y \in \operatorname{Im}_{\operatorname{f}}\\
m & \text{, else}\\
\end{array} \right.
</math>
It is now easy to verify that <math>\operatorname{g} \circ \operatorname{f} = \operatorname{id_A}</math>.
<br />
<math>'\Leftarrow'</math>:
<br />
Suppose there is a function <math>\operatorname{g}:B \rightarrow A</math> with <math>\operatorname{g} \circ \operatorname{f} = \operatorname{id_A}</math>. Then <math>\forall x,x' \in A, \operatorname{f}(x) = \operatorname{f}(x') \Rightarrow \operatorname{g}(\operatorname{f}(x)) = \operatorname{g}(\operatorname{f}(x')) \Rightarrow x = x'</math>. <math>\operatorname{f}</math> is thus injective.
<br />
Q.E.D.

'''Definition''': A function <math>\operatorname{f}:A \rightarrow B</math> is '''surjective''' if
:<math>\forall y \in B, \exists x \in A \mid \operatorname{f}(x) = y</math>

'''Lemma''': Consider a function <math>\operatorname{f}:A \rightarrow B</math>. Then <math>\operatorname{f}</math> is surjective if and only if there exists a function <math>\operatorname{g}:B \rightarrow A</math> with <math>\operatorname{f} \circ \operatorname{g} = \operatorname{id_B}</math>.
<br />
''Proof'':
<br />
<math>'\Rightarrow'</math>:
<br />
Suppose <math>\operatorname{f}</math> is surjective. We can define a suitable function <math>\operatorname{g}:B \rightarrow A</math> as follows:
:<math>\operatorname{g}(y):= \mbox{an } x \in A \mid \operatorname{f}(x) = y</math>
It is now easy to verify that <math>\operatorname{f} \circ \operatorname{g} = \operatorname{id_B}</math>.
<br />
<math>'\Leftarrow'</math>:
<br />
Suppose there is a function <math>\operatorname{g}:B \rightarrow A</math> with <math>\operatorname{f} \circ \operatorname{g} = \operatorname{id_B}</math>. Then <math>\forall y \in B \mbox{, let } x := \operatorname{g}(y)</math>. Then <math>\operatorname{f}(x) = \operatorname{f}(\operatorname{g}(y)) = y</math>. <math>\operatorname{f}</math> is thus surjective.
<br />
Q.E.D.

'''Definition''':  A function <math>\operatorname{f}:A \rightarrow B</math> is '''bijective''' if
it is both injective and surjective.

'''Lemma''': A function <math>\operatorname{f}:A \rightarrow B</math> is bijective if and only if there exists a function <math>\operatorname{g}:B \rightarrow A</math> with <math>\operatorname{g} \circ \operatorname{f} = \operatorname{id_A}</math> and <math>\operatorname{f} \circ \operatorname{g} = \operatorname{id_B}</math>. Furthermore it can be shown that such a <math>\operatorname{g}</math> is unique. We write it <math>\operatorname{f^{-1}}:B \rightarrow A</math> and call it the '''inverse''' of <math>\operatorname{f}</math>.
<br />
''Proof'':
<br />
Left as an exercise.

'''Proposition''': Consider a function <math>\operatorname{f}:A \rightarrow B</math>. Then
# <math>f</math> is injective iff <math>\forall S \subseteq A, f^{-1}(f(S))=S</math>
# <math>f</math> is surjective iff <math>\forall T \subseteq B, f(f^{-1}(T))=T</math>
# <math>f</math> is bijective iff the image and preimage of <math>f</math> are inverse of each other

'''Example:''' If <math>A</math> and <math>B</math> are sets such that <math>B\subseteq A</math>, there exists an obviously injective function <math>i\,:\, B\rightarrow A</math>, called the inclusion <math>B\subseteq A</math>, such that <math>i(b)=b</math> for all <math>b\in B</math>.

'''Example:''' If <math>\sim</math> is an equivalence relation on a set <math>X</math>, there is an obviously surjective function <math>\pi\,:\,X\rightarrow X/\sim</math>, called the canonical projection onto <math>X/\sim</math>, such that <math>\pi(x)=[x]</math> for all <math>x\in X</math>.

'''Theorem:''' Define the equivalence relation <math>\sim</math> on <math>A</math> such that <math>a\sim b</math> if and only if <math>f(a)=f(b)</math>. Then, if <math>f:A\rightarrow B</math> is any function, <math>f</math> decomposes into the composition

:<math>A\stackrel{\pi}{\longrightarrow} A/\sim \stackrel{\tilde{f}}{\longrightarrow} \mathrm{im}f \stackrel{i}{\longrightarrow} B</math>

where <math>\pi</math> is the canonical projection, <math>i</math> is the inclusion <math>\mathrm{im}\,f\subseteq B</math>, and <math>\tilde{f}</math> is the bijection <math>\tilde{f}([a])=f(a)</math> for all <math>a\in A</math>.

''Proof'': The definition of <math>\tilde{f}</math> immediately implies that <math>f=i\circ\tilde{f}\circ\pi</math>, so we only have to prove that <math>\tilde{f}</math> is well defined and a bijection. Let <math>a,a^\prime \in A</math>. Then <math>[a]=[a^\prime] \,\Rightarrow \, a\sim a^\prime \,\Rightarrow\, f(a)=f(a^\prime)</math>. This shows that the value of <math>\tilde{f}([a])</math> is independent of the representative chosen from <math>[a]</math>, and so it is well-defined.

For injectivity, we have <math>\tilde{f}([a])=\tilde{f}([a^\prime])\,\Rightarrow\, f(a)=f(a^\prime) \,\Rightarrow\, [a]=[a^\prime]</math>, so <math>\tilde{f}</math> is injective.

For surjectivity, let <math>b\in \mathrm{im}\,f</math>. Then there exists an <math>a\in A</math> such that <math>f(a)=b</math>, and so <math>\tilde{f}([a])=b</math> by definition of <math>\tilde{f}</math>. Since <math>b</math> is arbitrary in <math>\mathrm{im}\,f</math>, this proves that <math>\tilde{f}</math> is surjective.

Q.E.D.

'''Definition:''' Given a function <math>f\,:\,X\rightarrow Y</math>, <math>f</math> is a

(i) ''Monomorphism'' if given any two functions <math>g,h\,:\,W\rightarrow X</math> such that <math>f \circ g = f \circ h</math>, then <math>g=h</math>.

(ii) ''Epimorphism'' if given any two functions <math>g,h\,:\,Y\rightarrow Z</math> such that <math>g \circ f = h \circ f</math>, then <math>g=h</math>.

'''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 <math>f\,:\,B\rightarrow C</math> be a  monomorphism. Then, for any two functions <math>g,h\,:\,A\rightarrow B</math>, <math>f(g(a))=f(h(a)) \,\Rightarrow\, g(a)=h(a)</math> for all <math>a\in A</math>. This is the definition if injectivity. For the converse, if <math>f</math> is injective, it has a left inverse <math>f^\prime</math>. Thus, if <math>f(g(a))=f(h(a))</math> for all <math>a\in A</math>, compose with <math>f^\prime</math> on the left side to obtain <math>g(a)=h(a)</math>, such that <math>f</math> is a monomorphism.

(ii) Let <math>f\,:\,A\rightarrow B</math> be an epimorphism. Then, for any two functions <math>g,h\,:\, B\rightarrow C</math>, <math>g(f(a))=h(f(a))\,\Rightarrow\, g(b)=h(b)</math> for all <math>a\in A</math> and <math>b\in B</math>. Assume <math>\mathrm{im} f \neq B</math>, that is, that <math>f</math> is not surjective. Then there exists at least one <math>b\in B</math> not in <math>\mathrm{im}\,f</math>. For this <math>b</math> choose two functions <math>g,h</math> which coincide on <math>\mathrm{im}\, f</math> but disagree on <math>\{b\}</math>. However, we still have <math>g(f(a))=h(f(a))</math> for all <math>a\in A</math>. This violates our assumption that <math>f</math> is an epimorphism. Consequentally, <math>f</math> is surjective. For the converse, assume <math>f</math> is surjective. Then the epimorphism property immediately follows.

Q.E.D.

'''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 <math>A</math> and <math>B</math>, we have the canonical projections <math>\pi_A\,:\,A\times B \rightarrow A</math> sending <math>(a,b)</math> to <math>a</math>, and <math>\pi_B\,:\, A\times B\rightarrow B</math> sending <math>(a,b)</math> to <math>b</math>. These maps are obviously surjective.

In addition, we have the natural inclusions <math>i_A\,:\, A\rightarrow A\coprod B</math> and <math>i_B\,:\, B\rightarrow A\coprod B</math> which are obviously injective as stated above.

===Universal properties===

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 <math>A,B,C</math> be any sets.

(i) Let <math>f\,:\,C\rightarrow A</math> and <math>g\,:\,C\rightarrow B</math>. Then there exists a ''unique'' function <math>u\,:\,C\rightarrow A\times B</math> such that <math>f=\pi_A\circ u</math> and <math>g=\pi_B\circ u</math> are simultaneously satisfied. <math>u</math> is sometimes denoted <math>f\times g</math>.

(ii) Let <math>f\,:\,A\rightarrow C</math> and <math>g\,:\,B\rightarrow C</math>. Then there exists a ''unique'' function <math>u\,:\,A\coprod B \rightarrow C</math> such that <math>f=u\circ i_A</math> and <math>g=u\circ i_B</math> are simultaneously satifsied.

The canonical projections onto quotients also satisfy a universal property.

'''Theorem:''' Define the equivalence relation <math>\sim</math> on <math>X</math> and let <math>f\,:\,X\rightarrow Y</math> be any function such that <math>a\sim b \,\Rightarrow\, f(a)=f(b)</math> for all <math>a,b\in X</math>. Then there exists a ''unique'' function <math>\bar{f}\,:\,X/\sim \rightarrow Y</math> such that <math>f=\bar{f}\circ \pi</math>, where <math>\pi\,:\,X\rightarrow X/\sim</math> is the canonical projection.

{{BookCat}}
{{incomplete}}
{{Subject|Abstract Algebra}}