• 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\,.\]

• 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\).

• The “inputs” to that function are from the set \(\mathbf{R}\times\mathbf{R}\). For example, \((17.1,10/3)\).

• 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].

• increasing = never goes down
• strictly increasing = always goes up
• You can probably guess the definitions for decreasing and strictly decreasing.

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.∎

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

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.∎

Proof: There is no \(x\) which makes \(f(x)=-1\), so it is not onto.∎

Proof: For both \(x=1\) and \(x=-1\), we have \(f(x)=1\), so \(f\) is not one-to-one.∎

Proof: [Left to you.]

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

• This way, we know that if \(f:A\rightarrow B\) then \(f^{-1}:B\rightarrow A\).

• For finite sets, that's the end of the story.
• But for infinite sets, things get more interesting.

• Sounds obvious enough: if you can match up the elements, then there are the same number.
• But there are unexpected implications…

• Let's give the cardinality a name: \(|\mathbf{Z}^{+}|=\aleph_0\).
• That's a Hebrew letter “aleph”.

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

• 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:

  

  Source: Wikipedia Diagonal argument.svg

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

• 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\)

• 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}|\).

• i.e. finite sets and sets with \(|\mathbf{Z}|\) elements are countable.
• Larger sets are called uncountable.

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

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

• We have some options: round up, round down, round to the closest.

• 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 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\).

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

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.∎

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 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\,.\]

• Above, \(f\) is onto, but \(g\) is not.
• Neither is one-to-one, since both map 2 and 2.1 to the same value.

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