| Term | Notation Example(s) | We say in English … |
|---|---|---|
| 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\) |
| 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}\) or \(\mathbb{Z}^{\geq 0}\) | The (set of all) natural numbers. Note: we use the convention that \(0\) is a natural number. |
| piecewise rule definition | \(f(x) = \begin{cases} x & \text{if~}x \geq 0 \\ -x & \text{if~}x<0\end{cases}\) | Define \(f\) of \(x\) to be \(x\) when \(x\) is nonnegative and to be \(-x\) when \(x\) is negative |
| function application | \(f(7)\) | \(f\) of \(7\) or \(f\) applied to \(7\) or the image of \(7\) under \(f\) |
| \(f(z)\) | \(f\) of \(z\) or \(f\) applied to \(z\) or the image of \(z\) under \(f\) | |
| \(f(g(z))\) | \(f\) of \(g\) of \(z\) 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\) |
Mathematical object and data types
A mathematical object is any abstract object arising in mathematics.
What are some examples of mathematical objects?
Computers encode mathematical objects into data types. What are some examples of data types?
| Term | Examples: |
| (add additional examples from class) | |
| set unordered collection of elements | \(7 \in \{43, 7, 9 \}\) \(2 \notin \{43, 7, 9 \}\) |
| repetition doesn’t matter | |
| Equal sets agree on membership of all elements | |
| \(n\)-tuple (also called an \(n\)-dimensional vector) ordered sequence of entries with \(n\) “slots" (\(n >0\)) | |
| repetition matters, fixed length | |
| Equal \(n\)-tuples have corresponding entries equal | |
| string ordered finite sequence of elements each from specified set | |
| repetition matters, arbitrary finite length | |
| Equal strings have same length and corresponding characters equal |
Special cases:
When \(n=2\), the 2-tuple is called an ordered pair.
A string of length \(0\) is called the empty string and is denoted \(\lambda\).
A set with no elements is called the empty set and is denoted \(\{\}\) or \(\emptyset\).
A set is an unordered collection of elements.
Recall that the empty set (denoted \(\emptyset\) or \(\{~\}\)) is the set without any elements.
To define sets:
To define a set using roster method, explicitly list its elements using curly braces. That is, start with \(\{\) then list elements of the set separated by commas and close with \(\}\).
To define a set using set builder definition, either form “The set of all \(x\) from the universe \(U\) such that \(x\) is ..." by writing \[\{x \in U \mid ...x... \}\] or form “the collection of all outputs of some operation when the input ranges over the universe \(U\)" by writing \[\{ ...x... \mid x\in U \}\]
We use the symbol \(\in\) as “is an
element of” to indicate membership in a set.
Example sets: For each of the following, identify whether it’s defined using the roster method or set builder notation and give an example element.
\(\{ -1, 1\}\)
\(\{0, 0 \}\)
\(\{-1, 0, 1 \}\)
\(\{(x,x,x) \mid x \in \{-1,0,1\}
\}\)
\(\{ \}\)
\(\{ x \in \mathbb{Z} \mid x \geq 0
\}\)
\(\{ x \in \mathbb{Z} \mid x > 0
\}\)
\(\{\texttt{A},\texttt{C},\texttt{U},\texttt{G}\}\)
\(\{\texttt{A}\texttt{U}\texttt{G}, \texttt{U}\texttt{A}\texttt{G}, \texttt{U}\texttt{G}\texttt{A}, \texttt{U}\texttt{A}\texttt{A}\}\)
An \(n\)-tuple is a sequences of \(n\) entries.
To define \(n\)-tuples
To define \(n\)-tuples, list the entries separated by commas and enclosed by parentheses.
Example \(n\)-tuples: For each of the following \(n\)-tuple, come up with where it might come from. For example, \((88, 79, 100, 90, 68, 81,90)\) may be the grades a particular student will get for homeworks 1-7.
\((1,2.22, -0.8)\)
\((-1,-1,0,1,0,-1,0,0)\)
\((CSE20, CSE21, CSE101,
CSE105)\)
\((MILES,JONES,A000000,MUIR,91.86,A-)\)
A string over a finite alphabet is a finite sequence of characters or symbols.
Recall that the empty string, (usually denoted \(\lambda\)) is the string without any characters.
The characters you are allowed to use come from a finite set called an alphabet.
To define strings:
Usually, a string is given as a list of characters without any punctuation. In some cases, we will use the symbol “\(\circ\)" as a delimiter. For example, if the alphabet is \(\{\texttt{A},\texttt{C},\texttt{U},\texttt{G}\}\), then consider the string \(\texttt{A}\texttt{A}\texttt{A}\texttt{U}\texttt{A}\). It could also be written as \(\texttt{A}\circ\texttt{A}\circ\texttt{A}\circ\texttt{U}\circ\texttt{A}\).
string concatenation
String concatenation of strings \(x\) and \(y\), denoted \(xy\) or \(x\circ y\) is the result of “gluing together" the strings \(x\) first then \(y\). For example: \(\texttt{A}\texttt{U}\texttt{A}\texttt{A}\circ \texttt{G}\texttt{G}\texttt{C}=\texttt{A}\texttt{U}\texttt{A}\texttt{A}\texttt{G}\texttt{G}\texttt{C}\).
Pro-tip: the meaning of writing one element next to another like \(xy\) depends on the data-types of \(x\) and \(y\). When \(x\) and \(y\) are strings, the convention is that \(xy\) is the result of string concatenation. When \(x\) and \(y\) are numbers, the convention is that \(xy\) is the result of multiplication. This is (one of the many reasons) why is it very important to declare the data-type of variables before we use them.
Example strings: For each example, come up with an appropriate alphabet:
\(MATHEMATICS\)
\(A00000000\)
\(2598960\)
\(\texttt{C}\texttt{C}\texttt{A}\texttt{C}\texttt{U}\texttt{G}\texttt{C}\texttt{C}\texttt{A}\)
\(\lambda\)
\(9500~Gilman~Dr.\)
\(11100010101101000111111011111\)
\(mej016@eng.ucsd.edu\)
\(F96A4B0B\)
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 =
\{\texttt{A}, \texttt{C}, \texttt{U}, \texttt{G}\}\).
Formally, to define the set of all RNA strands, we need more than roster method or set builder descriptions.
New! Recursive Definitions of Sets: The set \(S\) (pick a name) is defined by: \[\begin{array}{ll} \textrm{Basis Step: } & \textrm{Specify finitely many elements of } S\\ \textrm{Recursive Step: } & \textrm{Give rule(s) for creating a new element of } S \textrm{ from known values existing in } S, \\ & \textrm{and potentially other values}. \\ \end{array}\] The set \(S\) then consists of all and only elements that are put in \(S\) by finitely many (a nonnegative integer number) of applications of the recursive step after the basis step.
Definition The set of nonnegative integers \(\mathbb{N}\) is defined (recursively) by: \[\begin{array}{ll} \textrm{Basis Step: } & \phantom{0 \in \mathbb{N}} \\ \textrm{Recursive Step: } & \phantom{\textrm{If } n \in \mathbb{N} \textrm{, then } n+1 \in \mathbb{N}} \end{array}\]
Examples:
Definition The set of all integers \(\mathbb{Z}\) is defined (recursively) by: \[\begin{array}{ll} \textrm{Basis Step: } & \phantom{0 \in \mathbb{Z}} \\ \textrm{Recursive Step: } & \phantom{\textrm{If } x \in \mathbb{Z} \textrm{, then } x+1 \in \mathbb{Z} \textrm{ and } x-1 \in \mathbb{Z}} \end{array}\]
Examples:
Definition The set of RNA strands \(S\) is defined (recursively) by: \[\begin{array}{ll} \textrm{Basis Step: } & \texttt{A}\in S, \texttt{C}\in S, \texttt{U}\in S, \texttt{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.
Examples:
Definition The set of bitstrings (strings of 0s and 1s) is defined (recursively) by: \[\begin{array}{ll} \textrm{Basis Step: } & \phantom{\lambda \in X} \\ \textrm{Recursive Step: } & \phantom{\textrm{If } s \in X \textrm{, then } s0 \in X \text{ and } s1 \in X} \end{array}\]
Notation: We call the set of bitstrings \(\{0,1\}^*\).
Examples:
Pro-tip: the meaning of writing one element next to another like \(xy\) depends on the data-types of \(x\) and \(y\). When \(x\) and \(y\) are strings, the convention is that \(xy\) is the result of string concatenation. When \(x\) and \(y\) are numbers, the convention is that \(xy\) is the result of multiplication. This is (one of the many reasons) why is it very important to declare the data-type of variables before we use them.
Fill in the missing entries in the table:
| Set | Example elements in this set: |
|---|---|
| \(B\) | ACGU |
| \((\texttt{A}, \texttt{C})\) \((\texttt{U}, \texttt{U})\) | |
| \(B \times \{-1,0,1\}\) | |
| \(\{-1,0,1\} \times B\) | |
| \((0,0,0)\) | |
| \(\{\texttt{A}, \texttt{C}, \texttt{G}, \texttt{U}\} \circ \{\texttt{A}, \texttt{C}, \texttt{G}, \texttt{U}\}\) | |
| \(\texttt{G}\texttt{G}\texttt{G}\texttt{G}\) | |
Example: The absolute value function
Domain
Codomain
Rule
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)\), \(P_2 = (1, 1, -1)\), \(P_3 = (1, 1, 1)\), \(P_4 = (0,-1,1)\)
Which of \(P_1\), \(P_2\), \(P_3\) has movie preferences most similar to \(P_4\)?
One approach to answer this question: use functions to define distance between user preferences.
For example, consider the function \(d_0: \phantom{the Cartesian product of the set of ratings on 3 movies with itself} \to \phantom{\mathbb{R}}\) given by \[d_0 (~(~ (x_1, x_2, x_3), (y_1, y_2, y_3) ~) ~) = \sqrt{ (x_1 - y_1)^2 + (x_2 - y_2)^2 + (x_3 -y_3)^2}\]
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 and \(P_2\) gives . Should this movie be recommended to \(P_3\)? Why or why not?
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.
When the domain of a function is a 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: } & \texttt{A}\in S, \texttt{C}\in S, \texttt{U}\in S, \texttt{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.
Definition (Of a function, recursively) A function 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 rnalen is
The codomain of rnalen is
Example function application: \[rnalen(\texttt{A}\texttt{C}\texttt{U}) =
\phantom{1+ rnalen(\texttt{A}\texttt{C}) = 1 + (1 + rnalen(\texttt{A}) )
= 1 + ( 1 + 1) = 3}\]
Extra example: A function 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}\]
\(basecount(~(\texttt{A}\texttt{C}\texttt{U},\texttt{A})~)
= basecount( ~(\texttt{A}\texttt{C}, \texttt{A})~) =
basecount(~(\texttt{A}, \texttt{A})~) = 1\)
\(basecount(~(\texttt{A}\texttt{C}\texttt{U},\texttt{G})~)
= basecount( ~(\texttt{A}\texttt{C}, \texttt{G})~) =
basecount(~(\texttt{A}, \texttt{G})~) = 0\)
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.