# Functions

- Let \(A\) and \(B\) be sets. A function from \(A\) to \(B\) is a mapping of each element of \(A\) to some element in \(B\).
- For a function \(f\), we will write \(f(a)=b\) if \(a\in A\) is mapped to \(b\in B\) by \(f\).
- We will call \(A\) the domain and \(B\) the codomain of \(f\).
- This is usually written \(f:A\rightarrow B\).
- The range of \(f\) is the subset of \(B\) that is actually mapped to by \(f\). That is, \[\mathrm{range}(f) = \{f(a)\mid a\in A\}\subseteq B\,.\]

- Note: some books/courses define “range” to be the thing we called “codomain” above. For this course, we'll stick with these terms.
- For example, we could define a function \(f:\mathbf{Z^{+}}\rightarrow\mathbf{Q}\) as \(f(n) = \frac{n-1}{n}\).
- The range of this function is: \[ \{f(1),f(2),f(3),f(4),\ldots\} = \left\{(n-1)/n\mid n\in\mathbf{Z}^{+}\right\}\subseteq\mathbf{Q}\,. \]
- And define \(g:\mathbf{R}\rightarrow\mathbf{R}\) as \(g(x) = x^2\).

- If we have functions that take multiple arguments (like \(f(x,y)=x+y\)), we can write their domain nicely with a cross product:
\[
f:\mathbf{R}\times\mathbf{R}\rightarrow \mathbf{R}\,.
\]
- The “inputs” to that function are from the set \(\mathbf{R}\times\mathbf{R}\). For example, \((17.1,10/3)\).

# Function Terminology

- There are a bunch of words that get applied to functions…
- A function is called one-to-one if \(f(a)=f(b)\) implies that \(a=b\) for all \(a\) and \(b\) in the domain.
- That is, the function maps from exactly one value in the domain to each value in the range.
- Or the equivalent contrapositive version: if \(a\) and \(b\) are
**different values**in the domain, then \(f(a)\) and \(f(b)\) are different. - e.g. \(f\) defined above is one-to-one: no value in the domain maps onto the same result as any other value.
- e.g. \(g\) is
**not**one-to-one because \(g(3)=g(-3)\) [and other counter-examples].

- A function is called increasing if for all \(x<y\) in the domain, \(f(x)\le f(y)\). It is strictly increasing if \(f(x)<f(y)\).
- increasing = never goes down
- strictly increasing = always goes up
- You can probably guess the definitions for decreasing and strictly decreasing.

*Theorem:*A strictly increasing function is one-to-one.*Proof:*Suppose it is not, that there is an increasing function \(f\) with \(x\) and \(y\) in the domain of \(f\), with \(x\ne y\) and \(f(x)=f(y)\). Without loss of generality, assume that \(x\lt y\).Then we have \(x\lt y\) with \(f(x)\not\lt f(y)\). This contradicts that \(f\) is increasing.∎

- A function \(f:A\rightarrow B\) is called onto if for every element \(b\in B\) there is an element \(a\in A\) with \(f(a)=b\).
- In other words, an onto function's codomain and range are the same.
- Examples of functions that are onto: \[ f_1:\mathbf{Z}\rightarrow\mathbf{Z}, \quad f_1(n)=n+1 \\ f_2:\mathbf{R}\rightarrow[-1,1], \quad f_2(x)=\sin x \\ f_3:\mathbf{R}\rightarrow\mathbf{R}, \quad f_3(x)=x^3 \]
- Some functions that are
**not**onto: \[ f_4:\mathbf{Z}\rightarrow\mathbf{Z}, \quad f_4(n)=|n| \\ f_5:\mathbf{R}\rightarrow\mathbf{R}, \quad f_5(x)=\sin x \\ f_6:\mathbf{Z}\rightarrow\mathbf{Q}, \quad f_6(n)=n/2 \] - Obviously, being “onto” depends on what we give as the codomain.

- A function is called a bijection or a one-to-one correspondence if it is both one-to-one and onto.
*Theorem:*The function \(f:\mathbf{R}\rightarrow\mathbf{R}\) defined as \(f(x)=x^3\) is a bijection.*Proof:*From the definition, we need to prove that is it both one-to-one and onto.First, \(f\) is one-to-one because if we have \(f(x)=y\) then we know that \(x^3=y\) and thus that \(x=\sqrt[3]{y}\). Because of something I remember from another course about cube roots, \(x\) is unique.

The function \(f\) is onto because each real number is the cube of some value (specifically, \(\sqrt[3]{y}\)). So we see that \(f\) is both one-to-one and onto, and thus a bijection.∎

