\documentclass{article}
\input{preamble.tex}
\title{Day 14}
\date{Monday June 11, 2012}
\newcommand{\df}{\textbf}

 \def\Display{\@empty}
\newcommand{\Hide}[2]{\ifx \Display\undefined \strut \\ \vspace{#1} \\ \strut  \else {\color{blue} #2} \fi  }
\newcommand{\cod}{\opname{cod}}

\begin{document}

\maketitle

\section{Function}

Relations are the first mathematical structure that we encountered. Sets act as the brick and mortar to the house of mathematical thinking, and relations lay the foundation.

As far as particularly nice structures go, we have investigated a lot of different properties relations have had. We have looked at order relations (linear orderings, partial orderings, etc) and equivalence relations (the integers mod $n$).  We now explore what the most important type of relation which is central in every field of mathematics: The function.

\subsection{Definition}

To begin with the motivation of the definition, we have seen equivalence classes. Equivalences classes are good at associating large chunks of similar data. For instance, if all we were interested in was the remainder when you divide by $5$, then we might as well associate $0$ with $5$ with $10$ with $15$ etc, and vice-a-versa.

Functions will fill a different niche for us. Instead of associating chucks of data. Functions will talk about a one way association from one set of data into another. This type of association is known colloquially as assignment. We will assign all of the pieces of data from one set into pieces of data into another set.

The key to why this is useful is the uniqueness property, which says that from the pieces of data we are assigned ``out of'', there is only one piece of data we are assigned ``into.'' Therefore, we need never make decisions on which thing gets assigned to some value, as there will always be exactly one.

\begin{dfn}

A function is a relation $R$ between two sets $A$ and $B$, such that:
\[
\A x\in A \st \E ! y\in B \stt x R y
\]
Moreover, we make the convention that $A\neq \emptyset$.

 Note: unlike the relations we have dealt with before, $A$ and $B$ need not be the same.
\end{dfn}

\subsection{Notation and Terminology}

Before we do lots of specific examples, it's best that we describe the notation. Foremost, in this course we will tend to use the letters $f,g,h$ as functions. This is fairly standard.

Next, the set on the lefthand side of the relation is called the \df{domain}.  If $f$ is a function, when we want to refer to the domain we write $\dom(f)$. The lefthand side of the relation is called the \df{codomain}. Similarly, when we want to refer to the codomain we write $\cod(f)$.

If $A$ is the domain and $B$ is the codomain then to write (or declare) that $f$ is a function that maps $A$ to $B$ we write
\[
f:A\to B
\]
Where we read that precisely as it looks.

The terminology also changes to say that $a$ is related to $b$ through the relation $f$. Instead we say $f$ \df{maps} $a$ to $b$, and we write
\[
f(a) = b
\]

\subsection{Underlying Set Structure}

Recall that if $R$ is a relation between $A$ and $B$ then $R\sbs A\times B$. Therefore, a function $f$ can really be identified with a set of ordered pairs.

\begin{question}
Given the property that all functions have, what do these ordered pairs look like?
\end{question}
\begin{ans}
Well, for every $a$ in the domain there is exactly one ordered pair with $a$ on the left hand side of the ordered pair, and the right hand side is some element from the codomain.
\end{ans}

\subsection{Some Examples}

\begin{eg}
Some simple examples of functions are the ones with a finite domain. For instance
\[
 f = \set{ (0,1), (1,2), (3,4) }
\]
is a function, with domain $\s{0,1,3}$. As a convention, when we give a function in terms of ordered pairs, we just assume the domain is given by this implicitly.

What does this mean? Well, it could be that the domain of the above $f$ is actually $\set{ 0,1,3,4 }$. But this would not be a function; can you see why using the property
\[
\A a\in \dom(f) \st \E! b\in \cod(f) \stt f(a) = b
\]
\end{eg}

\begin{eg}

Consider
\[
g = \set{ (0,1), (0,2), (1,2), (3,4) }
\]
This is not a function, as it violates the uniqueness clause; that is, for $a=0$ in the domain there are two elements in the codomain $1$ and $2$ that $a$ is mapped to.
\end{eg}

It is often the case where we specify a function as a \df{rule}. A rule is some procedure that given an element of the domain, you preform this procedure on it, and it creates a unique element of the codomain.

\begin{eg}
If $f:\R \to \R$, we might define $f$ using the rule that one takes a value and squares it. This obviously creates a function. There are two ways to notate it. The first, and most common, we write
\[
f(x) = x^2
\]

Note, $x$ here is just a dummy variable ( a bound variable) that is just used as a tool for declaring the function. We just might as well write
\[
f(y) = y^2
\]

The other way to specify where $f$ sends a value $x$ is to write
\[
x\mapsto x^2
\]
This has the benefit of showing exactly the assignment in a directed manner. However, it has the downside that the function $f$ being described is not explicitly written, and one must know from context which function is being described. That is why it is often the case where this type of definition is usually written
\begin{align*}
f: \R &\to \R \\
x&\mapsto x^2
\end{align*}
\end{eg}

Most functions that we encounter in math are described by rules. But, this leads to a problem because we can write down many rules which are ambiguous and/or do not assign values to every element of the domain. In this case, we say the rule is not \df{well-defined}.

\subsection{Well-Defined}

I can write down many rules. For instance, I might write the following for $f:\R \to \R$
\[
f(x) = \sqrt{x}
\]
But, this rule does not make sense, as $-1$ is a negative number, but $\sqrt{-1}$ is not a well-defined notion in the real numbers. In this case, we say the rule is not well-defined; it just doesn't make sense in defining a function.

Another case, is consider the function
\begin{align*}
f:\Z_7 &\to \Z_2 \\
[x]_7&\mapsto [x]_2
\end{align*}
Where $\Z_7 = \set{ [0]_7,[1]_7,\ldots,[6]_7 }$, that is $\Z_7$ is the set of equivalences classes mod $7$.

Here, what $f$ does is takes in an equivalence class mod $7$, which is of for $[x]_7$ for some $x\in \Z$, and assigns it to $[x]_2$.

The problem is, this is an ambiguous definition. To see why, consider $[1]_7$. According to our rule, this should get sent to $[1]_2$.  But, $[1]_7 = [8]_7$, which according to our rule gets sent to $[8]_2$, which is $[0]_2$. So $[1]_7$ is ambiguously being sent to $[0]_2$ and $[1]_2$. This isn't good!

There are $3$ ways a rule can be ill-defined:
\begin{itemize}
\item A rule may not be defined for everything in the domain.
\item A rule may be ambiguous, and try to send one element in the domain to two different places in the codomain.
\item A rule may try to send something in the domain to something outside of the codomain.
\end{itemize}

\subsection{Image}

 If $f(x) = x^2$ is a function from $\R$ to $\R$, then notice that all points in $(0,1)$ are sent to points in $(0,1)$. This is fairly interesting, and tells us something about the squaring function. This type of question is an interesting one to ask: where do the points of some subset of the domain go?

If $f$ is a function from $A$ to $B$, and $A'\sbs A$, then the \df{image of $A'$ under $f$} is the set of all points in $B$ that are mapped to by $A$. That is:
\begin{align*}
f[A'] &= \set{ b\in B \st \E a\in A' \stt f(a) = b } \\
&= \set{ f(a) \mid a\in A } & \mbox{\it more informal notation}
\end{align*}

Even asking the question what the image of the domain is can prove to be a very important concept. Thus we give that a name as well: the image of the domain of $f$ is called the \df{image of $f$} or the \df{range of $f$}. This is the set of ``attainable'' values, ie. values that we can achieve by using the function. We will notate this is $\im(f)$.

\begin{eg}
Consider, as before, $f(x) = x^2$. Then
\[
f[(-1,1)] = [0,1)
\]
and
\[
\im(f) = [0,\infty)
\]
\end{eg}

\subsection{Pre-Images}

Just as it is useful to ask where the subset of values of domain are sent, it is often usual to ask where a subset of the codomain could have came {\it from}.

There is nothing in the definition of function forcing everything in the codomain to be hit, or hit only once. Therefore, looking at preimages are a bit more complicated.

\begin{eg}
	A nice example would be the function $f(x) = x^2$ from $\R$ to $\R$. What elements hit $1$? Well, $1$ and $-1$, and nothing else. So we'd say the preimage of $\s{1}$ is $\s{-1,1}$. 
\end{eg}

So, if $f:A\to B$ is a function and $B'\sbs B$ we say that the \df{preimage of $B'$ under $f$} is the set of all points in $A$ that, after passing through the function $f$, ``land in'' $B$. That is:
\begin{align*}
	f^{-1}[B'] &= \set{ a\in A \mid \E b\in B' \stt f(a) = b } \\
				&= \set{ a \in A \mid f(a) \in B' } & \mbox{\it more informal notation}
\end{align*}

\begin{eg}
	Consider the function $f:\N \to \Z$ defined by $f(x) = x$. This is an example of an \df{inclusion map}. That is, a map from $A\to B$ where $A\sbs B$ defined by $x\mapsto x$, is called an inclusion map. 
	
	Let's calculate the following:
	\begin{enumerate}
		\item $\im(f)$
		\item $f[\set{ n\in \N \mid \E m\in \N n = 2m }]$
		\item $f^{-1}[ \set{ n\in \Z \mid n < 0 } ]$
	\end{enumerate}
	
	Well, the image of $f$ is just $\N$, or non-negative integers.
	
	The image of the even numbered naturals under this map are just the even numbered naturals. 
	
	As nothing maps into the negative numbers, the preimage of such a set is just $\emptyset$. 

\end{eg}


\subsection{Apples and Bananas}

The domain and codomain of a set might have very little in common with each other. One could imagine for instance, function which takes in a number and returns a description of a color. Thus the domain would be numbers, and the codomain would be English words, or maybe English words that are colors. Regardless, they are completely different entitied, and the only thing uniting them together. 

One must always be conscious of where it is the elements they are talking about living: the domain or the codomain. $f$ only knows how to send things out of the domain, and it promises to only return things in the codomain. 






\end{document}