Functions

Functions associate inputs with outputs in a well-defined way.

A function from a set $A$ to a set $B$ is a rule that assigns each input in $A$ to exactly one output in $B$.

Suppose $A$ and $B$ are sets. A function $f$ from $A$ to $B$ (denoted as $f:A\to B$) is a relation $f\subseteq A\times B$ from $A$ to $B$, satisfying the property that for each $a\in A$ the relation $f$ contains exactly one ordered pair of form $(a,b)$. The statement $(a,b)\in f$ is abbreviated $f(a)=b$.

Injective

A function is injective if different inputs map to different outputs. That is, for a function $f:A\to B$, if for all $a,a\prime \in A$, $a\ne a\prime$ implies $f(a)\ne f(a\prime )$.

Surjective

A function is surjective if there is an input that maps to every output in the codomain. For a function $f:A\to B$, $f$ is surjective if for every $b\in B$ there is an $a\in A$ with $f(a)=b$.

Bijective

A function is bijective if it is both injective and surjective.

The Pigeonhole Principle

Suppose $A$ and $B$ are finite sets and $f:A\to B$ is any function.

1. If $|A|>|B|$, then $f$ is not injective.
2. If $|A|<|B|$, then $f$ is not surjective.

Identity function

The identity function on a set is the function that sends any element of the set to itself. For a set $A$, the identity function on $A$ is the function $i_A:A\to A$ defined as $i_A(x)=x$ for every $x\in A$

Inverse relation

Given a relation $R$ from $A$ to $B$, the inverse relation of $R$ is the relation from $B$ to $A$ defined as $R^{-1}=(y,x):(x,y)\in R$. In other words, the inverse of $R$ is the relation $R^{-1}$ obtained by interchanging the elements in every ordered pair in $R$.

If $f:A\to B$ is bijective then its inverse is the function $f^{-1}:B\to A$. The functions f and $f^{-1}$ obey the equations $f^{-1}$ ◦ f = i_A$and$f ◦ f^{−1} = i_B$.