*Theorem:*The function \(f:\mathbf{R}\rightarrow\mathbf{R}\) defined as \(f(x)=x^2\) is not a bijection.*Proof:*There is no \(x\) which makes \(f(x)=-1\), so it is not onto.∎*Theorem:*The function \(f(x)=x^2\) is not a bijection, where the domain is \(\mathbf{R}\) and the codomain is \(\{x\mid x\in\mathbf{R}, x\ge 0\}\).*Proof:*For both \(x=1\) and \(x=-1\), we have \(f(x)=1\), so \(f\) is not one-to-one.∎*Theorem:*The function \(f:\mathbf{R}^{+}\rightarrow\mathbf{R}^{+}\) defined as \(f(x)=x^2\) is a bijection.*Proof:*[Left to you.]

# New Functions From Old

- A few ways to take existing functions and build new ones…
- For a one-to-one correspondence \(f\) from \(A\) to \(B\), the inverse function of \(f\) is written \(f^{-1}\). It is the function with \(f^{-1}:B\rightarrow A\) such that if \(f(x)=y\) then \(f^{-1}(y)=x\).
- Since \(f\) is one-to-one, we know that the \(x\) that makes \(f^{-1}(y)=x\) is unique (so \(f^{-1}\) really is a function).
- Since \(f\) is onto, we know that \(f^{-1}\) is defined everywhere in \(B\).
- In other words, the inverse of \(f\) is the function that reverses the effect of applying \(f\).
- One-to-one correspondence/bijections are also called invertible functions.

- Aside: we could have defined “inverse” on one-to-one (but not onto) functions. That would have mostly worked, but we wouldn't know what the domain of \(f^{-1}\) was.
- This way, we know that if \(f:A\rightarrow B\) then \(f^{-1}:B\rightarrow A\).

- e.g. \(f:\mathbf{R}\rightarrow\mathbf{R}\) defined as \(f(x)=x^3\) is invertible. We already have notation for the inverse: \(f^{-1}(x) = \sqrt[3]{x}\).
- e.g. \(f(x)=x^2\) is invertible if we restrict the domain to \(\mathbf{R}^{+}\), and \(f^{-1}=\sqrt{x}\).
- Given functions \(f:A\rightarrow B\) and \(g:B\rightarrow C\), the composition of \(f\) and \(g\) is written \(g\circ f\) and defined as \[(g\circ f)(a) = g(f(a))\,.\]
- e.g. Let \(f(x)=x^2\) and \(g(x)=x+1\), with the domain and range of each being \(\mathbf{R}\). Then, \[ (f\circ g)(x) = f(g(x)) = f(x+1) = (x+1)^2 = x^2+2x+1\,,\\ (g\circ f)(x) = g(f(x)) = f(x^2) = x^2+1\,. \]
- Clearly, \(f\circ g\ne g\circ f\). Composition is not commutative.
- Notice that for invertible function \(f\), we have: \[(f^{-1}\circ f)(x) = x\,,\\(f\circ f^{-1})(y) = y\,.\]

# Cardinality of Sets

- We defined the cardinality of a set to be the number of elements in the set.
- For finite sets, that's the end of the story.
- But for infinite sets, things get more interesting.

- Two sets have the same cardinality (\(|S|=|T|\)) if and only if there is a bijection between the elements of the two sets (and 1-to-1 and onto function \(f:S\rightarrow T\)).
- Sounds obvious enough: if you can match up the elements, then there are the same number.
- But there are unexpected implications…

- The set of positive integers (\(\{1,2,3,\ldots\}\)) has an infinite number of elements.
- Let's give the cardinality a name: \(|\mathbf{Z}^{+}|=\aleph_0\).
- That's a Hebrew letter “aleph”.

- How many positive even numbers (\(E=\{2,4,6,\ldots\}\)) are there?
- Consider the function from the positive integers to the positive evens \(f(n)=2n\).
- This function is one-to-one (no even number is produced multiple ways) and onto (no even number is missed). So it's a bijection.
- \(|E|=\aleph_0 = |\mathbf{Z}^{+}|\)
- There are the same number of integers and even numbers.
- Somehow, the set didn't get any smaller when we took out half of its elements.
- Infinity is weird.

