The first function, \(f\text{,}\) gives us more information about the set \(B\) than the second function, \(g\text{.}\) Since \(A\) clearly has four elements, \(f\) tells us that \(B\) contains at least four elements since each element of \(A\) is mapped onto a different element of \(B\text{.}\) The properties that \(f\) has, and \(g\) does not have, are the most basic properties that we look for in a function. The following definitions summarize the basic vocabulary for function properties.
A function \(f: A \rightarrow B\) is surjective if its range, \(f(A)\text{,}\) is equal to its codomain, \(B\text{.}\) A surjective function is called a surjection, or an onto function.
Example7.2.4.Injective but not surjective function.
Let \(A = \{1, 2, 3\}\) and \(B = \{a, b, c, d\}\text{,}\) and define \(f:A \rightarrow B\) by \(f(1) = b\text{,}\)\(f(2) = c\text{,}\) and \(f(3)
= a\text{.}\) Then \(f \) is injective but not surjective.
The characteristic function, \(\chi _S\text{,}\) in Exercise 7.1.5.4 is surjective if \(S\) is a proper subset of \(A\text{,}\) but never injective if \(\lvert A \rvert \gt 2\text{.}\)
Let \(A\) be the set of students who are sitting in a classroom, let \(B\) be the set of seats in the classroom, and let \(s\) be the function which maps each student into the chair he or she is sitting in. When is \(s\) one to one? When is it onto? Under normal circumstances, \(s\) would always be injective since no two different students would be in the same seat. In order for \(s\) to be surjective, we need all seats to be used, so \(s\) is a surjection if the classroom is filled to capacity.
Functions can also be used for counting the elements in large finite sets or in infinite sets. Let’s say we wished to count the occupants in an auditorium containing 1,500 seats. If each seat is occupied, the answer is obvious, 1,500 people. What we have done is to set up a one-to-one correspondence, or bijection, from seats to people. We formalize in a definition.
Two sets are said to have the same cardinality if there exists a bijection between them. If a set has the same cardinality as the set \(\{1,2,3,\ldots , n\}\text{,}\) then we say its cardinality is \(n\text{.}\)
The function \(f\) that opened this section serves to show that the two sets \(A=\{1, 2, 3, 4\}\) and \(B=\{a, b, c, d\}\) have the same cardinality. Notice in applying the definition of cardinality, we don’t actually appear to count either set, we just match up the elements. However, matching the letters in \(B\) with the numbers 1, 2, 3, and 4 is precisely how we count the letters.
Example7.2.10.As many evens as all positive integers.
Recall that \(2\mathbb{P}= \{b\in \mathbb{P} \mid b= 2k \textrm{ for some } k \in \mathbb{P} \}\text{.}\) Paradoxically, \(2\mathbb{P}\) has the same cardinality as the set \(\mathbb{P}\) of positive integers. To prove this, we must find a bijection from \(\mathbb{P}\) to \(2\mathbb{P}\text{.}\) Such a function isn’t unique, but this one is the simplest: \(f:\mathbb{P} \rightarrow 2\mathbb{P}\) where \(f(m) = 2m\text{.}\) Two statements must be proven to justify our claim that \(f\) is a bijection:
Proof: Let \(b \in 2\mathbb{P}\text{.}\) We want to show that there exists an element \(a \in \mathbb{P}\) such that \(f(a) = b\text{.}\) If \(b \in
2\mathbb{P}\text{,}\)\(b = 2k\) for some \(k \in \mathbb{P}\) by the definition of \(2\mathbb{P}\text{.}\) So we have \(f(k) = 2k = b\text{.}\) Hence, each element of 2\(\mathbb{P}\) is the image of some element of \(\mathbb{P}\text{.}\)
Another way to look at any function with \(\mathbb{P}\) as its domain is creating a list of the form \(f(1),f(2), f(3), \ldots\text{.}\) In the previous example, the list is \(2, 4, 6, \ldots\text{.}\) This infinite list clearly has no duplicate entries and every even positive integer appears in the list eventually.
A function \(f:\mathbb{P}\to A\) is a bijection if the infinite list \(f(1), f(2), f(3), \ldots\) contains no duplicates, and every element of \(A\) appears once in the list. In this case, we say the \(A\) is countably infinite, or simply countable.
When studying infinity, paradoxes abound. One of the first instances of this is when we observe that the set of even positive integers, in spite of the fact that they make up only half of the positive integers, has the same cardinality as the whole set of positive integers. This follows from our definition of cardinality with the function \(f(k)=2k\text{,}\) which is a bijection from the positive integers to the even positive integers. We can make a similar observation that the seemingly smaller set of powers of \(10\text{,}\)\(\{10^0,10^1,10^2,10^3,\dots\}\text{,}\) also has the same cardinality as the positive integer. Here, the function \(g(k)=10^k\) serves as our justification.
Going in the opposite direction, there are seemingly larger sets than the positive integer that are countably infinite. One such example is the Cartesian product of the positive integers with itself, \(\mathbb{P}\times \mathbb{P}\text{.}\) A function that justifies this claim doesn’t have such a neat formula, but it would start like this:
See the pattern? If it continues, every positive integer will map to a different pair and every pair of positive integer will be in the range of \(f\text{.}\)
Readers who have studied real analysis should recall that the set of rational numbers is a countable set, while the set of real numbers is not a countable set. See the exercises at the end of this section for an another example of such a set.
We close this section with a theorem called the Pigeonhole Principle, which has numerous applications even though it is an obvious, common-sense statement. Never underestimate the importance of simple ideas. The Pigeonhole Principle states that if there are more pigeons than pigeonholes, then two or more pigeons must share the same pigeonhole. A more rigorous mathematical statement of the principle follows.
Let \(f\) be a function from a finite set \(X\) into a finite set \(Y\text{.}\) If \(n\geq 1\) and \(\lvert X\rvert > n\lvert Y\rvert\text{,}\) then there exists an element of \(Y\) that is the image under \(f\) of at least \(n + 1\) elements of X.
Assume no such element exists. For each \(y \in Y\text{,}\) let \(A_y = \{x\in X \mid f(x) =y \}\text{.}\) Then it must be that \(\lvert A_y \rvert \leq n\text{.}\) Furthermore, the set of nonempty \(A_y\) form a partition of \(X\text{.}\) Therefore,
\begin{equation*}
\lvert X \rvert = \sum_{y\in Y}{\lvert A_y \rvert} \leq n \lvert Y \rvert
\end{equation*}
Assume that a room contains four students with the first names John, James, and Mary. Prove that two students have the same first name. We can visualize a mapping from the set of students to the set of first names; each student has a first name. The pigeonhole principle applies with \(n = 1\text{,}\) and we can conclude that at least two of the students have the same first name.
\(f_4 :\mathbb{P} \rightarrow \mathbb{P}\) defined by \(f_4(n)=\lceil n/2\rceil\text{,}\) where \(\lceil x\rceil\) is the ceiling of \(x\text{,}\) the smallest integer greater than or equal to \(x\text{.}\)
Suppose that \(m\) pairs of socks are mixed up in your sock drawer. Use the Pigeonhole Principle to explain why, if you pick \(m + 1\) socks at random, at least two will make up a matching pair.
Let \(X=\{\textrm{socks selected}\}\) and \(Y=\{\textrm{pairs of socks}\}\) and define \(f:X \to Y\) where \(f(x) =\)the pair of socks that \(x\) belongs to . By the Pigeonhole principle, there exist two socks that were selected from the same pair.
Given five points on the unit square, \(\{(x,y) \mid 0 \leq x, y \leq 1 \}\text{,}\) prove that there are two of the points a distance of no more than \(\frac{\sqrt{2}}{2}\) from one another.
Let \(A\) and \(B\) be finite sets where \(|A|=|B|\text{.}\) Is it possible to define a function \(f:A \rightarrow B\) that is one-to-one but not onto? Is it possible to find a function \(g:A \rightarrow B\) that is onto but not one-to-one?
The proof is due to Georg Cantor (1845-1918), and involves listing the rationals through a definite procedure so that none are omitted and duplications are avoided. In the first row list all nonnegative rationals with denominator 1, in the second all nonnegative rationals with denominator 2, etc. In this listing, of course, there are duplications, for example, \(0/1=0/2=0\text{,}\)\(1/1=3/3=1\text{,}\)\(6/4=9/6=3/2\text{,}\) etc. To obtain a list without duplications follow the arrows in Figure 7.2.15, listing only the circled numbers.
We obtain: \(0,1,1/2,2,3,1/3,1/4,2/3,3/2,4/1,\ldots\) Each nonnegative rational appears in this list exactly once. We now must insert in this list the negative rationals, and follow the same scheme to obtain:
Use the Pigeonhole Principle to prove that an injection cannot exist between a finite set \(A\) and a finite set \(B\) if the cardinality of \(A\) is greater than the cardinality of \(B\text{.}\)
Let \(f\) be any function from \(A\) into \(B\text{.}\) By the Pigeonhole principle with \(n=1\text{,}\) there exists an element of \(B\) that is the image of at least two elements of \(A\text{.}\) Therefore, \(f\) is not an injection.
The important properties of relations are not generally of interest for functions. Most functions are not reflexive, symmetric, antisymmetric, or transitive. Can you give examples of functions that do have these properties?
The proof is indirect and follows a technique called the Cantor diagonal process. Assume to the contrary that the set is countable, then the elements can be listed: \(n_1,n_2,n_3,\ldots\) where each \(n_i\) is an infinite sequence of 0s and 1s. Consider the array:
We assume that this array contains all infinite sequences of 0s and 1s. Consider the sequence \(s\) defined by \(s_i=\begin{cases}
0 & \textrm{ if } n_{\textrm{ii}}=1 \\
1 & \textrm{ if } n_{\textrm{ii}}=0
\end{cases}\)
