\documentclass[12pt, oneside]{article}

\usepackage[letterpaper, scale=0.89, centering]{geometry}
\usepackage{fancyhdr}
\setlength{\parindent}{0em}
\setlength{\parskip}{1em}

\pagestyle{fancy}
\fancyhf{}
\renewcommand{\headrulewidth}{0pt}
\rfoot{\href{https://creativecommons.org/licenses/by-nc-sa/2.0/}{CC BY-NC-SA 2.0} Version \today~(\thepage)}

\usepackage{amssymb,amsmath,pifont,amsfonts,comment,enumerate,enumitem}
\usepackage{currfile,xstring,hyperref,tabularx,graphicx,wasysym}
\usepackage[labelformat=empty]{caption}
\usepackage{xcolor}
\usepackage{multicol,multirow,array,listings,tabularx,lastpage,textcomp,booktabs}

\lstnewenvironment{algorithm}[1][] {   
    \lstset{ mathescape=true,
        frame=tB,
        numbers=left, 
        numberstyle=\tiny,
        basicstyle=\rmfamily\scriptsize, 
        keywordstyle=\color{black}\bfseries,
        keywords={,procedure, div, for, to, input, output, return, datatype, function, in, if, else, foreach, while, begin, end, }
        numbers=left,
        xleftmargin=.04\textwidth,
        #1
    }
}
{}
\lstnewenvironment{java}[1][]
{   
    \lstset{
        language=java,
        mathescape=true,
        frame=tB,
        numbers=left, 
        numberstyle=\tiny,
        basicstyle=\ttfamily\scriptsize, 
        keywordstyle=\color{black}\bfseries,
        keywords={, int, double, for, return, if, else, while, }
        numbers=left,
        xleftmargin=.04\textwidth,
        #1
    }
}
{}

\newcommand\abs[1]{\lvert~#1~\rvert}
\newcommand{\st}{\mid}

\newcommand{\A}[0]{\texttt{A}}
\newcommand{\C}[0]{\texttt{C}}
\newcommand{\G}[0]{\texttt{G}}
\newcommand{\U}[0]{\texttt{U}}

\newcommand{\cmark}{\ding{51}}
\newcommand{\xmark}{\ding{55}}

 
\begin{document}
\begin{flushright}
    \StrBefore{\currfilename}{.}
\end{flushright} \section*{Well defined functions}


Recall that a function is defined by its (1) domain, (2) codomain, and (3) rule assigning each 
element in the domain exactly one element in the codomain. 
The domain and codomain are nonempty sets.
The rule can be depicted as a table, formula, English description, etc.

A function can {\it fail to be well-defined} if there is some 
domain element where the function rule doesn't give a
unique codomain element. For example, the function rule might lead to 
more than one potential image, or to an image outside of the codomain.


{\it Example}: $f_A: \mathbb{R}^+ \to \mathbb{Q}$ with $f_A(x) = x$ is {\bf not} a well-defined function because

\vspace{100pt}


{\it Example}: $f_B: \mathbb{Q} \to \mathbb{Z}$ with $f_B\left(\frac{p}{q}\right) = p+q$ is {\bf not} a well-defined function because

\vspace{100pt}


{\it Example}: $f_C: \mathbb{Z} \to \mathbb{R}$ with $f_C(x) = \frac{x}{|x|}$ is {\bf not} a well-defined function because

\vspace{100pt}
 \vfill
\section*{Injective function definition}


{\bf Definition} : A function $f: D  \to C$ is {\bf one-to-one} (or  injective) 
means for every $a,b$ in the domain $D$, 
if $f(a) = f(b)$ then  $a=b$.

Formally, $f: D  \to  C$ is  one-to-one  means $\underline{\phantom{\forall a \in D \forall b \in D ~(f(a) = f(b) \to a = b)}}$.
 \vfill
\section*{Injective functions visually}


Informally, a function being one-to-one means ``no duplicate images''.

\phantom{Draw finite domain, finite codomain picture with duplicate image.}
\vspace{50pt} \vfill
\section*{Surjective function definition}


{\bf Definition}: A function $f: D  \to C$ is {\bf onto} (or  surjective) means for every $b$ in the codomain, 
there  is an element $a$ in the domain with  $f(a) = b$.

Formally, $f: D  \to  C$ is  onto  means $\underline{\phantom{\forall b \in C  \exists a \in D ( f(a) = b)}}$.
 \vfill
\section*{Surjective functions visually}


Informally, a function being onto means ``every potential image is an actual image''.

\phantom{Draw finite domain, finite codomain picture with duplicate image.}
\vspace{50pt} \vfill
\section*{Bijection definition}


{\bf Definition} : A function $f: D  \to C$ is a {\bf bijection} means that it is both 
one-to-one  and onto. The {\bf inverse} of a  bijection $f: D  \to  C$ is 
the function $g: C  \to  D$  such that $g(b) = a$ iff  $f(a) =  b$.
 \vfill
\section*{Predicate definition}


{\bf  Definition}: A  {\bf predicate}  is  a function from a given set (domain) to $\{T,F\}$.

A predicate can be applied, or {\bf evaluated} at, an element of the domain.

Usually, a predicate {\it describes a  property} that domain elements may or may not have.

Two predicates over the same domain are {\bf equivalent} means they evaluate to
the same truth values for all possible assignments of domain elements to the
input. In other words, they are equivalent means that they are equal as functions.

To define a predicate, we must specify its domain and its value at each domain element.
The rule assigning truth values to domain elements can be specified using a formula, 
English description, in a table (if the domain is finite), or recursively (if the domain is recursively
defined).

Note: Since logical operations are functions, they can be part of the definitions of predicates. \vfill
\section*{Predicate truth set definition}


{\bf Definition}: The {\bf truth  set} of a  predicate is the collection of all elements in its
domain where the predicate evaluates to $T$.

Notice that specifying the domain and the truth set is sufficient for defining
a predicate. \vfill
\section*{Predicate truth set example}


The truth set for the predicate $V(x)$ is $\underline{\phantom{\{ x ~\mid~ V(x) = T\} = \{ 001, 010, 011 \}}}$.

The truth set for the predicate $N(x)$ is $\underline{\phantom{\{ x ~\mid~ N(x) = T\} = \{ 101, 111 \}}}$.

The truth set for the predicate $Mystery(x)$ is $\underline{\phantom{\{ x ~\mid~ Mystery(x) = T\} = \{ 000, 001, 010, 101, 111 \}}}$.


\vfill \vfill
\section*{Defining functions more examples}


Let's practice with functions related to some of our applications so far.

Recall: We model the collection of user ratings of the four movies Superman, Wicked, KPop Demon Hunters, A Minecraft Movie as the set
$\{-1,0,1\}^4$ . One function that compares pairs of ratings is
$$d_0: \{-1,0,1\}^4 \times \{-1,0,1\}^4 \to \mathbb{R}$$
given by
\[
d_0 (~(~ (x_1, x_2, x_3, x_4), (y_1, y_2, y_3, y_4) ~) ~) = \sqrt{ (x_1 - y_1)^2 + (x_2 - y_2)^2 + (x_3 -y_3)^2 + (x_4 -y_4)^2}
\]

Notice: any ordered pair of ratings is an okay input to $d_0$.

Notice: there are (at most) 
\[
(3 \cdot 3 \cdot 3 \cdot 3)\cdot (3 \cdot 3 \cdot 3 \cdot 3) = 3^8 = 6561
\]
many pairs of ratings. There are therefore lots and lots of real numbers that are not the output of $d_0$.

\vfill

Recall: RNA is made up of strands of four different bases that encode genomic information
in specific ways.\\
The bases are elements of the set 
$B  = \{\A, \C, \U, \G \}$. The set of RNA strands $S$ is defined (recursively) by:
\[
\begin{array}{ll}
\textrm{Basis Step: } & \A \in S, \C \in S, \U \in S, \G \in S \\
\textrm{Recursive Step: } & \textrm{If } s \in S\textrm{ and }b \in B \textrm{, then }sb \in S
\end{array}
\]
where $sb$ is string concatenation.

\vfill

{\bf Pro-tip}: informal definitions sometime use $\cdots$ to indicate ``continue the pattern''. Often, 
to make this pattern precise we use recursive definitions.
\newpage
\begin{center}
\begin{tabular}{p{0.65in}ccp{2.4in}p{2.4in}}
{\scriptsize {\bf Name}} & {\scriptsize {\bf  Domain}} & {\scriptsize {\bf Codomain}} & {\scriptsize {\bf Rule}} &{\scriptsize {\bf Example}}\\
\hline 
$rnalen$ & $S$ & $\mathbb{Z}^+$ & 
    {\begin{align*}    
    &\textrm{Basis Step:} \\
    &\textrm{If } b \in B\textrm{ then } \textit{rnalen}(b) = 1 \\
    &\textrm{Recursive Step:}\\
    &\textrm{If } s \in S\textrm{ and } b \in B\textrm{, then  }\\
    &\textit{rnalen}(sb) = 1 + \textit{rnalen}(s)
    \end{align*}} & 
    {\begin{align*}
        rnalen(\A\C) &\overset{\text{rec step}}{=} 1 +rnalen(\A) \\ 
        &\overset{\text{basis step}}{=} 1 + 1 = 2
    \end{align*}}\\
\hline
$basecount$ & $S \times B$ & $\mathbb{N}$ & 
{\begin{align*}    
    &\textrm{Basis Step:} \\
    &\textrm{If } b_1 \in B, b_2 \in B \textrm{ then} \\
    &basecount(~(b_1, b_2)~) = \\
    &\begin{cases}
        1 & \textrm{when } b_1 = b_2 \\
        0 & \textrm{when } b_1 \neq b_2 \\
    \end{cases}\\
    &\textrm{Recursive Step:}\\
    &\textrm{If } s \in S, b_1 \in B, b_2 \in B\\
    &basecount(~(sb_1, b_2)~) = \\
    &\begin{cases}
        1 + \textit{basecount}(~(s, b_2)~) & \textrm{when } b_1 = b_2 \\
        \textit{basecount}(~(s, b_2)~) & \textrm{when } b_1 \neq b_2 \\
    \end{cases}
    \end{align*}} & 
    {\begin{align*}
        basecount(~(\A\C\U, \C)~) = 
    \end{align*}}\\
\hline
``$2$ to the power of''& $\mathbb{N}$ & $\mathbb{N}$ & 
{\begin{align*}    
&\textrm{Basis Step:} \\
&2^0= 1 \\
&\textrm{Recursive Step:}\\
&\textrm{If } n \in \mathbb{N}, 2^{n+1} = \phantom{2 \cdot 2^n}
\end{align*}}\\
\hline
``$b$ to the power of $i$''& $\mathbb{Z}^+ \times \mathbb{N}$ & $\mathbb{N}$ & 
{\begin{align*}    
&\textrm{Basis Step:} \\
&b^0 = 1 \\
&\textrm{Recursive Step:}\\
&\textrm{If } i \in \mathbb{N}, b^{i+1} = b \cdot b^i
\end{align*}}
\end{tabular}
\end{center}

\fbox{\parbox{\textwidth}{
    $2^0 = 1$~~\hfill $2^1=2$~~\hfill $2^2=4$~~\hfill $2^3=8$~~
    \hfill $2^4=16$~~\hfill $2^5=32$~~
    \hfill $2^6=64$~~\hfill $2^7=128$~~
    \hfill $2^8=256$~~\hfill $2^9=512$~~
    \hfill $2^{10}=1024$}}
\newpage \vfill
\section*{Definitions set prereqs}


\begin{center}
\begin{tabular}{|llp{9.8cm}|}
\hline
{\bf Term} & {\bf Notation Example(s)} & {\bf We say in English \ldots } \\
\hline
all reals & $\mathbb{R}$ & The (set of all) real numbers (numbers on the number line)\\
all integers & $\mathbb{Z}$ & The (set of all) integers (whole numbers including negatives, zero, and positives) \\
all positive integers & $\mathbb{Z}^+$ & The (set of all) strictly positive integers \\
all natural numbers & $\mathbb{N}$ & The (set of all) natural numbers (nonnegative integers). {\it We use the convention that $0$ is a natural number.} \\


\hline
\end{tabular}
\end{center} \vfill
\section*{Definitions functions prereqs}


\begin{center}
\begin{tabular}{|p{1.2in}p{2.8in}p{3in}|}
\hline
{\bf Term} & {\bf Notation Example(s)} & {\bf We say in English \ldots } \\
\hline
sequence & $x_1, \ldots, x_n$ & A sequence $x_1$ to $x_n$ \\
summation & $\sum_{i=1}^n x_i$ or $\displaystyle{\sum_{i=1}^n x_i}$ & The sum of the terms of the sequence $x_1$ to $x_n$ \\
&&\\
&&\\
piecewise rule definition & $f(x) = \begin{cases} \text{rule 1 for } x & \text{when~COND 1} \\ \text{rule 2 for } x & \text{when COND 2}\end{cases}$ &
Define $f$ of $x$ to be the result of applying rule 1 to $x$ when condition COND 1 is true and the result of 
applying rule 2 to $x$ when condition COND 2 is true. This can be generalized to having more than two conditions
(or cases).\\
&&\\
function application & $f(7)$ & $f$ of $7$ {\bf or} $f$ applied to $7$ {\bf or} the image of $7$ under $f$\\
                     & $f(z)$ & $f$ of $z$ {\bf or} $f$ applied to $z$ {\bf or} the image of $z$ under $f$\\
                     & $f(g(z))$ & $f$ of $g$ of $z$ {\bf or} $f$ applied to the result of $g$ applied to $z$ \\
&&\\
absolute value & $\lvert -3 \rvert$ & The absolute value of $-3$ \\
square root & $\sqrt{9}$ & The non-negative square root of $9$ \\


\hline
\end{tabular}
\end{center}

{\bf Pro-tip}: the meaning of two vertical lines $| ~~~ |$ depends on the data-types of what's between the lines.
For example, when placed around a number, the two vertical lines represent absolute value.
We've seen a single vertial line $|$ used as part of set builder definitions to represent ``such that''.
Again, this is 
(one of the many reasons) why is it very important to declare the data-type of variables before we use them.
 \vfill
\section*{Defining functions}


\fbox{\parbox{\textwidth}{{\bf New! Defining functions} A function is defined by its (1) domain, 
(2) codomain, and (3) rule assigning each 
element in the domain exactly one element in the codomain.\\

The domain and codomain are nonempty sets.

The rule can be depicted as a table, formula, piecewise definition, or English description.

The notation is 
\begin{center}
    ``Let the function FUNCTION-NAME: DOMAIN $\to$ CODOMAIN be given by \\
FUNCTION-NAME(x) = \ldots for every $x \in DOMAIN$''.
\end{center}

or 
\begin{center}
    ``Consider the function FUNCTION-NAME: DOMAIN $\to$ CODOMAIN defined as  \\
FUNCTION-NAME(x) = \ldots for every $x \in DOMAIN$''.
\end{center}
}}

\vfill
\newpage

Example: The absolute value function 

{\bf Domain}

{\bf Codomain}

{\bf Rule}

\vfill 
 \vfill
\section*{Defining functions ratings}


Recall our representation of Netflix users' ratings of movies as $n$-tuples, where
$n$ is the number of movies in the database. 
Each component of the $n$-tuple is $-1$ (didn't like the movie), $0$ 
(neutral rating or didn't watch the movie), or $1$ (liked the movie).

Consider the ratings $P_1 = (-1, 0, 1, 0)$, $P_2 = (1, 1, -1, 0)$, $P_3 = (1, 1, 1, 0)$,
$P_4 = (0,-1,1, 0)$


Which of $P_1$, $P_2$, $P_3$ has movie preferences most similar to $P_4$?

One approach to answer this question: use {\bf functions} to quantify difference among user preferences.

For example, consider the function 
$d_0: \{-1,0,1\}^4 \times \{-1,0,1\}^4 \to \mathbb{R}$
given by
\[
d_0 (~(~ (x_1, x_2, x_3, x_4), (y_1, y_2, y_3, y_4) ~) ~) = \sqrt{ (x_1 - y_1)^2 + (x_2 - y_2)^2 + (x_3 -y_3)^2 + (x_4 -y_4)^2}
\]


\vfill
\vfill

\begin{comment}
    

{\it Extra example:} A new movie is released, and $P_1$ and $P_2$ watch it before $P_3$, and give it
ratings; $P_1$ gives \cmark~and $P_2$ gives \xmark.
Should this movie be recommended to $P_3$? Why or why not?

{\it Extra example:} Define a new function that could be used to compare the $4$-tuples of ratings encoding
movie preferences now that there are four movies in the database.

\vfill
\end{comment}
\newpage \vfill
\section*{Defining functions recursively}


When the domain of a function is a {\it recursively defined set}, the rule assigning 
images to domain elements (outputs) can also be defined recursively.

Recall: The set of RNA strands $S$ is defined (recursively) by:
\[
\begin{array}{ll}
\textrm{Basis Step: } & \A \in S, \C \in S, \U \in S, \G \in S \\
\textrm{Recursive Step: } & \textrm{If } s \in S\textrm{ and }b \in B \textrm{, then }sb \in S
\end{array}
\]
where $sb$ is string concatenation.

{\bf Definition} (Of a function, recursively) A function \textit{rnalen} that computes the length of RNA strands in $S$ is defined by:
\[
\begin{array}{llll}
& & \textit{rnalen} : S & \to \mathbb{Z}^+ \\
\textrm{Basis Step:} & \textrm{If } b \in B\textrm{ then } & \textit{rnalen}(b) & = 1 \\
\textrm{Recursive Step:} & \textrm{If } s \in S\textrm{ and }b \in B\textrm{, then  } & \textit{rnalen}(sb) & = 1 + \textit{rnalen}(s)
\end{array}
\]

The domain of \textit{rnalen} is \phantom{$S$}\\

The codomain of \textit{rnalen} is \phantom{$\mathbb{Z}^+$}\\

Example function application:
\[
rnalen(\A\C\U) = \phantom{1+ rnalen(\A\C) = 1 + (1 + rnalen(\A) ) = 1 + ( 1 + 1) = 3}
\]

\vfill

{\it Example}: A function \textit{basecount} that computes the number of a given base 
$b$ appearing in a RNA strand $s$ is defined recursively:
    
\[
\begin{array}{llll}
& & \textit{basecount} : S \times B & \to \mathbb{N} \\
\textrm{Basis Step:} &  \textrm{If } b_1 \in B, b_2 \in B & \textit{basecount}(~(b_1, b_2)~) & =
        \begin{cases}
            1 & \textrm{when } b_1 = b_2 \\
            0 & \textrm{when } b_1 \neq b_2 \\
        \end{cases} \\
\textrm{Recursive Step:} & \textrm{If } s \in S, b_1 \in B, b_2 \in B &\textit{basecount}(~(s b_1, b_2)~) & =
        \begin{cases}
            1 + \textit{basecount}(~(s, b_2)~) & \textrm{when } b_1 = b_2 \\
            \textit{basecount}(~(s, b_2)~) & \textrm{when } b_1 \neq b_2 \\
        \end{cases}
\end{array}
\]

\begin{comment}
$basecount(~(\A\C\U,\A)~) = basecount( ~(\A\C, \A)~) = basecount(~(\A, \A)~) = 1$\\


$basecount(~(\A\C\U,\G)~) = basecount( ~(\A\C, \G)~) = basecount(~(\A, \G)~) = 0$\\


\vfill
{\it Extra example}: The function which outputs $2^n$ when given a nonnegative integer $n$ can be defined recursively, 
because its domain is the set of nonnegative integers.

\vfill
\end{comment}
 \vfill
\end{document}