Abstract Algebra/Functions

From Wikibooks, the open-content textbooks collection

Jump to: navigation, search

Contents

[edit] Definition

A function \operatorname{f} is a triplet (A,B,G) such that:

  • A is a set, called the domain of \operatorname{f}
  • B is a set, called the range of \operatorname{f}
  • G \subseteq A \times B, called the graph of \operatorname{f}

In addition the following two properties hold:

  1. \forall x \in A, \exists y \in B \mid (x,y) \in G.
  2. \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'.

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

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

\operatorname{f}:A \rightarrow B

[edit] Example

Let's consider the function from the real to the real wich squares its argument. We could define it like this:

\operatorname{f}:\mathbb{R} \rightarrow \mathbb{R}
\operatorname{f}:x \mapsto x^2

[edit] Remark

As you see in the definition of a function above, the domain and range are an integral part of the definition. In other words, even if the values of \operatorname{f}(x) don't change, changing the domain or range changes the function.

Let's look at the following four functions.

The function:

\operatorname{f_1}:\mathbb{R} \rightarrow \mathbb{R}
\operatorname{f_1}:x \mapsto x^2

is neither injective nor surjective (these terms will be defined later).

The function:

\operatorname{f_2}:\mathbb{R} \rightarrow \mathbb{R}_{\geq 0}
\operatorname{f_2}:x \mapsto x^2

is not injective but surjective.

The function:

\operatorname{f_3}:\mathbb{R}_{\geq 0} \rightarrow \mathbb{R}
\operatorname{f_3}:x \mapsto x^2

is injective but not surjective.

The function:

\operatorname{f_4}:\mathbb{R}_{\geq 0} \rightarrow \mathbb{R}_{\geq 0}
\operatorname{f_4}:x \mapsto x^2

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 range are known.

[edit] Image and preimage

For a set E, we write \mathcal{P}(E) for the set of subsets of E.

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

The image function:

\operatorname{f}:\mathcal{P}(A) \rightarrow \mathcal{P}(B),S \subseteq A \mapsto \{\operatorname{f}(x) \mid x \in S\}

The preimage function:

\operatorname{f^{-1}}:\mathcal{P}(B) \rightarrow \mathcal{P}(A),T \subseteq B \mapsto \{x \in A \mid \operatorname{f}(x) \in T\}

Note that these two functions are not necessarily inverse of one another (see the section on bijective functions below) and that the preimage has nothing to do with the inverse of \operatorname{f} (if it exists), since it is a function from \mathcal{P}(B) \rightarrow \mathcal{P}(A), and not from B \rightarrow A.

We define \operatorname{Im}_{\operatorname{f}}:=\operatorname{f}(A), which we call the image of \operatorname{f}.

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

[edit] Example

Let's take again the function:

\operatorname{f}:\mathbb{R} \rightarrow \mathbb{R}
\operatorname{f}:x \mapsto x^2

Let's consider the following examples:

\operatorname{f^{-1}}(\{4\})=\{-2,2\}
\operatorname{f^{-1}}(\mathbb{R}_{< 0}) = \emptyset
\operatorname{f}(\mathbb{R}_{\geq 0}) = \mathbb{R}_{\geq 0}

[edit] Further definitions

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

Let A be a set. We define the identity function on A as

\operatorname{id_A}:A \rightarrow A, x \mapsto x

[edit] Properties

Definition: A function \operatorname{f}:A \rightarrow B is injective if

\forall x \in A, x' \in A, \operatorname{f}(x) = \operatorname{f}(x') \Rightarrow x = x'

Lemma: Consider a function \operatorname{f}:A \rightarrow B and suppose A \neq \emptyset. Then \operatorname{f} is injective if and only if there exists a function \operatorname{g}:B \rightarrow A with \operatorname{g} \circ \operatorname{f} = \operatorname{id_A}.
Proof:
'\Rightarrow':
Suppose \operatorname{f} is injective. As A \neq \emptyset let's define m as an arbitrary element of A. We can then define a suitable function \operatorname{g}:B \rightarrow A as follows:

\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.

It is now easy to verify that \operatorname{g} \circ \operatorname{f} = \operatorname{id_A}.
'\Leftarrow':
Suppose there is a function \operatorname{g}:B \rightarrow A with \operatorname{g} \circ \operatorname{f} = \operatorname{id_A}. Then \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'. \operatorname{f} is thus injective.
Q.E.D.

Definition: A function \operatorname{f}:A \rightarrow B is surjective if

\forall y \in B, \exists x \in A \mid \operatorname{f}(x) = y

Lemma: Consider a function \operatorname{f}:A \rightarrow B. Then \operatorname{f} is surjective if and only if there exists a function \operatorname{g}:B \rightarrow A with \operatorname{f} \circ \operatorname{g} = \operatorname{id_B}.
Proof:
'\Rightarrow':
Suppose \operatorname{f} is surjective. We can define a suitable function \operatorname{g}:B \rightarrow A as follows:

\operatorname{g}(y):= \mbox{an } x \in A \mid \operatorname{f}(x) = y

It is now easy to verify that \operatorname{f} \circ \operatorname{g} = \operatorname{id_B}.
'\Leftarrow':
Suppose there is a function \operatorname{g}:B \rightarrow A with \operatorname{f} \circ \operatorname{g} = \operatorname{id_B}. Then \forall y \in B \mbox{, let } x := \operatorname{g}(y). Then \operatorname{f}(x) = \operatorname{f}(\operatorname{g}(y)) = y. \operatorname{f} is thus surjective.
Q.E.D.

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

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


The text in its current form is incomplete.

Retrieved from "http://en.wikibooks.org/wiki/Abstract_Algebra/Functions"