Discrete Mathematics· Note 03

Functions

Year 2 · Semester ILast updated

Jan. 14

Definitions

Let RR be a relation from AA to BB (R⊆A×BR\subseteq A\times B)
Definitions:
The domain of RR is the set { a∈A∣∃b∈B s.t.(a,b)∈R }\set{a\in A\mid\exists b\in B \ s.t. (a,b)\in R}.
The image of RR is the set { b∈B∣∃a∈A s.t.(a,b)∈R }\set{b\in B\mid\exists a\in A \ s.t. (a,b)\in R}.

Example of Domain and Image

Let A={ 1,2,3 }A=\set{1,2,3}
Let B={ 10,12,18,20 }B=\set{10,12,18,20}
R={ (1,12),(1,20),(3,10),(3,12) }R=\set{(\textcolor{red}{1},\textcolor{green}{12}),(\textcolor{red}{1},\textcolor{green}{20}),(\textcolor{red}{3},\textcolor{green}{10}),(\textcolor{red}{3},\textcolor{green}{12})}

The domain of RR is { 1,3 }\set{\textcolor{red}{1},\textcolor{red}{3}}
The image of RR is { 10,12,20 }\set{\textcolor{green}{10},\textcolor{green}{12},\textcolor{green}{20}}

A relation RR is called single valued if the following is true:

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

Definition:
A relation f⊆A×Bf\subseteq A\times B is called a function from AA to BB (denoted f:A→Bf:A\to B) if ff is single valued and the domain of ff is AA.

Example of a Function

Let A={ 1,2,3 }A=\set{1,2,3}
Let B={ 10,12,18,20 }B=\set{10,12,18,20}
Let f1:A→Bf_1:A\to B. f1={ (1,10),(2,18),(3,10) }f_1=\set{(1,10),(2,18),(3,10)}
Let f2:A→Bf_2:A\to B. f2={ (3,12),(2,10),(1,18) }f_2=\set{(3,12),(2,10),(1,18)}

(We write f1(2)=18f_1(2)=18, f2(3)=12f_2(3)=12, etc.)

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

Jan. 21

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

Missing example here.

If you can see this, please let me know that I’m missing the example.

One To One

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

Example of a One-to-One Function

In examples f1,2,3f_{1,2,3} above, f3f_3 is one to one, but not f1f_1 or f2f_2.

Onto

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

One to One and Onto in plain English
  • One to One: Every output has a unique input.
  • Onto: Everything in the codomain has at least one source in the domain
Bijection

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

The identity function on AA (where fIA(a)=af_{I_A}(a)=a) is trivially a bijection.

Composition of Functions

Let f:A→B,g:B→Cf:A\to B,g:B\to C.

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

∀a∈A:(g∘f)(a)=g(f(a))\forall a\in A: (g\of f)(a)=g\left(f(a)\right)


Note:

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

Let f,g:R→Rf,g:\R\to\R.
f(x)=x2+3f(x)=x^2+3
g(x)=2x−5g(x)=2x-5

(g∘f)(x)=g(f(x))=g(x2+3)=2(x2+3)−5=2x2+1(g\of f)(x) = g(f(x)) = g(x^2+3)=2(x^2+3)-5=2x^2+1

(f∘g)(x)=f(g(x))=f(2x−5)=(2x−5)2+3=4x2−20x+28(f\of g)(x)=f(g(x))=f(2x-5)={(2x-5)}^2+3=4x^2-20x+28

Note from this example, composition of functions is not commutative.
f∘g≠g∘ff\of g \not= g\of f in general.

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

If f:A→B, g:B→Cf:A\to B,\ g:B\to C are both onto, then so is g∘fg\of f.

Proof (good to be familiar with)

To show g∘fg\of f is onto, let c∈Cc\in C. We wish to find a source of cc under g∘fg\of f.

⇒\Rightarrow Since gg is onto, ∃b∈B\exists b\in B with g(b)=cg(b)=c.
⇒\Rightarrow Since ff is onto, ∃a∈A\exists a\in A with f(a)=bf(a)=b.

∴(g∘f)(a)=g(f(a))=g(b)=c⇒\therefore (g\of f)(a)=g(f(a))=g(b)=c\Rightarrow We found a source of cc under g∘fg\of f

If f:A→B, g:B→Cf:A\to B,\ g:B\to C are both one to one, then so is g∘fg\of f.

Proof (good to be familiar with)

Suppose (g∘f)(a1)=(g∘f)(a2)(g\of f)(a_1)=(g\of f)(a_2). We wish to show that a1=a2a_1=a_2.

⇒g(f(a1))=g(f(a2))\Rightarrow g(f(a_1))=g(f(a_2))
⇒\Rightarrow Since gg is one-to-one, we know that f(a1)=f(a2)f(a_1)=f(a_2)
⇒\Rightarrow Since ff is one-to-one, we know that a1=a2a_1=a_2

Invertibility

Definition:
f:A→Bf:A\to B is left invertible if there is some g:B→Ag:B\to A such that g∘f=IAg\of f = I_A.

We call gg a left inverse of ff.

Definition:
f:A→Bf:A\to B is right invertible if there is some g:B→Ag:B\to A such that f∘g=IBf\of g = I_B.

We call gg a right inverse of ff.

Function Invertibility [SUPER IMPORTANT]

f:A→Bf:A\to B is left invertible if and only if ff is one-to-one.
f:A→Bf:A\to B is right invertible if and only if ff is onto.
f:A→Bf:A\to B is invertible if and only if ff is a bijection.

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

We call ff an invertible function and gg the inverse function of ff (denoted f−1f^{-1}).

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

Jan. 28

Image and Inverse Image of Subsets

Let f:A→Bf:A\to B be any function, let C⊆A, D⊆BC\sseq A,\ D\sseq B

Then define:

  1. f(C)={ f(x)∣x∈C }=f(C)=\set{f(x)\mid x\in C}= the set of images of all elements of CC
  2. f−1(D)={ x∈A∣f(x)∈D }=f^{-1}(D)=\set{x\in A\mid f(x)\in D}= the set of all sources of elements of DD
Don’t mix up these terms!

f−1f^{-1} should not be confused with “ff inverse”; f−1(D)f^{-1}(D) is defined even when ff is not invertible.

Even though the notation is the same in both cases, if the parameter of f−1f^{-1} is a set, we’re referring to the inverse image of a subset, not the whole function.