-
Notifications
You must be signed in to change notification settings - Fork 0
/
HRGettingStarted2.html
1114 lines (943 loc) Β· 45.5 KB
/
HRGettingStarted2.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<?xml version="1.0" encoding="utf-8"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" lang="en" xml:lang="en">
<head>
<!-- 2023-01-04 Wed 22:51 -->
<meta http-equiv="Content-Type" content="text/html;charset=utf-8" />
<meta name="viewport" content="width=device-width, initial-scale=1" />
<title>Haskell Road; Getting Started Part 2</title>
<meta name="generator" content="Org Mode" />
<link rel="stylesheet" href="./tufte.css" type="text/css">
<style> .title { display: none; } </style>
<style> caption.t-bottom { caption-side: bottom; } </style>
<script>
window.MathJax = {
tex: {
ams: {
multlineWidth: '85%'
},
tags: 'ams',
tagSide: 'right',
tagIndent: '.8em'
},
chtml: {
scale: 1.0,
displayAlign: 'center',
displayIndent: '0em'
},
svg: {
scale: 1.0,
displayAlign: 'center',
displayIndent: '0em'
},
output: {
font: 'mathjax-dejavu',
displayOverflow: 'overflow'
}
};
</script>
<script
id="MathJax-script"
async
src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js">
</script>
</head>
<body>
<div id="content" class="content">
<h1 class="title">Haskell Road; Getting Started Part 2</h1>
<div class="header">
<link rel="stylesheet" href="hamb.css">
<link rel="stylesheet" href="tufte.css">
<img src="./images/heading6.png" style="padding: 0px 0px 22px 0px" alt="3-d graph" class="center">
<p>
<nav role="navigation">
<div id="menuToggle">
<!--
A fake / hidden checkbox is used as click reciever,
so you can use the :checked selector on it.
-->
<input type="checkbox" />
<!--
Some spans to act as a hamburger.
They are acting like a real hamburger,
not that McDonalds stuff.
-->
<span></span>
<span></span>
<span></span>
<!--
Too bad the menu has to be inside of the button
but hey, it's pure CSS magic.
-->
<ul id="menu">
<a href="index.html" target="_blank"><li>Home</li></a>
<a href="blog.html" target="_blank"><li>Blog</li></a>
<a href="preface.html" target="_blank"><li>Preface</li></a>
<a href="preliminaries.html" target="_blank"><li>Rabbit Holes</li></a>
<li>Numbers</li>
<ul>
<a href="numbers1.html" target="_blank"><li>Numbers 1</li></a>
<a href="numbers2.html" target="_blank"><li>Numbers 2</li></a>
</ul>
</ul>
</div>
</nav>
</div>
</p>
<div id="outline-container-org61035be" class="outline-2">
<h2 id="org61035be">Getting started part 2</h2>
</div>
<div id="outline-container-org51ab929" class="outline-2">
<h2 id="org51ab929">Monday at the library part 2</h2>
<div class="outline-text-2" id="text-org51ab929">
</div>
<div id="outline-container-org34cc2b8" class="outline-3">
<h3 id="org34cc2b8">Breaktime</h3>
<div class="outline-text-3" id="text-org34cc2b8">
<p>
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 <i>Vollkornbrot</i> sandwiches of hummus and cucumber. They
sit at a table and pour the water and pass around out the sandwiches.
</p>
<p>
<span class="fraktur">ππ±π’:</span> All right, so I
emailed the professor about a couple of questions from that first
chapter of <i>The Haskell Road</i>, and she replied saying, first, she’s
happy we’re tackling the material early. And she mentioned some
resources — a collection of texts she has on reserve at the
library. <br />
<span class="fraktur">ππ΄π’:</span> Sort of like, I’m
not going to give you the answers. I’m going to point you in the right
direction. <br />
[murmurs of acknowledgement] <br />
<span class="fraktur">ππ―π°π²π©π:</span> What books are
they? <br />
<span class="fraktur">ππ±π’:</span> Math. Upper level
college texts. Abstract algebra and number theory, mainly. <br />
[silence] <br />
<span class="fraktur">ππ΄π’:</span> I getting the
general impression that computer science has all these higher math
concepts, but then you don’t go as far as a math major does. <br />
[silence, eating and drinking] <br />
<span class="fraktur">ππ΄π’:</span> [continuing] I
guess you’re just supposed to learn as much as you can. But like she
said at the open house, computer science is a lot of <i>applied</i>
mathematics. <br />
[murmurs of agreement] <br />
<span class="fraktur">ππ―π°π²π©π:</span> And the math is
the hardest part for incoming CS students, those first four
semesters. And that’s why we’re emphasizing the math in this
course. <br />
[nods of agreement then silence as they eat and drink] <br />
<span class="fraktur">ππ―π°π²π©π:</span> [continuing]
Not so much hand-waving. And she doesn’t have set in stone what she
wants us to get through. The course is open-ended. Wow, I just find
that amazing. <br />
[murmurs of agreement] <br />
<span class="fraktur">ππ΄π’:</span> But I’m sure we’ll
need to keep moving and not be laggards about it. We’re high
schoolers, true, but this is like a super-AP course that’s exclusively
college-level material.<br />
<span class="fraktur">ππ±π’:</span> And that’s because
so much of the first year or so of a college comp-sci curriculum
really could and should be taught at the high school level. That’s her
theory — and we’re her <i>Versuchskaninchen</i><label for="1" class="margin-toggle sidenote-number"></label><input type="checkbox" id="1" class="margin-toggle"/><span class="sidenote">
<i>Versuchskaninchen</i>: test rabbit \(\simeq\) guinea pig.
</span>?<br />
[murmurs of agreement] <br />
<span class="fraktur">ππ―π°π²π©π:</span> A <i>whole</i> year,
the <i>whole</i> 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. <br />
<span class="fraktur">ππ±π’:</span> I guess you could
say Novalis is sort of an open <i>Gynmasium</i>. <br />
[soft laughter] <br />
<span class="fraktur">ππ΄π’:</span> And what happens
afterward? They definitely want you to just keep going at the U. Which
I wouldn’t mind at all. <br />
[looks about the table] <br />
<span class="fraktur">ππ±π’:</span> Yes, and lots of
people just drift into a half-and-half situation where there taking
courses over at the U. <br />
<span class="fraktur">ππ―π°π²π©π:</span> 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. <br />
<span class="fraktur">ππ±π’:</span> [laughing] Hardly!
You’re right there with us in everything we’re doing this coming year.
</p>
</div>
</div>
<div id="outline-container-orgbd110d0" class="outline-3">
<h3 id="orgbd110d0">Divided by</h3>
<div class="outline-text-3" id="text-orgbd110d0">
<p>
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.
</p>
<p>
<span class="fraktur">ππ±π’:</span> [reading from the
Divisibility section of <i>Proofs, A Long-Form Mathematical
Textbook</i><label for="2" class="margin-toggle sidenote-number"></label><input type="checkbox" id="2" class="margin-toggle"/><span class="sidenote">
<i><a href="https://longformmath.com/proofs-home">Proofs; A Long-Form Mathematics Textbook</a></i> by Jay Cummings
</span>] All right, so Professor Chandra wants us to
understand divisibility before we go to <i>greatest common divisor</i>, 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}\) produces an integer. <br />
[Ursula and Uwe read the section from a second copy] <br />
<span class="fraktur">ππ±π’:</span> [continuing] But
we don’t want that definition, we want <i>this</i> definition [writing on
the board]
</p>
\begin{align}
\exists \: k \in \mathbb{Z},\; a \neq 0, \;\;a \mid b \;\; \text{if} \;\; b = a \cdot k
\end{align}
<p>
<span class="fraktur">ππ±π’:</span> [continuing] The
symbol \(a \mid b\:\) means \(a\) divides \(b\) for some \(k\) where \(b = a \cdot
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 <i>multiply</i> with. Now
we have a mathy formalist way of seeing divisibility. <br />
[murmurs of approval] <br />
<span class="fraktur">ππ΄π’:</span> I like how he says
good definitions don’t just fall out of the sky. <br />
[murmurs of agreement] <br />
<span class="fraktur">ππ―π°π²π©π:</span> Then the
examples, like \(2 \mid 14\) is true because \(14 = 2 \cdot 7\:\), in other
words we’ve found a whole number integer, \(k = 7\), and we’re happy. <br />
<span class="fraktur">ππ±π’:</span> 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 \(7 \cdot k = 23\). <br />
<span class="fraktur">ππ΄π’:</span> 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 \cdot 0\) is always true for any \(a\) as long as \(k
= 0\;\). <br />
[murmurs of agreement] <br />
<span class="fraktur">ππ―π°π²π©π:</span> So for [writing
on the board] \(a \mid b\), we can say \(a\) is a <i>divisor</i> of \(b\), and
\(b\) is a <i>multiple</i> of \(a\), and \(b\) is <i>divisible</i> by \(a\). <br />
[murmurs of agreement] <br />
<span class="fraktur">ππ±π’:</span> So they want us to
understand that we’re not supposed to see \(2 \mid 14\) and just say it
<i>equals</i> \(7\). It’s not supposed to be seen as a calculation, it’s a
logic <i>expression</i> that’s true or false — for some value \(k\:\). <br />
<span class="fraktur">ππ΄π’:</span> Right. We’re in
the world of logic now, not grade school arithmetic. So everything has
to be reexplained and reworked. <br />
[murmurs of agreement] <br />
<span class="fraktur">ππ±π’:</span> All right, so in
this book<label for="3" class="margin-toggle sidenote-number"></label><input type="checkbox" id="3" class="margin-toggle"/><span class="sidenote">
A <i>Computational Introduction To Number Theory and Algebra</i> by
Victor Shoup; <a href="&shoup2009computational">&shoup2009computational</a>.
}
</span> they have a theorem about divisibility. [writing on
the board]
</p>
<ol class="org-ol">
<li>\(a \mid a\), \(1 \mid a\), and \(a \mid 0\);</li>
<li>\(0 \mid a \iff a = 0\);</li>
<li>\(a \mid b \iff -a \mid b \iff a \mid -b\);</li>
<li>\(a \mid b \land a \mid c \implies a \mid (b + c)\);</li>
<li>\(a \mid b \land b \mid c \implies a \mid c\)</li>
</ol>
<p>
<span class="fraktur">ππ±π’:</span> Good, now he’s
talking about the <i>transitive</i> property of divisibility. It is a
<i>proposition</i>, 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
</p>
\begin{align*}
a, b, c \in \mathbb{Z},\;\; a \mid b \;\land\; b \mid c \implies a \mid c
\end{align*}
<p>
<span class="fraktur">ππ±π’:</span> [continuing] And
then he goes on to prove it by saying assume the <i>if</i> part, the \(a
\mid b \;\land\; b \mid c\:\) part is true, that means the <i>then</i> part, the
\(a \mid c\) part is true. So [writing]
</p>
\begin{align*}
b &= a \cdot s \\[.4em]
c &= b \cdot t
\end{align*}
<p>
<span class="fraktur">ππ±π’:</span> [continuing] for
some integers \(s\) and \(t\;\). And now [writing]
</p>
\begin{align*}
c &= b \cdot t \\[.4em]
&= (a \cdot s) \cdot t \\[.4em]
&= a \cdot (s \cdot t) \quad\quad \ldots \; \text{associativity}
\end{align*}
<p>
<span class="fraktur">ππ±π’:</span> [continuing] So
since we have the form \(c = a \cdot (s \cdot 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 \cdot k\) where \(k = (s \cdot t)\:\). <br />
<span class="fraktur">ππ―π°π²π©π:</span> Good. Let’s
switch over to this other book [she picks up a Springer Verlag
book<label for="4" class="margin-toggle sidenote-number"></label><input type="checkbox" id="4" class="margin-toggle"/><span class="sidenote">
<i><a href="https://www.google.com/books/edition/The_Whole_Truth_About_Whole_Numbers/ahUGswEACAAJ?hl=en">The Whole Truth About Whole Numbers</a></i> by Sylvia Forman and
Agnes M. Rash;
</span> and pages through it] Ah, in this book there’s a section
called <i>Divisors and the Greatest Common Divisor</i>. [paging to section,
reading] Oh, here’s one, <i>Determine whether true or false</i> [writing on
the board]
</p>
\begin{align*}
2 \mid (6n + 4)
\end{align*}
<p>
<span class="fraktur">ππ΄π’:</span> Interesting. So
writing it in the divisibility way [gets up and writes on the board]
</p>
\begin{align*}
(6n + 4) = 2k
\end{align*}
<p>
<span class="fraktur">ππ΄π’:</span> So before we freak
out and get lost, let’s just notice that [writing]
</p>
\begin{align}
2(3n + 4) &= 2k \\[.4em]
3n + 4 &= k
\end{align}
<p>
<span class="fraktur">ππ΄π’:</span> [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. <br />
<span class="fraktur">ππ±π’:</span> And this whole
formal divisibility thing helps because if you just saw this one day
[writing on the board]
</p>
\begin{align}
\frac{(6n + 4)}{2} = 3n + 2
\end{align}
<p>
<span class="fraktur">ππ±π’:</span> [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\;\). <br />
<span class="fraktur">ππ―π°π²π©π:</span> [looking
ironically] Thanks, Uwe, Ute, for keeping it real. <br />
[laughter] <br />
<span class="fraktur">ππ±π’:</span> [reading text] All
right, we have this example [writing on board]
</p>
\begin{align*}
0 \mid 11
\end{align*}
<p>
<span class="fraktur">ππ±π’:</span> [continuing] which
is false because there can’t be any \(k\) where \(k \cdot 0\) equals
\(11\;\). Agreed? <br />
[nods of agreement] <br />
<span class="fraktur">ππ±π’:</span> [continuing] All
right, how about this?
</p>
<div class="epigraph"><blockquote>
<p>
Prove that if \(\,a \mid b\) then \(-\, a \mid b\)
</p>
</blockquote></div>
<p>
<span class="fraktur">ππ―π°π²π©π:</span> Let’s just
logic it out [getting up and writing on the board]
</p>
\begin{align*}
b & = a \cdot k \\[.4em]
b &= (-a) \cdot (-k) \\[.4em]
b &= - (a) \cdot (k) \\[.4em]
b &= - a \cdot k
\end{align*}
<p>
then
</p>
\begin{align*}
- a \mid b \quad \text{for some}\; k \in \mathbb{Z}
\end{align*}
<p>
<span class="fraktur">ππ―π°π²π©π:</span> [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\;\). <br />
[silence while the others study the board] <br />
<span class="fraktur">ππ΄π’:</span> Hold it. I’m not
sure we’ve got the spirit of this, quite. <br />
<span class="fraktur">ππ―π°π²π©π:</span> How so? <br />
<span class="fraktur">ππ΄π’:</span> [going to the
board] We need to make sure we understand this as [writing] \((-a) \mid
b\;\) and not as \(-(a \mid b)\:\), right? <br />
[murmurs of agreement] <br />
<span class="fraktur">ππ΄π’:</span> 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. <br />
<span class="fraktur">ππ―π°π²π©π:</span> Oh, I think
that was in here. [pulling a large-format book from her messenger
bag<label for="5" class="margin-toggle sidenote-number"></label><input type="checkbox" id="5" class="margin-toggle"/><span class="sidenote">
<i><a href="http://illustratedtheoryofnumbers.com/">An Illustrated Theory of Numbers</a></i> by Martin H. Weissman.
</span> 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 \cdot k\:\), meaning \(k\) can be anything and the expression remains
true. [reading further] And he’s calling \(k\) the <i>accessory
number</i>. [reading further] So his wording is the integers \(x\) that
satisfy \(7 \mid x\) are \(x = 7 \cdot 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] <br />
</p>
<div class="epigraph"><blockquote>
<p>
Plot the integers \(x\) which satisfy \(5 \mid (x - 2)\)
</p>
</blockquote></div>
<p>
<span class="fraktur">ππ±π’:</span> [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 <i>set</i> of
integers \(x\) must keep \(x - 2\) multiples of \(5\) also. So for example
</p>
\begin{align*}
-3 - 2 &= 5 \cdot -1 \\[.4em]
2 - 2 &= 5 \cdot 0 \\[.4em]
7 - 2 &= 5 \cdot 1 \\[.4em]
12 - 2 &= 5 \cdot 2 \\[.4em]
\ldots
\end{align*}
<p>
<span class="fraktur">ππ±π’:</span> [continuing] And
the so-called <i>geometric</i> view of this set of \(x\)’s would be a number
line with points [drawing on the board]
</p>
<img src="./images/divisibilityline1.svg" width="725px" style="padding: 15px 0px 0px 0px" alt="Number Line 1" class="center">
<span class="cap">Divisibility number line where x-2 must be a multiple of 5 </span>
<p>
<span class="fraktur">ππ±π’:</span> [continuing] Which
is to say, \(x\) is two more than a multiple of \(5\:\). <br />
<span class="fraktur">ππ―π°π²π©π:</span> Okay, next one
[writing on the board]
</p>
<div class="epigraph"><blockquote>
<p>
Plot the integers \(x\) which satisfy \(x \mid 12\:\).
</p>
</blockquote></div>
<p>
<span class="fraktur">ππ―π°π²π©π:</span> [continuing
writing] So that means \(12 = x \cdot k\) where \(k\) will just be the
integers. <br />
<span class="fraktur">ππ΄π’:</span> Again, I would say
we shouldn’t read too much into this. The basic fact is [going to the
board and writing] we have the set of integers that divide \(12\)
</p>
\begin{align}
[-1,-2,-3,-4,6,-12,1,2,3,4,6,12]
\end{align}
<p>
<span class="fraktur">ππ΄π’:</span> And however that
works out with \(x \cdot k\) is incidental, since whatever \(x\) and \(k\) need
to be, their product has to be in this [point at (5)] set.<br />
[murmurs of agreement] <br />
<span class="fraktur">ππ―π°π²π©π:</span> I’ll draw that
quickly [drawing number line]
</p>
<img src="./images/divisibilityline2.svg" width="725px" style="padding: 15px 0px 0px 0px" alt="Number Line 2" class="center">
<span class="cap">Divisors of 12 on an integer line</span>
<p>
<span class="fraktur">ππ―π°π²π©π:</span> All right,
Weissman deals with <i>transitive</i> again. But before that he talks about
<i>reflexive</i> and <i>antisymmetric</i> in relation to divisibility. [writing
on the board]
</p>
<div class="epigraph"><blockquote>
<p>
For every integer \(x\), \(x \mid x\)
</p>
</blockquote></div>
<p>
[smiles of ironic mute astonishment] <br />
</p>
<p>
<span class="fraktur">ππ―π°π²π©π:</span> [continuing] So
this is showing us the <i>reflexivity of divisibility</i> \(\mid\:\). Then he
says in the margin, <i>Every integer is a multiple of itself</i>. And then
he has [writing on board] \(x = x \cdot 1\) <br />
[silence] <br />
<span class="fraktur">ππ±π’:</span> [reading from her
laptop] According to Wikipedia, a <i>reflexive relation</i> is a binary
relation — or let’s say a <i>binary operator</i> — on a set \(X\) that
“relates” an element of \(X\) to itself. <br />
[silence] <br />
<span class="fraktur">ππ΄π’:</span> [reading his
laptop] I’m on the <i>Encyclopedia of Mathematics</i> site<label for="6" class="margin-toggle sidenote-number"></label><input type="checkbox" id="6" class="margin-toggle"/><span class="sidenote">
See <a href="https://encyclopediaofmath.org/wiki/Main_Page">The Encyclopedia of Mathematics</a>.
</span> for
reflexivity<label for="7" class="margin-toggle sidenote-number"></label><input type="checkbox" id="7" class="margin-toggle"/><span class="sidenote">
<a href="https://encyclopediaofmath.org/index.php?title=Reflexivity">Reflexivity; Encyclopedia of Mathematics.</a>
</span> and it talks about it in terms of relations as
well. But we don’t want to really unpack the whole Cartesian product,
relations, functions thing yet do we, no. <br />
[murmurs of agreement] <br />
<span class="fraktur">ππ΄π’:</span> It says a relation
is reflexive if it contains the <i>diagonal</i> or <i>identity</i> relation
[writing on the board] \(\{(a,a) : a \in A\}\) for set \(A\:\). <br />
<span class="fraktur">ππ―π°π²π©π:</span> So if that
\((a,a)\) is seen as just a coordinate pair on a regular Cartesian
coordinate plane, [drawing a graph on the board] then yes, it’s just
points on the diagonal
</p>
<img src="./images/reflexivecartesian1.svg" width="425px" style="padding: 15px 0px 0px 0px" alt="reflexivity" class="center">
<span class="cap">Approximation of Ursula's Cartesian plane reflexive relation drawing.</span>
<p>
[silence] <br />
<span class="fraktur">ππ΄π’:</span> So without getting
too lost in the details, reflexive means things are related somehow to
themselves. So equality would work, even <i>greater than or equal</i>, and
<i>less than or equal</i> since the equal part is true. So for example, all
integers are greater than <i>or</i> equal to themselves. [gives ironic
look] Well, it’s true. <br />
[laughter] <br />
<span class="fraktur">ππ±π’:</span> Antisymmetric is next? <br />
<span class="fraktur">ππ―π°π²π©π:</span> Right. And I’d
like to understand what <i>symmetric</i> means first — just to get <i>very</i>
confused. <br />
[laughter, then all searching on their laptops] <br />
<span class="fraktur">ππ΄π’:</span> Again, we’re
looking for <i>symmetric relation</i>. <br />
[murmurs of agreement] <br />
<span class="fraktur">ππ±π’:</span> Okay, Wikipedia
says a <i>symmetric relation</i> is basically, as I paraphrase it, a
situation where if \(a = b\) is true, then \(b = a\) is also true [writing
on the board]
</p>
\begin{align*}
\forall a,b \in X, \;\; aRb \iff bRa
\end{align*}
<p>
<span class="fraktur">ππ±π’:</span> [continuing] And
the \(aRb\) means \(a\) and \(b\) are in a relationship. And then examples
might be we’re in symmetric relationships with each other because
we’re all blood siblings to each other. So you Ursula are my sibling,
and I am your sibling. <br />
<span class="fraktur">ππ―π°π²π©π:</span> Right, but
blood sibling is <i>not</i> reflexive, it’s <i>irreflexive</i> because you can’t
be called a sibling of yourself. But then a number can be a multiple
of itself — \(1\) times itself — and we established that as
reflexive; but I’m not my own sibling. <br />
[murmurs of agreement]. <br />
<span class="fraktur">ππ΄π’:</span> So in a round
robin binary way, we share the same parents. That’s symmetric, but
it’s not reflexive, is it? You can’t share a parent with yourself, can
you? <br />
[silence] <br />
<span class="fraktur">ππ―π°π²π©π:</span> If it were
worded <i>my mother is my mother</i> or <i>my father is my father</i>, it’s the
same as saying <i>\(a\) is equal to \(a\)</i>, isn’t it? So the wording “parent
in common with myself” is misleading, because we’re not relating me
and my parent directly, we’re relating the parent to that same parent
by means of me as the joiner. Does that make sense? It’s in the basic
spirit of a binary relation that relates an element to itself. <br />
[half-hearted murmurs of agreement and ironic smirking] <br />
<span class="fraktur">ππ±π’:</span> And then we’ve
said the equals relation is reflexive <i>and</i> symmetric, right? Do we
want to say this, really? <br />
<span class="fraktur">ππ―π°π²π©π:</span> Sure, why not?
You know, so often I learn the “official” way, the accepted answer —
and then I talk myself into believing it. <br />
[laughter] <br />
<span class="fraktur">ππ±π’:</span> Are we ready to
tackle <i>antisymmetry</i>? <br />
[eager murmurs of agreement] <br />
<span class="fraktur">ππ±π’:</span> Okay, I’ve
searched on <i>antisymmetry</i> and gone to a Wolfram MathWorld page<label for="8" class="margin-toggle sidenote-number"></label><input type="checkbox" id="8" class="margin-toggle"/><span class="sidenote">
<a href="https://mathworld.wolfram.com/AntisymmetricRelation.html">Antisymmetric Relation</a>.
</span>
that says [reading]
</p>
<div class="epigraph"><blockquote>
<p>
A relation \(R\) on a set \(S\) is antisymmetric provided that distinct
elements are never both related to one another. In other words \(xRy\)
and \(yRx\) together imply that \(x = y\:\).
</p>
</blockquote></div>
<p>
<span class="fraktur">ππ±π’:</span> [continuing] And
then from the Wikipedia article [going to the board and writing]
</p>
<div class="epigraph"><blockquote>
<p>
If \(aRb\) with \(a \ne b\) then \(bRa\) must not hold.
</p>
</blockquote></div>
<p>
<span class="fraktur">ππ―π°π²π©π:</span> Good. So now
Weissman says [writing on the board]
</p>
<div class="epigraph"><blockquote>
<p>
For integers \(x\), \(y\), if \(x \mid y\) and \(y \mid x\), then \(x = \pm y\:\).
</p>
</blockquote></div>
<p>
<span class="fraktur">ππ―π°π²π©π:</span> [continuing]
And then he shows it by saying [writing on the board]
</p>
\begin{align*}
\text{if}\;\;y &= mx \quad \text{and} \\[.5em]
x &= ny \quad \text {for some integers}\;\; x, y
\end{align*}
<p>
<span class="fraktur">ππ―π°π²π©π:</span> [continuing]
And then we can say [writing]
</p>
\begin{align}
x = ny = n(mx) = (nm)x
\end{align}
<p>
<span class="fraktur">ππ―π°π²π©π:</span> [continuing]
And now if we say \(x \ne 0\) we can divide this [pointing to (6)] by
\(x\:\) [writing on board]
</p>
\begin{align*}
\frac{x}{x} &= \frac{ny}{x} = \frac{n(mx)}{x} = \frac{(nm)x}{x} \\[.5em]
1 &= \frac{ny}{x} = nm = nm
\end{align*}
<p>
<span class="fraktur">ππ―π°π²π©π:</span> [continuing] So
multiplying by a number is the same as dividing by its reciprocal —
and vice versa. And now we have a reciprocal relationship between \(n\)
and \(m\) since two numbers multiplied equaling \(1\) means they must be
reciprocals of each other [writing on the board]
</p>
\begin{align*}
1 &= nm \\[.5em]
\frac{1}{m} &= n \\[.5em]
\frac{1}{n} &= m
\end{align*}
<p>
<span class="fraktur">ππ―π°π²π©π:</span> [continuing,
writing on the board] But as he’s saying, \(\frac{1}{m}\) and
\(\frac{1}{n}\) cannot be anything but \(1\) and still be integers, so
it’s proven that \(n = m = \pm1\:\) So subbing into [points to (6)]
</p>
\begin{align*}
x &= ny \\[.5em]
x &= (\pm1)y
\end{align*}
<p>
<span class="fraktur">ππ΄π’:</span> Which is, again,
showing us that division is not ever going to be symmetric unless
we’re just talking about an integer dividing itself, basically —
that is, plus or minus itself. <br />
[murmurs of agreement] <br />
<span class="fraktur">ππ―π°π²π©π:</span> [looking at the
Weissman text] So then he does <i>transitivity</i> with divisibility, and
it’s the same as we did before. Then he does [writing on the board]
</p>
\begin{align*}
d,x,y \in \mathbb{Z}\; \land\; d \mid x \implies d \mid xy
\end{align*}
<p>
<span class="fraktur">ππ―π°π²π©π:</span> There’s his
proof, that is [writing on the board]
</p>
\begin{align*}
x &= md \\[.5em]
xy &= (md)y \quad \text{(multiply both sides by $y$)} \\[.5em]
xy &= (my)d
\end{align*}
<p>
<span class="fraktur">ππ―π°π²π©π:</span> So \(xy\) is a
multiple of \(d\), that multiple being \((my)\). Okay? <br />
[murmurs of agreement] <br />
<span class="fraktur">ππ―π°π²π©π:</span> Next, is this
one [writing on the board]
</p>
<div class="epigraph"><blockquote>
<p>
If \(d \mid x\) and \(d \mid y\), then \(d \mid (x + y)\) and \(d \mid (x - y)\).
</p>
</blockquote></div>
<p>
<span class="fraktur">ππ―π°π²π©π:</span> [continuing]
And the proof is we can say [writing on board] for \(x = md\) and \(y =
nd\) for integers \(m\) and \(n\)
</p>
\begin{align*}
x \pm y = (md) \pm (nd) = (m \pm n)d
\end{align*}
<p>
<span class="fraktur">ππ―π°π²π©π:</span> [continuing]
And this shows that \(x \pm y\) is a multiple of \(d\). [reading further in
the Weissman text] Then he gives a variation on this idea, which he
calls the <i>two out of three principle for divisibility</i>. [writing on
the board]
</p>
<div class="epigraph"><blockquote>
<p>
Let \(a\),\(b\),\(c\) be integers satisfying the equation \(a + b = c\). Let
\(d\) bye an integer. If two of the set \(\{a,b,c\}\) are multiples of
\(d\), then the third number must also be a multiple of \(d\).
</p>
</blockquote></div>
<p>
[silence] <br />
<span class="fraktur">ππ±π’:</span> This is just the
previous one reworded, right? The basic situation [writing on the
board] \(a + b = c\) can be rearranged into \(a = c - b\) or \(b = c -
a\). So whichever two you have as multiples of \(d\), we add or subtract
them to get the third, and that’s covered by \(d \mid (x \pm y)\). <br />
[soft murmurs of agreement] <br />
<span class="fraktur">ππ―π°π²π©π:</span> This
demonstrates two-out-of-three [reading from
the text and copying on the board]
</p>
<div class="epigraph"><blockquote>
<p>
Demonstrate that \(2\,999\,997\) is a multiple of \(3\).
</p>
</blockquote></div>
<p>
<span class="fraktur">ππ΄π’:</span> Okay, my
turn. [going to the board and writing] Since \(3\,000\,000 - 3 =
2\,999\,997\), we know because of the two-out-of-three principle<label for="9" class="margin-toggle sidenote-number"></label><input type="checkbox" id="9" class="margin-toggle"/><span class="sidenote">
Uwe uses the \(\therefore\) which is the symbol for <i>therefore</i>.
</span>
</p>
\begin{align*}
3 &\mid 3\,000\,000 \quad &\text{(first known)}\\[.5em]
3 &\mid 3 \quad &\text{(second known)} \\[.5em]
\therefore \;\; 3 &\mid (3\,000\,000 - 3)
\end{align*}
<p>
<span class="fraktur">ππ±π’:</span> Exactly. We knew
two were divisible by \(d\), so those two added or subtracted from one
another we could know as well. Good. <br />
[murmurs of satisfaction] <br />
<span class="fraktur">ππ΄π’:</span> Hey, we’re really
going down this rabbit hole. <br />
<span class="fraktur">ππ―π°π²π©π:</span> [perusing
Weissman] It’s only one, no, two more exercises, then it goes on to
something else. Let’s do this next one and go back to Cummings. <br />
[murmurs of agreement] <br />
<span class="fraktur">ππ΄π’:</span> No matter what,
I’ll never see division the same again. <br />
[laughter] <br />
<span class="fraktur">ππ±π’:</span> Hey, I just
searched on <code>haskell divisibility</code> and a stackoverflow came
up<label for="10" class="margin-toggle sidenote-number"></label><input type="checkbox" id="10" class="margin-toggle"/><span class="sidenote">
See <a href="https://stackoverflow.com/questions/3990095/testing-divisibility-of-ints-by-11">Testing divisibility of Ints by 11</a>.
</span>. It basically asks whether an integer is divisible by
\(11\). And then it has some trick about adding and subtracting the
digits of the number, right. But then somebody gives the answer
[writing on the board]
</p>
<pre class="code"><code><span class="org-haskell-definition">divisibleBy11</span> x <span class="org-haskell-operator">=</span> x <span class="org-haskell-operator">`rem`</span> 11 <span class="org-haskell-operator">==</span> 0
</code></pre>
<p>
<span class="fraktur">ππ―π°π²π©π:</span> I’ll try it
[typing into her monitor-connected laptop and running]
</p>
<pre class="code"><code><span class="org-haskell-definition">divisibleBy11</span> 33
</code></pre>
<pre class="example">
<interactive>:222:1-13: error:
Variable not in scope: divisibleBy11 :: t0 -> t
</pre>
<p>
<span class="fraktur">ππ―π°π²π©π:</span> I assume that
<code>rem</code> means remainder, as in, Give me the remainder of a division. And
then that’s checked if equal to \(0\). <br />
[murmurs of agreement] <br />
<span class="fraktur">ππ΄π’:</span> Again, we’re
getting the true-false nature of divisibility. It’s not just dividing
a number by another. It’s asking yes or no whether a number properly
divides another. <br />
<span class="fraktur">ππ―π°π²π©π:</span> Okay, here’s
the next problem
</p>
<div class="epigraph"><blockquote>
<p>
Find all integers \(x\) which satisfy \(x \mid (x + 6)\).
</p>
</blockquote></div>
<p>
[silence] <br />
<span class="fraktur">ππ―π°π²π©π:</span> [reading on]
Then he’s solving it with his two out of three principle. So if we can
find two parts of this that are divisible, then the sum or difference
of these is then divisible as well. <br />
[silence] <br />
<span class="fraktur">ππ―π°π²π©π:</span> A hint is that
we’re supposed to <i>assume</i> the \(x \mid (x + 6)\) is one of the
givens. Then we need another given. Then we add or subtract these two
givens to get the final formula. <br />
<span class="fraktur">ππ±π’:</span> Formula? <br />
<span class="fraktur">ππ΄π’:</span> In the last one we
had \(3\) divides one thing, and then \(3\) divides another thing,
therefore those two things \(3\) divides, when added or subtracted, also
are divisible by \(3\). So we could say the thing dividing is an unknown
variable \(x\). It divides, supposedly, \((x + 6)\), but then we need
another thing that \(x\) divides. <br />
[silence] <br />
<span class="fraktur">ππ΄π’:</span> [writing on the
board] So, just pulling something out of thin air, if we assume the
second give is \(x \mid 7\), then we’ve got something…
</p>
\begin{align*}
x \mid (x + 6) - 7 = x \mid x - 1
\end{align*}
<p>
<span class="fraktur">ππ΄π’:</span> …that doesn’t
help us much. It’s just a new “what can \(x\) be” question. That is,
we’re going in circles. <br />
<span class="fraktur">ππ±π’:</span> Something tells me
we want to get rid of stuff on the right hand side of the
\(\mid\). Either get rid of the \(x\) or the \(6\). <br />
[murmurs of agreement] <br />
<span class="fraktur">ππ±π’:</span> [continuing] So
why don’t we assume — oh, I know! Let’s say \(x \mid x\) is the other
given since that’s always true. <br />
<span class="fraktur">ππ΄π’:</span> Good. [writing on
board]
</p>
\begin{align*}
x &\mid x \quad \text{...second given after $x \mid (x + 6)$}\\[.5em]
x &\mid (x + 6) - x = 6 \quad \text{...subtracting one given from another}\\[.5em]
x &\mid 6
\end{align*}
<p>
[silence] <br />
<span class="fraktur">ππ±π’:</span> What that’s saying
— as far as I can tell [writing on the board] \(x \mid (x + 6) \iff x
\mid 6\). Right? So whatever \(x\)’s divide \(6\) will be our desired set
for \(x \mid (x + 6)\) as well. <br />
<span class="fraktur">ππ―π°π²π©π:</span> Let me test it
with something Haskell. [starts a new source block]
</p>
<pre class="code"><code><span class="org-rainbow-delimiters-depth-1">[</span>x <span class="org-haskell-operator">|</span> x <span class="org-haskell-operator"><-</span> <span class="org-rainbow-delimiters-depth-2">[</span><span class="org-haskell-operator">-</span>20,<span class="org-haskell-operator">-</span>19<span class="org-haskell-operator">..</span>20<span class="org-rainbow-delimiters-depth-2">]</span>, <span class="org-rainbow-delimiters-depth-2">(</span><span class="org-rainbow-delimiters-depth-3">(</span>x <span class="org-haskell-operator">`rem`</span> 6<span class="org-rainbow-delimiters-depth-3">)</span> <span class="org-haskell-operator">==</span> 0<span class="org-rainbow-delimiters-depth-2">)</span><span class="org-rainbow-delimiters-depth-1">]</span>
</code></pre>
<pre class="example">
[-18,-12,-6,0,6,12,18]
</pre>
<p>
<span class="fraktur">ππ―π°π²π©π:</span> No, wrong, I’ve
got the <code>6</code> trying to go into the <code>x</code>. Need to reverse them.
</p>
<pre class="code"><code><span class="org-rainbow-delimiters-depth-1">[</span>x <span class="org-haskell-operator">|</span> x <span class="org-haskell-operator"><-</span> <span class="org-rainbow-delimiters-depth-2">[</span><span class="org-haskell-operator">-</span>20,<span class="org-haskell-operator">-</span>19<span class="org-haskell-operator">..</span>20<span class="org-rainbow-delimiters-depth-2">]</span>, <span class="org-rainbow-delimiters-depth-2">(</span><span class="org-rainbow-delimiters-depth-3">(</span>6 <span class="org-haskell-operator">`rem`</span> x<span class="org-rainbow-delimiters-depth-3">)</span> <span class="org-haskell-operator">==</span> 0<span class="org-rainbow-delimiters-depth-2">)</span><span class="org-rainbow-delimiters-depth-1">]</span>
</code></pre>
<pre class="example">
[-6,-3,-2,-1*** Exception: divide by zero
</pre>
<p>
<span class="fraktur">ππ―π°π²π©π:</span> And obviously
we can’t divide by zero. We need to filter out the zero. <br />
<span class="fraktur">ππ±π’:</span> Right. [searching
on her laptop] Okay, there’s a <code>filter</code> function. All you need to do
is say [writing on the board] <code>filter (\=0) [-20,-19..20]</code> and with
that <i>not equals zero</i> in the middle, <code>0</code> should get filtered out. <br />
<span class="fraktur">ππ―π°π²π©π:</span> Got
it. [typing]
</p>
<pre class="code"><code><span class="org-rainbow-delimiters-depth-1">[</span>x <span class="org-haskell-operator">|</span> x <span class="org-haskell-operator"><-</span> filter <span class="org-rainbow-delimiters-depth-2">(</span><span class="org-haskell-operator">/=</span>0<span class="org-rainbow-delimiters-depth-2">)</span> <span class="org-rainbow-delimiters-depth-2">[</span><span class="org-haskell-operator">-</span>20,<span class="org-haskell-operator">-</span>19<span class="org-haskell-operator">..</span>20<span class="org-rainbow-delimiters-depth-2">]</span>, <span class="org-rainbow-delimiters-depth-2">(</span><span class="org-rainbow-delimiters-depth-3">(</span>6 <span class="org-haskell-operator">`rem`</span> x<span class="org-rainbow-delimiters-depth-3">)</span> <span class="org-haskell-operator">==</span> 0<span class="org-rainbow-delimiters-depth-2">)</span><span class="org-rainbow-delimiters-depth-1">]</span>
</code></pre>
<pre class="example">
[-6,-3,-2,-1,1,2,3,6]
</pre>
<p>
<span class="fraktur">ππ―π°π²π©π:</span> Or I could do
it this way [typing]
</p>
<pre class="code"><code><span class="org-haskell-constructor">:</span><span class="org-rainbow-delimiters-depth-1">{</span>
<span class="org-haskell-definition">xDivides6</span> <span class="org-haskell-operator">=</span> <span class="org-rainbow-delimiters-depth-2">[</span>x <span class="org-haskell-operator">|</span> x <span class="org-haskell-operator"><-</span> sampleList, <span class="org-rainbow-delimiters-depth-3">(</span><span class="org-rainbow-delimiters-depth-4">(</span>6 <span class="org-haskell-operator">`rem`</span> x<span class="org-rainbow-delimiters-depth-4">)</span> <span class="org-haskell-operator">==</span> 0<span class="org-rainbow-delimiters-depth-3">)</span><span class="org-rainbow-delimiters-depth-2">]</span>
<span class="org-haskell-keyword">where</span> sampleList <span class="org-haskell-operator">=</span> <span class="org-rainbow-delimiters-depth-2">[</span><span class="org-haskell-operator">-</span>20,<span class="org-haskell-operator">-</span>19<span class="org-haskell-operator">..</span><span class="org-rainbow-delimiters-depth-3">(</span><span class="org-haskell-operator">-</span>1<span class="org-rainbow-delimiters-depth-3">)</span><span class="org-rainbow-delimiters-depth-2">]</span> <span class="org-haskell-operator">++</span> <span class="org-rainbow-delimiters-depth-2">[</span>1<span class="org-haskell-operator">..</span>20<span class="org-rainbow-delimiters-depth-2">]</span>
<span class="org-haskell-constructor">:</span><span class="org-rainbow-delimiters-depth-1">}</span>
</code></pre>
<pre class="code"><code>xDivides6
</code></pre>
<p>
<span class="fraktur">ππ―π°π²π©π:</span>