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

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

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

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

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.

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

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

Bijective function

a function is bijective iff it is surjective and injective

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

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.