1Questions and Answers

Given two sets $X$ and $Y$, a function $f$ from $X$ to $Y$ is a rule that selects for each element of $X$ exactly one element of $Y$. The mathematical notation $f:X\rightarrow Y$ says that $f$ is a function from $X$ to $Y$. The element $y\in Y$ that is selected for $x\in X$ is called the value of the argument $x$ and is written as $f(x)$. Note that $X,Y,x,y$ are variables here that are placeholders for concrete sets and concrete elements of these sets.

For example, if $X$ is the set of countries in the world and $Y$ is the set of cities in the world, then we can consider the function $f:X\rightarrow Y$ that selects for each country its capital. The value of the argument Austria is Vienna,

Because sets are mathematical entities and do not correspond to bags in real life, they do not actually contain countries or cities, but just text symbols that identify the countries and cities.

We can also think of $X$ as questions in a quiz, and $Y$ as answers. Then a function $f$ provides an answer $y=f(x)\in Y$ for every question $x\in X$. Our example function above provides the answer to every question of the form What is the capital of country $x$?

In this example, there are elements of $Y$ (for example, Zurich) that are not selected for any $x$, so there may be answers that will never be given. That’s ok. The only thing we require is that for every question, there is an answer. We also allow that several questions have the same answer. As an example, consider the function corresponding to the question What is the first letter of country $x$’s name? This gives the same answer A for Austria, or Australia, or Albania, or....

The mathematician creates another theorem out of this.

2Invertible functions

Suppose we are given the answer and want to know what the question was. If there is always a single question $x\in X$ that leads to a given answer $y\in Y$, then this defines a function $f^{-1}:Y\rightarrow X$ that we call the inverse of $f$: For every answer $y\in Y$, $f^{-1}(y)$ is then the single question $x\in X$ with answer $y$. We can think of $f^{-1}$ as the function that “undoes" $f$: if we compute $f^{-1}(f(x))$, we get back $x$ for every question $x\in X$, so nothing happened. Indeed, $f$ takes us from the question $x$ to the answer $f(x)$, and $f^{-1}$ takes us from the answer $f(x)$ back to the question $f^{-1}(f(x))=x$.

Let’s look at this for the function $f$ corresponding to questions of the form What is the capital of country $x$? If we are given the answer Vienna, we know that the question was Austria. Similarly, for every answer that is actually the capital of some country $x$, we know the question (namely $x$). But if the answer is Zurich, we cannot find a question with this answer. So the function $f$ is not invertible. But it becomes invertible if we say that $Y$ is not the set of all cities in the world but only the set of all capitals in the world.

Let’s consider the function corresponding to the question What is the first letter of country $x$’s name? This function is not invertible, even if we say that $Y$ is only the set of letters that occur as first letter of some country’s name. Indeed, if the answer was A, we can’t tell whether the question was Austria, or Australia, or Albania, or....

The pigeon‐hole principle.Even without remembering several countries whose names start with A, we would have known that the function just considered cannot be invertible. After all, there are only 26 letters, but (much) more than 26 countries in the world, so it is inevitable that several country names start with the same letter. This is known as the pigeon‐hole principle, and in function language, it can be stated as follows.

There is a fun fact based on the pigeon‐hole principle: you can find two people in Zurich with exactly the same number of hairs. This is due to the fact that a human (according to various sources, and adding a safety margin) has never more than $200,000$ hairs. Hence, among roughly $400,000$ people in Zurich, there must certainly be two with the same number of hairs. Unfortunately, the pigeon‐hole principle does not tell us how to find them.

A variant of the pigeon‐hole principle shows that $f:X\rightarrow Y$ is also not invertible if $Y$ has more elements than $X$. Indeed, if there are less questions than answers, then some answer will never be given and hence $f$ is not invertible. This is what happened to Zurich in the country capitals example above. But again, we do not need to remember the capital status of Zurich to make the argument (many people get that status wrong, anyway). We simply need to know that there are (many) more cities in the world than countries, so it is inevitable that some cities are not capitals.

