GStest1.org

Haskell Road; Getting Started Part 2

#

#

Getting started part 2

Monday at the library part 2

Breaktime

The von der Surwitzes pop over to the student center cafe for a break. They grab a large mineral water, a brand they knew in Germany, and Ute has packed some Vollkornbrot sandwiches of hummus and cucumber. They sit at a table and pour the water and pass around out the sandwiches.

𝔘𝔱𝔢: All right, so I emailed the professor about a couple of questions from that first chapter of The Haskell Road, and she replied saying, first, she’s happy we’re tackling the material early. And she mentioned some resources — a few texts she has on reserve at the library.
𝔘𝔴𝔢: Sort of like, I’m not going to give you the answers. I’m going to point you in the right direction. What books are they? \ [murmurs of acknowledgement] \ 𝔘𝔱𝔢: Math. Upper level college texts. Abstract algebra and number theory. \ 𝔘𝔴𝔢: I’ve heard computer science has all these higher math concepts, but then you don’t go as far as a math major does. \ [silence, eating and drinking] \ 𝔘𝔴𝔢: [continuing] I guess you’re just supposed to learn as much as you can. But like she said at the open house, a computer scientist is really an applied mathematician. \ [murmurs of agreement] \ 𝔘𝔯𝔰𝔲𝔩𝔞: And the math is the hardest part for incoming CS students, those first four semesters, ergo, that’s what we’re emphasizing it in this course. \ [nods of agreement then silence as they eat and drink] \ 𝔘𝔯𝔰𝔲𝔩𝔞: [continuing] So no hand-waving. And she doesn’t have a set amount she wants us to get through. The course is open-ended. I just find that amazing. \ [murmurs of agreement] \ 𝔘𝔴𝔢: But I’m sure we’ll need to keep moving and not be laggards about it. \ [murmurs of agreement] \ 𝔘𝔯𝔰𝔲𝔩𝔞: A whole year, the whole school year. Her sabbatical ends next summer, but I’m pretty sure I’ll want to continue. I don’t know if I want to be a computer scientist or software engineer, but learning this can’t hurt. \ 𝔘𝔱𝔢: I guess you could say Novalis is sort of an open Gynmasium. \ [soft laughter] \ 𝔘𝔴𝔢: And what happens afterward? They definitely want you to just keep going at the U. Which I wouldn’t mind at all. \ [looks about the table] \ 𝔘𝔱𝔢: Yes, and lots of people just drift into a half-and-half situation where there taking courses over at the U. \ 𝔘𝔯𝔰𝔲𝔩𝔞: Well, Father has tenure now. But I don’t know if Mutti can go on working from here. [shrugging and sighing] Anyway, I guess you two will cross that bridge before I will. \ 𝔘𝔱𝔢: [laughing] Hardly! You’re right there with us in everything we’re doing this coming year.

Divided by

• cite:&cummings2021proofs
• cite:&forman2015whole

Back at the library study room they’ve checked out the reserved books and are looking through sections of those that deal with the basic theory of division.

𝔘𝔱𝔢: [reading from the Divisibility section of /Proofs, A Long-Form Mathematical Textbook/[fn:1]] All right, so Professor Chandra wants us to understand divisibility before we go to greatest common divisor, and before we talk about primes. She said, You have to know all of the implications of “divided by” before you can advance. And like it’s saying in here, [reading] you could just say, $a$ divides $b$ if $\frac{a}{b}$ is an integer.
[Ursula and Uwe read the section from a second copy] \ 𝔘𝔱𝔢: [continuing] But we don’t want that definition, we want this definition [getting up and writing on the board]

\begin{align} ∃ \: k ∈ \mathbb{Z},\; a ≠ 0, \;\;a \mid b \;\; \text{if} \;\; b = a ⋅ k \end{align}

