Nov 11-15
Definition: A function \(f:A\to B\) is a subset \(f\subset A\times B\) with the property that for every \(a\in A\) there is exactly one \(b\) in \(B\) so that \((a,b)\in f\). We write \(f:A\to B\) to mean that \(f\) is a function with domain \(A\) and co-domain \(B\).
Compare this with the definition of a function as a “rule.” The associated “rule” says: to compute \(f(a)\), find the (uniquely determined) pair \((a,b)\) in \(f\), and then set \(f(a)=b\).
In some sense this definition replaces the notion of a function with its graph.
\(A\) is called the DOMAIN of \(f\) and \(B\) is called the CO-DOMAIN.
The range of \(f\) is the subset of \(b\) that occur in a pair \((a,b)\in f\).
A function can be drawn as a graph or as a “mapping” between two sets (see figure 12.3 in Hammack).
Consider problem 1 from Hammack. \(A=\{0,1,2,3,4\}\) and \(B=\{2,3,5,6\}\). Then \(f=\{(0,3),(1,3),(2,4), (3,2), (4,2)\}\) Verify that \(f\) is a function and then find its range.
Is the subset of pairs of integers \((x,y)\) where \(3x+y=4\) a function from \(\mathbf{Z}\) to \(\mathbf{Z}\)?
Definition: A function is injective if it has the property that \(f(a)\not=f(b)\) implies \(a\not=b\). (or \(f(a)=f(b)\) implies \(a=b\)). A function is surjective if for every \(b\in B\) there is an \(a\) with \((a,b)\in f\). A function is bijective if it is both injective and surjective.
Injective is also called “one-to-one.” Surjective is also called “onto.”
Surjectivity depends on the codomain (you can shrink the codomain to make the function surjective).
This function is not injective because \(f(n,m)\) is always even; so for example \(f(n,m)=1\) has no solution. It is not injective because \(f(4,2)=f(0,0)=0\) so there are two different elements \(a=(4,2)\) and \(b=(0,0)\) in the domain with \(f(a)=f(b)\).
To check surjectivity, you have to show that, if \(y\in \mathbb{Q}-\{5\}\), then the equation \((5x+1)/(x-2)=y\) has a solution \(x\in \mathbb{Q}-\{2\}\). Set \(x=(-2y-1)/(-y+5)\). Since \(y\not=5\), this makes sense for any \(y\) in the codomain. Also the function on the right is never equal to \(2\), so the \(x\) is in the domain of the function.
Such a function is determined by its values on each element in the domain. To count the functions, you can send each of \(0\), \(1\), and \(2\) to any of \(0\), \(1\), and \(2\); so you have three choices of three things, for a total of \(27=3^3\) functions. If the function is injective, then \(0\), \(1\), and \(2\) need to go to different things, so you have three choices for where to send \(0\), then \(2\) choices for where to send \(1\), and then \(2\) goes to whatever is left. That’s a total of \(3\times 2\times 1 =6\) injective functions. If the function is surjective, then something has to hit \(0\) – there are three choices; something has to hit \(1\) – there are two choices left – and then whatever you haven’t used must hit \(2\). So again there are \(3\times 2\times 1=6\) maps. Implicit in this is the fact that in this case the surjective, injective, and bijective functions are all the same.
Theorem: The function \(f:\mathbb{Z}_m\to \mathbb{Z}_m\) given by \(f(x)=ax\) is bijective if and only if \(\mathrm{gcd}(a,m)=1\).
First suppose that \(\mathrm{gcd}(a,m)=1\). We show that \(f(x)=ax\) is injective. Suppose that \(f(x)=f(y)\). This means that \(ax\equiv ay\pmod{m}\). Since \(\mathrm{gcd}(a,m)=1\) we can cancel the \(a\) and see that \(x\equiv y\pmod{m}\). Therefore \(f\) is injective (congruence means equality in \(\mathbb{Z}_m\) ). To show that \(f\) is surjective, we must show that we can solve the equation \(f(x)=y\) for any \(y\in \mathbb{Z}_m\). This is the equation
\[ax\equiv y\pmod{m}\]
and by the theorem on linear congruences this has a solution when \(\mathrm{gcd}(a,m)=1\) since \(1\) divides \(y\) for any \(y\).
Therefore if \(\mathrm{gcd}(a,m)=1\) the map \(f\) is surjective and injective and thus bijective.
Now we show that if the function is bijective then \(\mathrm{gcd}(a,m)=1\). It’s a little easier to assume instead that \(\mathrm{gcd}(a,m)\not=1\) and prove that the function is not bijective. For this we can give counterexamples. Suppose \(d=\mathrm{gcd}(a,m)\) and let \(k=m/d\). Then \(k\not\equiv 0 \pmod{m}\) (since \(d>1\) so \(k<m\).) But \(ak=am/d=(a/d)m\equiv 0\pmod{m}\). So \(f(k)=f(0)\) but \(k\not=0\) in \(\mathbb{Z}_{m}\) so \(f\) is not injective. In fact, \(f\) is not surjective either. Since \(d>1\), by the theorem on congruences we cannot find \(x\in\mathbb{Z}_{m}\) such that \(ax\equiv 1\pmod{m}\), so \(1\) is not in the range of \(f\).
Theorem: Let \(a\) and \(b\) be integers with \(b\not=0\) and let \(f:\mathbb{Z}\times\mathbb{Z}\to\mathbb{Z}\) be the function \(f(x,y)=ax+by\). Then the range of \(f\) is the set of \(n\in\mathbb{Z}\) such that \(d=\mathrm{gcd}(a,b)\) divides \(n\).
This is a restatement of (a part of) the theorem on linear diophantine equations. The range of \(f\) is the set of integers \(A\) such that \(f(x,y)=A\) has a solution; and the theorem on diophantine equations tells us that this equation has a solution exactly when \(d|A\).
Definition: Suppose that \(f:A\to B\) is a function and \(g:B\to C\) is a function. The composition \(g\circ f\) is a function from \(A\to C\) defined by \((g\circ f)(a)=g(f(a))\).
This makes sense because \(f(a)\in B\) and \(g:B\to C\).
Examples:
\(f:\mathbf{R}\to\mathbf{R}\) given by \(f(x)=x^2\), and \(g:\mathbf{R}\to\mathbf{R}\) with \(g(x)=\sin(x)\). What are \(f\circ g\) and \(g\circ f\)?
\(A=\{0,1,2,3\}\), \(B=\{1,2,3,4\}\), \(C=\{1,3,5,6\}\). \(f=\{(0,1),(1,2), (2,3),(3,3)\}\) in \(A\times B\). \(g=\{(1,3), (2,3),(3,3),4,3)\}\) in \(B\times C\). What is the composition?
Theorem: Composition of functions is associative.
Theorem: If \(f:A\to B\) and \(g:B\to C\) are injective then \(g\circ f\) is injective. Similarly if \(f\) and \(g\) are surjective then \(g\circ f\) is surjective. And if both are bijective, so is the composition.
Let’s verify that if \(f\) and \(g\) are injective then so is \(g\circ f\). Suppose \(g(f(x))=g(f(y))\). Then by injectivity of \(g\) we have \(f(x)=f(y)\). By injectivity of \(f\) we have \(x=y\). Therefore \(g\circ f\) is injective.
The converse is false. Let \(A=\{a,b\}\), let \(B=\{0,1,2\}\), and let \(C=\{u,v\}\). Define \(f:A\to B\) by \(f(a)=0\), \(f(b)=1\). Define \(g:B\to C\) by \(g(0)=u\), \(g(1)=v\), \(g(2)=v\). Now \(g\circ f\) sends \(a\to u\) and \(b\to v\) so it is injective; but \(g\) is not injective.
There is a partial converse:
Proposition: If \(g\circ f\) is injective, then \(f\) is injective. If \(g \circ f\) is surjective, then \(g\) is surjective.
Someone asked in class about linear maps \(f:\mathbf{R}^{M}\to\mathbf{R}^{N}\). In linear algebra you learned about the rank and the nullity of a linear map (or a matrix). The rank is the dimension of the range of \(f\). The nullity is the dimension of the null space of \(f\). An important basic theorem about linear maps is that rank plus nullity is the dimension of the domain of \(f\).
The null space of \(f\) is the space of vectors that map to zero under \(f\). If \(f\) were injective, then the only value that can map to zero is zero, so \(f\) is injective if and only if its nullity is zero.
If \(f\) is surjective, then its range must be equal to its codomain, so \(f\) is surjective if and only if the rank of \(f\) is \(n\).
If \(f\) is bijective, then its rank must be \(n\) and its nullity must be zero; but this requires that \(m=n\). So a linear map is bijective if \(m=n\) and its nullity is zero or its rank is \(n\).