The upshot is that $f:X\rightarrow Y$ can only be invertible if $X$ and $Y$ actually have the same number of elements. The following picture summarizes the situation.

Actually, if $X$ is a finite set, we can always think of a function $f:X\rightarrow Y$ as a (possibly large) table, and in this table view, it is quite easy to see when a function is invertible. Consider the case where $X=Y=\{ 1,2,3,4\}$. The function

is invertible, because every element of $Y$ occurs exactly once in the right column. This is the same as saying that there is a single question for every possible answer $y\in Y$.

Hence, for an invertible function, the right column just lists all the elements of $Y$, in some order. Also, the inverse is very easy to construct from the table, by simply interchanging the two columns (instead of going from questions to answers, we now go from answers to questions). This means, the inverse of the previous function is

but we would typically still reorder the rows so that the left column is sorted for better readability of the table (see Exercise 7 below).

In contrast,

is not invertible, because an element of $Y$ occurs twice (and another one not at all) in the right column.

You will not be surprized that there is a general theorem behind this:

The expression $n!$ is known as the factorial and it denotes the product of the numbers between $1$ and $n$. For example, $3!=1\cdot 2\cdot 3=6$ and $4!=1\cdot 2\cdot 3\cdot 4=24$.

3Numerical functions

If $X$ and $Y$ are sets of numbers, we can visualize $f$ in a coordinate system with $X$‐ and $Y$‐axes. You know this from high school where you have looked at numerical functions such as $\sin (x),\cos (x)$, or $\log (x)$.

Let us do a simpler example. Recall that $\R$ is the set of real numbers and set $X=Y=\R .$ Our function $f:X\rightarrow Y$ is defined by

This looks as follows in the coordinate system.

On the $X$‐axis, we have the arguments $x$ (questions), and on the $Y$‐axis the values $y$ (answers). For example, question $0$ has answer $f(0)=2\cdot 0-5=-5$, and for question $3,$ the answer is $f(3)=2\cdot 3-5=1$. We can summarize these question/answer pairs in form of the points (2‐tuples) $(0,-5)$ and $(3,1)$.

The fat line is the graph of $f$, the set of all points of the form $(x,f(x))$. Hence, for every question $x$ on the $X$‐axis, the height of the graph at $x$ gives us the answer $f(x)$.

The fact that $f$ is a function can also be seen by looking at the graph. We know that for every question $x$, there is a single answer $f(x)$. This means, whenever we draw a vertical line (dashed) at some value $x$ on the X‐axis, then this line intersects the graph of $f$ in a single point $(x,f(x))$:

Is this particular function invertible? To check this formally, we must consider any possible real number $y$ and see whether we can find a unique $x$ such that $f(x)=y$. If it exists, such a number $x$ must satisfy

There is indeed a unique such number that we get by solving the previous equation for $x$ by the school method: So $f$ is invertible, and $f^{-1}:\R \rightarrow \R$ is defined by

But we can also tell directly from the picture that $f$ is invertible, meaning that for every answer $y$, there is a single question $x$ with this answer. Namely, whenever we draw a horizontal line at some $y$, this line intersects the graph of $f$ in a single point $(x,y)$ at which $y=f(x)$ (by definition of the graph), or $x=f^{-1}(y)$ as we can write, once we know that $f$ is invertible.

We can even get the graph of the inverse function $f^{-1}$ from the picture. Indeed, when we find $f^{-1}(y)$ from $y$ via the horizontal line at $y$, we do the same as when we find $f(x)$ from $x$ via the vertical line at $x$—only the roles of $X$‐ and $Y$‐axis are interchanged. Hence, when we simply mirror the picture at the diagonal (dotted), we obtain the graph of $f^{-1}$!

The function $f(x)=2x-5$ is an affine function, and the mathematician immediately sees a theorem at the horizon that discusses all affine functions at once, using variables.

The condition $a\neq 0$ is needed so that we can divide by $a$ in the proof. If $a=0$, the function is indeed not invertible. In this case we have $f(x)=b$, so every question $x$ has the same answer $b$.