𝔘𝔱𝔢: [continuing] The symbol $a \mid b\:$ means $a$ divides $b$ for some $k$ where $b = a ⋅ k\;$ and $a$ is not equal to zero. [pausing] Right, all that makes sense. So basically, this turns the whole question of divisibility into finding a proper integer value for $k\:$ to multiply with . Now we have a math-formalist way of seeing divisibility.
[murmurs of approval] \ 𝔘𝔴𝔢: I like how he says good definitions don’t just fall out of the sky. \ [murmurs of agreement] \ 𝔘𝔯𝔰𝔲𝔩𝔞: Then the examples, like $2 \mid 14$ is true because $14 = 2 ⋅ 7\:$, in other words we’ve found a whole number integer, $k = 7\:$ and we’re happy. \ 𝔘𝔱𝔢: Again, we’ve turned division into an issue of true-false logic and multiplication. [writing on the board] So $7 \mid 23$ doesn’t work because we have no solution for $7k = 23\;$. \ 𝔘𝔴𝔢: And look at that last one where it’s $a \mid 0\;$. That’s true, for a non-zero $a$ since we can say $0 = a ⋅ 0$ is always true for any $a$ as long as $k = 0\;$. \ [murmurs of agreement] \ 𝔘𝔱𝔢: And like he says we’re not supposed to look at $2 \mid 14$ and just say it equals $7\;$. It’s not supposed to be seen as a calculation, it’s a logic expression that is true or false — for some value $k\:$. \ 𝔘𝔴𝔢: Right. We’re in the world of logic now, not grade school arithmetic. So everything has to be reexplained and reworked. \ [murmurs of agreement] \ 𝔘𝔱𝔢: Good, now he’s talking about the transitive property of divisibility. It is a proposition, which is a type of theorem, and that means it comes with a proof. [writing on the board] Here it is in the compact math logic form

\begin{align*} a, b, c ∈ \mathbb{Z},\;\; a \mid b \;∧\; b \mid c \implies a \mid c \end{align*}

𝔘𝔱𝔢: [continuing] And then he goes on to prove it by saying assume the if part, the $a \mid b \;∧\; b \mid c\:$ part is true, that means the then part, the $a \mid c$ part is true. So [writing]

\begin{align*} b &= a ⋅ s \[.4em] c &= b ⋅ t \end{align*}

𝔘𝔱𝔢: [continuing] for some integers $s$ and $t\;$. And now [writing]

\begin{align*} c &= b ⋅ t \[.4em] &= (a ⋅ s) ⋅ t \[.4em] &= a ⋅ (s ⋅ t) \quad\quad \ldots \; \text{associativity} \end{align*}

𝔘𝔱𝔢: [continuing] So since we have the form $c = a ⋅ (s ⋅ t)$ where we assumed $s$ and $t$ are integers, and that’s the basic form of divisibility, so yes, $a \mid c$ since we’ve shown $c = a ⋅ k$ where $k = (s ⋅ t)\:$.
𝔘𝔯𝔰𝔲𝔩𝔞: Good. Let’s switch over to this other book [she picks up a Springer Verlag book[fn:2] and pages through it] Ah, in this book there’s a section called Divisors and the Greatest Common Divisor. [paging to section, reading] Oh, here’s one, Determine whether true or false [writing on the board]

\begin{align*} 2 \mid (6n + 4) \end{align*}

𝔘𝔴𝔢: Interesting. So writing it in the divisibility way [gets up and writes on the board]

\begin{align*} (6n + 4) = 2k \end{align*}

𝔘𝔴𝔢: So before we freak out and get lost, let’s just notice that [writing]

\begin{align} 2(3n + 4) &= 2k \[.4em] 3n + 4 &= k \end{align}

𝔘𝔴𝔢: [continuing] I’d say we don’t need to go any further with this. $2 \mid (6n + 4)$ is true — which means it’s got solutions — because $2$ will go into $(6n + 4)$ for whatever $n$ wants to be.
𝔘𝔱𝔢: And this whole formal divisibility thing helps because if you just saw this one day [writing on the board]

\begin{align} \frac{(6n + 4)}{2} = 3n + 2 \end{align}

𝔘𝔱𝔢: [continuing] you’ve now got a second way to see the idea that the equation is true for any $n$, that it’s dependent on $n\;$.
𝔘𝔯𝔰𝔲𝔩𝔞: [looking ironically] Thanks, Uwe, Ute, for keeping it real. \ [laughter] \ 𝔘𝔱𝔢: [reading text] All right, we have this example [writing on board]

\begin{align*} 0 \mid 11 \end{align*}

𝔘𝔱𝔢: [continuing] which is false because there can’t be any $k$ where $k ⋅ 0$ equals $11\;$. Agreed?
[nods of agreement] \ 𝔘𝔱𝔢: [continuing] All right, how about this?

Prove that if $\,a \mid b$ then $-\, a \mid b$

𝔘𝔯𝔰𝔲𝔩𝔞: Let’s just logic it out [getting up and writing on the board]

\begin{align*} b & = a ⋅ k \[.4em] b &= (-a) ⋅ (-k) \[.4em] b &= - (a) ⋅ (k) \[.4em] b &= - a ⋅ k \end{align*}

then

\begin{align*}

• a \mid b \quad \text{for some}\; k ∈ \mathbb{Z}

\end{align*}

