maths.free › Discrete Math & Logic › 6. Discrete Structures Revisited › Functions

Functions

This section contains many details about functions, much of which should be familiar from non-discrete contexts.

Functions

This section contains many details about functions, much of which should be familiar from non-discrete contexts. As you read, consider how the way we talk about functions here might be different from what you know from other areas of mathematics.

A function is a rule that assigns each input exactly one output. We call the output the image of the input. The set of all inputs for a function is called the domain. The set of all allowable outputs is called the codomain. We would write \(f:X \to Y\) to describe a function with name \(f\), domain \(X\), and codomain \(Y\). This does not tell us which function \(f\) is though. To define the function, we must describe the rule. This is often done by giving a formula to compute the output for any input (although this is certainly not the only way to describe the rule).

For example, consider the function \(f:\N \to \N\) defined by \(f(x) = x^2 + 3\). Here the domain and codomain are the same set (the natural numbers). The rule: Take your input, multiply it by itself, and add 3. This works because we can apply this rule to every natural number (every element of the domain) and the result is always a natural number (an element of the codomain). Notice though that not every natural number is actually an output (there is no way to get 0, 1, 2, 5, etc.). The set of natural numbers that are outputs is called the range of the function (in this case, the range is \(\{3, 4, 7, 12, 19, 28, \ldots\}\), all the natural numbers that are 3 more than a perfect square).

The key thing that makes a rule a function is that there is exactly one output for each input. That is, it is important that the rule be a good rule. What output do we assign to the input 7? There can only be one answer for any particular function.

Example

The following are all examples of functions:

  1. \(f:\Z \to \Z\) defined by \(f(n) = 3n\). The domain and codomain are both the set of integers. However, the range is only the set of integer multiples of 3.

  2. \(g: \{1,2,3\} \to \{a,b,c\}\) defined by \(g(1) = c\), \(g(2) = a\), and \(g(3) = a\). The domain is the set \(\{1,2,3\}\), the codomain is the set \(\{a,b,c\}\) and the range is the set \(\{a,c\}\). Note that \(g(2)\) and \(g(3)\) are the same element of the codomain. This is okay since each element in the domain still has only one output.

  3. \(h:\{1,2,3,4\} \to \N\) defined by the table:

    \(x\) 123 4
    \(h(x)\) 369 12

    Here the domain is the finite set \(\{1,2,3,4\}\), and the codomain is the set of natural numbers, \(\N\). At first you might think this function is the same as \(f\) defined above. It absolutely is not. Even though the rule is the same, the domain and codomain are different, so these are two different functions.

Example

Just because you can describe a rule in the same way you would write a function does not mean that the rule is a function. The following are NOT functions.

  1. \(f:\N \to \N\) defined by \(f(n) = \frac{n}{2}\). The reason this is not a function is because not every input has an output. Where does \(f\) send 3? The rule says that \(f(3) = \frac{3}{2}\), but \(\frac{3}{2}\) is not an element of the codomain.

  2. Consider the rule that matches each person to their phone number. If you think of the set of people as the domain and the set of phone numbers as the codomain, then this is not a function, since some people have two phone numbers. Switching the domain and codomain sets doesn't help either, since some phone numbers belong to multiple people (assuming some households still have landlines when you are reading this).

Describing Functions

It is worth making a distinction between a function and its description. The function is the abstract mathematical object that in some way exists whether or not anyone ever talks about it. But when we do want to talk about the function, we need a way to describe it. A particular function can be described in multiple ways.

Some calculus textbooks talk about the Rule of Four, that every function can be described in four ways: algebraically (a formula), numerically (a table), graphically, or in words. In discrete math, we can still use any of these to describe functions, but we can also be more specific since we are primarily concerned with functions that have \(\N\) or a finite subset of \(\N\) as their domain.

Describing a function graphically usually means drawing the graph of the function: plotting the points on the plane. We can do this and might get a graph like the following for a function \(f:\{1,2,3\} \to \{1,2,3\}\).

It would be absolutely WRONG to connect the dots or try to fit them to some curve. There are only three elements in the domain. A curve would mean that the domain contains an entire interval of real numbers.

Here is another way to represent that same function:

This shows that the function \(f\) sends 1 to 2, 2 to 1, and 3 to 3: Just follow the arrows.

