Functions
Contents
3.1. Functions#
Functions are incredibly important to the study of mathematics. We have all seen functions in some way during our previous mathematical education. Although, functions are usually only introduced informally and, moreover, for the case of real numbers.
The fundamental part of a function is it takes some input and returns another. That is, it associates an input with an output. We have probably heard of notions like the “vertical line test” to determine if a curve on the Cartesian plane is in fact a function or not.
The vertical line test is the visual analogue to the fact that the output of a function must be associated with exactly one input. Indeed, this informal description of a function is what we have used since grade school.
3.1.1. A Formal Definition#
Consider now a more generalized and formal description.
Definition (function)
A function \(f\) is a binary relation from a set \(X\) to a set \(Y\) such that for every \(x \in X\), there is exactly one \(y \in Y\) such that \((x,y) \in f\).
Notice that the definition of a function is as a special kind of binary relation. We have previously seen reflexivity, symmetry, transitivity, and antisymmetry. Now, we see that a function is a special kind of relation with two properties:
Every element of \(X\) must appear as the first coordinate of some pair in the binary relation \(f\).
Every element of \(X\) must appear only once in the binary relation \(f\).
When these two properties hold, a binary relation is a function.
Tip
The terms function and map are often used interchangeably. Although, in some branches of mathematics, a map is more general than a function, but still not as general as a binary relation.
Take a very simple first example. Consider the following binary relations from \(A = \{1,2,3\}\) to \(B = \{a,b,c\}\).
Which of these binary relations are in fact functions?
Solution
\(\mathcal{R}_1\) is a function.
\(\mathcal{R}_2\) is a function.
\(\mathcal{R}_3\) is not a function, \(1\) appears twice.
\(\mathcal{R}_4\) is not a function, \(3\) does not appear in any pair and both \(1\) and \(2\) both appear twice each.
\(\mathcal{R}_5\) is not a function, \(3\) does not appear in any pair.
When a binary relation is a function, we use special terminology and notation. Let \(\mathcal{R}\) be a binary relation from the set \(A\) to the set \(B\). If \(\mathcal{R}\) is in fact a function, we often use lower-case roman letters: \(f, g, h,\) etc., rather than \(\mathcal{R}\) to signify that we have a function rather than a more general binary relation.
Moreover, we use a special notation \(f : A \rightarrow B\) to signify that the function \(f\) is from set \(A\) to set \(B\). We say \(f\) maps \(A\) to \(B\). When a binary relation is a function, we call \(A\) the domain of the function and \(B\) the codomain of a function.
Definition (domain)
When a binary relation from set \(A\) to set \(B\) is a function, we call \(A\) the domain of the function.
Definition (codomain)
When a binary relation from set \(A\) to set \(B\) is a function, we call \(B\) the codomain of the function.
Let \(f : A \rightarrow B\) be a function. We write \(f(a) = b\) when \(a \in A\), \(b \in B\), and \((a,b) \in f\). Here, \(f(a)\) is called the image of \(a\) under \(f\) while \(a\) is called the preimage. We can also say that \(f(a)\) is the value of \(f\) applied to the argument \(a\).
Important
Do not mix up \(f\) and \(f(x)\). \(f\) is a function. \(f(x)\) denotes the element in the codomain associated with \(x\) in the binary relation \(f\).
3.1.2. Representing Functions#
Much like sets, we can construct and represent functions in many ways. Indeed, functions are binary relations and binary relations are sets.
Discrete functions using the roster method.
One representation of a function is the roster method, just as for sets. Given a finite domain, it is possible to simply list all of the pairs in the function. Consider the previous example from Section 2.2.1 relating students to majors.
A discrete and finite function
Let \(S\) be the set of students \(\{\text{Andrea}, \text{Bruce}, \text{Davood}, \text{Fiona}, \text{Jalal}, \text{Rahul}\}\).
Let \(M\) be the set of majors \(\{\text{Computer Science}, \text{Mathematics}, \text{Physics}, \text{Chemistry}, \text{Biology}\}\)
A function \(f : S \rightarrow M\) maps each student in \(S\) to a unique element of \(M\).
Functions as formulas.
A more simple description of a function is as a formula. Consider a simple linear function \(f\). There are two ways to express it.
The former is common in calculus and should be very familiar. It is called functional notation That latter, which is read “\(x\) maps to \(2x + 5\)”, is called arrow notation. Arrow notation can be used to describe a function without giving it a particular name. In both cases, the domain and codomain can be implicit by context, and typically are both \(\mathbb{R}\).
However, we should be explicit, and define a function using three things: its domain, its codomain, and a formula describing the mapping.
Functional and Arrow Notations
The following two notations define the same real quadratic function.
Let \(f : \mathbb{R} \rightarrow \mathbb{R}\) be defined by \(f(x) = 2x^2 - 5x + 3\).
However, there are cases where we do not need to write the domain and codomain of a function explicitly. We can say “a function of a real variable” to mean that the domain of a function is a (subset) of the real numbers. We can say “a real-valued function” to mean a that the codomain of a function is the real numbers. Further, we can say “a function over the reals” to mean that the domain and codomain of the function are both the real numbers.
Functions as algorithms.
We can also represent functions as algorithms. Note that this does not mean that all computer functions or computer algorithms are functions.
Indeed, void computer functions are not mathematical functions. Moreover, methods, which operate on objects in object-oriented languages
are typically not mathematical functions because they use some notion of “state”.
An algorithm which returns a value solely depending on its input arguments (i.e. has no state), can represent a mathematical function.
Consider representing the previous quadratic function in python.
def f(x) :
v = 2*x**2
v -= 5*x
v += 3
return v
Functions as graphs.
We have not yet defined formally what a graph is. See Section 7. However, we can still understand and represent functions pictorially using Venn diagrams, nodes, and arrows. At least, when the function is discrete and finite.
The image below represents the function \(\{(a,2), (b,3), (c,1), (d,3)\}\).
Fig. 3.1 A function from \(A = \{a,b,c,d\}\) to \(B = \{1,2,3,4\}\).#
Note that it is not required to explicitly draw the sets \(A\) and \(B\). One only needs to draw the nodes and the arrows connecting them.
3.1.3. Properties of Functions#
Now that we can construct and represent functions, let us consider some properties of them.
An important property is a function’s range. As we have seen in the previous examples, not even element of the codomain necessarily appears in a function. For example, in Fig. 3.1, the element \(4 \in B\) is not mapped to by any element of the domain \(A\).
Definition (range)
The range of a function \(f : A \rightarrow B\) is the set of all images of \(f\) under \(A\). It is denoted by \(f(A)\).
Therefore, the range of a function is a (not necessarily strict) subset of its codomain. As we will see later, functions have special properties when their range equals their codomain.
For a function \(f : A \rightarrow B\), we can extend the notation of its range \(f(A)\) to any subset of \(A\). For \(S \subseteq A\) we have:
Properties of functions
Consider the function \(f : A \rightarrow B\) described in the image below.
What is:
\(f(a)\)?
The image of \(d\)?
The domain of \(f\)?
The range of \(f\)?
The preimage of \(12\)?
\(f(A)\)?
The preimage of \(6\)?
\(f(\{a,c,d\})\)?
Properties of functions
\(2\)
\(12\)
\(\{a,b,c,d\} = A\)
\(f(A) = \{2,12\}\)
\(\{b,d\}\)
\(\{2,12\}\)
There is none!
\(\{2,12\}\)
What this checkpoint tells us is that there is not necessarily a preimage of an element of the codomain. Moreover, the preimage may not be unique. When this is the case, we say the preimage of an element \(b\) is the subset \(S\) of the domain \(A\) such that \(f(S) = \{b\}\).
Equality#
The equality of functions is not obvious and can sometimes be misleading. Consider the functions:
\(f : \mathbb{R} \rightarrow \mathbb{R}\) where \(f(x) = x^2\) and
\(g : \mathbb{R} \rightarrow \mathbb{R}^+\) where \(g(x) = x^2\).
These functions are not equal. Their formulas and domains are the same but not their codomains.
Formally, two functions \(f: A \rightarrow B\) and \(g: A \rightarrow B\) are equal if and only if \(\forall a \in A\ f(a) = g(a)\). That is, their domains and codomains are the same, and images of every element of the domain is the same under both functions.
Partial functions#
Now that we are familiar with functions, lets consider the formal properties that make a binary relation a function. A binary relation is a function if it is total and univalent.
Definition (total)
A binary relation \(\mathcal{R}\) from \(A\) to \(B\) is total if, for every element \(a \in A\), there exists an element \(b \in B\) such that \((a,b) \in \mathcal{R}\).
Definition (univalent)
A binary relation \(\mathcal{R}\) from \(A\) to \(B\) is univalent or right-unique if, for every \(a \in A\), and for every \(b,c \in B\) we have:
If a binary relation is univalent but not total, it is a partial function. For a partial function, the set of all preimages is a subset of the domain and is called the domain of definition. Let \(f : A \rightarrow B\) be a partial function. Let \(S \subseteq A\) be its domain of definition. We say that the partial function is undefined for elements in \(A \setminus S\).
Square root as a partial function
Consider the function \(f : \mathbb{N} \rightarrow \mathbb{R}\) where \(f(n) = \sqrt{n}\). This is a partial function from \(\mathbb{Z}\) to \(\mathbb{R}\) since the square root of negative integers is undefined when the codomain is the real numbers.
This example shows a very important property of functions. A formula alone does not define a function. Consider \(f(n) = \sqrt{n}\) from \(\mathbb{R}\) to \(\mathbb{C}\). In this case, the image of negative numbers under \(f\) are all well-defined complex numbers.
Total and univalent
Show that \(f : \mathbb{R} \rightarrow \mathbb{R}\) where \(f(x) = \ln(x)\) is not a function.
Show that \(g : (0, \infty) \rightarrow \mathbb{C}\) where \(g(x) = \ln(x)\) is a function.
Total and univalent
To show \(f\) is not a function, it is sufficient to show that there exists \(x \in \mathbb{R}\) such that \(f(x)\) is undefined (that is, \(f(x) \not\in \mathbb{R}\), the codomain). Let \(x = -1\). \(f(-1) = \ln(-1)\) and \(\ln(-1)\) is not a real number. For yet another example, take \(x=0\), then \(\ln(0)\) is undefined for any codomain.
To show \(g\) is a function, we must show that it is total and univalent.
Total. Let \(x\) be an element of the domain of \(g\). Since \(0\) itself is not in the domain we can assume \(x > 0\) and we have \(g(x) = \ln(x)\). This \(g(x)\) is well defined for all such \(x\).
Univalent. Proceed by contradiction, assume there exists \(a \in (0,\infty)\) such that \(\ln(a) = b\) and \(\ln(a) = c\) where \(b \neq c\). \(\ln(a) = b\) implies \(e^b = a\). Similarly, we have \(e^c = a\). Therefore, \(e^b = e^c\) and \(b = c\). A contradiction.
Note that proofs for univalent are similar to uniqueness proofs.
Plots of functions#
We have seen in the previous section that we can represent a function using a graph where nodes from the domain are connected by arrows to nodes from its codomain.
Unfortunately, the “graph of a function” is not the same as “graphs as functions” or “functional graphs”. These latter two refer to describing a discrete function as a graph. The former is what is typically taught in grade school: the graph of a (single-variable) function is a collection points or curves which represents the function on a Cartesian plane. (I prefer to call this graphical/pictorial representation the “plot” of the function, taking its name from “plotting”, the act of drawing the graph.)
Formally, the graph of a function is actually equal to the function itself. For a function \(f: X \rightarrow Y\), its graph is the set:
Notice that this is the same set of tuples defining the function as a binary relation. However, the graph of a function is used for a different purpose. It is used to describe it visually. When the domain and codomain are a set of numbers, like \(\mathbb{N}\), \(\mathbb{Z}\), \(\mathbb{R}\), or \(\mathbb{C}\), we can plot the graph of a function on a coordinate system.
For a function \(f: \mathbb{R} \rightarrow \mathbb{R}\), it and its graph are a subset of \(\mathbb{R} \times \mathbb{R}\). Therefore, it is easy to “embed” it in the space \(\mathbb{R}^2\). Informally, that means drawing all the points in \(f\) on the Cartesian plane. Since \(f\) is over the reals, it has infinitely many points no matter how far you “zoom in”. That is, it is continuous. Its representation in \(\mathbb{R}^2\) appears as a curve.
Fig. 3.2 The graph of \(f(x) = \frac{1}{2}x^3 + x^2 - \frac{3}{2}x\) for \(f: \mathbb{R} \rightarrow \mathbb{R}\).#
For a function, say, over the integers, we can also embed its graph in the space \(\mathbb{R}^2\). However, its graph is no longer a curve but a collection of discrete points. The same function as Fig. 3.2 is shown below, but now with the domain being the integers.
Fig. 3.3 The graph of \(f(x) = \frac{1}{2}x^3 + x^2 - \frac{3}{2}x\) for \(f: \mathbb{Z} \rightarrow \mathbb{Z}\).#
Injective, Surjective, Bijective#
In addition to total and univalent, we may strengthen the conditions on a function to get particular kinds of very useful functions. Functions that are one-to-one, onto, or invertible are very important in practice.
Injective
Definition (injective)
A function is injective if every element in the range of the function has a unique preimage. That is, for a function \(f : A \rightarrow B\), \(\forall a_1, a_2 \in A, a_1 \neq a_2 \rightarrow f(a_1) \neq f(a_2)\).
When a function is injective, we call it an injection or a one-to-one function.
Fig. 3.4 An injective function from \(A\) to \(B\).#
One way to remember what “injective” means is to think “into”. Injective functions transform or map elements of \(A\) into elements of \(B\). That is, the transformed elements of \(A\) can be uniquely found within \(B\). When a function maps two (or more) elements of \(A\) to the same element of \(B\), that function is not injective. Consider Fig. 3.1. This function is not injective since \(a\) and \(c\) both map to \(2\) by \(f\).
For an injective function \(f: A \rightarrow B\), we must have \(|A| \leq |B|\).
Surjective
Definition (surjective)
A function is surjective if its codomain and range are equal. That is, for a function \(f : A \rightarrow B\), \(\forall\ b \in B \exists\ a \in A\) such that \(f(a) = b\).
When a function is surjective, we call it a surjection or an onto function.
Fig. 3.5 A sujective function from \(A\) to \(B\).#
One way to remember what “surjective” means is to think “onto”. From French, we can think “sur” means “on”. From Latin, “sur” also means “over”, “above”, “on top”. A surjective function fully “covers”, “shadows” or is “on top of” its codomain.
For an surjective function \(f: A \rightarrow B\), we must have \(|A| \geq |B|\).
Bijection
Definition (bijective)
A function is bijective if it is both injective and surjective.
When a function is bijective, we call it a bijection or an invertible function or a one-to-one correspondence. Note that the “correspondence” is very important. A one-to-one function may not be a bijection and therefore may not be a one-to-one correspondence.
Fig. 3.6 A bijective function from \(A\) to \(B\).#
Notice that a bijective function can always be rearranged so that:
the mappings are all parallel to each other,
every element of the domain maps to a unique element of the codomain, and
every element of the codomain has a unique premiage.
Fig. 3.7 A bijective function from \(A\) to \(B\).#
Since a bijective function is both injective and surjective, a bijective function \(f : A \rightarrow B\) must have \(|A| = |B|\).
Injective, Surjective, Bijective
For the following functions, determine if they are surjective, injective, or bijective. If so, give a proof. If not, supply a counterexample.
Suppose \(A = \{a,b,c,d\}\) and \(B = \{1,2,3,4,5\}\).
Injective, Surjective, Bijective
\(f_1\) is not a surjection because \(5\) does not have a preimage. \(f_1\) is an injection since every element of \(A\) has a unique image in \(B\).
\(f_2\) is not injective since, for example, \(f(3,4) = 9 + 8 = f(1,7) = 3 + 14 = 17\). \(f_2\) is surjective, since for any integer \(x\) we can solve \(x = 3n + 2m\). Namely, using \((x, -x)\).
3.1.4. Special Functions#
There are certain functions which are quite important and we give them special names. For example, “quadratic functions” and “cubic functions” are polynomial functions of degree \(2\) and \(3\), respectively.
These names describe an entire set of functions. Indeed, there are infinitely many quadratic functions over the reals. They are described by the set:
We have several other important functions to consider.
Identity function#
The identity function is a function from a set to the same set which always has its value equal to its argument. That is, \(f(a) = a\) for all \(a\) in the domain of \(f\).
Given a set \(A\), we denote the identity function on the set \(A\) as \(\text{id}_A\). We have:
Note that the identity function on a set \(A\) is the unique bijective and reflexive function on \(A\). Can you prove that?
A discrete identity function
Let \(A = \{1,2,3,4,5\}\). The identity function on \(A\) is:
Constant function#
A constant function is a function whose value is the same for every possible input. A constant function can map from one set to another, or from one set to itself. The only requirement is that the value of the function is always exactly the same value regardless of the input.
A constant and discrete example
Let \(A = \{a,b,c\}\) and \(B = \{1,2,3\}\). The following are all different constant functions from \(A\) to \(B\).
Let \(f\) be a function over the reals. For any \(c \in \mathbb{R}\), The function \(f(x) = c\) is a constant function. This is a typical example from calculus. Recall that the derivative of any linear function is a constant function. Fig. 3.8 shows a plot of the constant function \(y = \frac{3}{2}\).
Fig. 3.8 A plot of \(f(x) = 1.5\).#
Bijective constants?
As a consequence of the definition, unless the cardinality of the domain or codomain is 1, a constant function is not injective or surjective, respectively. Consider why. Draw a picture describing constant functions whose domain or codomain have only one element (not a very exciting function!).
Solution
Floor and Ceiling#
In the next chapter, we will explore The Integers. Two useful functions whose codomain are the integers are called ceiling and floor.
We can think of ceiling as “rounding up” a number to the nearest integer while floor is “rounding down” to the nearest integer. For a number \(x\), we denote its ceiling as \(\lceil x \rceil\) and its floor as \(\lfloor x \rfloor\).
Formally, ceiling is a function from \(\mathbb{R}\) to \(\mathbb{Z}\) defined as:
Meanwhile, floor is a function from \(\mathbb{R}\) to \(\mathbb{Z}\) defined as:
Hitting the floor
We have the following equalities.
\(\lfloor 4.5\rfloor = 4\)
\(\lfloor 3.999\rfloor = 3\)
\(\lceil 4.0001\rceil = 5\)
\(\lceil \sqrt{3}\rceil = 2\)
\(\lfloor -4.3\rfloor = -5\)
\(\lceil -10.9\rceil = -10\)
Factorial function#
The last important function which we will explore in this chapter is the factorial function. It will become extremely useful in our study of combinatorics.
The factorial function is a function \(f: \mathbb{N} \rightarrow \mathbb{Z}^+\) defined by \(f(n) = n!\) with:
For example, \(3! = 6, 0! = 1, 12! = 6402373705728000\).
The factorial function is known for growing extremely quickly. In particular, its values grow faster than exponential growth. For relatively small arguments, the factorial function has very very large values.
Stirling’s approximation
Computing the factorial of large, but not that large, numbers is surprisingly challenging. The typical definition requires computing \(n-1\) multiplications to determine \(n!\).
Stirling’s approximation is a relatively inexpensive formula used to approximate the factorial. For a real number \(n\), Stirling’s approximation is:
Not to be confused with equivalence relations, we may say that Stirling’s approximation is “asymptotic to” the factorial and we may write \(n! \sim n^n e^{-n}\sqrt{2\pi n}\). Two functions being asymptotic means that their ratio approaches \(1\) as their arguments grow larger and larger.
For two functions \(f\) and \(g\) over the reals, we write \(f \sim g\) when we have:
3.1.5. Inverse functions#
An invertible function is one which has an inverse. What is an inverse?
Definition (inverse function)
Given a bijection \(f\) from set \(A\) to set \(B\), then the inverse of \(f\), denoted \(f^{-1}\) is a function from \(B\) to \(A\) defined as \(f^{-1}(b) = a \leftrightarrow f(a) = b\).
Given a function, its inverse is a function that “reverses” the mapping caused by the original function. The inverse function “undoes” the transformation caused by the original function.
It should be clear from the definition of an injective function that only injective functions are reversible in this way. Indeed, each image needs a unique preimage in order to reverse the original mapping.
However, we additionally require that invertible functions are surjective. Remember that a defining feature of functions is that they are total over their domain. If a function is not surjective, then its reverse mapping will not be total and thus not a function.
These facts tell us that invertible functions are necessarily bijective functions, and, bijections necessarily have inverses.
A first inverse
Consider the function \(f: \mathbb{R} \rightarrow \mathbb{R}\) given by \(f(x) = \frac{1}{2}x + 3\).
This linear function clearly has an inverse. Indeed, we can “solve” for \(f(x)\). Letting \(y = f(x)\):
A discrete inverse
Let \(f = \{(2,a), (3,b), (c,1)\}\) be a function. Is \(f\) invertible? If so, give its inverse.
A discrete inverse
Yes, \(f\) is invertible because it is a bijection. Its inverse is \(f^{-1} = \{(a,2), (b,3), (c,1)\}\)
Since all inverses are bijections, it follows naturally that an inverse itself is also a bijection. Therefore, the inverse of an inverse is the original function. That is, for a function \(f\), \(f^{-1^{-1}} = f\).
Can we prove that an inverse is also a bijection?
Theorem
If a function \(f: X \rightarrow Y\) is a bijection, then so is \(f^{-1}: Y \rightarrow X\).
Proof
Injective: Let \(y_1, y_2 \in Y\). Assume \(f^{-1}(y_1) = f^{-1}(y_2)\). Let \(x_1 = f^{-1}(y_1)\) and \(x_2 = f^{-1}(y_2)\). Therefore, \(x_1 = x_2\) and, since \(f\) is injective, \(f(x_1) = f(x_2) = y_1 = y_2\). Hence, \(f^{-1}\) is injective.
Surjective: Let \(x \in X\). \(f(x) = y\) for some \(y \in Y\). By definition, we have \(f^{-1}(y) = x\). Since \(f\) is surjective, and we chose \(x\) arbitrarily, then \(f^{-1}\) is also surjective. \(\blacksquare\)
3.1.6. Function Composition#
The composition of functions is an operation performed on functions themselves (not elements of their domains), to produce another function.
Definition (composition)
Given a function \(f: A\rightarrow B\) and a function \(g: B \rightarrow C\), the composition of \(g\) and \(f\) is the function \(g \circ f: A \rightarrow C\) defined as \((g \circ f)(a) = g(f(a))\).
The composition of two functions takes the range of the second function and uses it as the domain of the first. That is, the “output” of the second is used as the “input” to the first. In this way, function composition “chains” functions together.
Fig. 3.15 The composition of functions \(f: A \rightarrow B\) and \(g: B \rightarrow C\).#
In Fig. 3.15, \(f(c) = 1, g(1) = y\), and \((g \circ f)(c) = g(f(c)) = y\). Notice also that \(g\) is a bijection. However, \(f \circ g\) is not surjective. \(g\) on its own has \(g(4) = z\). However, there is no element of \(A\) such that \((f \circ g)(\cdot) = z\).
Tip
When we want to talk about the value of a function without considering a particular preimage, we can use the notation \(f(\cdot)\) to refer to the function being applied to some element of the domain, but without giving that element a particular name or symbol.
Pictorial Composition
Draw a picture to describe the function \((g \circ f): A \rightarrow C\) from Fig. 3.15 without using the intermediary set \(B\).
Pictorial Composition
It is not always possible to compose two functions. For two functions to be composable, the codomain of the first must be the domain of the second. Moreover, given two functions \(f\) and \(g\), \(f \circ g\) and \(g \circ f\) are often not equal.
The order of the composition certainly matters. If \(f: A \rightarrow B\), \(g: B \rightarrow C\) are functions, then \(f \circ g\) is not even defined, unless \(C = A\).
Consider the case two functions whose domain and codomain are both the real numbers. Composition is well defined in both directions but may give very different functions.
Order of composition
Let \(f(x) = x^2\) and \(g(x) = 2x + 1\) be two functions over the reals.
This example shows how the operation of composition is not commutative.
In computer science, we are very familiar with function composition. When the returned value of a function (in the sense of a programming language) is used as the input to another function, we have function composition.
The following code segment shows the function composition of the previous example’s real functions written in Python.
def f(x) :
return x**2
def g(x) :
return 2*x + 1
print(f(g(4)))
print(g(f(4)))
81
33
Lastly, a discussion on function compositions would be incomplete without considering again function inverses. Function inverses have a great property that a function composed with its inverse gives the identity function.
For example, Consider any invertible function over a set \(A\). \(f: \mathbb{A} \rightarrow \mathbb{A}\). It holds that:
When an invertible function does not have the same domain and codomain, the composition of the two function still produces the identity function, but the domain of the identity function depends on the order of composition.
Consider an invertible function \(f: A \rightarrow B\) and its inverse \(f^{-1}: B \rightarrow A\).
3.1.7. Proofs with Functions#
Proofs with functions follow similarly to proofs over predicate logic or proofs with sets. They begin by appealing to the definition of the object in question and then applying one of our many proof techniques: direct, contrapositive, contradiction, cases, etc.
We have already seen examples of proving that functions are surjective, injective, or bijective. In general, however, it can be very challenge to formally prove if a function is surjective of injective. This is particularly true for continuous functions over an infinite domain. One must employ calculus and/or real analysis to show that, for example, \(f(x) = x^3\) is surjective. Although, intuitively, it is “obviously” a surjective function since it is a continuous function with \(\lim_{x\rightarrow -\infty} f(x) = -\infty\) and \(\lim_{x \rightarrow \infty} f(x) = \infty\).
The kinds of proofs regarding functions which we will do in this course applies to discrete functions and properties which can be proved without the need for analysis. But, some basic calculus (like limits) may be helpful.
For example, we have previously shown that an arbitrary function and its inverse are both bijections. Here is another example regarding arbitrary functions.
Composing bijections
Theorem
If \(f: A \rightarrow B\) and \(g: B \rightarrow C\) are invertible functions, then \((g \circ f)\) is invertible.
Proof.
Assume \(f\) and \(g\) are bijections. \((g \circ f)\) is a function from \(A\) to \(C\). Let \(x \in A\). By definition, we have that \((g \circ f)(x) = g(f(x))\).
Let us prove surjection. Since \(f\) is a bijection, \(f(A) = B\). Since \(g\) is a bijection \(g(B) = C\). Hence, \((g \circ f)(A) = g(f(A)) = C\) and the composition is surjective.
We now prove that the composition is injective. Let \(x_1, x_2 \in X\). We will show that \((g \circ f)(x_1) = (g \circ f)(x_2) \rightarrow x_1 = x_2\). Since \(g\) is a bijection, \(g(f(x_1)) = g(f(x_2)) \rightarrow f(x_1) = f(x_2)\). Since \(f\) is a bijection, \(f(x_1) = f(x_2) \rightarrow x_1 = x_2\).
Therefore, \((g \circ f)\) is a bijection. \(\blacksquare\)
Another useful property of functions that will helps in proofs is monotonicity. This is described by the following definitions.
Definition (non-decreasing)
A function \(f: \mathbb{R} \rightarrow \mathbb{R}\) is non-decreasing if for all \(x,y \in \mathbb{R}\), \(x \leq y \rightarrow f(x) \leq f(y)\). A strictly non-decreasing or strictly increasing function has \(x < y \rightarrow f(x) < f(y)\).
Definition (non-increasing)
A function \(f: \mathbb{R} \rightarrow \mathbb{R}\) is non-increasing if for all \(x,y \in \mathbb{R}\), \(x \leq y \rightarrow f(x) \geq f(y)\). A strictly non-increasing or strictly decreasing function has \(x < y \rightarrow f(x) > f(y)\).
Definition (monotonic)
A function is monotonic if it is either non-increasing or non-decreasing. A function is strictly monotonic if it is either strictly non-increasing or strictly non-decreasing.
The graph of monotonic functions do not have turning points, points where the graph goes from moving upwards, to moving downwards, or vice versa. Turning points are special kinds of stationary points, where the derivative of a function is \(0\).
Fig. 3.16 The cubic \(f(x) = \frac{1}{4}(x^3 + x^2 + x + 1)\) is strictly increasing.#
We can verify that the function shown in the graph above is monotonic by computing its derivative. \(\frac{d}{dx} f(x) = \frac{1}{4}(3x^2 + 2x + 1)\). This derivative is always positive and hence the function is strictly increasing.
A useful property of strictly monotonic functions is that they are always injective.
Proposition
Any function \(f\) which is strictly monotonic is injective.
Proof
We look to show that “\(f\) is strictly monotonic” \(\rightarrow\) \(f\) is injective.
A function is strictly monotonic if it is either strictly increasing or strictly decreasing, yielding two cases.
Case 1: strictly increasing. By definition, we have \(\forall x,y\) \(x < y \rightarrow f(x) < f(y)\). Therefore, for any \(x_1 \neq x_2\), we have \(f(x_1) \neq f(x_2)\) since either \(x_1 < x_2\) and \(f(x_1) < f(x_2)\) or \(x_1 > x_2\) and \(f(x_1) > f(x_2)\).
Case 2: strictly decreasing. By definition, we have \(\forall x,y\) \(x < y \rightarrow f(x) > f(y)\). Therefore, for any \(x_1 \neq x_2\), we have \(f(x_1) \neq f(x_2)\) since either \(x_1 < x_2\) and \(f(x_1) > f(x_2)\) or \(x_1 > x_2\) and \(f(x_1) < f(x_2)\). \(\blacksquare\)
Now, do a proof with functions yourself.
Floor proofs
Show that, for any real number \(x\), \(\lfloor 2x \rfloor = \lfloor x \rfloor + \lfloor x + \frac{1}{2}\rfloor\).
Hint: Let \(n\) be an integer such that \(\lfloor x \rfloor = n\). Then, \(x = n + \epsilon\) for \(0 \leq \epsilon < 1\).
Solution
Let \(x = n+ \epsilon\) with \(n\) an integer and \(0 \leq \epsilon < 1\). We have \(\lfloor 2x\rfloor = \lfloor 2n + 2\epsilon\rfloor\) meanwhile the righthand side has \(\lfloor x \rfloor + \lfloor x + \frac{1}{2}\rfloor = \lfloor n + \epsilon \rfloor + \lfloor n + \epsilon + \frac{1}{2}\rfloor\).
Therefore, the question is whether or not \(\lfloor \frac{1}{2} + \epsilon\rfloor = \lfloor 2\epsilon \rfloor\). We have two cases: \(\epsilon \geq \frac{1}{2}\) and \(\epsilon < \frac{1}{2}\).
Case 1: \(\epsilon < \frac{1}{2}\). Therefore, \(\lfloor 2x \rfloor = 2n\) since \(2\epsilon < 1\), \(\lfloor x\rfloor = n\), and \(\lfloor x + \frac{1}{2} \rfloor = \lfloor n +\epsilon + \frac{1}{2}\rfloor = n\), since \(\epsilon + \frac{1}{2} < 1\). Hence, \(\lfloor 2x \rfloor = 2n = \lfloor x \rfloor + \lfloor x + \frac{1}{2}\rfloor\).
Case 2: \(\epsilon \geq \frac{1}{2}\). We have \(2x = 2n + 2\epsilon\) and, since \(2\epsilon \geq 1\), \(\lfloor 2x \rfloor = 2n + 1\). \(\lfloor x \rfloor = n\), since \(\epsilon < 1\) still. But, \(\lfloor x + \frac{1}{2}\rfloor = \lfloor n + \epsilon + \frac{1}{2}\rfloor = n + 1\). Therefore, \(\lfloor 2x \rfloor = 2n + 1 = \lfloor x \rfloor + \lfloor x + \frac{1}{2}\rfloor\).
In either case, the two functions are equal. \(\blacksquare\).
Cardinality of Sets#
Sometimes rather than proving statements regarding functions, we must use functions to prove properties of other mathematical objects. An important example of has to do with the cardinality of sets.
We have seen cardinality already in Section 2.1.2 as the “size” of a set. In the finite case, this is easy. Now, we consider the case of infinite sets. Consider the following definition.
Definition (cardinality)
Two sets \(A\) and \(B\) have the same cardinality if there exists a bijection between them. When this is the case, we write \(|A| = |B|\)
Notice that this definition includes sets with an infinite number of elements. Therefore, two two infinite sets have the same cardinality? Does \(|\mathbb{Z}| = |\mathbb{R}|\)? The answer, as we will explore, is no. This suggests an interesting point of view where one infinity can be smaller than another infinity. Perplexing.
Let’s consider a finite example first.
Cardinality and a finite bijection
Let \(A = \{1,2,3,4,5\}\) and \(B = \{2,4,6,8,10\}\).
An obvious bijection exists between \(A\) and \(B\) (one of many possible bijections). \(f: A \rightarrow B\) defined by \(f(x) = 2x\).
This \(f\) is clearly a bijection. Indeed, \(f^{-1}: B \rightarrow A\) is defined by \(f^{-1}(x) = \frac{1}{2}x\).
Therefore, \(|A| = |B|\).
Explicitly defining a bijection between \(A\) and \(B\) in the previous example may feel silly since we can simply count that \(A\) has \(5\) elements and \(B\) has \(5\) elements. Could we similarly count all the natural numbers \(\mathbb{N}\)? Given an infinite amount of time, we could count the natural numbers. Take any natural number \(n\). The next natural number is \(n+1\). We call a set countable if it is either finite or “countably infinite”.
Definition (finite set)
A set \(A\) is finite if its cardinality is a natural number \(n\). That is, \(|A| < |\mathbb{N}|\).
Definition (countably infinite)
A set \(A\) is countably infinite if \(|A| = |\mathbb{N}|\).
Definition (uncountably infinite)
A set \(A\) is uncountably infinite if \(|A| > |\mathbb{N}|\).
Informally, countable sets, and thus countably infinite sets, are simply sets that can be indexed. That is, they have a “first” element, a “second” element, etc. There may be an infinite number of elements to count/label, but they are still countable. This may feel counter-intuitive, but so is infinity.
Consider \(\mathbb{N}\) and \(\mathbb{N} \setminus \{0\}\). In this second set we have removed \(0\) from the set of natural numbers. You could think that \(\mathbb{N} \setminus \{0\}\) is somehow “smaller” than \(\mathbb{N}\). But, that is not the case. Consider the following bijection.
This \(f\) is clearly a bijection. \(f^{-1}: \mathbb{N} \setminus \{0\} \rightarrow \mathbb{N}\) is defined as \(f(x) = x - 1\). Therefore, by definition, \(|\mathbb{N}| = |\mathbb{N} \setminus \{0\}|\). We may have removed an element from \(\mathbb{N}\), but both sets are still countably infinite.
Many other common sets are also countably infinite. \(\mathbb{Z}\), \(\mathbb{Z}^+\), \(\mathbb{Q}\), the set of even integers, and the set of odd integers are all countably infinite.
Can you come up with a proof to show \(|\mathbb{N}| = |\mathbb{Z}|\)? The below checkpoint gets you most of the way. First, one must find a bijection. Second, one should prove formally that the function is truly a bijection.
The integers are countable
Find a bijection \(f: \mathbb{N} \rightarrow \mathbb{Z}\) to prove that \(|\mathbb{N}| = |\mathbb{Z}|\).
The integers are countable
Let \(f\) be a function from \(\mathbb{N}\) to \(\mathbb{Z}\) defined as:
This function is clearly a bijection. All negative integers map to twice their positive. All positive integers map to twice their value minus 1. Indeed, that describes \(f^{-1}\).
This is yet another counter-intuitive result. One can feel that the integers are twice as large as the natural numbers, since the former has all the negative numbers that the natural numbers do not. However, as long as we can “count” a set, by associating a unique natural number to each element of that set, then the set is countable. Indeed, doing this association is finding a bijection between that set and the natural numbers.
With this argument we can also show the the rational numbers \(\mathbb{Q}\) are countable. The same intuition which tells us that the integers are twice as large as the natural numbers may tell us that the rational numbers are much larger than the integers. The rational numbers is the set all possible fractions of integers. There appears to be an infinite choice of numerators and an infinite choice of denominators, so surely the set of rational numbers is somehow larger. This intuition is incorrect.
The correct intuition is based on the idea of ordering a set. If one can order the elements of the set so that there is a “first” element, a “second” element, a “third” element, and so on, then that set is countable (and possibly countably infinite).
The following figure demonstrates how you could order the positive rational numbers, therefore (informally) showing that \(|\mathbb{Q}| = |\mathbb{N}|\).
Fig. 3.17 Ordering the positive rational numbers.#
In Fig. 3.17, we start by counting rational numbers \(\frac{p}{q}\) such that \(p+q = 2\), then \(p+q=3\), then \(p+q = 4\), etc. We skip counting fractions which are not fully reduced (i.e. skip numbers that have already been counted). In the figure, counted numbers are circled. Continuing in this way we would enumerate all possible rational numbers. Moreover, there is a clear one-to-one correspondence between the rational numbers being counted and \(\mathbb{N}\): \(\{ (\frac{1}{1}, 0), (\frac{2}{1}, 1), (\frac{1}{2}, 2), (\frac{1}{3}, 3), \ldots\}\).
Therefore, the positive rational numbers are countable. The same process could be applied to the negative rational numbers, simply make all numerators in Fig. 3.17 negative. So, the negative rational numbers are countable. The following lemma establishes that \(\mathbb{Q}\) is also countably infinite.
Lemma
The union of two countable sets is countable.
Proof:
Let \(A\) and \(B\) be two countable sets. If \(A\) and \(B\) are finite, then the proof is obvious. If one of \(A\) and \(B\) are finite and the other countably infinite, it follows from a similar argument as with \(\mathbb{N}\) and \(\mathbb{N} \setminus \{0\}\) having the same cardinality that \(A \cup B\) is also countably infinite. (The formal proof is left to the reader).
Consider now the case that both \(A\) and \(B\) are countably infinite. We can thus associate each element of \(A\) with a unique natural number and the same with elements of \(B\) (that is, a bijection exists between \(A\) and \(\mathbb{N}\) and between \(B\) and \(\mathbb{N}\)). Let \(a_n\) be the element of \(A\) associated with \(n \in \mathbb{N}\). Similarly for \(b_n \in B\). Then, we can count all the elements of \(A \cup B\) by listing them as \(a_1, b_1, a_2, b_2, a_3, b_3, \ldots\), skipping elements which are have already been counted. Therefore, a bijection exists between \(A \cup B\) and \(\mathbb{N}\). \(\blacksquare\)
Corollary
The set of rational numbers \(\mathbb{Q} = \mathbb{Q}^+ \cup \mathbb{Q}^- \cup \{0\}\) is countably infinite.
Uncountably Infinite#
Finally, we cannot conclude this section without considering sets which are uncountably infinite. In particular we will see that any subset of the real numbers is uncountably infinite and that, naturally, the real numbers themselves are uncountably infinite.
We will begin by showing that the unit interval \([0,1)\) is uncountably infinite. It follows from a classic proof: Canto’s diagonalization argument.
Theorem
The interval \([0,1)\) is uncountably infinite.
Proof:
We proceed by contradiction. Assume \([0,1)\) is countable. Thus, the elements of \([0,1)\) can be listed as \(r_1, r_2, r_3\), etc. Notice that any element of \([0,1)\) has the decimal form \(0.d_1d_2d_3d_4\cdots\), where \(d_i\) is a digit in \(\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}\). Write out each element in order using this decimal form. I will show that there is an element in \([0,1)\) which is not listed.
Let \(x\) be an element of \([0,1)\). I will show that \(x\) is not listed among \(r_1\), \(r_2\), \(r_3\), etc. Assign the digit \(d_i\) of \(x\) to be different from \(d_i\) of \(r_i\), for all \(i = 0, 1, 2, \ldots\)
Fig. 3.18 Cantor’s diagonal argument.#
Surely \(x \in [0,1)\) since its whole number digit is 0 and every digit after the decimal place is one among \(\{0,1,2,3,4,5,6,7,8,9\}\). Moreover, \(x\) cannot be in the list of elements \(r_1, r_2, r_3, \ldots\) Indeed, \(x\) differs from \(r_1\) by digit \(d_1\), it differs from \(r_2\) by digit \(d_2\), etc. Hence, the assumption that \([0,1)\) was countable is incorrect. \(\blacksquare\)
Since \([0,1) \subset \mathbb{R}\) it follows that \(\mathbb{R}\) is also uncountably infinite. Moreover, that gives us the following relations:
Uncountable intervals.
In fact, any (non-singleton) interval of the real numbers has the same cardinality as \([0,1)\). That is, every interval is uncountable.
This follows from the fact that we can define a “scaling” function \(f_s(x) = sx\) and a “translation” function \(g_t(x) = x + t\) which are both bijections on the reals. \(f_s\) scales the interval \([0,1)\) to the interval \([0, s)\). \(g_t\) translates the interval \([0,1)\) to the interval \([t, 1+t)\).
Then, the function \(g_a \circ f_{b-a}\) is a bijection from \([0,1)\) to any interval \([a,b)\).
3.1.8. Exercises#
Exercise 3.1
Let \(A = \{1,2,3,4\}\). Which of the following binary relations defines a function from the set \(A\)? If not, explain why.
\(f = \{(1,1), (2,2), (3,3), (4,4)\}\)
\(f = \{(1,2), (2,3), (3,4)\}\)
\(f = \{(4,2), (2,4), (3,4), (4,2)\}\)
\(f = \{(1,4), (3,2), (2,3), (1,3), (4,2)\}\)
\(f = \{(4,4), (1,4), (2,4), (3,4) \}\)
\(f = \{(1,8), (2,1), (3,9), (4,6) \}\)
Solution to Exercise 3.1
Yes
No. f(4) is undefined.
No. f(1) is undefined.
No. f(1) does not have a unique image
Yes.
Yes. The function has domain \(A\) is thus from \(A\). We have not restricted the function’s co-domain.
Exercise 3.2
Consider the set \(S\) of students currently enrolled at courses at Western University, the set \(P\) of professors at Western University, and the set \(C\) of course offerings in the current semester. Under what circumstances would each of the following relations actually a function?
\(\{(s,p) \in S \times P \ |\ s \text{ is enrolled in a course taught by } p\}\)
\(\{(p,s) \in P \times S \ |\ p \text{ teaches } s\}\)
\(\{(p,c) \in P \times C \ |\ p \text{ teaches } c\}\)
\(\{(c,p) \in C \times P \ |\ c \text{ is taught by } p\}\)
Solution to Exercise 3.2
If, for every student, all of their courses are taught by the same professor.
If every professor teaches a class of size exactly 1.
If every professor teaches exactly one course.
If every course (and all of its sections) is taught by exactly one professor.
Exercise 3.3
Let \(S = \{1,2,3,4,5\}\), Let \(f: S \rightarrow \mathbb{Z}\) be a function defined as:
Describe \(f\) as a binary relation using the roster method. Show that \(f\) is one-to-one.
Solution to Exercise 3.3
Since every argument maps by \(f\) to a unique value, \(f\) is one-to-one (i.e. injective).
Exercise 3.4
For each of the following functions, determine its range. Is the function an injection, surjection, or bijection? If so, explain why (not necessarily a formal proof). If not, give a counterexample.
\(f_1: \left\{ \begin{array}{l}\mathbb{R} \rightarrow \mathbb{R} \\ x \mapsto x^3 + 5x^2\end{array} \right.\)
\(f_2: \left\{ \begin{array}{l}\mathbb{R} \rightarrow \mathbb{R} \\ x \mapsto x^4 + 2x^2 + 10\end{array} \right.\)
\(f_3: \left\{ \begin{array}{l}\mathbb{R} \rightarrow \mathbb{R}^+ \\ x \mapsto e^x\end{array} \right.\)
Hint: it may help to plot the function on a Cartesian plane.
Solution to Exercise 3.4
The range of \(f_1\) is \(\mathbb{R}\). It is surjective, since its range equals its codomain. Indeed, \(\forall y \in \mathbb{R}\), there is an \(x\) such that \(f(x) = y\). It is not injective since both \(f_1(0) = f_1(-5) = 0\).
The range of \(f_2\) is \([10, \infty)\). Indeed, \(f_2(0) = 10\) is the minimum. \(f_2\) is not surjective since its range is not equal to its codomain. \(f_2\) is not injective since \(f(-1) = f(1) = 13\).
The range of \(f_3\) if \(\mathbb{R}^+\). Indeed, an exponential function is never negative, \(\lim_{x \rightarrow -\infty} e^x = 0\), and \(\lim_{x \rightarrow \infty} e^x = \infty\). Since the codomain of \(f_3\) is \(\mathbb{R}^+\), it is surjective. Futher, \(f_3\) is injective. Since the exponential function is known to be strictly monotonic (recall \(\frac{d}{dx} e^x = e^x\)) it must be injective.
Exercise 3.5
For each of the following functions, determine if they are a injection, surjection, or bijection. Explain why.
\(f_1: \mathbb{Q} \rightarrow \mathbb{Q}, f(x) = 3x + 2\)
\(f_2: \mathbb{N} \rightarrow \mathbb{N}, f(x) = 3x + 2\)
\(f_3: \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}, f(x,y) = 5x + 3y\)
\(f_4: \mathbb{Z} \times \mathbb{Z} \rightarrow \mathbb{Z}, f(x,y) = 5x + 3y\)
Solution to Exercise 3.5
\(f_1\) is a bijection. If \(f_1(x_1) = f_1(x_2)\) then \(3x_1 + 2 = 3x_2 + 2\). Thus, \(x_1=x_2\). \(f_1\) is also surjective since, for any \(y \in \mathbb{Q}\) we can define \(y = f(\frac{1}{3}(y-2))\).
\(f_2\) is an injection but not a surjection. Notice that \(f(0) = 2, f(1) = 5\). There is no \(x\) which maps to \(3\) or \(4\) (among many).
\(f_3\) is neither injective nor surjective. \(f(3,5) = f(6,0)\), for example. Moreover, there is no pair such that, for example, \(f(x,y) = 1\).
\(f_4\) is not injective for the same reason as \(f_3\). It is, however, surjective. Let \(z \in \mathbb{Z}\) Can we fine \(x,y\) such that \(z = 5x + 3y\)? The answer is always yes. Why?
Exercise 3.6
Consider the function \(f : \mathbb{Q}^+ \rightarrow \mathbb{Q}^+\) such that \(f(x) = \frac{1}{x}\). Prove that \(f\) is a bijection. Recall that \(\mathbb{Q}^+ = \{a \in Q \ |\ a > 0\}\).
Exercise 3.7
A grocery store sells hot dogs weiners in packs of \(8\) and hot dog buns in packs of \(12\). If you would like to serve \(N\) hot dogs at your next BBQ, what is the minimum number of packages of weiners and buns you must buy for:
\(N=14\)
\(N=200\)
\(N=426\)
In each case, if there are any leftovers, how many leftovers of each ingredient will there be?
Solution to Exercise 3.7
\(2\) packs each of weiners and buns. \(2\) leftover weiners, \(10\) leftover buns.
\(25\) packs of weiners and \(\lceil 200/12 \rceil = 17\) packs of buns. \(4\) leftover buns.
\(\lceil 426/8 \rceil = 54\) packs of weiners, \(\lceil 426/12 \rceil = 36\) packs of weiners. \(6\) leftover weiners and \(6\) leftover buns. (What luck! An equal number of dugs and buns.)
Exercise 3.8
Data transmitted over a digital network is often performed using packet switching, where data to be transmitted is partitioned into smaller chunks called packets. Consider the Wi-Fi technical standard 802.11. This standard specifies that it can send at most 2304 bytes of data within a packet.
How many packets are needed to send a message that is 23.5KB?
How many packets are needed to send a message that is 32MB?
The WEP encryption protocol for Wi-Fi adds 8 bytes of overhead to each packet it sends. Therefore, at most 2296 bytes of data can be sent within a packet encrypted with WEP. How many packets are needed to send that 23.4KB message with encryption?
Hint: Recall that 1 KB = 1024 bytes, 1 MB = 1024 KB.
Solution to Exercise 3.8
23.4KB = 24064 bytes. \(\lceil 24064 / 2304 \rceil = 11\) packets to be sent.
32 MB = 33554432 bytes. \(\lceil 33554432 /2304 \rceil = 14564\) packets to be sent.
\(\lceil 33554432 / 2296 \rceil = 14615\) packets to be sent.
Exercise 3.9
Let \(f\) be a function from \(\mathbb{Z}\) to \(\mathbb{Z}\) defined as \(f(x) = 2x + 1\). Is \(f\) invertible? If so, give its inverse. If not, explain why.
Solution to Exercise 3.9
\(f\) is not invertible. Indeed, it is not surjective. There is no value of \(x\) which gives, for example, \(f(x) = 4\). The range of \(f\) is only the odd integers.
Exercise 3.10
Let \(f\) be a function from \([1, \infty)\) to \([0, \infty)\) defined as \(f(x) = x^2 - 2x + 1\). Is \(f\) invertible? If so, give its inverse. If not, explain why.
Exercise 3.11
Let \(f\) be a function from the set \(\{a,b,c\}\) to the same set such that \(f(a) = b, f(b) = c, f(c) = a\). Let \(g\) be a function from the set \(\{a,b,c\}\) to the set \(\{1,2,3\}\) such that \(g(a) = 3\), \(g(b) = 2\), \(g(c) = 1\).
What is the composition of \(f\) and \(g\)?
What is the composition of \(g\) and \(f\)?
Solution to Exercise 3.11
The composition of \(g\) and \(f\) is \(g \circ f = \{(a,2), (b,1), (c,3)\}\).
The composition of \(f\) and \(g\) is undefined!
Exercise 3.12
Let \(f: \mathbb{Z} \rightarrow \mathbb{Q}\) be a function defined as \(f(x) = 2(\frac{x}{3})^2 + 7\). Can you find two functions \(f_1 : \mathbb{Z} \rightarrow \mathbb{Q}\) and \(f_2 : \mathbb{Q} \rightarrow \mathbb{Q}\) such that \(f(x) = f_2(f_1(x))\)?
Solution to Exercise 3.12
One possible solution: \(f_1(x) = \frac{x^2}{9}\), \(f_2(x) = 2x + 7\)
Exercise 3.13
Prove that if \(f: B \rightarrow C\) and \(g: A \rightarrow B\) are two injective functions, prove that \((f\circ g)\) is also injective.
Solution to Exercise 3.13
See proof in text that the composition of bijective functions are bijective
Exercise 3.14
Prove that \(f: \mathbb{Q} \rightarrow \mathbb{Q}\) defined as \(f(x) = \frac{2}{3}x + 5\) is a bijection. Do so by finding its inverse and showing that \(f \circ f^{-1} = \text{id}_{\mathbb{Q}}\).
Solution to Exercise 3.14
Let \(f^{-1}(x) = (3/2)*(x-5)\). Indeed, we have: $\( (f \circ f^{-1})(x) = \frac{2}{3}(\frac{3}{2}(x-5)) + 5 \\ = (x-5) + 5 = x \)$
Exercise 3.15
Prove the following theorem.
Theorem
If \(f: A \rightarrow B\) and \(g: B \rightarrow C\) are invertible functions, then \((g \circ f)^{-1} = (f^{-1} \circ g^{-1})\).
Exercise 3.16
Recall that an even function is a function \(f: A \rightarrow B\) such that \(\forall a \in A\ (-a \in A \rightarrow f(a) = f(-a))\). Prove the following theorem.
Theorem
If \(f: \mathbb{Z} \rightarrow \mathbb{Z}\) is an even function, then \(f\) is not injective.
Solution to Exercise 3.16
Let \(f: \mathbb{Z} \rightarrow \mathbb{Z}\) be an even function. Since the domain of \(f\) is \(\mathbb{Z}\), \(-a \in \mathbb{Z}\) for all choices of \(a \in \mathbb{Z}\). Thus, since \(f\) is even, we have \(f(a) = f(-a)\) for all \(a \in \mathbb{Z}\).
The definition of injective is: \(\forall x,y \in \mathbb{Z}, f(x) = f(y) \rightarrow x=y\). Let \(a\) be a non-zero integer. Since \(f\) is even, we have \(f(a) = f(-a)\), but \(a \neq -a\), serving as a counter example to injectivity. \(\blacksquare\)
Exercise 3.17
Let \(E = \{3x \ |\ x \in \mathbb{N}\}\). Prove that \(E\) is countable.
Exercise 3.18
Let \(T\) be a subset of \([0,1)\) such that the only digits (other than the leading and trailing 0s) appearing in the elements of \(T\) are \(4\) and \(6\). For example, \(0.444 \in T\), \(0.646464 \in T\), \(0.6644446 \in T\) and so on.
Prove by contradiction that \(T\) is uncountable.
Solution to Exercise 3.18
Cantor’s diagonalization argument except now instead of replacing the diagonal element with any digit, we replace it with 6 or 0 if it was originally 4; or we replace it with 4 or 0 if it was originally 6; or we replace it with 4 or 6 if it was originally 0.