Function

Definition

Relation $f\subseteq A\times B$ is a function $f:A\to B$ if:

• $\forall a\in A\exists b\in B(afb)$ (without this condition, $f$ is a partial function)
  • one input (of the domain) maps to at least one output.
• $\forall a\in A\forall b,b^{\prime }\in B(afb\wedge af{b}^{\prime }\to b=b^{\prime })$ (assure right-uniqueness)
  • one input maps to at most one output.

$f(A)=\{f(a)|a\in A\}$

NOTE

A function is a special relation

Notation of the set of all functions

$B^A$ is the set of all functions $f:A\to B$

Transitivity of injectivity and surjectivity

$f,g$ injective/surjective $⟹$ $g\circ f$ injective/surjective Proof for injectivity $a\ne a^{\prime }⟹f(a)\ne f(a^{\prime })$ $⟹g(f(a))\ne g(f(a^{\prime }))$ $⟹(g\circ f)(a)\ne (g\circ f)(a^{\prime })$