# 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$$.
• 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$$.
• 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.