- How many positive rational numbers are there?
- If we can set up a bijection between them and the positive integers, there must be the same number.
- There's no obvious formula for one, but consider this diagram:
- We can put all the positive rationals on a grid like that, and ignore the duplicates (where the numerator and denominator have a common factor: coloured red in the figure).
- Then follow that diagonal zig-zag path to pass by each one. Let that order define a function: \[ f(1)=1/1\\ f(2)=2/1\\ f(3)=1/2\\ f(4)=1/3\\ f(5)=3/1\\ \vdots \]
- That function is a bijection between the positive integers and rationals.
- Therefore, \(|\mathbf{Q}^{+}|= |\mathbf{Z}^{+}|\).
- That's even more surprising: throwing all of the fractions in there didn't make the set any bigger.

- Are there sets with cardinality larger than \(\aleph_0\)? Yes.
- Consider the interval \([0,1)\), the set \(\{x\mid x\in\mathbf{R}, 0\le x\lt 1\}\).
- It has cardinality greater than \(\aleph_0\). To prove that, we need to show that there is no bijection between \([0,1)\) and \(\mathbf{Z}^{+}\).
- Suppose you claim to have found one. For every positive integer, your function produces a real in that range.
- It must be one-to-one (no duplicates—easy) and onto (hits every real in the range—impossible).
- Your function must be like this (with each \(d_{mn}\) being a digit in the decimal expansion of the real number): \[ f(1) = 0.d_{11}d_{12}d_{13}d_{14}\ldots\\ f(2) = 0.d_{21}d_{22}d_{23}d_{24}\ldots\\ f(3) = 0.d_{31}d_{32}d_{33}d_{34}\ldots\\ f(4) = 0.d_{41}d_{42}d_{43}d_{44}\ldots\\ \vdots \]
- I will find a real number that your function doesn't return as follows: it's \(0.e_1e_2e_3e_4\ldots\) where I'll choose each digit in the decimal expansion as: \[e_i= \left\{\begin{array}{rl} 1 &\text{ if }d_{ii}=0 \\ 0 &\text{ otherwise} \end{array} \right.\,.\]
- That number is definitely not in the range of your function: it differs from each \(f(i)\) in the \(i\)-th decimal position.
- So, there can be no bijection between the positive integers and this (or any) range of real numbers.
- \(|\mathbf{R}|>\aleph_0\)

- So, there must be some notion of the “size” of an infinite set: the set of reals is larger than the set of integers.
- That's why we called \(|\mathbf{Z}^{+}|=\aleph_0\): it's the first “size” of an infinite set.
- The next larger infinity is \(\aleph_1\), then \(\aleph_2\), …
- Is \(|\mathbf{R}|=\aleph_1\)? Either yes or no. Or both. Or neither. Kurt Gödel ruined everything. Google “incompleteness theorem” and “continuum hypothesis” if you want to know why.
- But, \(|P(\mathbf{Z})|=|\mathbf{R}|\).

- Sets with cardinality \(\aleph_0\) or less are called countable.
- i.e. finite sets and sets with \(|\mathbf{Z}|\) elements are countable.
- Larger sets are called uncountable.

- Are there an infinite number of infinities?
- Yes.
- You can prove that for any set, \(|S|<|P(S)|\) with an argument very much like the \(|\mathbf{R}|>\aleph_0\) one above.
- So, if you want a set larger than \(\mathbf{R}\), then \(P(\mathbf{R})\) is one, and \(P(P(\mathbf{R}))\) is even bigger.

- One notable implication to computer science: uncomputability.
- The total number of programs you can write is \(\aleph_0\) (even assuming infinite memory).
- The number of functions that map integers to integers has cardinality \(\gt\aleph_0\).
- So, we can't write a computer program to compute some functions (most of them, actually).
- These functions are uncomputable.
- It's not a problem of a bad language or bad hardware: the math is against us.
- Annoyingly, some of those functions are ones it would be nice to have a program for.

# Some Important Functions

- A few functions that you may or may not have seen before, but we need defined…
- A common thing to want to do: round a real number to an integer.
- We have some options: round up, round down, round to the closest.

- The floor function maps a real number \(x\) to the largest integer \(n\) with \(n\le x\).
- i.e. it rounds
**down**. - It is written \(\lfloor x \rfloor\).
- e.g. \(\lfloor 10.2 \rfloor=10\), \(\lfloor 10.999 \rfloor=10\), \(\lfloor 10 \rfloor=10\), \(\lfloor -10.2 \rfloor=-11\), \(\lfloor -10.999 \rfloor=-11\), \(\lfloor -10 \rfloor=-10\)
- Notice: it doesn't just chop off the fraction part (and round toward zero). It actually rounds down, so we know that \(\lfloor x \rfloor\le x\).

