--- a/handouts/notation.tex Sat May 05 10:31:00 2018 +0100
+++ b/handouts/notation.tex Fri Jun 01 15:28:37 2018 +0100
@@ -5,7 +5,7 @@
\begin{document}
-\fnote{\copyright{} Christian Urban, King's College London, 2014, 2015, 2016, 2017}
+\fnote{\copyright{} Christian Urban, King's College London, 2014, 2015, 2016, 2017, 2018}
\section*{A Crash-Course on Notation}
@@ -89,8 +89,8 @@
\noindent
However, we do not want to do this kind of explicit coercion in our
pencil-and-paper, everyday arguments. So in our (mathematical)
-definitions we regard strings as lists of characters, we will also
-write \dq{$hello$} as
+definitions we regard strings as lists of characters and we will also
+write \dq{$hello$} as list
\[
[\text{\it h, e, l, l, o}] \qquad\text{or simply}\qquad \textit{hello}
@@ -114,7 +114,7 @@
\dq{\textit{foo}} $@$ \dq{\textit{bar}}, gives
\dq{\textit{foobar}}. But as said above, we will often
simplify our life and just drop the double quotes whenever it
-is clear we are talking about strings, So we will often just
+is clear we are talking about strings. So we will often just
write \textit{foo}, \textit{bar}, \textit{foobar} or
\textit{foo $@$ bar}.
@@ -153,25 +153,29 @@
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
+We can define sets by giving all their elements, for example $\{0, 1\}$ for
+the set containing just $0$ and $1$. But often we need to use \defn{set
+ comprehensions} to define sets. For example the set of all \emph{even}
+natural numbers can be defined as
\[
\{n\;|\;n\in\mathbb{N} \wedge n\;\text{is even}\}
\]
-\noindent Though silly, but the set $\{0, 1, 2\}$ could also be
+\noindent Set comprehensions consist of a ``base set'' (in this case
+all the natural numbers) and a predicate (here eveness).
+
+Though silly, but the set $\{0, 1, 2\}$ could also be
defined by the following set comprehension
\[
-\{n\;|\; n^2 < 9 \wedge n \in \mathbb{N}\}
+\{n\;|\; n \in \mathbb{N} \wedge n^2 < 9\}
\]
\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:
+that set comprehensions are quite powerful constructions. For example they
+could be used to define set union,
+set intersection and set difference:
\begin{eqnarray*}
A \cup B & \dn & \{x\;|\; x \in A \vee x \in B\}\\
@@ -208,17 +212,18 @@
\noindent but using the big union notation is more concise.
-As an aside: 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 $\mathbb{N}\backslash\{0\} = \{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$. If you think,
-the second must be more infinite\ldots{} well, then think again. Because the two
-infinite sets
+As an aside: 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 other sets. Yes, you read
+correctly, there can be sets that are ``more infinite'' than
+others. If you think this is obvious: say you have the infinite set
+$\mathbb{N}\backslash\{0\} = \{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$ and all other
+numbers. If you think, the second must be more infinite\ldots{} well,
+then think again. Because the two infinite sets
\begin{center}
$\{1, 2, 3, 4, \ldots\}$ and
@@ -226,12 +231,12 @@
\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
+contain actually the same amount of elements. Does this make sense?
+Though this might all look strange, 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. But during the first 9 lectures we can go by without this
-``weird'' stuff.
+``weird'' stuff. End of aside.\smallskip
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
@@ -302,7 +307,7 @@
\end{equation}
\noindent This star operation is often also called
-\emph{Kleene-star}. Unfolding the definition in \eqref{star}
+\emph{Kleene-star}. Unfolding the definition in~\eqref{star}
gives
\[