The arrow diagram used to define the function above can be very helpful in visualizing functions. We will often be working with functions with finite domains, so this kind of picture is often more useful than a traditional graph of a function.

Note that for finite domains, finding an algebraic formula that gives the output for any input is often impossible. Of course we could use a piecewise-defined function, like \[f(x) = \begin{cases} x+1 \amp \text{ if } x = 1 \\ x-1 \amp \text{ if } x = 2 \\ x \amp \text{ if } x = 3\end{cases}\]. This describes exactly the same function as above, but we can all agree is a ridiculous way of doing so.

\(x\) 01234
\(f(x)\) 33241
\(x\) 0123 45\(\ldots\)
\(f(x)\) 0 1491625\(\ldots\)

For a function \(f:\N \to \N\), a recursive definition consists of an initial condition together with a recurrence relation. The initial condition is the explicitly given value of \(f(0)\). The recurrence relation is a formula for \(f(n+1)\) in terms of \(f(n)\) (and possibly \(n\) itself).

Condensed — the full section is in Levin, Discrete Mathematics: An Open Introduction.

Surjections, Injections, and Bijections

We now turn to investigating special properties functions might or might not possess.

In the examples above, you may have noticed that sometimes there are elements of the codomain that are not in the range. When this sort of thing does not happen (that is, when everything in the codomain is in the range), we say the function is onto or that the function maps the domain onto the codomain. This terminology should make sense: The function puts the domain (entirely) on top of the codomain. The fancy math term for an onto function is a surjection, and we say that an onto function is a surjective function.

In pictures:

Example

Which functions are surjective (i.e., onto)?

  1. \(f:\Z \to \Z\)\(f(n) = 3n\)
  2. \(g: \{1,2,3\} \to \{a,b,c\}\)\(g = \begin{pmatrix}1 \amp 2 \amp 3 \\ c \amp a \amp a \end{pmatrix}\)

  3. \(h:\{1,2,3\} \to \{1,2,3\}\) defined as follows:

Solution

  1. \(f\)\(n \in \Z\)\(\frac{1}{3}\)\(\frac{1}{3}\)\(3\Z\)\(\Z\)
  2. \(g\)\(x \in \{1,2,3\}\)\(g(x) = b\)\(b\)missing
  3. \(h\)

To be a function, a rule cannot assign a single element of the domain to two or more different elements of the codomain. However, we have seen that the reverse is permissible: A function might assign the same element of the codomain to two or more different elements of the domain. When this does not occur (that is, when each element of the codomain is the image of at most one element of the domain), then we say the function is one-to-one. Again, this terminology makes sense: We are sending at most one element from the domain to one element from the codomain. One input to one output. The fancy math term for a one-to-one function is an injection. We call one-to-one functions injective functions.

In pictures:

Example

Which functions are injective (i.e., one-to-one)?

  1. \(f:\Z \to \Z\)\(f(n) = 3n\)
  2. \(g: \{1,2,3\} \to \{a,b,c\}\)\(g = \begin{pmatrix}1 \amp 2 \amp 3 \\ c \amp a \amp a \end{pmatrix}\)

  3. \(h:\{1,2,3\} \to \{1,2,3\}\) defined as follows:

Solution

  1. \(f\)most\(x\)\(x/3\)\(x\)\(x\)\(x\)
  2. \(g\)\(2\)\(3\)\(a\)
  3. \(h\)

Be careful: surjective and injective are NOT opposites. You can see in the two examples above that there are functions that are surjective but not injective, injective but not surjective, both, or neither. In the case when a function is both one-to-one and onto (an injection and surjection), we say the function is a bijection, or that the function is a bijective function.

Condensed — the full section is in Levin, Discrete Mathematics: An Open Introduction.

Image and Inverse Image

When discussing functions, we have notation for talking about an element of the domain (say \(x\)) and its corresponding element in the codomain (we write \(f(x)\), which is the image of \(x\)). Sometimes we will want to talk about all the elements that are images of some subset of the domain. It would also be nice to start with some element of the codomain (say \(y\)) and talk about which element or elements (if any) from the domain it is the image of. We could write those \(x\) in the domain such that \(f(x) = y\), but this is a lot of writing. Here is some notation to make our lives easier.

