handouts/notation.tex
changeset 550 71fc4a7a7039
parent 505 5b9cf7fbd51a
child 736 d3e477fe6c66
--- 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
 
 \[