Let R be a relation from A to B (R⊆A×B) Definitions:
The domain of R is the set {a∈A∣∃b∈Bs.t.(a,b)∈R}.
The image of R is the set {b∈B∣∃a∈As.t.(a,b)∈R}.
Example of Domain and Image
Let A={1,2,3}
Let B={10,12,18,20} R={(1,12),(1,20),(3,10),(3,12)}
The domain of R is {1,3}
The image of R is {10,12,20}
A relation R is called single valued if the following is true:
If (a,b)∈R and (a,c)∈R, then b=c.
Alternatively, for every a∈A, there is at most one b∈B such that (a,b)∈R.
Definition:
A relation f⊆A×B is called a function from A to B (denoted f:A→B) if f is single valued and the domain of f is A.
Example of a Function
Let A={1,2,3}
Let B={10,12,18,20}
Let f1:A→B.f1={(1,10),(2,18),(3,10)}
Let f2:A→B.f2={(3,12),(2,10),(1,18)}
(We write f1(2)=18,f2(3)=12, etc.)
Clearly every f:A→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, andf(x)=g(x) for all x 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→B is called one-to-one (or injective) if whenever a1=a2, then f(a1)=f(a2).
Alternatively, If f(a1)=f(a2), then a1=a2.
Example of a One-to-One Function
In examples f1,2,3 above, f3 is one to one, but not f1 or f2.
Onto
Definition: f:A→B is called onto (or surjective) if for every b∈B, there is some a∈A such that f(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→B is both one-to-one and onto, then f is called a bijection (or one-to-one correspondence).
For example, f3 is a bijection.
The identity function on A (where fIA(a)=a) is trivially a bijection.
Composition of Functions
Let f:A→B,g:B→C.
Definition:
The composed function(g∘f):A→C is defined as follows:
Note reverse notation: Though f is applied to g, we write g∘f.
(g∘f)(a) is G of F of a
Example of Composed Functions
Let f,g:R→R. f(x)=x2+3 g(x)=2x−5
(g∘f)(x)=g(f(x))=g(x2+3)=2(x2+3)−5=2x2+1
(f∘g)(x)=f(g(x))=f(2x−5)=(2x−5)2+3=4x2−20x+28
Note from this example, composition of functions is not commutative. f∘g=g∘f in general.
However, function composition is associative.
E.g., let f,g,h:R→R.(h∘(g∘f))(x)=((h∘g)∘f)(x).
If f:A→B,g:B→C are both onto, then so is g∘f.
Proof (good to be familiar with)
To show g∘f is onto, let c∈C. We wish to find a source of c under g∘f.
⇒ Since g is onto, ∃b∈B with g(b)=c. ⇒ Since f is onto, ∃a∈A with f(a)=b.
∴(g∘f)(a)=g(f(a))=g(b)=c⇒ We found a source of c under g∘f
If f:A→B,g:B→C are both one to one, then so is g∘f.
Proof (good to be familiar with)
Suppose (g∘f)(a1)=(g∘f)(a2). We wish to show that a1=a2.
⇒g(f(a1))=g(f(a2)) ⇒ Since g is one-to-one, we know that f(a1)=f(a2) ⇒ Since f is one-to-one, we know that a1=a2
Invertibility
Definition: f:A→B is left invertible if there is some g:B→A such that g∘f=IA.
We call g a left inverse of f.
Definition: f:A→B is right invertible if there is some g:B→A such that f∘g=IB.
We call g a right inverse of f.
Function Invertibility [SUPER IMPORTANT]
f:A→B is left invertible if and only if f is one-to-one. f:A→B is right invertible if and only if f is onto. f:A→B is invertible if and only if f is a bijection.
if f is invertible, there is a unique function g:B→A such that g∘f=IA and f∘g=IB. (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→B be any function, let C⊆A,D⊆B
Then define:
f(C)={f(x)∣x∈C}= the set of images of all elements of C
f−1(D)={x∈A∣f(x)∈D}= the set of all sources of elements of D
Don’t mix up these terms!
f−1 should not be confused with “f inverse”; f−1(D) is defined even when f is not invertible.
Even though the notation is the same in both cases, if the parameter of f−1 is a set, we’re referring to the inverse image of a subset, not the whole function.