To address the first situation, what we are after is a way to describe the set of images of elements in some subset of the domain. Suppose \(f:X \to Y\) is a function and that \(A \subseteq X\) is some subset of the domain (possibly all of it). We will use the notation \(f(A)\) to denote the image of \(A\) under \(f\), namely the set of elements in \(Y\) that are the image of elements from \(A\). That is, \(f(A) = \{f(a) \in Y \st a \in A\}\). \(f(A)\) the image of \(A\) under \(f\)

We can do this in the other direction as well. We might ask which elements of the domain get mapped to a particular set in the codomain. Let \(f:X \to Y\) be a function and suppose \(B \subseteq Y\) is a subset of the codomain. Then we will write \(f\inv(B)\) for the inverse image of \(B\) under \(f\), namely the set of elements in \(X\) whose image are elements in \(B\). In other words, \(f\inv(B) = \{x \in X \st f(x) \in B\}\) . \(f\inv(B)\) the inverse image of \(B\) under \(f\)

Often we are interested in the element(s) whose image is a particular element \(y\) of in the codomain. The notation above works: \(f\inv(\{y\})\) is the set of all elements in the domain that \(f\) sends to \(y\). It makes sense to think of this as a set: there might not be anything sent to \(y\) (if \(y\) is not in the range), in which case \(f\inv(\{y\}) = \emptyset\). Or \(f\) might send multiple elements to \(y\) (if \(f\) is not injective). As a notational convenience, we usually drop the set braces around the \(y\) and write \(f\inv(y)\) instead for this set.

Since \(f\inv(y)\) is a set, it makes sense to ask for \(\card{f\inv(y)}\), the number of elements in the domain that map to \(y\).

Condensed — the full section is in Levin, Discrete Mathematics: An Open Introduction.

Practice (23)

