Math Functions

Function

A function $f$ from a set $X$ to a set $Y$, denoted $f:X\to Y$ is a relation that satisfies the following ($f$ is well-defined)

1. $\forall x\in X\exists y\in Y(x,y)\in f$
2. $\forall x\in X\forall y_1,y_2\in Y\left(\left((x,y_1)\in f\wedge (x,y_2)\in f\right)\to y_1=y_2\right)$ (all the $y$ in 1. is unique) or
   Let $f$ be a relation on sets $X$ and $Y$ i.e. $f\subseteq X\times Y$ . Then $f$ is a function from $X$ to $Y$ iff $\forall x\in X\exists !y\in Y(x,y)\in f$
   or
   $f:X\to Y=\{(x,y):(x,y)\in (X\times Y)\wedge b=f(a)\}$
   or $f:X\to Y=\{(x,y):(x,y)\in (X\times Y)\wedge \forall x\in X\exists !y\in Y(x,y)\in f\}$
   A function from $X$ to $Y$ is a mapping from each element of $X$ to exactly one element of $Y$
   i.e. in the function diagram, there is only one arrow coming out from every element of $X$ and every element of $X$ has an arrow coming out of it
   or
   A function $f:X\to Y$ is well-defined (exists), if it has the following property:
   $\forall x_1,x_2\in X(x_1=x_2\to f(x_1)=f(x_2))$

Definitions

• let $f:X\to Y$ be a function. $f(x)=y$ iff $(x,y)\in f$
  • $x\stackrel{f}{\to }y$
  • $f:x\mapsto y$
• $x$ is the argument of $f$
• $f(x)$ is the image of $x$ under $f$
• If $f(x)=y$ then $x$ is a preimage of $y$
• $X$ is the domain of $f$
• $Y$ is the co-domain of $f$
• range is all possible outputs of $f$, or the setwise image of $X$ under $f$
• two functions can be derived from $g:X\to Y$
  • $f:\mathcal{P}(X)\to \mathcal{P}(Y)$ is the setwise image of $g$
  • $f^{-1}:\mathcal{P}(y)\to \mathcal{P}(X)$ is the setwise preimage of $g$
  • if $A\subseteq X$, then let $f(A)=\{f(x):x\in A\}$
  • if $B\subseteq Y$, then let $f^{-1}(B)=\{x\in X:f(x)\in B\}$
  • $f(A)$ is the setwise image of $A$, and $f^{-1}(B)$ is the setwise preimage of $B$ under $g$
  • note: $f^{-1}$ here is not an inverse function although they have the same symbol. $f^{-1}(\alpha )$ can also be written $\text{setwise\_preimage}(f)(\alpha )$
  • e.g. $g:\mathbb{Z}\to \mathbb{Z}$ defined $g(x)=x^2\forall x\in \mathbb{Z}$ . $g(\{-2,0,2\})=\{4,0,4\}=\{0,4\}$ and $g^{-1}(\{0,1,2\})=\{-1,0,1\}$ because $g(0)=0;g(-1)=g(1)=1$ and $g^{-1}(\{2\})=\{\}$
  • Setwise preimage function always exists

Equality of Functions

$f:A\to B$ and $g:C\to D$ are equal ($f=g$) iff:

1. $A=C$ and $B=D$ , and
2. $f(x)=g(x)\forall x\in A$

Properties of Functions

• An injection (or injective function)
  • one-to-one or $\forall x_1,x_2\in X(f(x_1)=f(x_2)\to x_1=x_2)$ or equivalently (contrapositive), $x_1\ne x_2\to f(x_1)\ne f(x_2)$
  • f is not injective iff $\exists x_1,x_2\in X(f(x_1)=f(x_2)\wedge x_1\ne x_2)$
• A surjection (or surjective function or “onto”)
  • all elements in the co-domain have an input that result in it (range = co-domain)
  • $\forall y\in Y\exists x\in X(y=f(x))$
• A bijection (or bijective function)
  • one-to-one correspondence (all elements in co-domain has exactly one item that results in it)
  • a function is bijective iff it is both injective and surjective
  • $\forall y\in Y\exists !x\in X(y=f(x))$
  • If a function has an inverse, then it is bijective