- i.e. it rounds
- The ceiling function maps a real number \(x\) to the smallest integer \(n\) with \(n\ge x\) and is written \(\lceil x \rceil\).
- i.e. it rounds
**up**. - e.g. \(\lceil 6/7 \rceil=1\), \(\lceil 7/6 \rceil=2\), \(\lceil -1/3 \rceil=0\), \(\lceil -10/3 \rceil=-3\)
- Again, remember that it's always up, so \(\lceil x \rceil\ge x\).

- i.e. it rounds
- These are very useful when doing problems that are inherently about integers.
- e.g. A bus leaves from Yuquan to Zijingang campus every seven minutes and carries 100 people. How many people can leave from Yuquan every hour?
- Not \(100\cdot 60/7\): there are not \(60/7=8.5714\) buses leaving in the next hour, and they will not carry \(857.14\) people.
- \(100\cdot \lfloor 60/7\rfloor = 800\) people.

- Note that \(\lfloor x+y\rfloor \ne \lfloor x\rfloor + \lfloor y\rfloor\). Consider this with \(x=0.5, y=0.7\).
*Theorem:*For any real number \(x\), there is a unique integer \(n\) and real number \(f\) with \(0\le f < 1\) and \(x=n+f\). These values are \(n=\lfloor x\rfloor\) and \(f=x-n\).*Proof:*Suppose there is another such integer \(m\) and real \(e\) satisfying these conditions, with \(m\ne n\). Let \(e=x-m\), so \(x=m+e\).From the definition, we know that \(\lfloor x\rfloor\) is the largest integer less than or equal to \(x\). If \(m>n\), then \(m>x\) and \(e<0\). This does not satisfy the conditions of the theorem.

So, \(m<n\) and since they are integers, \(n-m\ge 1\). Now, we have \[\begin{align*} x = n+f &= m+e\\ n-m &= e-f\\ 1 &\le e-f \\ 1+f&\le e\\ 1&\le e\,. \end{align*}\] This contradicts the assumption, so \(n\) and \(f\) must be unique.∎

- As you can see, it can be infuriatingly hard to prove something obvious.
- What is missing from that proof? [Note when you're studying: it's not nothing.]
*Theorem:*For a real number \(x\) and integer \(n\), \(x\lt n\) if and only if \(\lfloor x\rfloor \lt n\).*Proof:*First, [for the “only if” part] we know from the definition that \(\lfloor x\rfloor \le x\), so if \(x\lt n\) then \(\lfloor x\rfloor \le n\).Now, [for the “if” part] consider \(\lfloor x\rfloor \lt n\). From the previous theorem, we know that there is an \(0\le f\lt 1\) with \(x=\lfloor x\rfloor+f\).

Now, suppose that \(x\ge n\). Since both \(n\) and \(\lfloor x\rfloor\) are integers, \[\begin{align*} n &\gt \lfloor x\rfloor\\ n &\ge \lfloor x\rfloor +1\\ n &\ge x-f +1\\ x &\ge x-f +1\\ f &\ge 1\,. \end{align*}\] This contradicts the conditions on \(f\), so by contradiction we must have \(x\lt n\).∎

- The factorial function maps \(\mathbf{N}\) to \(\mathbf{Z}^{+}\). The factorial of \(n\) is written \(n!\) and defined as \[n!=1\cdot 2\cdot \cdots\cdot (n-1)\cdot n\,.\]

# Codomain and Ranges

- A little more commentary on codomain and range…
- The codomain is the thing you give as part of the function definition. e.g. \(\mathbf{Z}\) in
\[f : \mathbf{R}\rightarrow\mathbf{Z}\text{ with }f(x)=\lfloor x\rfloor + 1\,.\]
- The value given for the codomain could be larger, but that's less useful. e.g. it's correct but a little stupid to say \[g : \mathbf{R}\rightarrow\mathbf{R}\text{ with }g(x)=\lfloor x\rfloor + 1\,.\]

- That means that the same equation could be onto or not onto, depending on the way the function is defined.
- Above, \(f\) is onto, but \(g\) is not.
- Neither is one-to-one, since both map 2 and 2.1 to the same value.

- This function is
**both**one-to-one and onto: \[h : \mathbf{Z}\rightarrow\mathbf{Z}\text{ with }h(x)=\lfloor x\rfloor + 1\,.\] - So if you don't give the domain and codomain, you haven't finished defining the function.
- e.g. if I ask “give a function that is one-to-one that has the property…” and you don't give the domain and codomain, you didn't get it right.