Try each one on paper first. Reveal the answer to check; verified ones can be opened in the solver for every step.

  1. Explain, in your own words, the relationship between the codomain of a function and the range of a function.

  2. If a function has domain and codomain of equal sizes, must the function be surjective? Must it be injective? Could it be only one of these? Briefly explain your thinking.

  3. What questions do you have? Write at least one question about the content of this section that you or a classmate might be curious about after reading this section.

  4. Consider the function \(f:\{1,2,3,4,5\} \to \{1,2,3,4\}\) given by the table below:

    \(x\) 12345
    \(f(x)\) 3 2412

    1. Is \(f\) injective? Explain.

    2. Is \(f\) surjective? Explain.

    3. Write the function using two-line notation.

    Atbildēt uz šo jautājumu

    1. \(f\) is not injective, since \(f(2) = f(5)\); two different inputs have the same output.

    2. \(f\) is surjective, since every element of the codomain is an element of the range.

    3. \(f=\begin{pmatrix}1 \amp 2 \amp 3 \amp 4 \amp 5 \\ 3 \amp 2 \amp 4 \amp 1 \amp 2\end{pmatrix}\).

  5. Consider the function \(f:\{1,2,3,4\} \to \{1,2,3,4\}\) given by the graph below.

    1. Is \(f\) injective? Explain.

    2. Is \(f\) surjective? Explain.

    3. Write the function using two-line notation.

  6. For each function given below, determine whether or not the function is injective and whether or not the function is surjective.

    1. \(f:\N \to \N\)\(f(n) = n+4\)
    2. \(f:\Z \to \Z\)\(f(n) = n+4\)
    3. \(f:\Z \to \Z\)\(f(n) = 5n - 8\)
    4. \(f:\Z \to \Z\)\(f(n) = \begin{cases}n/2 \amp \text{ if } n \text{ is even} \\ (n+1)/2 \amp \text{ if } n \text{ is odd} . \end{cases}\)

    Atbildēt uz šo jautājumu

    1. \(f\)
    2. \(f\)
    3. \(f\)
    4. \(f\)\(f(5) = 3 = f(6)\)

  7. Let \(A = \{1,2,3,\ldots,10\}\). Consider the function \(f:\pow(A) \to \N\) given by \(f(B) = |B|\). That is, \(f\) takes a subset of \(A\) as an input and outputs the cardinality of that set.

    1. Is \(f\) injective? Prove your answer.

    2. Is \(f\) surjective? Prove your answer.

    3. Find \(f\inv(1)\).

    4. Find \(f\inv(0)\).

    5. Find \(f\inv(12)\).

    Atbildēt uz šo jautājumu

    1. \(f\) is not injective. To prove this, we must simply find two different elements of the domain which map to the same element of the codomain. Since \(f(\{1\}) = 1\) and \(f(\{2\}) = 1\), we see that \(f\) is not injective.

    2. \(f\) is not surjective. The largest subset of \(A\) is \(A\) itself, and \(|A| = 10\). So no natural number greater than 10 will ever be an output.

    3. \(f\inv(1) = \{\{1\}, \{2\}, \{3\}, \ldots \{10\}\}\) (the set of all the singleton subsets of \(A\) ).

    4. \(f\inv(0) = \{\emptyset\}\). Note that it would be wrong to write \(f\inv(0) = \emptyset\); that would claim that there is no input which has 0 as an output.

    5. \(f\inv(12) = \emptyset\), since there are no subsets of \(A\) with cardinality 12.

  8. Consider the set \(\N^2 = \N \times \N\), the set of all ordered pairs \((a,b)\) where \(a\) and \(b\) are natural numbers. Consider a function \(f: \N^2 \to \N\) given by \(f((a,b)) =a+b\) .

    1. Let \(A = \{(a,b) \in \N^2 \st a, b \le 10\}\). Find \(f(A)\).

    2. Find \(f\inv(3)\) and \(f\inv(\{0,1,2,3\})\).

    3. Give geometric descriptions of \(f\inv(n)\) and \(f\inv(\{0, 1, \ldots, n\})\) for any \(n \ge 1\).

    4. Find \(\card{f\inv(8)}\) and \(\card{f\inv(\{0,1, \ldots, 8\})}\).

  9. Let \(f:X \to Y\) be some function. Suppose \(3 \in Y\). What can you say about \(f\inv(3)\) if you know,

    1. \(f\) is injective? Explain.

    2. \(f\) is surjective? Explain.

    3. \(f\) is bijective? Explain.

    Atbildēt uz šo jautājumu

    1. \(|f\inv(3)| \le 1\). In other words, either \(f\inv(3)\) is the empty set or is a set containing exactly one element. Injective functions cannot have two elements from the domain both map to 3.

    2. \(|f\inv(3)| \ge 1\). In other words, \(f\inv(3)\) is a set containing at least one elements, possibly more. Surjective functions must have something map to 3.

    3. \(|f\inv(3)| = 1\). There is exactly one element from \(X\) which gets mapped to 3, so \(f\inv(3)\) is the set containing that one element.

  10. Find a set \(X\) and a function \(f:X \to \N\) so that \(f\inv(0) \cup f\inv(1) = X\).

    Atbildēt uz šo jautājumu

    \(X\) can really be any set, as long as \(f(x) = 0\) or \(f(x) = 1\) for every \(x \in X\). For example, \(X = \N\) and \(f(n) = 0\) works.

  11. What can you deduce about the sets \(X\) and \(Y\) if you know,

    1. there is an injective function \(f:X \to Y\)? Explain.

    2. there is a surjective function \(f:X \to Y\)? Explain.

    3. there is a bijective function \(f:X \to Y\)? Explain.

  12. Suppose \(f:X \to Y\) is a function. Which of the following are possible? Explain.

    1. \(f\)
    2. \(f\)
    3. \(|X| = |Y|\)\(f\)
    4. \(|X| = |Y|\)\(f\)
    5. \(|X| = |Y|\)\(X\)\(Y\)\(f\)
    6. \(|X| = |Y|\)\(X\)\(Y\)\(f\)

  13. Let \(f:X \to Y\) and \(g:Y \to Z\) be functions. We can define the composition of \(f\) and \(g\) to be the function \(g\circ f:X \to Z\) for which the image of each \(x \in X\) is \(g(f(x))\). That is, plug \(x\) into \(f\), then plug the result into \(g\) (just like composition in algebra and calculus).

    1. If \(f\) and \(g\) are both injective, must \(g\circ f\) be injective? Explain.

    2. If \(f\) and \(g\) are both surjective, must \(g\circ f\) be surjective? Explain.

    3. Suppose \(g\circ f\) is injective. What, if anything, can you say about \(f\) and \(g\)? Explain.

    4. Suppose \(g\circ f\) is surjective. What, if anything, can you say about \(f\) and \(g\)? Explain.

    Atbildēt uz šo jautājumu

    Hint:

    Work with some examples. What if \(f = \twoline{1\amp 2 \amp 3}{a \amp a \amp b}\) and \(g = \twoline{a\amp b \amp c}{5 \amp 6 \amp 7}\)?

  14. Consider the function \(f:\Z \to \Z\) given by \(f(n) = \begin{cases}n+1 \amp \text{ if }n\text{ is even} \\ n-3 \amp \text{ if }n\text{ is odd} . \end{cases}\)

    1. Is \(f\) injective? Prove your answer.

    2. Is \(f\) surjective? Prove your answer.

    Atbildēt uz šo jautājumu

    1. \(f\) is injective.

      Proof

      Let \(x\) and \(y\) be elements of the domain \(\Z\). Assume \(f(x) = f(y)\). If \(x\) and \(y\) are both even, then \(f(x) = x+1\) and \(f(y) = y+1\). Since \(f(x) = f(y)\), we have \(x + 1 = y + 1\) which implies that \(x = y\). Similarly, if \(x\) and \(y\) are both odd, then \(x - 3 = y-3\) so again \(x = y\). The only other possibility is that \(x\) is even and \(y\) is odd (or vice-versa). But then \(x + 1\) would be odd, and \(y - 3\) would be even, so it cannot be that \(f(x) = f(y)\). Therefore if \(f(x) = f(y)\) we then have \(x = y\), which proves that \(f\) is injective.

    2. \(f\) is surjective.

      Proof

      Let \(y\) be an element of the codomain \(\Z\). We will show there is an element \(n\) of the domain (\(\Z\)) such that \(f(n) = y\). There are two cases: First, if \(y\) is even, then let \(n = y+3\). Since \(y\) is even, \(n\) is odd, so \(f(n) = n-3 = y+3-3 = y\) as desired. Second, if \(y\) is odd, then let \(n = y-1\). Since \(y\) is odd, \(n\) is even, so \(f(n) = n+1 = y-1+1 = y\) as needed. Therefore \(f\) is surjective.

  15. At the end of the semester a teacher assigns letter grades to each of her students. Is this a function? If so, what sets make up the domain and codomain, and is the function injective, surjective, bijective, or neither?

    Atbildēt uz šo jautājumu

    Yes, this is a function, if you choose the domain and codomain correctly. The domain will be the set of students, and the codomain will be the set of possible grades. The function is almost certainly not injective, because it is likely that two students will get the same grade. The function might be surjective it will be if there is at least one student who gets each grade.

  16. In the game of Hearts, four players are each dealt 13 cards from a deck of 52. Is this a function? If so, what sets make up the domain and codomain, and is the function injective, surjective, bijective, or neither?

  17. Seven players are playing 5-card stud. Each player initially receives 5 cards from a deck of 52. Is this a function? If so, what sets make up the domain and codomain, and is the function injective, surjective, bijective, or neither?

    Atbildēt uz šo jautājumu

    This is not a function.

  18. Consider the function \(f:\N \to \N\) that gives the number of handshakes that take place in a room of \(n\) people assuming everyone shakes hands with everyone else. Give a recursive definition for this function.

    Atbildēt uz šo jautājumu

    Hint:

    To find the recurrence relation, consider how many new handshakes occur when person \(n+1\) enters the room.

    The recurrence relation is \(f(n+1) = f(n) + n\).

  19. Let \(f:X \to Y\) be a function and \(A \subseteq X\) be a finite subset of the domain. What can you say about the relationship between \(\card{A}\) and \(\card{f(A)}\)? Consider both the general case and what happens when you know \(f\) is injective, surjective, or bijective.

    Atbildēt uz šo jautājumu

    In general, \(\card{A} \ge \card{f(A)}\), since you cannot get more outputs than you have inputs (each input goes to exactly one output), but you could have fewer outputs if the function is not injective. If the function is injective, then \(\card{A} = \card{f(A)}\), although you can have equality even if \(f\) is not injective (it must be injective restricted to \(A\)).

  20. Let \(f:X \to Y\) be a function and \(B \subseteq Y\) be a finite subset of the codomain. What can you say about the relationship between \(\card{B}\) and \(\card{f\inv(B)}\)? Consider both the general case and what happens when you know \(f\) is injective, surjective, or bijective.

    Atbildēt uz šo jautājumu

    In general, there is no relationship between \(\card{B}\) and \(\card{f\inv(B)}\). This is because \(B\) might contain elements that are not in the range of \(f\), so we might even have \(f\inv(B) = \emptyset\). On the other hand, there might be lots of elements from the domain that all get sent to a few elements in \(B\), making \(f\inv(B)\) larger than \(B\).

    More specifically, if \(f\) is injective, then \(\card{B} \ge \card{f\inv(B)}\) (since every element in \(B\) must come from at most one element from the domain). If \(f\) is surjective, then \(\card{B} \le \card{f\inv(B)}\) (since every element in \(B\) must come from at least one element of the domain). Thus if \(f\) is bijective then \(\card{B} = \card{f\inv(B)}\).

  21. Let \(f:X \to Y\) be a function, \(A \subseteq X\) and \(B \subseteq Y\).

    1. Is \(f\inv\left(f(A)\right) = A\)? Always, sometimes, never? Explain.

    2. Is \(f\left(f\inv(B)\right) = B\)? Always, sometimes, never? Explain.

    3. If one or both of the above do not always hold, is there something else you can say? Will equality always hold for particular types of functions? Is there some other relationship other than equality that would always hold? Explore.

  22. Let \(f:X \to Y\) be a function and \(A, B \subseteq X\) be subsets of the domain.

    1. Is \(f(A \cup B) = f(A) \cup f(B)\)? Always, sometimes, or never? Explain.

    2. Is \(f(A \cap B) = f(A) \cap f(B)\)? Always, sometimes, or never? Explain.

    Atbildēt uz šo jautājumu

    Hint:

    One of these is not always true. Try some examples!

  23. Let \(f:X \to Y\) be a function and \(A, B \subseteq Y\) be subsets of the codomain.

    1. Is \(f\inv(A \cup B) = f\inv(A) \cup f\inv(B)\)? Always, sometimes, or never? Explain.

    2. Is \(f\inv(A \cap B) = f\inv(A) \cap f\inv(B)\)? Always, sometimes, or never? Explain.

