-
Notifications
You must be signed in to change notification settings - Fork 0
/
numbers2.html
3027 lines (2450 loc) · 133 KB
/
numbers2.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>
<!-- 2022-11-04 Fri 11:06 -->
<meta http-equiv="Content-Type" content="text/html;charset=utf-8" />
<meta name="viewport" content="width=device-width, initial-scale=1" />
<title>‎</title>
<meta name="generator" content="Org Mode" />
<link rel="stylesheet" href="./tufte.css" type="text/css">
<script type="text/x-mathjax-config">
MathJax.Hub.Config({
displayAlign: "center",
displayIndent: "0em",
"HTML-CSS": { scale: 100,
linebreaks: { automatic: "false" },
webFont: "TeX"
},
SVG: {scale: 100,
linebreaks: { automatic: "false" },
font: "TeX"},
NativeMML: {scale: 100},
TeX: { equationNumbers: {autoNumber: "AMS"},
MultLineWidth: "85%",
TagSide: "right",
TagIndent: ".8em"
}
});
</script>
<script src="https://cdn.jsdelivr.net/npm/mathjax@2/MathJax.js?config=TeX-AMS_HTML"></script>
</head>
<body>
<div id="content" class="content">
<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="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-orgaee9956" class="outline-2">
<h2 id="orgaee9956">Numbers</h2>
</div>
<div id="outline-container-orgd8d0d64" class="outline-2">
<h2 id="orgd8d0d64">Introduction to part 2</h2>
<div class="outline-text-2" id="text-orgd8d0d64">
<p>
We’ll pick up where we left off with our breakdown of the three basic
<i>qualities of quantities</i><label for="1" class="margin-toggle sidenote-number"></label><input type="checkbox" id="1" class="margin-toggle"/><span class="sidenote">
If you’re jumping in here make sure you reload <code>numbers1.hs</code>,
along with <code>numbers2.hs</code> from this section’s work.
</span>
</p>
<ul class="org-ul">
<li>cardinality, or <i>how many?</i></li>
<li>ordinality, or <i>what order?</i></li>
<li>enumeration, or, generally, <i>how do we count out things?</i></li>
</ul>
<p>
In this section we’ll tackle enumeration.
</p>
<p>
To be sure, <i>enumeration</i>, or as it is also called <i>combinatorics</i>, is
a huge and active field of mathematics, parts of which are included in
introductions to Discrete Mathematics, and in general, are fair game
throughout a CS degree. This means our approach with CIMIC will have
to be rather pruned and directed, since the combinatorics tree is big
and bushy.
</p>
<p>
Truth be told, the first time you hear about enumeration as a
beginning Haskeller isn’t really about all this deep, bushy math,
rather doing things like completing a <i>range</i><label for="2" class="margin-toggle sidenote-number"></label><input type="checkbox" id="2" class="margin-toggle"/><span class="sidenote">
Make sure you’ve seen <a href="http://learnyouahaskell.com/starting-out#texas-ranges">Texas ranges</a> in LYAHFGG.
</span>, e.g.
</p>
<pre class="code"><code><span class="org-rainbow-delimiters-depth-1">[</span>1<span class="org-haskell-operator">..</span>12<span class="org-rainbow-delimiters-depth-1">]</span>
</code></pre>
<pre class="example">
[1,2,3,4,5,6,7,8,9,10,11,12]
</pre>
<p>
or<label for="3" class="margin-toggle sidenote-number"></label><input type="checkbox" id="3" class="margin-toggle"/><span class="sidenote">
In this next example we use the open-ended “infinite” list —
which will typically go on forever, locking up your computer as it
tries to list <i>all</i> of numbers, or in this case letters. We use the
function <code>take</code> to take just the first <code>27</code> letters and not go any
further. Curiously, Haskell thinks the twenty-seventh letter is
<code>{</code>. That’s because these are <i>unicode</i> characters, of which there are
some 1,114,015, according to Haskell. It’s usually safe to use an
infinite list with preface functions <br />
<code>λ> length ['a'..]</code> <br />
<code>1114015</code>
</span>
</p>
<pre class="code"><code><span class="org-haskell-definition">take</span> 27 <span class="org-rainbow-delimiters-depth-1">[</span><span class="org-string">'a'</span><span class="org-haskell-operator">..</span><span class="org-rainbow-delimiters-depth-1">]</span>
</code></pre>
<pre class="example">
abcdefghijklmnopqrstuvwxyz{
</pre>
<p>
This is a tool of Haskell’s that allows us to “enumerate” (fill in) a
pattern of list elements. And it should be no surprise that Haskell
has a type class, <code>Enum</code> to which types can register instances. <code>Enum</code>
has special method functions which create this behavior, this
enumeration-ness, for a data type. But before we talk about <code>Enum</code>,
let’s work with the more discrete math side of things.
</p>
</div>
<div id="outline-container-org50a7766" class="outline-3">
<h3 id="org50a7766">Enumeration is enumerating, counting, listing out…</h3>
<div class="outline-text-3" id="text-org50a7766">
<p>
…completing a numerical layout given certain conditions perhaps?
It’s a bit difficult to describe what enumeration is. To count
something might seem like a dynamic process. We take objects out of a
box and <i>count</i> how many there are — with each object increasing the
<a href="https://www.dictionary.com/browse/augend">augend</a>, the final augend being the answer. In simple language this is
finding a sum. But what if finding, e.g., a sum isn’t as simple as
just grabbing one after another out of a box? What if the grabbing
<i>and</i> the displaying, arranging, stacking on the table is complex and
involved? There are many situations that have very deep, very complex
grabbing, and arranging processes.
</p>
<p>
The simplest way to display a set is to literally list out each
element one by one. This is considered enumeration as well. Then
there’s the use of <i><font color = "#650d1c" size =
5%>ellipses (…)</font></i> to indicate we want elements
“filled out” according to some scheme we’re following. But here we
encounter LE issues, ambiguities. For example \(\{1,2,3,\ldots\}\;\)
could mean a listing of the counting numbers, or it might indicate the
<a href="https://en.wikipedia.org/wiki/Fibonacci_number">Fibonacci sequence</a> where each new number (beyond the first two) is the
previous two added together, i.e.,
\(\{1,2,3,5,8,13\ldots\}\;\;\)<label for="4" class="margin-toggle sidenote-number"></label><input type="checkbox" id="4" class="margin-toggle"/><span class="sidenote">
We’ll take apart how Haskell’s enumeration-ness class <code>Enum</code>
handles ranges just up ahead.
</span>.
</p>
</div>
</div>
</div>
<div id="outline-container-org9b4f2d4" class="outline-2">
<h2 id="org9b4f2d4">Natural numbers</h2>
<div class="outline-text-2" id="text-org9b4f2d4">
<p>
Sometime long ago somebody wondered, If I have something like a big
number — the biggest I can possibly imagine — doesn’t adding \(1\)
to that number result in a new biggest number? And in general, can’t
we say that starting from nothing, adding one more gets the <i>next</i>
number? There’s no Haskell <code>Next</code> class that we know of, but next-ness
is a curious beast indeed.
</p>
</div>
<div id="outline-container-org5052b66" class="outline-3">
<h3 id="org5052b66">The natural, whole, positive, counting numbers<label for="5" class="margin-toggle sidenote-number"></label><input type="checkbox" id="5" class="margin-toggle"/><span class="sidenote">
…with no bigodd nonsense about them — a phrase used
repeatedly by the character ironically called Sparkler in Charles
Dickens’ <i>Little Dorrit</i>.
</span></h3>
<div class="outline-text-3" id="text-org5052b66">
<p>
Taking a stab at a word definition of the natural counting numbers,
\(\mathbb{N}\), in a quasi-set notation style
</p>
\begin{align*}
\mathbb{N} = \{all\; the\; whole\; numbers\; starting\; with\; zero\}
\end{align*}
<p>
But what do we mean by <i>all</i> and <i>starting with</i>? And what about
order? Or are these whole numbers just in whatever order as long
as they’re <i>after</i> zero? Of course our intuitive understanding of what
counting numbers are saves us from silly hypothetical questions like
this, right?
</p>
</div>
</div>
<div id="outline-container-orge46d223" class="outline-3">
<h3 id="orge46d223">Peano’s approach to the natural numbers</h3>
<div class="outline-text-3" id="text-orge46d223">
<p>
The latter half of the nineteenth century saw mathematics going
through an intense effort to expand and deepen mathematical formalism
and exactness. Mathematicians wanted to firm up math’s logical
underpinnings, clean up sloppy, intuitive, hand-waving
half-understandings and put things on solid, unassailable logical
footing. One such mathematician was <a href="https://en.wikipedia.org/wiki/Giuseppe_Peano">Giuseppe Peano</a>.
</p>
<p>
Logical soul-searching led Peano to ask what exactly were the counting
numbers after all? Sure, there’s the Kindergarten version of
\(\mathbb{N}\;\), but was there something set-theoretic foundational
underneath just rattling off numbers like a child? After all, that’s
not much different from circus animals learning tricks.
</p>
<p>
Let’s warm up by considering what we said in the last section about
\(3\) being what comes after \(2\), which in turn comes after \(1\;\). In
effect, one number <i>succeeds</i> another. And so, in theory at least, we
could start at \(0\;\) and literally build a chain of <i>succeeds</i> up
to any number we want. This is like saying every journey starts with a
first step, followed by the next step, then the next, etc. Yes, this
may seen trivial, silly, but there’s a lot of math packed in this
concept.
</p>
</div>
<div id="outline-container-org422f4a7" class="outline-4">
<h4 id="org422f4a7">A first stab at a formalization</h4>
<div class="outline-text-4" id="text-org422f4a7">
<p>
Later we’ll go into a more detail about what a function is
set-theoretically, but to get started that brutalist interpretation of
functions you learned sometime after Kindergarten will do. So let’s
have the idea of one thing succeeding another housed in a <i>successor
function</i> \(S(n)\;\). And yet we won’t say something like
</p>
\begin{align*}
S(n) = n + 1
\end{align*}
<p>
because that would be too, well, brutalist.
</p>
<p>
For example, if we start at \(0\), the successor to \(0\) is \(1\;\), or
\(S(0) = 1\;\). But if we’re going to be highly abstract and pure about
this, we don’t want or need to connect this to any actual numerical
symbols of base\(_{10}\) like \(1\;\). So we’ll just use the usual numerical
symbols as reminders. Let’s So in order to Instead, we’ll just keep
reapplying the successor function \(S\;\) similar to nesting Russian
dolls<label for="6" class="margin-toggle sidenote-number"></label><input type="checkbox" id="6" class="margin-toggle"/><span class="sidenote">
Russian or <i>matryoshka</i> dolls: <br />
<img src="images/russiandolls.png" alt="russiandolls.png" /> <br />
<br />
</span>
</p>
\begin{align*}
0 &= 0 \\
1 &= S(0) \\
2 &= S(S(0)) \\
3 &= S(S(S(0))) \\
4 &= S(S(S(S(0)))) \\
\ldots
\end{align*}
<p>
Awkward? YMMV<label for="7" class="margin-toggle sidenote-number"></label><input type="checkbox" id="7" class="margin-toggle"/><span class="sidenote">
Your mileage may vary.
</span>. But we have to admit we’ve defined something akin
to the natural numbers using just the constant \(0\) and a successor
function applied to it. Now, let’s define addition on this system. To
do this we’ll use these two <i>identities</i>
</p>
\begin{align}
x + 0 &= x \\
x + s(y) &= s(x + y)
\end{align}
<p>
This should cover all possible cases of addition. Testing, let’s add
\(1\) and \(2\;\) or \(s(0) + s(s(0))\;\)
</p>
\begin{align}
s(0) + s(s(0)) &= \\
s(s(0) + s(0)) &= \\
s(s(s(0)) + 0) &= s(s(s(0)))
\end{align}
<ul class="org-ul">
<li>We apply (2) to (3) to get (4); in effect abstracting \(1+2\;\), the
left side of (2), to the <i>successor</i> of \(1+1\;\), the right side of
(2).</li>
<li>But now the inner part of (4), namely \(s(0) + s(0)\;\), resembles (2)
allowing us to match the first \(s(0)\) to \(x\) and the second to
\(s(y)\), which in turn allows us to rewrite it as \(s(s(0) +
0)\;\).</li>
<li>But according to (1) \(s(0) + 0 = s(0)\;\;\), leaving \(s(s(0))\;\)</li>
<li>Including back in the outermost \(s\) we now have \(s(s(s(0)))\;\) our
answer.</li>
</ul>
<p>
What have we accomplished with this convoluted method? For one, we’ve
reduced the entire idea of the natural numbers, along with adding two
of these reimagined natural numbers, to just a small set of symbols,
namely
</p>
<ul class="org-ul">
<li>a <i>constant</i> symbol \(0\)</li>
<li>variable symbols \(x\) and \(y\)</li>
<li>and a function symbol \(s\)</li>
</ul>
<p>
And with these four symbols we create statements made of <i>terms</i> built
from our symbols as in (1) and (2), e.g., \(x + 0\;\) is term, and
\(s(x + y)\;\) is another term. This allows us to state our problem as
terms, then <i>rewrite</i> these terms step-by-step as we did above to get
to a final term rewrite that is our answer. And so we have a <i>term
rewriting system</i> that provides addition of our natural
numbers<label for="8" class="margin-toggle sidenote-number"></label><input type="checkbox" id="8" class="margin-toggle"/><span class="sidenote">
Rewriting is basically what you do when you, e.g., take steps
to simplify or reduce a fraction. More on normal or canonical forms
later.
</span>. As Madhavan Mukund says<label for="9" class="margin-toggle sidenote-number"></label><input type="checkbox" id="9" class="margin-toggle"/><span class="sidenote">
<a href="https://www.cmi.ac.in/~madhavan/papers/pdf/programming-language-concepts.pdf">Mukund lecture notes</a>.
</span>
</p>
<div class="epigraph"><blockquote>
<p>
In a sense, rewriting is at the heart of all formulations of
computability — any computational device’s fundamental behaviour is
to read symbols and generate other symbols, which amounts to rewriting
the input as the output.
</p>
</blockquote></div>
<p>
So what’s the alternative? Your modern digital computer creates a
human-friendly world of numbers and addition with the help of base\(_{2}\)
binary numbers, computer circuit board logic gates, and lots and lots
of Assembler code to manage it all. Then come the higher languages
which present math as we normally see it, e.g., \(1 + 1 = 2\;\). When
seen in this light, we might begin to appreciate a very basic,
fundamental fact about modern computing, namely, <font color =
"#4715b3">we can create strategies to accomplish logical
calculations by manipulating (rewriting) <i>terms</i> built of
<i>symbols</i>.</font> Again, this adds a whole new dimension to
our age-old math world mix of scrolls, paper, books, pencils,
blackboards and chalk, and those mysterious mental representations of
math inside our human brains.
</p>
</div>
</div>
<div id="outline-container-org23d5bf0" class="outline-4">
<h4 id="org23d5bf0">A first look at induction and recursion<label for="10" class="margin-toggle sidenote-number"></label><input type="checkbox" id="10" class="margin-toggle"/><span class="sidenote">
At this point we can say induction and recursion (and
recurrence relations in general) are just two sides of the same
coin. Make sure you’ve got this <a href="http://learnyouahaskell.com/recursion">LYAHFGG’s Recursion</a> chapter under your
belt.
</span></h4>
<div class="outline-text-4" id="text-org23d5bf0">
<img src="./images/fallingdominoes.png" width="725px" style="padding: 15px 0px 0px 0px" alt="Induction example: dominoes falling" class="center">
<span class="cap">Example of induction: if one domino falls, so will the next.</span>
<p>
Simplistic as our natural number system in the previous section may
seem, there’s actually quite a bit of math theory to unpack to really
understand what just happened. When we build a number up from repeated
or nested application of the successor function \(s\) we were using the
ideas of <i>induction</i> and <i>recursion</i><label for="11" class="margin-toggle sidenote-number"></label><input type="checkbox" id="11" class="margin-toggle"/><span class="sidenote">
You may or may not have encountered induction. Typically, a
math course will introduce it as a proof strategy.
</span>.
</p>
<p>
Again, this may seem very simplistic, but the idea of induction is
inherent to the natural numbers. So if \(\mathbb{N}\;\) is also referred
to as the counting numbers, then we count or <i>enumerate</i> things with
them—going up as high as we need to
</p>
<table id="org4eb7195" border="2" cellspacing="0" cellpadding="6" rules="groups" frame="hsides">
<caption class="t-above"><span class="table-number">Table 1:</span> Enumeration of the first ten primes</caption>
<colgroup>
<col class="org-right" />
<col class="org-right" />
<col class="org-right" />
<col class="org-right" />
<col class="org-right" />
<col class="org-right" />
<col class="org-right" />
<col class="org-right" />
<col class="org-right" />
<col class="org-right" />
</colgroup>
<tbody>
<tr>
<td class="org-right">1</td>
<td class="org-right">2</td>
<td class="org-right">3</td>
<td class="org-right">4</td>
<td class="org-right">5</td>
<td class="org-right">6</td>
<td class="org-right">7</td>
<td class="org-right">8</td>
<td class="org-right">9</td>
<td class="org-right">10</td>
</tr>
<tr>
<td class="org-right">2</td>
<td class="org-right">3</td>
<td class="org-right">5</td>
<td class="org-right">7</td>
<td class="org-right">11</td>
<td class="org-right">13</td>
<td class="org-right">17</td>
<td class="org-right">19</td>
<td class="org-right">23</td>
<td class="org-right">29</td>
</tr>
</tbody>
</table>
<p>
Let’s make a quick look-up table in Haskell for Table 1
</p>
<pre class="code"><code>
<span class="org-haskell-definition">primeEnum</span> n <span class="org-haskell-operator">|</span> <span class="org-rainbow-delimiters-depth-1">(</span>n <span class="org-haskell-operator"><</span> 11<span class="org-rainbow-delimiters-depth-1">)</span> <span class="org-haskell-operator">&&</span> <span class="org-rainbow-delimiters-depth-1">(</span>n <span class="org-haskell-operator">></span> 0<span class="org-rainbow-delimiters-depth-1">)</span> <span class="org-haskell-operator">=</span> <span class="org-haskell-keyword">case</span> <span class="org-rainbow-delimiters-depth-1">(</span>n<span class="org-rainbow-delimiters-depth-1">)</span> <span class="org-haskell-keyword">of</span>
1 <span class="org-haskell-operator">-></span> 2
2 <span class="org-haskell-operator">-></span> 3
3 <span class="org-haskell-operator">-></span> 5
4 <span class="org-haskell-operator">-></span> 7
5 <span class="org-haskell-operator">-></span> 11
6 <span class="org-haskell-operator">-></span> 13
7 <span class="org-haskell-operator">-></span> 17
8 <span class="org-haskell-operator">-></span> 19
9 <span class="org-haskell-operator">-></span> 23
10 <span class="org-haskell-operator">-></span> 29
<span class="org-haskell-operator">|</span> otherwise <span class="org-haskell-operator">=</span> error <span class="org-string">"We only know the first ten primes."</span>
</code></pre>
<pre class="code"><code><span class="org-haskell-definition">primeEnum</span> 9
</code></pre>
<pre class="example">
23
</pre>
<p>
Mathematicians abstracted “the next one” by saying for any \(n \in
\mathbb{N}\;\), there will be a \(n+1 \in \mathbb{N}\;\;\) “next one after
\(n\;\)”. Myriad phenomena in life and math lend themselves to this
“if you’ve got this one, you can get next one” idea.
</p>
<p>
𝖟𝕭<label for="12" class="margin-toggle sidenote-number"></label><input type="checkbox" id="12" class="margin-toggle"/><span class="sidenote">
<b>zB</b>: German abbreviation for <i>zum Beispiel</i>, or for example.
</span>: A classic proof using mathematical induction is the
proposition<label for="13" class="margin-toggle sidenote-number"></label><input type="checkbox" id="13" class="margin-toggle"/><span class="sidenote">
Propositions are statements or assertions that can be proven
to be either true or false. Make sure you went down <a href="https://math.libretexts.org/Courses/Monroe_Community_College/MTH_220_Discrete_Math/2%3A_Logic/2.1%3A_Propositions">this rabbit hole</a>.
</span>
</p>
\begin{align*}
P(n) = 0 + 1 + 2 + 3 + \ldots + n = \frac{n(n+1)}{2}
\end{align*}
<p>
To be clear, we’re not <i>deriving</i> this formula<label for="14" class="margin-toggle sidenote-number"></label><input type="checkbox" id="14" class="margin-toggle"/><span class="sidenote">
The story behind this formula is interesting. See <a href="https://letstalkscience.ca/educational-resources/backgrounders/gauss-summation">this</a> for the
backstory. Note the formula is <br />
\begin{align*}
\frac{\text{(number of pairs)} ⋅ \text{(sum of each pair)}}{2}
\end{align*} <br />
</span>, we’re
attempting to <i>prove</i> it. So for example if we add the first three
numbers, according to the formula we should get \(6\;\)
</p>
\begin{align*}
\frac{(3)(3+1)}{2} = \frac{(12)}{2} = 6
\end{align*}
<p>
An induction proof is a two-step process: a <i>base case</i> and an
<i>induction step</i>
</p>
<p>
<b>Base case</b>: \(P(0)\)
</p>
<p>
\(P(0)\;\) is trivial. Just plug in \(0\)
</p>
\begin{align*}
\frac{(0)(0+1)}{2} = \frac{(0\cdot1)}{2} = 0
\end{align*}
<p>
<b>Inductive step</b>: Now we have to consider \(n \gt 0\;\) cases. The whole
idea is to show that for any number \(k \ge 0\;\), if \(P(k)\;\) works, so
will \(P(k+1)\;\)
</p>
<p>
We start by assuming what is called the <i>induction hypothesis</i>, i.e.,
that our statement \(P\) will hold for \(P(n)\;\). Here we’re saying for
the unique case when \(n = k\;\) that \(P(k)\;\) is true
</p>
\begin{align}
0 + 1 + 2 + \ldots + k = \frac{k(k+1)}{2}
\end{align}
<p>
Good. Now we want to consider \(P(k+1)\;\). We’ll just add it on both
sides since it is the next step after \(k\;\)
</p>
\begin{align*}
(0 + 1 + 2 + \ldots + k) + (k + 1) = \frac{k(k+1)}{2} + (k+1)
\end{align*}
<p>
Now, we consider just the right side of this equation and do some
algebraic manipulation
</p>
\begin{align*}
\frac{k(k+1)}{2} + (k+1) &= \frac{k(k+1)}{2} + \frac{2(k+1)}{2} \\
&= \frac{k(k+1)+2(k+1)}{2}
&= \frac{(k+1)(k+2)}{2}
&= \frac{(k+1)((k+1)+1)}{2}
\end{align*}
<p>
Going back to our original left-hand side
</p>
\begin{align}
(0 + 1 + 2 + \ldots + k) + (k + 1) = \frac{(k+1)((k+1)+1)}{2}
\end{align}
<p>
Now, compare (6) with (7). On the left-hand side of (7) we have the
next step \((k+1)\;\) and on the right-hand side of (7) we have in the
numerator the “number of pairs” increased from \(k\;\) to \(k+1\;\) and
the “sum of each pair” likewise increased by \(1\;\) from \(k+1\) to \(k +
1 + 1\;\). Through algebraic manipulation we have proved that “the next
one” will indeed increase as we might want it to. For example, if we
total the first ten numbers
</p>
\begin{align*}
\text{Total sum} = \frac{10 \cdot 11}{2}
\end{align*}
<p>
and totalling the next number \(11\) will just be
</p>
\begin{align*}
\text{Total sum} = \frac{11 \cdot 12}{2}
\end{align*}
<p>
which is covered in our proof for <i>any</i> \(k+1\;\).
</p>
</div>
</div>
<div id="outline-container-org8084541" class="outline-4">
<h4 id="org8084541">The “missing number” question</h4>
<div class="outline-text-4" id="text-org8084541">
<p>
We’ll do a Haskell example where Gauss’ summing formula will be of
use.
</p>
<p>
<font color = "#4715b3">
⇲ In a sequence on natural numbers \(1 \ldots n\;\) one of the numbers \(k\;\)
is missing, e.g., \(1, \ldots, k-1, k+1, \ldots, n\;\). Find which
number it is.
</font>
</p>
<p>
If we have a relatively short list we can no doubt spot it, e.g.,
\(1,2,4,5\;\); obviously \(3\;\) is missing. But what if our sequence is
thousands of numbers long. For example, with Haskell’s list completion
we can create a list representing a very big sequence
</p>
<pre class="code"><code><span class="org-rainbow-delimiters-depth-1">[</span>1<span class="org-haskell-operator">..</span>100<span class="org-rainbow-delimiters-depth-1">]</span>
</code></pre>
<pre class="example">
[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]
</pre>
<p>
Still doable, but for a sequence going from \(1\) to \(1,000\) it would be
hard to spot the missing number. One solution would be to recurse
through the list testing each number that it was the next after the
previous
</p>
<pre class="code"><code><span class="org-haskell-constructor">:</span><span class="org-rainbow-delimiters-depth-1">{</span>
<span class="org-haskell-definition">missingNumberGen</span> n m <span class="org-haskell-operator">|</span>
<span class="org-haskell-constructor">:</span><span class="org-rainbow-delimiters-depth-1">}</span>
</code></pre>
<pre class="code"><code><span class="org-haskell-constructor">:</span><span class="org-rainbow-delimiters-depth-1">{</span>
<span class="org-haskell-definition">missingTest1</span> xs
<span class="org-haskell-constructor">:</span><span class="org-rainbow-delimiters-depth-1">}</span>
</code></pre>
</div>
</div>
<div id="outline-container-org5889dcc" class="outline-4">
<h4 id="org5889dcc">Recurrence relations</h4>
<div class="outline-text-4" id="text-org5889dcc">
<p>
For example, what if we add up the first three
consecutive odd numbers
</p>
<p>
Peano postulated <i>axioms</i>,
givens, starting points. Using set theory methods, he attempted to
</p>
<p>
According to a modern treatment, there are five basic Peano axioms<label for="15" class="margin-toggle sidenote-number"></label><input type="checkbox" id="15" class="margin-toggle"/><span class="sidenote">
Peano actually had nine axioms; however, four of these deal
with the equality of his natural numbers, which we’ll deal with later
when we explore <i>relations</i>, a more general concept above functions.
</span>. The
first axiom states
</p>
<ol class="org-ol">
<li><font color = "#4715b3">\(0\) is a natural number, i.e., \(0
\in \mathbb{N}\) </font></li>
</ol>
<p>
This is our starting point. Peano then gives four axioms to establish
<i>equality</i>
</p>
<ol class="org-ol">
<li value="2"><font color = "#4715b3"> For every natural number
\(n\), \(S(n)\;\) is a natural number. That is, the natural numbers
are closed under \(S\;\). Or \(x \in \mathbb{N} \rightarrow Sx \in \mathbb{N}\;\;\).
</font></li>
</ol>
<ol class="org-ol">
<li><font color = "#4715b3">For all natural numbers x and y, if x = y, then y = x. That is, equality is symmetric.</font>
<ol class="org-ol">
<li></li>
</ol></li>
</ol>
</div>
</div>
</div>
<div id="outline-container-org42e273c" class="outline-3">
<h3 id="org42e273c">Closures</h3>
<div class="outline-text-3" id="text-org42e273c">
<p>
From the <i>LibreTexts series</i> on Discrete Mathematics, we saw the
concept of <i><a href="https://math.libretexts.org/Courses/Monroe_Community_College/MTH_220_Discrete_Math/1%3A_Introduction_to_Discrete_Mathematics/1.5%3A_Introduction_to_Sets_and_Real_Numbers">sets</a></i> and how they formalize our ideas about
numbers. Again, think of the <i>set</i> of natural numbers. In set notation
we can list just a few <i>consecutive</i>, <i>distinct</i> numbers, then rely on
ellipses, (…), to indicate “continue with this consecutive, distinct
number pattern”
</p>
\begin{align*}
\mathbb{N} = \{0,1,2,3,\ldots \}
\end{align*}
<p>
This is a more abstract and probably more precise set notation for
\(\mathbb{N}\;\) than the previous word-based one. But again we’re
assuming ordinality without actually defining it. And notice how our
\(\mathbb{N}\;\) depiction contains no negative numbers<label for="16" class="margin-toggle sidenote-number"></label><input type="checkbox" id="16" class="margin-toggle"/><span class="sidenote">
Some treatments do not consider zero a natural counting number
and use \(\mathbb{N}_0\) to symbolize the natural numbers <i>including</i>
zero.
</span>. Again,
what consequence does that have on doing arithmetic on \(\mathbb{N}\;\)?
For one, how would we do subtraction? Won’t that crash if we try to
take a bigger number from a smaller number<label for="17" class="margin-toggle sidenote-number"></label><input type="checkbox" id="17" class="margin-toggle"/><span class="sidenote">
Supposedly, the idea of negative numbers came from the banking
world of the medieval age. So if I give you something that costs three
ducats and you only have two, then you <b>owe</b> me one ducat.
</span>? Subtraction is a
<i>binary operation</i><label for="18" class="margin-toggle sidenote-number"></label><input type="checkbox" id="18" class="margin-toggle"/><span class="sidenote">
We’ll have more to say about binary operations when we look
into functions.
</span> of taking one amount from another. Asking in
higher-math-speak, <font color = "#4715b3">does the
binary operation of subtractions on all possible pairs of \(\mathbb{N}\)
yield results that <i>stay inside of</i> \(\mathbb{N}\;\)?</font>
</p>
\begin{align*}
\{(b -a) \in\,\mathbb{N}\; |\; a \in \mathbb{N},\: b \in \mathbb{N}\}
\end{align*}
<p>
or generally, where \(\circ\) means any sort of operator, e.g., \(+\),
\(-\), \(\div\), etc.
</p>
\begin{align*}
\{ \}
\end{align*}
<p>
Apparently not.
</p>
<p>
In more formal language, <font color = "#4715b3">the binary
operation of subtraction <i>on</i> (the members of) some set \(S\) will
assign to each and every possible pair \(a, b \in S\;\) a unique element
\(c \in S\) where \(c = a - b\). </font> That is, a binary
operation combines any two elements of the set to produce a third
element of that same set.
</p>
<p>
If you study this wording closely, it is definitely saying there can
be no such binary operator subtraction on \(\mathbb{N}\) because \(c\) can
definitely fall outside of \(\mathbb{N}\) —as it does when, e.g., \(a =
6\) and \(b = 10\;\).<label for="19" class="margin-toggle sidenote-number"></label><input type="checkbox" id="19" class="margin-toggle"/><span class="sidenote">
Peruse <a href="https://math.libretexts.org/Bookshelves/Abstract_and_Geometric_Algebra/First-Semester_Abstract_Algebra%3A_A_Structural_Approach_(Sklar)/02%3A_Groups/2.01%3A_Binary_Operations_and_Structures">this</a> treatment of binary operations. Again, we’ll dive
in deeper later.
</span> In math-speak, a binary operation \(a
\circ b\;\) must be <i>well-defined</i> and <i>inside of</i> \(S\)
</p>
<p>
\(\mathfrak{Fazit}\:\): The binary operation of subtraction is <i>not</i>
<b>closed</b> on \(\mathbb{N}\;\).
</p>
<p>
(Proof of addition on \(\mathbb{N}\;\)?)
</p>
<p>
Semigroups
</p>
</div>
</div>
<div id="outline-container-orgad3828f" class="outline-3">
<h3 id="orgad3828f">Unary numeral system</h3>
<div class="outline-text-3" id="text-orgad3828f">
<p>
There is the <i><a href="https://en.wikipedia.org/wiki/Unary_numeral_system">unary numeral system</a></i> (UNS) where numbers are
represented in a <i>unary</i><label for="20" class="margin-toggle sidenote-number"></label><input type="checkbox" id="20" class="margin-toggle"/><span class="sidenote">
Unfortunately, <i>unary</i> here has two meanings. It means we’re
only using one numeral to do our counting, <i>and</i> it indicates a unary
function, i.e., a function that takes only one value and returns only
something from its domain—which is a very abstract version of the
idea of a <i>unary operator</i> where only one thing is operated on. For
example, addition is a <i>binary operation</i> since it takes <i>two</i> numbers
and adds them. But making a number a negative number by placing the
negative sign in front of the number is an example of a unary
operation.
</span> way, e.g., one is \(1\), two is \(11\),
three is \(111\), et cetera. The UNS system is not really positional,
i.e., the column of a \(1\) is immaterial since the \(1\)’s are completely
interchangeable—although when we want to go up a number, we do have
to move everything over one column. But again, the columns do not
indicate anything numerically as columns do with, e.g., our decimal
system<label for="21" class="margin-toggle sidenote-number"></label><input type="checkbox" id="21" class="margin-toggle"/><span class="sidenote">
More on the <i>binary</i> number system later.
</span>.
</p>
<p>
How would we add or subtract in our UNS system? Ironically, we could
invent a sort of columnar subtracting borrowing from decimal vertical
subtraction
</p>
\begin{array}{r}
&11111\\
-\!\!\!\!\!\!&11\\
\hline
&11100
\end{array}
<p>
then we just throw out the zeroes and count up the ones. But we can’t
really do addition vertically. Perhaps not vertically but
horizontally
</p>
\begin{align*}
11111 + 11 = 1111111
\end{align*}
<p>
We could also remove the \(+\) and run together or <i>concatenate</i> the
\(1\)’s. More on concatenation later.
</p>
<p>
Next, we write some Haskell code to do UNS subtraction<label for="22" class="margin-toggle sidenote-number"></label><input type="checkbox" id="22" class="margin-toggle"/><span class="sidenote">
Make sure you’ve got past Chapter 6, <i>Higher Order Functions</i>
in LYAHFGG.
</span>
</p>
</div>
<div id="outline-container-org2029de2" class="outline-5">
<h5 id="org2029de2">UNS Subtraction</h5>
<div class="outline-text-5" id="text-org2029de2">
<p>
Turning math into code means we must first decide which data structure
to use. For our string of \(1\)’s we will use the Haskell <i>list</i> data
structure. This may seem ironic to a budding mathematician who
went down the set theory rabbit holes above. Yes, so much of math can
be seen as <i>set theory</i>-based. And no, a list is not a set. And yes,
Haskell has a library for sets. But as beginners we will simulate sets
with lists<label for="23" class="margin-toggle sidenote-number"></label><input type="checkbox" id="23" class="margin-toggle"/><span class="sidenote">
We could also represent our \(1\)’s as a string, i.e., like text
between double-quotes, but any string in Haskell is just a list of the
text’s individual characters, e.g., <code>"1111"</code> is really just
<code>['1','1','1','1']</code>.
</span>. This means our set of \(1\)’s will be represented as
a list with the integer \(1\) repeated as its elements, e.g.,
<code>[1,1,1,1,1]</code> is \(11111\).
</p>
<p>
First we’ll try a really primitive way to do UNS subtraction
</p>
<ul class="org-ul">
<li>Put \(1\)’s into lists,</li>
<li>Apply the built-in list element counter function, <a href="http://zvon.org/other/haskell/Outputprelude/length_f.html">length</a>, on each to
count the number of \(1\)’s in each,</li>
<li>Subtract one from the other.</li>
</ul>
<p>
Not very enlightening, but it works
</p>
<pre class="code"><code><span class="org-rainbow-delimiters-depth-1">(</span>length <span class="org-rainbow-delimiters-depth-2">[</span>1,1,1,1<span class="org-rainbow-delimiters-depth-2">]</span><span class="org-rainbow-delimiters-depth-1">)</span> <span class="org-haskell-operator">-</span> <span class="org-rainbow-delimiters-depth-1">(</span>length <span class="org-rainbow-delimiters-depth-2">[</span>1,1<span class="org-rainbow-delimiters-depth-2">]</span><span class="org-rainbow-delimiters-depth-1">)</span>
</code></pre>
<pre class="example">
2
</pre>
<p>
We can write our own function <code>uns1</code> for this taking two values as
input
</p>
<pre class="code"><code><span class="org-haskell-definition">uns1</span> list1 list2 <span class="org-haskell-operator">=</span> <span class="org-rainbow-delimiters-depth-1">(</span>length list1<span class="org-rainbow-delimiters-depth-1">)</span> <span class="org-haskell-operator">-</span> <span class="org-rainbow-delimiters-depth-1">(</span>length list2<span class="org-rainbow-delimiters-depth-1">)</span>
</code></pre>
<pre class="code"><code><span class="org-haskell-definition">uns1</span> <span class="org-rainbow-delimiters-depth-1">[</span>1,1,1,1<span class="org-rainbow-delimiters-depth-1">]</span> <span class="org-rainbow-delimiters-depth-1">[</span>1,1<span class="org-rainbow-delimiters-depth-1">]</span>
</code></pre>
<pre class="example">
2
</pre>
<p>
Now, let’s create a better function utilizing Haskell’s type and
recursion features
</p>
<pre class="code"><code><span class="org-haskell-definition">unsSub2</span> <span class="org-haskell-operator">::</span> <span class="org-rainbow-delimiters-depth-1">[</span>a<span class="org-rainbow-delimiters-depth-1">]</span> <span class="org-haskell-operator">-></span> <span class="org-rainbow-delimiters-depth-1">[</span>a<span class="org-rainbow-delimiters-depth-1">]</span> <span class="org-haskell-operator">-></span> <span class="org-rainbow-delimiters-depth-1">[</span>a<span class="org-rainbow-delimiters-depth-1">]</span>
<span class="org-haskell-definition">unsSub2</span> l1x l2x <span class="org-haskell-operator">|</span> null l1x <span class="org-haskell-operator">=</span> l2x
<span class="org-haskell-operator">|</span> null l2x <span class="org-haskell-operator">=</span> l1x
<span class="org-haskell-definition">unsSub2</span> <span class="org-rainbow-delimiters-depth-1">(</span>l1<span class="org-haskell-constructor">:</span>l1x<span class="org-rainbow-delimiters-depth-1">)</span> <span class="org-rainbow-delimiters-depth-1">(</span>l2<span class="org-haskell-constructor">:</span>l2x<span class="org-rainbow-delimiters-depth-1">)</span> <span class="org-haskell-operator">=</span> unsSub2 l1x l2x
</code></pre>
<p>
We’re relying on Haskell’s pattern matching and guards to accomplish
loop-like behavior … a lot at once.
</p>
<p>
It seems to work when the subtrahend is smaller than the minuend
</p>
<pre class="code"><code><span class="org-haskell-definition">unsSub2</span> <span class="org-rainbow-delimiters-depth-1">[</span>1,1,1,1,1,1<span class="org-rainbow-delimiters-depth-1">]</span> <span class="org-rainbow-delimiters-depth-1">[</span>1,1,1,1,1<span class="org-rainbow-delimiters-depth-1">]</span>
</code></pre>