0.3: Functions
( \newcommand{\kernel}{\mathrm{null}\,}\)
Let A be a set. Then A×A={(a1,a2)|a1,a2∈A} is the Cartesian product of A.
If A=R then this is the Cartesian plane - Like {x,y:x,y∈A}.
A function f is a subset (symbol is ⊆) of A×B such that for every a∈A there exists a unique b∈B such that f(a)=b.
Denoted by f:A→B or Af→B.
A is the domain of the function f.
B is the co-domain of the function f.
The range of f is f(A)={f(x):x∈A}⊆B=Im(f), the image of f.
A well-defined function is one that for every value of A, there is one and only one value of B.
Definition:
Let f be a function from A→B.
-
f is called onto (surjective) if f(A)=B.
-
f is called one to one (injective) if f(x1)=f(x2),x1,x2∈A then x1=x2.
-
f is bijective if it is surjective and injective.
-
A function can be injective, surjective, bijective (both injective & surjective), or neither.
Note:
Let f:A→B. If f is 1-1 and onto then f is a bijection from A→B.
If there is a bijection between two finite sets, the number of elements in each set is the same. Notationally: |A| = |B|.
Consider the mapping:
Is this mapping
a) Well defined?
b) Is it surjective?
c) Is it injective?
d) Is it bijective?
Solution
The function is well-defined. Not injective. Not subjective, not bijective.
Consider the mapping:
Is this mapping
a) Well defined?
b) Is it surjective?
c) Is it injective?
d) Is it bijective?
Solution
This is well defined bijective function.
Given f:Q→Z where Q={ab:a,b∈Z,b≠0} and f(ab)=a. Is this a well-defined function?
Solution
Let A and B be sets such that A={ab:a,b∈Z,a≠0} and B=Z.
Using a counterexample, f(ab) is not a well-defined function since f(12)=1 and f(24)=2, but 12=24. This is an example of an element in A that maps to more than one element in B.
Example 0.3.6
Let
Q={ab:b>0,and gcd(a,b)=1}
and f:Q→Z that is defined by
f(ab)=a.
a) Is f a well-defined function? b) Is it surjective? c) Is it injective? d) Is it bijective?
Solution
-
The function is well-defined.
Let A and B be set.
Let a∈A.
We need to show that if f(a)=b then b∈B and if f(a)=b1 that b=b1.
We are given f:Q→Z, which means that this is a function thus f(a) will map to one and only one element of B. Thus if f(a)=b and if f(a)=b1 then b=b1.
In b) below, we have shown that the function is surjective, thus f(a)=b,
-
The function is surjective
Proof:
We shall show that f(Q)=Z by showing that f(Q)⊆Z and Z⊆f(Q).
Since we are given f:Q→Z, f(Q)⊆Z.
Next, we shall show that Z⊆f(Q).
Let n∈Z, then n1∈Q and f(n1)=n.
Hence n∈f(Q).
Hence Z⊆f(Q).
Since Z⊆f(Q) and f(Q)⊆Z,f(Q)=Z.◻
-
The function is not injective.
Counterexample:
Let A={ab:b>0,and gcd(a,b)=1} and B=Z.
Note 14,13∈A and that f(14),f(13)∈B and that f(14)=f(13)=1.
Since 14≠13 , the function is not injective.
-
The function is not bijective since it has been shown not to be both injective and surjective.
Operation on functions: Composition
Let f:A→B and g:B→C. Then the composition functions of g and f, g∘f:A→C, defined by
(g∘f)(a)=g(f(a)),∀a∈A.
Identity function idA:A→A defined by idA(x)=x,∀x∈A.
Let f:A→B then f has an inverse g:B→A if (f∘g)=idB and (g∘f)=idA. Note the domain of f∘g is the domain of g.
Let f:A→B be a bijection. Then the inverse of f, denoted by f−1:B→A defined by f−1(b)=a if f(a)=b if a∈A and b∈B. In this case, f∘f−1=idA, and f−1∘f=idB.
Let f:A→B and g:B→C. Then g∘f:A→C.
-
If f and g are surjective, then g∘f is surjective.
Proof:
We will show that g∘f is surjective.
Let c∈C . Since g is surjective, there exists b∈B such that g(b)=c.
Since f is surjective, there exists a∈A such that f(b)=a.
Hence there exists a∈A such that gf(f(a))=c.
Therefore, if f and g are surjective, then g∘f is surjective.◻
(better proof) If f is onto and g is onto then g∘f is onto.
Proof:
We shall show that (g∘f)(A)=C.
Since f and g are onto, by definition of a function, (g∘f)(A)⊆C.
Now we need to show that C⊆(g∘f)(A).
Let c∈C.
Since g is onto ∃b∈B s.t. c=g(b).
Since f is onto, ∃a∈A s.t. b=f(a).
Consider (g∘f)(a)=g(f(a)) (by definition)
=g(b)
=c.
Therefore c∈(g∘f)(A).
Hence C⊆(g∘f)(A).
Since (g∘f)(A)⊆C and C⊆(g∘f)(A), then g∘f is onto.◻
-
If f and g are injective, then g∘f is injective. That is,
If f is 1-1 and g is 1-1 then g∘f is 1-1.
Proof:
Let a1,a2∈A such that g∘f(a1)=g∘f(a2). Then g(f(a1))=g(f(a2)).
Since g is 1-1, f(a1)=f(a2).
Since, f is 1-1, a1=a2.
Hence g∘f is injective.
Given A is a matrix and TA:R2→R2 defined by TA[xy]=[1101][xy]. Note this is a matrix transformation which is linear.
-
Is TA 1-1?
Yes, TA is 1-1.
Proof:
Let [x1y1]and [x2y2]∈R2 s.t. TA[x1y1]=TA[x2y2].
We will show that [x1y1]=[x2y2].
TA[xy]=[x+yy].
Thus [x1+y1y1]=[x2+y2y2].
Thus x1+y1=x2+y2 and y1=y2.
Thus x1=x2 and y1=y2.
Hence [x1y1]=[x2y2].
Thus TA is 1-1.◻
-
Is TA[xy] onto?
Yes, TA[xy] is onto.
Proof:
We know by definition that TA[xy]⊆R2.
We need to show that R2⊆TA[xy].
Let [ab]∈R2.
Find [xy]∈R2 s.t. [1101][xy]=[ab].
[x+yy]=[ab].
Thus y=b and x=a−b.
Thus TA[a−bb]=[ab].
Thus TA is onto.◻
-
Does TA have an inverse? If so, what is it?
a) Yes TA has an inverse since it is a bijection (1-1 and onto) ∴ T−1A exists.
Proof: By definition? Obvious?
b) T−1A:R2→R2.
T−1A[xy]=[1−101][xy]
=[x−yy].
Check: T−1A⋅TA=[1−101]⋅[1101]=[1001].
Let f:A→B and g:B→C. Then g∘f:A→C . Given g∘f is injective and f is onto, prove that g is injective.
Proof:
Assume g∘f is injective. (by definition)
Let x1,x2∈B s.t. g(x1)=g(x2).
We shall show that x1=x2.
Let a1,a2∈A.
Since f is surjective (by definition), we know that f(a1)=x1 and f(a2)=x2.
Since x1∈B and f is surjective, ∃a1∈A s.t. f(a1)=x1.
Since x2∈B and f is surjective, ∃a2∈A s.t. f(a2)=x2.
Since g(x1)=g(x2), then g(f(a1))=g(f(a2)) and g∘f)(a1)=(g∘f)(a2).
Since g∘f) is injective, a1=a2.
Thus f(a1)=f(a2) since f is a function.
Therefore, x1=x2.
Hence g is injective.
Consider the mapping α:
Find α2 , α3 and α−1.