Symbols used here

A = \begin{pmatrix} a & b \\ c & d \end{pmatrix}
matrix
A rectangular array of numbers; a linear map.
x \in A,\ A \subseteq B
element of, subset
x belongs to A; every element of A is in B.
A \cup B,\ A \cap B,\ A \setminus B
union, intersection, difference
In either; in both; in A but not B.
i
imaginary unit
i² = −1.
\leq,\ \geq
less/greater than or equal
Inequalities that allow equality; < and > exclude it.
n!
factorial
n × (n−1) × … × 1; the number of orderings of n things. 0! = 1.
\binom{n}{k}
binomial coefficient, "n choose k"
Number of k-element subsets of n things: n!/(k!(n−k)!).
\sum_{k=1}^{n} a_k
summation
Add a_k for k = 1 up to n.
\emptyset,\ |A|
empty set, cardinality
The set with no elements; the number of elements of A.
\forall,\ \exists
for all, there exists
Quantifiers: every x; at least one x.
\neg,\ \wedge,\ \vee,\ \Rightarrow,\ \Leftrightarrow
not, and, or, implies, iff
Logical connectives.
\blacksquare\ \text{or}\ \square
end of proof (halmos)
Marks the point where the statement has been established.
a \equiv b \pmod n
congruent modulo n
n divides a − b; a and b have the same remainder.
O(n^2),\ \Theta,\ \Omega
big-O notation
Grows no faster than n² (up to a constant), for large n.
a \bmod n
remainder
What is left after dividing a by n.

Questions people ask

What makes mathematics "discrete"?

It deals with separate, countable objects — integers, graphs, statements — rather than continuous quantities. No limits, no infinitesimals; instead induction, counting and logic.

How does a proof by induction work?

Show the statement for the first case, then show that whenever it holds for n it holds for n + 1. Like dominoes: the first falls, and each knocks over the next.

Izmēģiniet savu

Parts of this page are adapted from Levin, Discrete Mathematics: An Open Introduction (CC BY-SA 4.0). Condensed and re-explained here; errors are ours.

Vairāk Discrete Math & Logic

Truth tablesSums and inductionProof by inductionAlgorithms and growth of functions