03. Functions

$\gdef \N{\mathbb{N}} \gdef \Z{\mathbb{Z}} \gdef \Q{\mathbb{Q}} \gdef \R{\mathbb{R}} \gdef \C{\mathbb{C}} \gdef \setcomp#1{\overline{#1}} \gdef \sseq{\subseteq} \gdef \pset#1{\mathcal{P}(#1)} \gdef \covariant{\operatorname{Cov}} \gdef \of{\circ} \gdef \p{^{\prime}} \gdef \pp{^{\prime\prime}} \gdef \ppp{^{\prime\prime\prime}} \gdef \pn#1{^{\prime\times{#1}}} $

Jan. 14

Definitions¶

Let \(R\) be a relation from \(A\) to \(B\) (\(R\subseteq A\times B\))
Definitions:
The domain of \(R\) is the set \(\set{a\in A\mid\exists b\in B \ s.t. (a,b)\in R}\).
The image of \(R\) is the set \(\set{b\in B\mid\exists a\in A \ s.t. (a,b)\in R}\).

A relation \(R\) is called single valued if the following is true:

• If \((a,b)\in R\) and \((a,c)\in R\), then \(b=c\).
  • Alternatively, for every \(a\in A\), there is at most one \(b\in B\) such that \((a,b)\in R\).

Definition:
A relation \(f\subseteq A\times B\) is called a function from \(A\) to \(B\) (denoted \(f:A\to B\)) if \(f\) is single valued and the domain of \(f\) is \(A\).

Clearly every \(f:A\to B\) consists of exactly 3 pairs.
Intuitively: A function \(f\) is a “machine” taking in input and yielding output.
Another way of saying this is that it maps values of \(A\) to values of \(B\).

Jan. 21

Two functions \(f,g\) are equal only if they have the same domain, the same range, and \(f(x)=g(x)\) for all \(x\) in the domain.

One To One¶

Definition:
\(f:A\to B\) is called one-to-one (or injective) if whenever \(a_1\neq a_2\), then \(f(a_1)\neq f(a_2)\).
Alternatively, If \(f(a_1)=f(a_2)\), then \(a_1=a_2\).

Onto¶

Definition:
\(f:A\to B\) is called onto (or surjective) if for every \(b\in B\), there is some \(a\in A\) such that \(f(a)=b\).

Bijection¶

Definition:
If \(f:A\to B\) is both one-to-one and onto, then \(f\) is called a bijection (or one-to-one correspondence).
For example, \(f_3\) is a bijection.

The identity function on \(A\) (where \(f_{I_A}(a)=a\)) is trivially a bijection.

Composition of Functions¶

Let \(f:A\to B,g:B\to C\).

Definition:
The composed function \((g\of f):A\to C\) is defined as follows:

Note:

1. This is exactly the same as Composition of Relations, applied to functions.
2. Note reverse notation: Though \(f\) is applied to \(g\), we write \(g\of f\).
   1. \((g\of f)(a)\) is G of F of a

Note from this example, composition of functions is not commutative.
\(f\of g \not= g\of f\) in general.

However, function composition is associative.
E.g., let \(f,g,h:\R\to\R\). \((h\of(g\of f))(x)=((h\of g)\of f)(x)\).

If \(f:A\to B,\ g:B\to C\) are both onto, then so is \(g\of f\).

If \(f:A\to B,\ g:B\to C\) are both one to one, then so is \(g\of f\).

Invertibility¶

Definition:
\(f:A\to B\) is left invertible if there is some \(g:B\to A\) such that \(g\of f = I_A\).

We call \(g\) a left inverse of \(f\).

Definition:
\(f:A\to B\) is right invertible if there is some \(g:B\to A\) such that \(f\of g = I_B\).

We call \(g\) a right inverse of \(f\).

if \(f\) is invertible, there is a unique function \(g:B\to A\) such that \(g\of f = I_A\) and \(f\of g = I_B\). (I.e., \(g\) is both a left and right inverse of \(f\).)

We call \(f\) an invertible function and \(g\) the inverse function of \(f\) (denoted \(f^{-1}\)).

Note: if \(f\) is invertible, then \(f^{-1}\) is invertible, and \({(f^{-1})}^{-1}=f\).

Jan. 28

Image and Inverse Image of Subsets¶

Let \(f:A\to B\) be any function, let \(C\sseq A,\ D\sseq B\)

Then define:

1. \(f(C)=\set{f(x)\mid x\in C}=\) the set of images of all elements of \(C\)
2. \(f^{-1}(D)=\set{x\in A\mid f(x)\in D}=\) the set of all sources of elements of \(D\)