--- a/handouts/notation.tex Wed May 31 09:14:39 2017 +0100
+++ b/handouts/notation.tex Mon Jun 19 10:44:28 2017 +0100
@@ -69,9 +69,9 @@
\defn{Strings} are lists of characters. Unfortunately, there
are many ways how we can write down strings. In programming
-languages, they are usually written as \dq{$hello$} where the
+languages, they are usually written as \dq{\texttt{hello}} where the
double quotes indicate that we are dealing with a string. In
-programming languages, such as Scala, strings have a special
+typed programming languages, such as Scala, strings have a special
type---namely \pcode{String} which is different from the type
for lists of chatacters. This is because strings can be
efficiently represented in memory, unlike general lists. Since
@@ -114,12 +114,10 @@
write \textit{foo}, \textit{bar}, \textit{foobar} or
\textit{foo $@$ bar}.
-Occasionally we will use the notation $a^n$ for strings, which
-stands for the string of $n$ repeated $a$s. So $a^{n}b^{n}$ is
-a string that has as many $a$s by as many $b$s.
-
-A simple property of string concatenation is
-\emph{associativity}, meaning
+Occasionally we will use the notation $a^n$ for strings, which stands
+for the string of $n$ repeated $a$s. So $a^{n}b^{n}$ is a string that
+has as many $a$s by as many $b$s. A simple property of string
+concatenation is \emph{associativity}, meaning
\[(s_1 @ s_2) @ s_3 = s_1 @ (s_2 @ s_3)\]
@@ -141,15 +139,19 @@
\{1, 2, 3\}
\]
-\noindent The notation $\in$ means \emph{element of}, so $1
-\in \{1, 2, 3\}$ is true and $4 \in \{1, 2, 3\}$ is false.
-Sets can potentially have infinitely many elements. For
-example the set of all natural numbers $\{0, 1, 2, \ldots\}$
-is infinite. This set is often also abbreviated as
-$\mathbb{N}$. We can define sets by giving all elements, for
-example $\{0, 1\}$ for the set containing just $0$ and $1$,
-but also by \defn{set comprehensions}. For example the set of
-all even natural numbers can be defined as
+\noindent The notation $\in$ means \emph{element of}, so $1 \in \{1,
+2, 3\}$ is true and $4 \in \{1, 2, 3\}$ is false. Not that the
+\emph{list} $[1, 2, 3]$ is something different from the \emph{set}
+$\{1, 2, 3\}$: in the former we care about the order and potentially
+several occurrences of a number; while with the latter we do not.
+Also sets can potentially have infinitely many elements. For example
+the set of all natural numbers $\{0, 1, 2, \ldots\}$ is infinite. This
+set is often also abbreviated as $\mathbb{N}$. Lists can be very large, but they cannot contain infinitely many elements.
+
+We can define sets by giving all elements, for example $\{0, 1\}$ for
+the set containing just $0$ and $1$, but also by \defn{set
+ comprehensions}. For example the set of all even natural numbers can
+be defined as
\[
\{n\;|\;n\in\mathbb{N} \wedge n\;\text{is even}\}
@@ -162,8 +164,9 @@
\{n\;|\; n^2 < 9 \wedge n \in \mathbb{N}\}
\]
-\noindent Notice that set comprehensions could be used
-to define set union, intersection and difference:
+\noindent Can you see why this defines the set $\{0, 1, 2\}$? Notice
+that set comprehensions could be used to define set union,
+intersection and difference:
\begin{eqnarray*}
A \cup B & \dn & \{x\;|\; x \in A \vee x \in B\}\\
@@ -200,13 +203,28 @@
\noindent but using the big union notation is more concise.
-While this stuff about sete might all look trivial or even
-needlessly pedantic, \emph{Nature} is never simple. If you
-want to be amazed how complicated sets can get, watch out for
-the last lecture just before Christmas where I want you to
-convince you of the fact that some sets are more infinite than
-others. Actually that will be a fact that is very relevant to
-the material of this module.
+While this stuff about sets might all look trivial or even needlessly
+pedantic, \emph{Nature} is never simple. If you want to be amazed how
+complicated sets can get, watch out for the last lecture just before
+Christmas where I want to convince you of the fact that some sets are
+more infinite than others. Yes, you read correctly, there can be sets
+that are ``more infinite'' then others. If you think this is obvious:
+say you have the infinite set $\{1, 2, 3, 4, \ldots\}$ which is all
+the natural numbers except $0$, and then compare it to the set
+$\{0, 1, 2, 3, 4, \ldots\}$ which contains the $0$. Yes, the second must be more infinite\ldots{} well, then think again. Because the two
+infinite sets
+
+\begin{center}
+ $\{1, 2, 3, 4, \ldots\}$ and
+ $\{0, 1, 2, 3, 4, \ldots\}$
+\end{center}
+
+\noindent
+contain actually the same number of elements. Does this make sense?
+Though this might all look strange this about infinite sets will be a
+topic that is very relevant to the material of this module. It tells
+us what we can compute with a computer (actually algorithm) and what
+we cannot.
Another important notion in this module are \defn{languages}, which
are sets of strings. One of the main goals for us will be how to