Function
A function from \( X \) to \( Y \) denoted by \( f: X \to Y \) is a
binary relation \( R \) on \( X \times Y \) such that if \( \left ( x , y \right ) , \left ( x , z \right ) \in R \), then \( z = y \), which says given an element \( x \in X \) it is only ever related to a single \( y \in Y \).
Function Equality
Suppose that \( f : X \to Y \) and \( g : X \to Y \) are two functions, then we say that they are equal and write \( f = g \) when
\[
f \left( x \right) = g \left( x \right)
\]
for every \( x \in X \)
dom f
Given a function \( f: X \to Y \), then we denote \( \text{dom} \left ( f \right ) := X \) which we is shorthand for the word domain
ran f
Given a function \( f{:} X \to Y \), then we denote \( \text{ran} \left ( f \right ) := Y \) which we is shorthand for the word range
Constant Function
Suppose that we have a
function \( f: X \rightarrow Y \) such that there is a value \( c \in Y \) such that for every \( x \in X \), we have \( f \left( x \right) = c \), then we say that \( f \) is
constant with value \( c \)
Identity Function
Let \( X \) be a set, the we define the following function \( \operatorname{ id } _ X : X \to X \), such that for any \( a \in X \)
\[
\operatorname{ id } _ X \left( a \right) = a
\]
and call it the identity function on \( X \).
Domain Restricted Function
Let \( f: E \to F \) let \( A \subseteq E \), then the restriction of \( f \) to \( A \) is the function \( f \restriction _ A : A \to F \) defined by:
\[
f \restriction _ A \left( x \right) := f \left( x \right)
\]
for each \( x \in A \)
The restriction of a function is thought of as the same function but with elements from it's domain removed, or restricted to a smaller set.
Inclusion Function
Suppose that \( A \subseteq B \), the inclusion function \( \iota : A \rightarrow B \) is defined by:
\[
\iota \left( x \right) = x
\]
where the output of \( \iota \) is considered as an element from \( B \)
Restriction Equals Inclusion Composed with Original
let \( f : E \to F \) and suppose \( A \subseteq E \), and let \( \iota: A \to E \) be the
inclusion function, then we have
\[
f \restriction A = f \circ \iota
\]
Let \( x \in A \), then \( f \restriction A \left( x \right) = f \left( x \right) \), and \( \left( f \circ \iota \right) \left( x \right) = f \left( \iota \left( x \right) \right) = f \left( x \right) \)
thus the two functions are equal.
Function Composition
Suppose that \( A , B , C \) are sets, and that \( f: A \to B , g: B \to C \) are functions, then we define
\[
g \circ f \left( x \right) := g \left( f\left ( x \right ) \right )
\]
for any \( x \in A \), so that \( g \circ f : A \to C \)
Function Addition
Suppose that \( f, g: X \to Y \) are functions and \( \oplus \) is a binary operation on \( Y \), then we define \( f \oplus g : X \to Y \) as:
\[
\left( f \oplus g \right) \left( x \right) := f \left( x \right) \oplus g \left( x \right)
\]
Function Multiplication
Let \( f: X \to Y \) be a function and let \( \otimes \) be a binary operation on \( Y \), then for any \( c \in Y \), we define \( c \otimes f : X \to Y \) as:
\[
\left( c \otimes f \right) \left( x \right) = c \otimes f \left( x \right)
\]
Image of a Set
Let \( f: X \to Y \) be a function and \( S \subseteq X \), then \( f{\left ( S \right )} := \left \lbrace y \in Y : y = f{\left ( s \right )} , \text{ for some } s \in S \right \rbrace \)
Inverse Image of a Function
Suppose \( f{:} X \to Y \) and \( U \subseteq Y \), then \( f^{- 1}{\left ( U \right )} := \left \lbrace x \in X : f{\left ( x \right )} \in U \right \rbrace \)
Inverse Image of The Range is The Domain
Suppose that \( f \) is a function, then
\[
f ^ { -1 } \left( \operatorname{ ran } \left( f \right) \right) = \operatorname{ dom } \left( f \right)
\]
\( x \in f ^ { -1 } \left( \operatorname{ ran } \left( f \right) \right)\) iff \( f \left( x \right) \in \operatorname{ ran } \left( f \right) \) iff \( x \in \operatorname{ dom } \left( f \right) \) by definition
Inverse Image of a Composition
Suppose that we have two functions \( f : X \to Y \) and \( g: Y \to Z \) and suppose that \( S \subseteq Z \), then
\[
\left( g \circ f \right) ^ { -1 } \left( S \right) = f ^ { -1 } \left( g ^ { -1 } \left( S \right) \right)
\]
A point \( p \) is an element of \( \left( g \circ f \right) ^ { -1 } \left( S \right) \) iff \( \left( g \circ f \right) \left( p \right) \in S \) by definition this means that \( g \left( f \left( p \right) \right) \in S \) iff \( f \left( p \right) \in g ^ { -1 } \left( S \right) \) iff \( p \in f ^ { -1 } \left( g ^ { -1 } \left( S \right) \right) \) as needed.
Union Factors through Inverse Image
\( f ^ { -1 } \left( \bigcup \mathcal{ M } \right) = \bigcup \left\{ f ^ { -1 } \left( M \right): M \in \mathcal{ M } \right\} \)
We can observe that \( p \in f ^ { -1 } \left( \bigcup \mathcal{ M } \right) \), if and only if \( f \left( p \right) \in \bigcup \mathcal{ M } \), iff there exists some \( M \in \mathcal{ M } \) such that \( f \left( p \right) \in M \) iff \( p \in f ^ { -1 } \left( M \right) \) so that \( p \in \bigcup \left\{ f ^ { -1 } \left( M \right) : M \in \mathcal{ M } \right\}\) as needed.
Since all the logical connectives in the above proof are iff's then this shows the two sets equal
Set Difference Factors through Inverse Image
Suppose that \( f: X \rightarrow Y \), and that \( A, B \subseteq Y \), then
\[
f ^ { -1 } \left( A \setminus B \right) = f ^ { -1 } \left( A \right) \setminus f ^ { -1 } \left( B \right)
\]
\( x \in f ^ { -1 } \left( A \setminus B \right) \) iff \( f \left( x \right) \in A \setminus B \) iff \( f \left( x \right) \in A \) and \( f \left( x \right) \notin B \), iff \( x \in f ^ { -1 } \left( A \right) \) and \( x \notin f ^ { -1 } \left( B \right) \), iff \( x \in f ^ { -1 } \left( A \right) \setminus f ^ { -1 } \left( B \right) \), as needed.
Intersection Factors through Inverse Image
\( f ^ { -1 } \left( \bigcap \mathcal{ M } \right) = \bigcap \left\{ f ^ { -1 } \left( M \right): M \in \mathcal{ M } \right\} \)
We can observe that \( p \in f ^ { -1 } \left( \bigcap \mathcal{ M } \right) \), if and only if \( f \left( p \right) \in \bigcap \mathcal{ M } \), iff for every \( M \in \mathcal{ M } \) we have \( f \left( p \right) \in M \) iff \( p \in f ^ { -1 } \left( M \right) \) (still for each \( M \in \mathcal{ M } \) ) so that \( p \in \bigcap \left\{ f ^ { -1 } \left( M \right) : M \in \mathcal{ M } \right\}\) as needed.
Since all the logical connectives in the above proof are iff's then this shows the two sets equal
Image of the Inverse Image
Suppose that \( f: X \rightarrow Y \) is a function, and that \( S \subseteq Y \), then
\[
f \left( f ^ { -1 } \left( S \right) \right) \subseteq S
\]
Let \( p \in f \left( f ^ { -1 } \left( S \right) \right) \), therefore \( p = f \left( x \right) \) where \( x \in f ^ { -1 } \left( S \right) \), therefore \( f \left( x \right) \in S \) as needed.
Note that the above proposition is not equality, consider the function \( f: X \rightarrow \left\{ 0, 1 \right\} \) defined as \( f \left( x \right) = 0 \) for every \( x \in X \), then \( f \left( f ^ { -1 } \left( \left\{ 0, 1 \right\} \right) \right) = \left\{ 0 \right\} \). This hints at how we can force equality
Inverse Image of the Image
Suppose that \( S \subseteq X \), then \( f ^ { -1 } \left( f \left( S \right) \right) \supseteq S \)
Let \( s \in S \), we wish to prove that \( s \in f ^ { -1 } \left( f \left( S \right) \right) \), which means that we must show \( f \left( s \right) \in f \left( S \right) \), clearly this is true since \( s \in S \)
This proposition is not equality if we consider the function \( f : \left\{ 1, 2, 3, 4 \right\} \rightarrow \left\{ 1, 2, 3, 4 \right\} \) and define \( f \left( 1 \right) = 1 , f \left( 2 \right) = 2 , f \left( 3 \right) = 2, f \left( 4 \right) = 1\), then if we consider \( f ^ { -1 } \left( f \left( \left\{ 1, 2 \right\} \right) \right) \) we see it equals \( \left\{ 1, 2, 3, 4 \right\} \) which is clearly a superset.
Invertible Function
Let \( f: X \rightarrow Y \) be a
function, then \( f \) is said to be
invertible if there exists a function \( g: Y \rightarrow X \) such that \( g \left( f \left( x \right) \right) = x \) for every \( x \in X \) and \( f \left( g \left( y \right) \right) = y \) for every \( y \in Y \)
Inverse Function
Suppose that \( f \) is
invertible, then there is a function \( g \) satifying said properties, then we define the notation \( f ^ { -1 } := g \) and say that \( f ^ { -1 } \) is the inverse function of \( f \)
Note that this seems quite similar to the inverse image notation, which looks like \( f ^ { -1 } \left( S \right) \) where \( S \subseteq Y \), note that they differ as the inverse image is a function from \( P \left( Y \right) \) to \( P \left( X \right) \), so it is a function that maps sets to sets.
This differs from the inverse of a function because it operates on individual elements of \( Y \), so we may write things like \( f ^ { -1 } \left( s \right) \) where \( s \in Y \), noting that \( f ^ { -1 } : Y \rightarrow X \).This idea of using the same notation for a function, but having the type of it's parameters be different is usually known as overloading in the world of programming.
If this is your first brush with notation overloading, then know that it can be confusing, but all confusion can be cleared by inspecting what the inputs are to the function. This should remind you that a function is not just a name, it's signature is given by it's name, input types and return type. To see if you really understand this, answer the following exercise.
This means that the notation \( f ^ { -1 } \left( y \right) \) where \( y \in \operatorname{ ran } \left( f \right) \) is reserved only for functions \( f \) whose inverse exists, otherwise we have problems for example if \( f \) was not surjective and there was an element \( z \) that can never get mapped to then what does \( f ^ { - 1 }\left( z \right) \) mean? If it was not injective, then suppose that there was \( a \neq b \) such that \( f \left( a \right) = f \left( b \right) \) then \( a \stackrel{?}{=} f ^ { - 1 } \left( f \left( a \right) \right) = f ^ { - 1 } \left( f \left( b \right) \right) \stackrel{?}{=} b \) makes no sense because we know that \( a \neq b \), so we must have injectivity. Therefore you must be carful not to write the symbol \( f ^ { - 1 } \) unless you know that \( f \) is invertible.
Inverse Image of the Inverse Function is the Image
Let \( f: X \rightarrow Y \) and assume that it's inverse exists \( f ^ { -1 } : Y \rightarrow X \) and let \( S \subseteq Y \) show that:
\[
\left( f ^ { -1 } \right) ^ { -1 } \left( S \right) = f \left( S \right)
\]
Suppose that \( p \in \left( f ^ { -1 } \right) ^ { -1 } \left( S \right) \), by definition this is only true when \( f ^ { -1 } \left( p \right) \in S \), so \( f ^ { -1 } \left( p \right) = s \) for some \( s \in S \), equivalent to \( p = f \left( s \right) \), which is true if and only if \( p \in f \left( S \right) \).
All logical connectives in the above proof are iff's therefore we've shown the two sets equal.
Injective Function
a
function \( f{:} X \to Y \) is injective iff \( \forall x , y \in X , f{\left ( x \right )} = f{\left ( y \right )} \implies x = y \)
Inverse Image of Image Equality
Suppose that \( f: X \rightarrow Y \) and that \( S \subseteq X \), if \( f \) is injective then
\[
f ^ { -1 } \left( f \left( S \right) \right) = S
\]
We've already proven that \( f ^ { -1 } \left( f \left( S \right) \right) \supseteq S \), so we just need to prove that \( f ^ { -1 } \left( f \left( S \right) \right) \subseteq S \).
Suppose that \( p \in f ^ { -1 } \left( f \left( S \right) \right) \), therefore \( f \left( p \right) \in f \left( S \right) \), which means that there is some \( s \in S \) such that \( f \left( p \right) = f \left( s \right) \), since we assumed that \( f \) was injective this implies that \( p = s \), which concludes by showing \( p \in S \).
Surjective Function
a
function \( f{:} X \to Y \) is surjective iff \( \forall y \in Y , \exists x \in X \text{ such that } f{\left ( x \right )} = y \)
Image of Inverse Image Equality
Suppose that \( f: X \rightarrow Y \) and that \( S \subseteq Y \), if \( f \) is surjective then
\[
f \left( f ^ { -1 } \left( S \right) \right) = S
\]
We're already aware that \( f \left( f ^ { -1 } \left( S \right) \right) \subseteq S \) , so we must just show that \( f \left( f ^ { -1 } \left( S \right) \right) \supseteq S \).
So we start by assuming \( s \in S \), and now we must show that \( s \in f \left( f ^ { -1 } \left( S \right) \right) \), this is only true if \( s = f \left( x \right) \) for some \( x \in \left( f ^ { -1 } \left( S \right) \right) \), which in turn means that \( x \) also has to satisfy: \( f \left( x \right) \in S \).
We start with \( s \in S \subseteq Y \), thus since \( s \in Y \) and \( f \) is surjective we get some \( a \in X \) such that \( f \left( a \right) = s \), since \( s \in S \) , then also \( a \in f \left( S \right) \) as needed.
composition of two bijective functions is bijective
Suppose \( A , B , C \) are non-empty sets and \( f: A \to B , g: B \to C \) are functions, and that \( g{\circ} f{:} A \to C \) is a function. Then if \( f \) and \( g \) are
bijective then \( g{\circ} f \) is also bijective.
We'll show that \( g{\circ} f \) is surjective first, so let \( c \in C \), since \( g \) is bijective we get some \( b \in B \) such that \( g{\left ( b \right )} = c \), since \( b \in B \), then since \( f \) is surjective we get some \( a \in A \) such that \( f{\left ( a \right )} = b \), thus \( g{\circ} f{\left ( a \right )} = g{\left ( f{\left ( a \right )} \right )} = g{\left ( b \right )} = c \) so then \( g{\circ} f \) is surjective
Now let's show that \( g{\circ} f \) is injective, so suppose that \( a_{1} , a_{2} \in A \) and assume that \( g{\circ} f{\left ( a_{1} \right )} = g{\circ} f{\left ( a_{2} \right )} \), note that this means \( g{\left ( f{\left ( a_{1} \right )} \right )} = g{\left ( f{\left ( a_{2} \right )} \right )} \), therefore since \( g \) is injective we know that \( f{\left ( a_{1} \right )} = f{\left ( a_{2} \right )} \) and since \( f \) is injective then we know that \( a_{1} = a_{2} \) as needed.
Self Map
Suppose that \( X \) is a set, then a self map is any function of the form \( f: X \to X \)
Function Iteration
Given a function \( f: X \to X \), then we define
\[
f ^ { \circ 0 } := \operatorname{ id } _ X
\]
and then for any \( n \in \mathbb{ N } _ 1 \) we define via
composition:
\[
f ^ { \circ n } = f \circ f ^ { \circ n - 1 }
\]
So for example \( f ^ { \circ 3 } \left( x \right) = f \left( f \left( f \left( \operatorname{ id } \left( x \right) \right) \right) \right) \) which is what we expect.
Relation Preserving Function
Suppose that \( \left( R, X \right) \) and \( \left( S, Y \right) \) are
binary relations, and \( f: X \to Y \) a function, then we say that \( f \) is relation preserving if given \( x, y \in X \)
\[
x R y \implies f \left( x \right) S f \left( y \right)
\]
Note that when the relation is an order, we say that it is an order preserving function, you are already familiar with them, consider \( f \left( x \right) = x + 1 \) on \( \mathbb{ R } \).
Relation Reversing Function
Suppose that \( \left( R, X \right) \) and \( \left( S, Y \right) \) are relations, and \( f: X \to Y \) a function, then we say that \( f \) is relation reversing if given \( x, y \in X \)
\[
x R y \implies f \left( y \right) S f \left( x \right)
\]
The Inverse of an Order Preserving Function is Order Preserving
Suppose that \( \left( A, \le _ A \right) \) and \( \left( B, \le B \right) \) are partial orders and \( f: A \to B \) is order preserving and invertible, then \( f ^ { - 1 } : B \to A\) is also order preserving
Let \( b _ 1, b _ 2 \in B \) such that \( b _ 1 \le _ B b _ 2 \) now we want to prove that \( f ^ { - 1 } \left( b _ 1 \right) \le _ A f ^ { - 1 } \left( b _ 2 \right) \).
If it so happens that \( b _ 1 = b _ 2 \) then we automatically have that \( f ^ { - 1 } \left( b _ 1 \right) = f ^ { - 1 } \left( b _ 2 \right) \) as \( \le _ A \) is reflexive.
So suppose rather that \( b _ 1 \le _ B b _ 2 \) and that \( b _ 1 \neq b _ 2 \). Note that \( f ^ { - 1 } \left( b _ 1 \right) = a _ 1 \) and \( f ^ { - 1 } \left( b _ 2 \right) = a _ 2 \) for some \( a _ 1, a _ 2 \in A \) since \( \le _ A \) is a total order than \( a _ 1, a _ 2 \) are comparable, if it so happens that \( a _ 2 \le _ A a _ 1 \) then since \( f \) is order preserving, then we would have \( f \left( a _ 2 \right) \le _ B f \left( a _ 1 \right) \iff b _ 2 \le _ B b _ 1 \) since \( f \) was assumed invertible, which would only be possible if \( b _ 1 = b _ 2 \) which we know is not the case, therefore we must have that \( a _ 1 \le _ A a _ 2 \) which means that \( f ^ { - 1 } \left( b _ 1 \right) \le _ A f ^ { -1 } \left( b _ 2 \right) \)
When a Function Defined in Terms of a Function is a Function
Suppose that \( g : A \to B \) and \( h : A \to A \), then if \( f \) is a defined such that
\[
f \left( g \left( a \right), g \left( b \right) \right) = g \left( h \left( a, b \right) \right)
\]
is a function iff for any \( x, y, z, w \in A \)
\[
\left(g \left( x \right) = g \left( z \right) \land g \left( y \right) = g \left( w \right) \right) \implies g \left( h \left( x, y \right) \right) = g \left( h \left( z, w \right) \right)
\]