Let’s look at some non‐invertible numerical function. We define $f:\R \rightarrow \R$ by $f(x)=|x|$, the absolute value of $x$. This is the value that we get from $x$ by ignoring the sign. For example, $|5|=5$ and $|-6|=6$. This function is immediately seen to be non‐invertible. For starters, there is no question that leads to a negative answer. But even for a positive answer such as $6$, there are two possible questions, namely $6$ and $-6$. If we look at this in a coordinate system, we can graphically see what is going on:

If we draw a (dashed) horizontal line at some negative $y$, it does not intersect the graph of $f$ at all; such a $y$ corresponds to an answer that is never given. If we draw a horizontal line at some positive $y$, it intersects the graph of $f$ twice; this corresponds to the case where we have two questions leading to answer $y$. Only for $y=0$, there is a single question $x=0$.

We could “fix” $f(x)=|x|$ to make it invertible by defining $f:\R _+\rightarrow \R _+$, where $\R _+$ is the set of nonnegative real numbers. Then $f$ would “live” only in the upper right square of the coordinate system, and there it is invertible. Indeed, for every nonnegative answer $y$, there is only one nonnegative question, namely $y$ itself. This “fix” works because $f(x)=|x|$ just outputs the input for $x\in \R _+$. In general, a function $f:X\rightarrow X$ with $f(x)=x$ for all $x\in X$ is called identity and is always invertible, with $f^{-1}=f$.

This is related to famous Hilbert’s Hotel, a hotel with infinitely many rooms numbered $1,2,...$. Some evening, a new guest arrives without a reservation. Unfortunately, the hotel is fully booked, i.e. there are infinitely many guests already, and all rooms are taken. Fortunately, the clerk can solve the problem by simply asking every guest to move to the room one number higher: the guest in room $1$ moves to room $2$, the one in room $2$ moves to room $3$, and so on. This frees up room $1$ which can then be given to the new guest.

In some sense, the sets $\N =\{ 0,1,2,...\}$ and $\N '=\{ 1,2,3...,n\}$ have the same size. Actually, in a very precise sense. We simply define two infinite sets $X$ and $Y$ to be of the same size whenever there is an invertible function $f:X\rightarrow Y$. The following exercise shows that even the sets $\N$ and $\Z =\{ ...,-2,-1,0,1,2,...\}$ have the same size, although it rather looks like $\Z$ might have twice the size of $\N$.

4Functions with more arguments

Sometimes, several questions need to be asked before an answer can be given. To understand this, let’s think of a pocket calculator. It typically has an $\boxed {x^2}$ key. To use it, you type in the question (argument) $x$, for example $5$, and then press $\boxed {x^2}$ to get the answer (value) $x^2$; in this example $x^2=x\cdot x=25$. But there is also an $\boxed {x^y}$ key. This requires two arguments $x$ and $y$. To use it, you type in the first argument $x$, for example $3$, then press $\boxed {x^y}$, type in the second argument $y$, for example $4$, and finally press $\boxed {=}$ to get the value $x^y$; in this example $3^4=3\cdot 3\cdot 3\cdot 3=81$.

Mathematically, this is a function with two arguments: $f(x,y)=x^y$. In a strict mathematical sense, there is only one argument, namely the pair $(x,y)$, and one would have to write $f((x,y))$, but even mathematicians don’t like this and typically think of two arguments instead of one argument that consists of two parts. We could also have three or more arguments. We will not go into what the sets $X$ and $Y$ are in $f:X\rightarrow Y$ if the function $f$ has several arguments. But they exist, and we can also ask whether $f$ is invertible, just like for “normal” functions with one argument.

Functions with two arguments can also be specified via a value table, but this time, the table is two‐dimensional. Let us suppose that we want to compute $x^y$ only for $x$ and $y$ between $0$ and $4$. Then the value table is the following.

You might find it weird that $0^0=1$, but let’s not discuss it; we only wanted to point out that this is not a typo.