• Inverse
  • for $f:X\to Y$ , $g:Y\to X$ is an inverse of $f$ iff $\forall x\in X\forall y\in Y(y=f(x)\leftrightarrow x=g(y))$
  • inverse of $f$ is denoted $f^{-1}$
  • inverse functions are unique
  • There exists an inverse iff it is bijective (theorem 7.2.3)

Composing Functions

Let $f:X\to Y$ and $g:Y\to Z$
The composition of f and g, $g\circ f:X\to Z$ is defined as: $(g\circ f)(x)=g(f(x))\forall x\in X$
From tutorial 6 Q2, $(g\circ f{)}^{-1}=f^{-1}\circ g^{-1}$

Identity Functions

The identity function on a set $X$ , $i{d}_x$ , is the function from $X$ to $X$ defined by $i{d}_x(x)=x$ for all $x\in X$ let $f:X\to Y$ Theorem 7.3.1:

• $f\circ i{d}_x=f$
• $i{d}_x\circ f=f$

Inverse Function

Composing a function ith its inverse results in the identity function: Theorem 7.3.2 (let $f:X\to Y$)

Properties

• Composing a function with its inverse results in the identity function (Theorem 7.3.2). Let $f:X\to Y$
  • $f^{-1}\circ f=i{d}_x$
  • $f\circ f^{-1}=i{d}_y$
• Function composition is associative
  • for $f:A\to B$, $g:B\to C$ and $h:C\to D$, then $(h\circ g)\circ f=h\circ (g\circ f)$
• Function composition is not commutative
  • Apart from special cases, $g\circ f\ne f\circ g$
• If $f$ and $g$ are both injective, then $g\circ f$ is injective (Theorem 7.3.3)
• If $f$ and $g$ are both surjective, then $g\circ f$ is surjective (Theorem 7.3.4)

Functions on ${\mathbb{Z}}_n$

• ${\mathbb{Z}}_n$ is the set of equivalence classes on mod-$n$ Congruence Relations.
  • In terms of functions, it can be taken that the domain is bounded to $n$ integer values
• Addition and multiplication functions on ${\mathbb{Z}}_n$ are well-defined (the “same” input will result in the “same” output (mod-n))
  • Let $f$ be the $+$ mod-n function, and $[x]$ means $x$ mod $n$
    • $f$ is defined as $[x_1]f[y_1]=[x_1+y_1]$
    • well defined means: for all $n\in {\mathbb{Z}}^{+}$ and all $[x_1],[y_1],[x_2],[y_2]\in {\mathbb{Z}}_n$ : $[x_1]=[x_2]\wedge [y_1]=[y_2]\to [x_1]f[y_1]=[x_2]f[y_2]$
  • Same for multiplication

Representing Sequences and Strings

Sequence (infinite)

• A sequence $a_0,a_1,a_2\dots$ can be represented by a function $a$ whose domain is ${\mathbb{Z}}_{\ge 0}$ that satisfies $a(n)=a_n$ for all $n\in {\mathbb{Z}}_{\ge 0}$
  • Therefore, any function whose domain is ${\mathbb{Z}}_{\ge m}$ for some $m\in \mathbb{Z}$ represents a sequence
• Sequences can be denoted $A^{\infty }=Seq(A)=\exists n\in \mathbb{Z}\mathbb{Z}\to A$
  • i.e. all the elements of the sequence can be found in $A$

String (finite)

• A string is a finite sequence
• A string or word over set $A$ is an expression of the form $a_0{a}_1{a}_2\dots a_{l-1}$ where $l\in {\mathbb{Z}}_{\ge 0}$ and $a_0,a_1,\dots ,a_{l-1}\in A$
• $l$ is the length of the string. The empty string $\epsilon$ is the string of length $0$
• Strings can be denoted $A^{\ast }=Str(A)=\exists m\in \mathbb{Z},l\in {\mathbb{Z}}_{\ge 0}[m,m+l)\to A$
  • i.e. all the elements of the string can be found in $A$

Equality

• Sequences $a_0,a_1,a_2,\dots$ and $b_0,b_1,b_2,\dots$
  • if their corresponding elements are equal, or $a(n)=b(n)$ for every $n\in {\mathbb{Z}}_{\ge 0}$
• Strings
  • if their lengths are equal and their corresponding elements are equal, or $a_i=b_i$ for all $i\in \{0,1,\dots ,l-1\}$