𝔘𝔯𝔰𝔲𝔩𝔞: [continuing] So $k$ by virtue of being an integer, which can be either positive or negative, we’ve derived $-\, a \mid b$ from $a \mid b\;$.
[silence while the others study the board] \ 𝔘𝔴𝔢: Hold it. I’m not sure we’ve got the spirit of this, quite. \ 𝔘𝔯𝔰𝔲𝔩𝔞: How so? \ 𝔘𝔴𝔢: [going to the board] We need to make sure we understand this as [writing] $(-a) \mid b\;$ and not as $-(a \mid b)\:$, right? \ [murmurs of agreement] \ 𝔘𝔴𝔢: So that means we’ve got [writing] $b = (-a)(-k)$ as the only possible solution to keep that $b$ positive. And I don’t think you meant to factor out $-1\:$ like you did. So $k$ must be negative to go with the $-a\:$, which then gives positive $b\;$. That’s what is meant, I think. Yes, $k$ being an integer allows this. But again, we’re dealing with a multiplicative relationship, we’re not doing division. And I’m sure we’ll find out why this is so important in a while. \ 𝔘𝔯𝔰𝔲𝔩𝔞: Oh, I think that was in here. [pulling a large-format book from her messenger bag[fn:3] and pages to tabbed page]. Right, and he shows that $0 \mid 0\:$, that zero divides zero, is true — because [writing on board] $0 = 0 ⋅ k\:$, meaning $k$ can be anything and the expression remains true. [reading further] And he’s calling $k$ the accessory number. [reading further] So his wording is the integers $x$ that satisfy $7 \mid x$ are $x = 7 ⋅ k$ — and that will be the arithmetic progression of the multiples of $7\:$. They’re evenly spaced. Good. And there’s this [going to the board and writing] \

Plot the integers $x$ which satisfy $5 \mid (x - 2)$

𝔘𝔱𝔢: [going to the board and writing] So if that’s to be true then we’ve got $x - 2 = 5k\:$, and that means for the multiples of $5\:$, the set of integers $x$ must keep $x - 2$ multiples of $5$ also. So for example

\begin{align*} -3 - 2 &= 5 ⋅ -1 \[.4em] 2 - 2 &= 5 ⋅ 0 \[.4em] 7 - 2 &= 5 ⋅ 1 \[.4em] 12 - 2 &= 5 ⋅ 2 \[.4em] \ldots \end{align*}

𝔘𝔱𝔢: [continuing] And the so-called geometric view of this set of $x$’s would be a number line with points [writing on the board]

\usetikzlibrary{intersections,arrows.meta}
\begin{tikzpicture}[scale=3]
  \clip (-0.6,-0.2) rectangle (0.6,1.51);
  \draw[step = .5cm, help lines] (-1.4,-1.4) grid (1.4,1.4);
  \filldraw[fill=green!20,draw = green!50!black] (0,0) -- (3mm,0mm)
  arc [start angle = 0, end angle = 30,radius = 3mm] -- cycle;
  \draw[->] (-1.5,0) -- (1.5,0);
  \draw[->] (0,-1.5) -- (0,1.5);
  \draw (0,0) circle [radius=1cm];
  \foreach \x in {-1,-0.5,1}
  \draw(\x cm, 1pt) -- (\x cm, -1 pt) node [anchor = north] {$\x$};
  \foreach \y in {-1,-0.5,1}
  \draw(1pt,\y cm) -- (-1pt, \y cm) node[anchor = east] {$\y$};
\end{tikzpicture}

\begin{tikzpicture}
\draw[->] (-3,0) -- (-2,0) arc[radius=0.5cm,start angle=-180,end angle=0] (-1,0) -- (1,0) arc[radius=0.5cm,start angle=180,end angle=0] (2,0) -- (3,0);
\filldraw (-1.5,0) circle[radius=1mm];
\filldraw (1.5,0) circle[radius=3mm];
\end{tikzpicture}

\begin{tikzpicture}[scale=5]
\draw[very thick] (1,0) -- (2,0);
\path [draw=black, fill=black] (1,0) circle (2pt);
\path [draw=black, fill=white, thick] (2,0.0) circle (2pt);
\draw[latex-latex] (-3.5,0) -- (3.5,0) ;
\foreach \x in  {-3,-2,-1,0,1,2,3}
\draw[shift={(\x,0)},color=black] (0pt,3pt) -- (0pt,-3pt);
\foreach \x in {-3,-2,-1,0,1,2,3}
\draw[shift={(\x,0)},color=black] (0pt,0pt) -- (0pt,-3pt) node[below] 
{$\x$};
\end{tikzpicture}

\begin{tikzpicture}[scale=1.5]
  \draw [-] (-3,0) -- (3,0);
  \draw (-3,-0.2) -- (-3,0.2);
  \draw (3,-0.2) -- (3,0.2);
  \draw (1.8,-0.2) -- (1.8,0.2); % u_5
  \draw (0.6,-0.2) -- (0.6,0.2); % u_4
  \draw (-0.6,-0.2) -- (-0.6,0.2); % u_3
  \draw (-1.8,-0.2) -- (-1.8,0.2); % u_2

  % u1
  \node [below] at (-3,-0.32) {$x_1 = 0$};
  \node [above] at (-3,0.2) {$u_1 = 1$};

  % u2
  \node [below] at (-1.8,-0.2) {$x_2 = \frac{1}{4}$};
  \node [above] at (-1.8,0.2) {$u_2$};
  
  % u3
  %\node [below] at (-0.6,-0.2) {$x_3 = \frac{1}{2}$};
  %\node [above] at (-0.6,0.2) {$u_3$};
  
  % u4
  %\node [below] at (0.6,-0.2) {$x_4 = \frac{3}{4}$};
  %\node [above] at (0.6,0.2) {$u_4$};
  
  % u5
  % \node [below] at (1.8,-0.32) {$x_4 = 1$};
  % \node [above] at (1.8,0.2) {$u_5$};
  
  % u6
  %\node [below] at (3,-0.32) {$x_6$};
  %\node [above] at (3,0.2) {Ghost Node};
  
\end{tikzpicture}

\begin{tikzpicture}[thick,
  time/.style={minimum height=5mm,minimum width=6mm,fill=#1,text=black},
  % every node/.style={draw},
  ]
  \draw[black,-latex] (0,0)--(11,0);
  \def\dx{1}
  \foreach \i in {0,...,10} {
    \ifnum\i>0
      \def\ann{$ $}
    \else
      \def\ann{$ 2X$}
    \fi
    \draw[] (\i*\dx,.2) -- (\i*\dx,-.2)
    node[pos=0,above=2mm,time=white] (P\i) {\ann}
    node[pos=1,below=2mm,time=white] (Q\i) {$\i$};
  }
  \node[time=white] at (P9) (x) {$2X(1-\frac{0.12}{12})^{-4\times12}(1+\frac{0.10}{2})^{5\times2} $};
  \draw[-latex] (P0)--(P4.center);
  \draw[-latex] ([xshift=1mm]P4.center)--(P6.east);
\end{tikzpicture}

\begin{tikzpicture}[scale=2.5]
  \draw[thick,->] (0,0) -- (4.5,0) node[anchor=north west] {x axis};
  \draw[thick,->] (0,0) -- (0,4.5) node[anchor=south east] {y axis};
\end{tikzpicture}

𝔘𝔴𝔢: Good. gold standard for figuring out lowest common denominator.
𝔘𝔯𝔰𝔲𝔩𝔞: I’d say so, but now we need to see how Haskell does it internally, and how The Haskell Road… does it and stop being amateurs. \ [laughter] \

𝔘𝔴𝔢: I feel like you and the professor are like very strong bakers kneading and kneading and kneading my brain [demonstrates with imaginary brain-dough]
[laughter] \ 𝔘𝔴𝔢: No, this had really worked out, you, Ursula, racing ahead with the Haskell. And I going ahead with the set theory, and you, Ute, going on ahead with the math logic. I mean, we’re definitely making progress. It’s just that we have so much to learn! \ [affirmations]

Footnotes

[fn:1] Proofs; A Long-Form Mathematics Textbook by Jay Cummings

[fn:2] The Whole Truth About Whole Numbers by Sylvia Forman and Agnes M. Rash;

[fn:3] An Illustrated Theory of Numbers by Martin H. Weissman.

[fn:13] See Wikipedia’s Set-builder notation

[fn:12] See this from LYAHFGG.

[fn:11] A famous line from a Stefan Georg poem: Ich fühle Luft von anderem Planeten or I feel (the) air of (the other) another planet.

[fn:10] Available here. The page dealing with sections is here in 3.2.1. Also The wiki.haskell.org has a page on sections as well.

[fn:9] …In arithmetic and number theory, the least common multiple, lowest common multiple, or smallest common multiple of two integers $a$ and $b\:$, usually denoted by $lcm(a, b)\:$, is the smallest positive integer that is divisible by both $a$ and $b\;$…

[fn:8] See the article here.

[fn:7] See Typeclasses 101 in Learn You a Haskell….

[fn:6] See Why it is impossible to divide Integer number in Haskell?

[fn:5] Check out anonymous or lambda functions here.

[fn:4] Professor Chandra has demonstrated at the Racket command line how rationals could be directly added, e.g.,
> (+ 1/32 1/943720) \ and get back \ 117969/3774880