-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathnumbers1.html
2116 lines (1853 loc) · 117 KB
/
numbers1.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-12-04 Sun 21:26 -->
<meta http-equiv="Content-Type" content="text/html;charset=utf-8" />
<meta name="viewport" content="width=device-width, initial-scale=1" />
<title>Numbers</title>
<meta name="generator" content="Org Mode" />
<link rel="stylesheet" href="./tufte.css" type="text/css">
<style> .title { display: none; } </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-tex',
displayOverflow: 'overflow'
}
};
</script>
<script
id="MathJax-script"
async
src="https://cdn.jsdelivr.net/npm/mathjax@2/MathJax.js?config=TeX-AMS_HTML">
</script>
</head>
<body>
<div id="content" class="content">
<h1 class="title">Numbers</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-org6aea065" class="outline-2">
<h2 id="org6aea065">Numbers</h2>
</div>
<div id="outline-container-org8af822f" class="outline-2">
<h2 id="org8af822f">Thursday at the library</h2>
<div class="outline-text-2" id="text-org8af822f">
<p>
It’s Thursday afternoon and the von der Surwitz siblings meet in their
reserved study room at the main university library to go over
Wednesday’s lecture and examples. After Wednesday’s class, they’re
glad they and the other ItCS participants had met with Professor
Chandra at the Novalis Tech Open House two weeks prior to the start of
school and had gotten a heads-up on what was ahead, including her
repository. As a result they all had gone down the minimal
prerequisite rabbit holes and were more or less ready.
</p>
<p>
Ursula von der Surwitz has plugged in her laptop to the big monitor
and is scrolling through Professor Chandra’s first substantive lecture
on Wednesday of the first week of classes<label for="1" class="margin-toggle sidenote-number"></label><input type="checkbox" id="1" class="margin-toggle"/><span class="sidenote">
This is also on her GitHub repository.
</span>.
</p>
<p>
⌜…<br />
For most of us our first experience with the abstraction power of
numbers begins when our parents teach us to hold up three fingers to
show everyone we’re three years old. And so we were introduced to the
idea of seeing an abstract numerical magnitude such as the number
three as a mapping or connection of three fingers to three years of
life.
</p>
<p>
Then at some point we learn what mathematician Eugenia Cheng<label for="2" class="margin-toggle sidenote-number"></label><input type="checkbox" id="2" class="margin-toggle"/><span class="sidenote">
See her popular layman’s book <i>How To Bake \(\pi\;\)</i>. One
interesting aspect of this book is her treatment of <i>category theory</i>,
which is a superset of type theory, much of which is baked into
Haskell.
</span>
calls the “counting poem,” i.e., we learn how to count from one to
ten, usually on our fingers. And about this time we learn to negotiate
numerically, like when we said, <i>I’ll give so many of these if you
give me so many of that</i>. But then begins formal school math, and each
year math becomes progressively less interesting, less popular — to
the point of being a hated subject. This in my opinion is due to the
curriculum being based on conditioned learning, the <i>when you see
this, do this</i> method … unfortunately.
</p>
<p>
But if you major in math in college you eventually start to see in the
later years<label for="3" class="margin-toggle sidenote-number"></label><input type="checkbox" id="3" class="margin-toggle"/><span class="sidenote">
In many places in the world the typical American college
Freshman-Sophomore math sequence of calculus, diff-eqs, and linear
algebra is completed at the college-prep level. For example, Germany
and Switzerland have college freshmen starting with Analysis.
</span> — after the four Freshman and Sophomore semesters
of calculus, differential equations, and linear algebra — what is
commonly called “higher math.” And these upper-semester math courses
can be a complete reboot of math, weeding out vague, ad hoc,
<i>parochial</i><label for="4" class="margin-toggle sidenote-number"></label><input type="checkbox" id="4" class="margin-toggle"/><span class="sidenote">
<b>parochial</b>: … very limited or narrow in scope or outlook;
provincial…
</span> notions, replacing them with a rigorous,
theoretical, formalistic, foundational understanding of math. As
mathematician Joe Fields says, this is when you stop being a “see
this, do this” calculator and become a prover, i.e., a deeper thinker
about math.
</p>
<p>
<i><a href="https://en.wikipedia.org/wiki/Set_theory">Set theory</a></i> is a big part of this formalism<label for="5" class="margin-toggle sidenote-number"></label><input type="checkbox" id="5" class="margin-toggle"/><span class="sidenote">
Make sure you’re attacking the <i>LibreTexts</i> series, e.g.,
one of the first three rabbit holes in the math section.
</span>. Set theory is an
exacting, don’t-take-stuff-for-granted world, which turns out to be
good for the computer world as well since computer circuits don’t
attend human grade school, don’t learn poems, and don’t have
fingers<label for="6" class="margin-toggle sidenote-number"></label><input type="checkbox" id="6" class="margin-toggle"/><span class="sidenote">
If machines were capable of conditioned learning, your car
should be able to self-drive certain oft-travelled routes, e.g., from
your home to the grocery store.
</span>. Again, if you want a computer to understand something,
you have to spell it out in very precise and exacting ways. That is to
say, you’re always facing <i>logical entailment</i> (LE) with computers. So
how then <i>does</i> a computer understand numbers? And isn’t a computer
doing numbers the same way a clock does time? Think about it. Does a
ticking clock that you have to wind up have any real concept of time?
No, it doesn’t.
</p>
<p>
One fascinating twist of mathematical history is how, on the whole,
the Greeks seemed to favor geometry over numbers. Their mastery of
geometry really got going with <a href="https://en.wikipedia.org/wiki/Euclid%27s_Elements">Euclid’s Elements</a> ca. 300 BC, which
starts with just a point and a line and from there builds up expansive
theorems about complex geometric shapes, i.e., no numbers<label for="7" class="margin-toggle sidenote-number"></label><input type="checkbox" id="7" class="margin-toggle"/><span class="sidenote">
It was a long-revered feat of logical minimalism that all
two-dimensional shapes in <i>Elements</i> could be produced with just a
compass and a straightedge. Follow the Wikipedia link and note the
animation of <a href="https://en.wikipedia.org/wiki/Euclid%27s_Elements#/media/File:HexagonConstructionAni.gif">the construction of a hexagon</a>. It wasn’t until the
development of calculus and infinitesimal methods in the Renaissance
that this compass-and-stick purity was set aside.
</span>. Even
when Euclid’s geometry worked with the concepts of length and angles,
no numbers were employed<label for="8" class="margin-toggle sidenote-number"></label><input type="checkbox" id="8" class="margin-toggle"/><span class="sidenote">
Later we’ll explore how Descartes united algebra and geometry.
</span>. And as the physicist Julian Barbour
said, A triangle is known for its shape not its size.
</p>
<p>
This week we’ll talk about numbers in a fairly theoretical but not
really difficult manner. Along with the math, we’ll do some work with
Haskell that you should be ready for<label for="9" class="margin-toggle sidenote-number"></label><input type="checkbox" id="9" class="margin-toggle"/><span class="sidenote">
Make sure you’re getting along with the Haskell rabbit hole materials — at
the very least worked through half of LYAHFFG.
</span>. <br />
…⌟
</p>
<p>
<span class="fraktur">𝔘𝔯𝔰𝔲𝔩𝔞:</span> So like
Professor Chandra said yesterday, we need to see things in terms of
set theory from here on out. <br />
[murmurs of agreement] <br />
<span class="fraktur">𝔘𝔴𝔢:</span> And like she said,
with set theory we can properly define relations and function. All of
which sounds rather ominous. Like everything we thought we knew was
about to go away.<br />
[more agreement murmurs] <br />
<span class="fraktur">𝔘𝔯𝔰𝔲𝔩𝔞:</span> [continuing] So
here’s her breakdown of what she called number classification or
taxonomy. [scrolling…] <br />
</p>
<p>
⌜…
</p>
<ul class="org-ul">
<li>\(\mathbb{N}\;\): the <i>natural</i> counting numbers, often starting with
\(0\;\); otherwise, with \(1\;\).</li>
<li>\(\mathbb{Z}\;\): whole number <i>integers</i> — just like \(\mathbb{N}\;\)
but with the positive numbers duplicated as negative numbers, along
with \(0\;\) between them.</li>
<li>\(\mathbb{Q}\;\): the <i>rational</i> numbers — composed as
\(\frac{a}{b}\;\) where \(a\) and \(b\) are integers and \(b\) cannot be
\(0\;\) — although this is really too simple and we’ll be expanding
on it later.</li>
<li>\(\mathbb{R}\;\): the <i>real</i> numbers are the limit of a convergent
sequence of rational numbers… Really? Yes, but this is a higher
math sort of definition. Suffice it to say for now reals are the
rational numbers (including recurring decimals) along with
<b>ir</b>-rational numbers (non-recurring decimals), e.g., the square
root of \(2\;\). In other words, numbers that are expressed with
decimals<label for="10" class="margin-toggle sidenote-number"></label><input type="checkbox" id="10" class="margin-toggle"/><span class="sidenote">
Two questions: Are repeating decimal numbers also rational? If
yes, then why can’t rational numbers represent all numbers? That is,
why do we need real and complex numbers? Programming challenge: Write
a function that takes a real decimal number and figures out its
fraction, e.g. \(3.14\) is \(157/50\:\). Does Haskell have a built-in way
to do this? Hint: Check out <a href="https://rosettacode.org/wiki/Convert_decimal_number_to_rational#Haskell">Convert decimal number to rational</a>. Maybe
compare with how Julia and Racket do it.
</span>. <i>Lots</i> more to come…</li>
<li>\(\mathbb{C}\;\): the <i>complex</i> numbers are of the form \(a + bi\;\)
where \(a\) and \(b\) are real numbers and \(i\) is the square root of
\(-1\;\). Again, lots more later.</li>
</ul>
<p>
…⌟
</p>
<p>
<span class="fraktur">𝔘𝔴𝔢:</span> Right. We’re not
supposed to worry about this too much yet; we’ll go into it more
later. Just realize that we’re talking about the <i>set</i> of natural
numbers, the <i>set</i> of real numbers, et cetera. <br />
[murmurs of agreement] <br />
<span class="fraktur">𝔘𝔱𝔢:</span> Their traits and
properties, as she said. And the fact that each number “species” is a
subset of the next one up [writing on the whiteboard]
</p>
\begin{align*}
\mathbb{N} \subset \mathbb{Z} \subset \mathbb{Q} \subset \mathbb{R}\ \subset \mathbb{C}
\end{align*}
<p>
<span class="fraktur">𝔘𝔱𝔢:</span> [continuing] One
is contained by the other. <br />
<span class="fraktur">𝔘𝔴𝔢:</span> [paging through
his written notes] Then she once more drove home the point that set
theory is important [quoting]
</p>
<p>
⌜… <br />
Set theory is the basic foundation of math, and is fundamental to the
discrete math of computer science. But there’s a new kid is on the
block, namely, <i>category theory</i>, which is even more foundational than
set theory. With Haskell we’ll encounter some of the rudiments of
category theory now and then. <br />
…⌟
</p>
<p>
<span class="fraktur">𝔘𝔴𝔢:</span> Anybody know what
that means? <br />
<span class="fraktur">𝔘𝔯𝔰𝔲𝔩𝔞:</span> We all watched
the video? [clicking on <a href="https://youtu.be/ZG6t0-JMrw0">this</a> YouTube link] Did you all watch it? <br />
<span class="fraktur">𝔘𝔱𝔢:</span> Ahhh, yes, but I
can tell I’m a long way from really getting it, or why it’s such a big
deal. <br />
<span class="fraktur">𝔘𝔴𝔢:</span> So we see a bunch
of stuff we supposedly already know being repackaged in a way that
uncovers how we really only had a superficial understanding of the
concepts. <br />
[laughter] <br />
<span class="fraktur">𝔘𝔯𝔰𝔲𝔩𝔞:</span> I watched it,
but it’ll take some time to sink in because [nodding to Uwe] on one
level I guess I understood, but I don’t think I caught what the whole
point was<label for="11" class="margin-toggle sidenote-number"></label><input type="checkbox" id="11" class="margin-toggle"/><span class="sidenote">
Professor Chandra connected this to Haskell by mentioning
Haskell’s “point-free” programming … but didn’t elaborate.
</span>. I suppose that’s coming as well. <br />
<span class="fraktur">𝔘𝔱𝔢:</span> But wasn’t it a
bit ominous the way she said this is higher math — if not grad
school stuff? But we’re not supposed to be intimidated! No! At least
not yet. <br />
[nods and laughter] <br />
<span class="fraktur">𝔘𝔴𝔢:</span> Like they’ve been
saying, we’re <i>Versuchskaninchen</i>. <br />
[laughter] <br />
<span class="fraktur">𝔘𝔱𝔢:</span> Guinea pigs. No,
but I’m getting the impression this could be a great course. <br />
[nods]
</p>
</div>
</div>
<div id="outline-container-org84e44b4" class="outline-2">
<h2 id="org84e44b4">Numbers in Haskell</h2>
<div class="outline-text-2" id="text-org84e44b4">
<p>
<span class="fraktur">𝔘𝔯𝔰𝔲𝔩𝔞:</span> [scrolling] So
we then come to Haskell’s version of the numbers. <br />
[all study the screen] <br />
<span class="fraktur">𝔘𝔱𝔢:</span> Which is supposed
to be close to the whole mathematical taxonomy. <br />
</p>
<p>
⌜…
</p>
<ul class="org-ul">
<li><code>Int</code>: limited-precision integers in at least the range \([-2^{29} ,
2^{29})\;\).</li>
<li><code>Integer</code>: arbitrary-precision integers (read <i>lots</i> of integers,
lots more than <code>Int</code>).</li>
<li><code>Rational</code>: arbitrary-precision rational numbers.</li>
<li><code>Float</code>: single-precision floating-point numbers.</li>
<li><code>Double</code>: double-precision floating-point numbers</li>
<li><code>Complex</code>: complex numbers as defined in <code>Data.Complex</code>.</li>
</ul>
<p>
…⌟
</p>
<p>
<span class="fraktur">𝔘𝔯𝔰𝔲𝔩𝔞:</span> And she tells
us not to worry about what <i>precision</i> and <i>floating-point</i> mean for
the time being. <br />
<span class="fraktur">𝔘𝔱𝔢:</span> Right, because
they’re part of how the electrical logic circuits do numbers. The
whole “logical entailment” of doing numbers on an electric machine
thing. <br />
[murmurs of agreement] <br />
<span class="fraktur">𝔘𝔴𝔢:</span> And we’re not to
worry about natural numbers yet. We’ll do those separate. <br />
[murmurs of agreement] <br />
</p>
</div>
</div>
<div id="outline-container-orgb86acaa" class="outline-2">
<h2 id="orgb86acaa">The qualities of quantity</h2>
<div class="outline-text-2" id="text-orgb86acaa">
<p>
<span class="fraktur">𝔘𝔯𝔰𝔲𝔩𝔞:</span> [scrolling] So
here’s more.
</p>
<p>
⌜… <br />
A number is a concept, first and foremost a symbol related to
<i>quantity</i> and <i>magnitude</i>. And as such a number has great powers of
abstraction. Numbers may be applied in the abstraction exercises of
counting or enumerating, as well as measuring things<label for="12" class="margin-toggle sidenote-number"></label><input type="checkbox" id="12" class="margin-toggle"/><span class="sidenote">
But then measuring must be “quantified” by counting unit-wise
what was measured; hence, everything comes back to counting. This will
come up when we explore real numbers versus rational numbers.
</span>.
</p>
<img src="./images/threediagram1.png" style="padding: 10px 0px 0px 0px" width="280" alt="Diagram of three" class="center">
<span class="cap">The concept, the embodiment of three and "three-ness"</span>
<p>
Consider these <i>qualities</i> of quantities
</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>
As we’ve said, when we bring the computer into this quantification
game, we cannot assume these basic qualities as given<label for="13" class="margin-toggle sidenote-number"></label><input type="checkbox" id="13" class="margin-toggle"/><span class="sidenote">
Inside your head you automatically know how many and in what
order the numbers \(1\) through \(10\) are. However, a computer must be
taught such basic quantitative qualities.
</span>. <br />
…⌟
</p>
<p>
<span class="fraktur">𝔘𝔯𝔰𝔲𝔩𝔞:</span> [continuing]
Any thoughts, questions? <br />
[all study the screen] <br />
<span class="fraktur">𝔘𝔱𝔢:</span> Let’s go on.
</p>
</div>
<div id="outline-container-org01ccaf4" class="outline-3">
<h3 id="org01ccaf4">Cardinality</h3>
<div class="outline-text-3" id="text-org01ccaf4">
<p>
⌜… <br />
In everyday language <a href="https://en.wikipedia.org/wiki/Cardinal_numeral">cardinal numbers</a> are simply the counting numbers,
\(\mathbb{N}\;\), either as words or numerical symbols. In set theory,
however, <i>cardinality</i> has a different meaning, i.e., <i>the number the
objects in a set</i>. So if we consider the box of stars in the diagram
above to be a <i>set</i> of stars, then the cardinality of this set is \(3\)
since there are three stars<label for="14" class="margin-toggle sidenote-number"></label><input type="checkbox" id="14" class="margin-toggle"/><span class="sidenote">
We indicate the set’s cardinality by surrounding the symbol for
a set with <i>pipes</i> ( <b><b>|</b></b> ), e.g., \(|S_{stars}|\;\). This is not the same
as <i>absolute value</i>, although they might be cousins.
</span>
</p>
\begin{align*}
|\,S_{stars} \,| &= 3 \\
|\,\{a, b, c\}\,| &= 3 \\
|\,\mathbb{N}\,| &= \infty \\
|\,\mathbb{Z}\,| &= \infty
\end{align*}
<p>
But why are we being so “conceptual” about the simple idea of amount,
and why must we give it a fancy name? Again, math likes to <i>formalize</i>
things, nail things down. Starting with exactness and precision we can
then build very complex and logically-based math<label for="15" class="margin-toggle sidenote-number"></label><input type="checkbox" id="15" class="margin-toggle"/><span class="sidenote">
Have a look at <a href="https://en.wikipedia.org/wiki/Cardinality">this Wikipedia discussion of cardinality</a>. Later
we will look into <i><a href="https://en.wikipedia.org/wiki/Cardinal_number">cardinal numbers</a></i>, which is a deeper dive into set
theory.
</span>. Now, if two
sets have the same cardinality, is this somehow significant? Above, we
see that both the set of natural numbers and the set of integers have
infinity as their cardinality. Are, therefore, \(\mathbb{N}\) and
\(\mathbb{Z}\) the same “size?”
</p>
<p>
<font color = "#650d1c">The <i>bijection principle</i> states that
two sets have the same size <i>if and only if</i> there is a <i>bijection</i>
(injective <i>and</i> surjective together) between
them</font><label for="16" class="margin-toggle sidenote-number"></label><input type="checkbox" id="16" class="margin-toggle"/><span class="sidenote">
We’ll look at injective, surjective, and bijective when we
delve into functions from a set theory perspective. Also, mathematical
logic will introduce us to <i>if and only if</i>.
</span>.
</p>
<p>
Which means \(|\,S_{stars} \,|\;\) and \(|\,\{a, b, c\}\,|\;\) can be matched
up one-to-one, thus, they must have the same cardinality. But again,
what about sets of things that supposedly have an infinite size? How
do we “count,” or “pair up” infinite sets<label for="17" class="margin-toggle sidenote-number"></label><input type="checkbox" id="17" class="margin-toggle"/><span class="sidenote">
To excite your curiosity, isn’t \(\infty + 1\) still just \(\infty\;\)? The
Greeks contemplated this and concluded that infinity has the power to
consume, destroy individual numbers. It wasn’t until the German
mathematician Georg Cantor came along in the late nineteenth century
that we learned to wrangle infinity.
</span>? Surprisingly, there
are different kinds of infinity — which necessitates this exactness
and preciseness. More about cardinality theory later. <br />
…⌟
</p>
<p>
<span class="fraktur">𝔘𝔴𝔢:</span> So basically,
cardinality is a formalism from set theory about amount and
magnatude. Fair enough. <br />
<span class="fraktur">𝔘𝔯𝔰𝔲𝔩𝔞:</span> What about this
section? [scrolling]
</p>
</div>
<div id="outline-container-orgc5a6f9f" class="outline-4">
<h4 id="orgc5a6f9f">Haskell and cardinality</h4>
<div class="outline-text-4" id="text-orgc5a6f9f">
<p>
⌜… <br />
The first thing to know about Haskell and set theory is, yes, we can
do real set theory with Haskell’s <code>Data.Set</code> package. But as beginners
learning the ropes we will start with a simpler representation of sets
through Haskell’s basic <i>list</i> data structure. Realize, however, that
a list is not a set; they are two different beasts, and we’ll have to
account for that. For one, a set may have duplicates, whereas a list
holds a definite <i>sequence</i> of things, i.e., every element of the list
is unique, even if some elements are repeated<label for="18" class="margin-toggle sidenote-number"></label><input type="checkbox" id="18" class="margin-toggle"/><span class="sidenote">
So it’s not really a “grocery list,” it’s a “grocery set”
since \(\{eggs,sugar,coffee,eggs\}\;\;\;\) is invariably interpreted as
just \(\{eggs,sugar,coffee\}\;\;\), right? Or would you go ahead and get
eggs twice? Can you come up with another real-world example where a
set of things doesn’t care about order or duplicates?
</span>. So the <i>set</i>
\(\{1,2,1\}\;\) is the same as \(\{1,2\}\;\) is the same as \(\{2,1,1\}\;\)
because sets don’t mind duplicates, nor do they worry about
order<label for="19" class="margin-toggle sidenote-number"></label><input type="checkbox" id="19" class="margin-toggle"/><span class="sidenote">
Why is this? There is a LE to the definition
of a set union, namely, \(A \cup B = \{x \;\;|\;\; x \in A \;\;\;or\;\;\; x \in
B \}\quad\). Consider the sets \(A = \{1,2,3\}\;\), \(B = \{2,3,4\}\;\),
and \(C = \{3,4,5\}\;\). If you draw out Their union \(A \cup B \cup C = \{x
\;|\; x \in A \;\;\text{or}\;\;x \in B\;\; \text{or}\;\;x \in C \}\quad\;\;\) as
a Venn diagram, you’ll see how duplicates get left out.
</span>. But the <i>lists</i> <code>[1,2,1]</code>, <code>[1,2]</code>, and <code>[2,1,1]</code> are in
fact all different lists. Initially, we’ll practice set theory with
lists and build alternate set theory code based on lists. Then when we
understand “squirrel math” a little more, i.e., how to work with the
data structures known as <i>trees</i>, we’ll do proper set theory with
Haskell’s set theory module, <a href="https://hackage.haskell.org/package/containers-0.6.6/docs/Data-Set.html">Data.Set</a><label for="20" class="margin-toggle sidenote-number"></label><input type="checkbox" id="20" class="margin-toggle"/><span class="sidenote">
Take a look at this Hackage page. It has <a href="https://haskell-containers.readthedocs.io/en/latest/set.html">an intro to Haskell’s
sets</a>. Get in the habit of perusing Hackage whenever you’re using a
Haskell function or data type you don’t quite understand. Sometimes
you’ll have to just dive into the code, but sometimes there are
excellent intro docs like this. And yet there are also set operations
in <code>Data.List</code>. Perhaps look into these two options.
</span>. For the immediate
future we’ll consider a list to be a beginner’s substitute for a
set. And so a simple “how many” function on a list standing in for a
set is <i>length</i>
</p>
<pre class="code"><code><span class="org-haskell-definition">length</span> <span class="org-rainbow-delimiters-depth-1">[</span>1,2,3,4,5<span class="org-rainbow-delimiters-depth-1">]</span>
</code></pre>
<pre class="example">
5
</pre>
<p>
Again, more to come. Watch this space<label for="21" class="margin-toggle sidenote-number"></label><input type="checkbox" id="21" class="margin-toggle"/><span class="sidenote">
Meanwhile, here’s a brain-teaser that goes to the heart of
this set-list issue — especially in Haskell, Why are set union and
intersection commutative and associative due to their lack of order?
</span>. <br />
…⌟
</p>
<p>
<span class="fraktur">𝔘𝔴𝔢:</span> So, bottom line,
we’re not going to have real sets with Haskell right away, just a sort
of <i>Ersatz</i> sets with lists. Are we all sort of familiar with Haskell
lists from the <i>Learn You…</i>? <br />
[murmurs of affirmation as Ursula clicks on a tab showing LYAHFGG’s
section on lists] <br />
<span class="fraktur">𝔘𝔱𝔢:</span> So what about
finding another example of sets having duplicates and being in
different order? [looks back and forth] <br />
<span class="fraktur">𝔘𝔯𝔰𝔲𝔩𝔞:</span> Well, here’s
mine [scrolling to her personal annotation of the professors notes and
reading aloud]
</p>
<p>
⌜… <br />
A “set” of students in a class pass around a sign-in sheet each day on
which they sign their name. Some days the names are in one order,
other days another order, depending on how it was passed around the
room. And sometimes a student accidentally signs twice. But it’s still
the same set of students, order and duplicate sign-ins
notwithstanding. <br />
…⌟
</p>
<p>
<span class="fraktur">𝔘𝔴𝔢:</span> Oooh,
<i>notwithstanding</i>! You’re getting fancy with your English. <br />
[laughter] <br />
<span class="fraktur">𝔘𝔯𝔰𝔲𝔩𝔞:</span> Hey, no
brain-shaming! <br />
[laughter] <br />
<span class="fraktur">𝔘𝔴𝔢:</span> [continuing] No,
really, that’s a great example because it brings out the difference
between the actual set and how it’s being — <i>represented</i>. <br />
<span class="fraktur">𝔘𝔱𝔢:</span> So do we all
understand her side note about set unions? <br />
<span class="fraktur">𝔘𝔴𝔢:</span> I drew some Venn
diagrams [pulls out a hand drawing and places it on the table] and,
yes, you can see how all the overlaps are telling us not to worry
about the duplicates of the individual sets making up the union. <br />
<span class="fraktur">𝔘𝔱𝔢:</span> Right, and it’s
curious how when you just look at the set notations, you don’t
necessarily see that. At least I don’t. I mean [writing on the board]
\(A \cup B \cup C = \{x \;|\; x \in A \;\;\text{or}\;\;x \in B\;\; \text{or}\;\;x
\in C \}\quad\;\;\) doesn’t necessarily tell you it doesn’t want
duplicates. <br />
<span class="fraktur">𝔘𝔴𝔢:</span> By the way, don’t
forget union and intersection are <i>binary</i>, right? <br />
[nods of agreement] <br />
<span class="fraktur">𝔘𝔱𝔢:</span> All right then,
[correcting her formula] \(A \cup B = \{x \;|\; x \in A \;\;\text{or}\;\;x \in
B\;\}\;\;\;\;\). Satisfied? <br />
[Ursula giggles] <br />
<span class="fraktur">𝔘𝔴𝔢:</span> All right, unless
you have the word <i>or</i> to mean that we don’t keep picking up the same
element from the different sets. But the <i>inclusive or</i> of set union
means it can be from one <i>or</i> the other — <i>or</i> from <i>both</i> of
them. So I definitely see your point, the set notation <i>doesn’t</i> tell
us not to include duplicates — without some <i>exclusive</i> sort of
<i>inclusive or</i>. Only the Venn diagram really shows us this. I mean,
the whole point of this is to think about whether the definition of
set union rules out duplicates, doesn’t worry about order, and has
commutativity. I don’t see that <br />
[murmurs of agreement] <br />
<span class="fraktur">𝔘𝔱𝔢:</span> So in the rabbit
hole on logic, we had the truth tables, right? So they talked about
<i>logical or</i>, which they also called <i>disjunction</i>. And then they had
a truth table for <i>or</i> which showed how the only time something wasn’t
true was when <i>both</i> of the statements were false. <br />
<span class="fraktur">𝔘𝔴𝔢:</span> Basically, it’s
the same operations with both sets and logic. <br />
<span class="fraktur">𝔘𝔯𝔰𝔲𝔩𝔞:</span> More later. <br />
[murmurs of agreement] <br />
<span class="fraktur">𝔘𝔯𝔰𝔲𝔩𝔞:</span> All right, so
what about this brain teaser? <br />
<span class="fraktur">𝔘𝔱𝔢:</span> Right. [getting up
and writing on the board]
</p>
\begin{align*}
A \cup B &= B \cup A, \\[.5em]
A \cap B &= B \cap A, \\[.5em]
(A \cup B) \cup C &= A \cup (B \cup C), \quad and \\[.5em]
(A \cap B) \cap C &= A \cap (B \cap C)
\end{align*}
<p>
<span class="fraktur">𝔘𝔱𝔢:</span> [continuing] The
first thing we have to know is what are union and intersection in the
world of lists? I figured out that putting lists together come in two
forms, the <i>cons</i> operation, and the concatenation operator. <br />
<span class="fraktur">𝔘𝔯𝔰𝔲𝔩𝔞:</span> Right. Like
this. [creating a source block]
</p>
<pre class="code"><code>1 <span class="org-haskell-constructor">:</span> <span class="org-haskell-constructor"><span class="org-rainbow-delimiters-depth-1">[]</span></span>
</code></pre>
<pre class="example">
[1]
</pre>
<p>
<span class="fraktur">𝔘𝔯𝔰𝔲𝔩𝔞:</span> [continuing]
for <code>cons</code> and then this for concatenation
</p>
<pre class="code"><code><span class="org-rainbow-delimiters-depth-1">[</span>1<span class="org-rainbow-delimiters-depth-1">]</span> <span class="org-haskell-operator">++</span> <span class="org-rainbow-delimiters-depth-1">[</span>2<span class="org-rainbow-delimiters-depth-1">]</span>
</code></pre>
<p>
<span class="fraktur">𝔘𝔴𝔢:</span> You showed me that
<a href="https://stackoverflow.com/questions/19238091/union-function-in-haskell">stackoverflow post</a> where they created a <code>union</code> function for
lists. But then one commentor noted how no, these list versions of
union didn’t allow for commutativity and all. <br />
<span class="fraktur">𝔘𝔯𝔰𝔲𝔩𝔞:</span> Exactly. Only
the <code>Data.Set</code>, the true set theory package did. <br />
[silence while digesting the ideas] <br />
<span class="fraktur">𝔘𝔱𝔢:</span> Yeah, right, I
looked through it, but I consider myself just a beginner with Haskell,
but it seemed to be talking mainly about how you eliminate
duplicates. <br />
<span class="fraktur">𝔘𝔴𝔢:</span> But what about
that “equational reasoning”? One of you guys went into that, didn’t
you? <br />
[Ursula and Ute trade glances] <br />
<span class="fraktur">𝔘𝔱𝔢:</span> Well, I looked it
up on Wikipedia and was redirected to an article that was actually
called <a href="https://en.wikipedia.org/wiki/Universal_algebra">Universal algebra</a> [Ursula brings up the article on the
monitor], and in the <i>Basic idea</i> section <br />
<span class="fraktur">𝔘𝔴𝔢:</span> Once again, on
that fateful day when we sat down and talked with Professor Chandra
she told us to not fear the rabbit hole! <br />
[laughter] <br />
<span class="fraktur">𝔘𝔱𝔢:</span> <i>And</i> to expect a
whole new way of seeing math. <br />
<span class="fraktur">𝔘𝔴𝔢:</span> Right, that didn’t
present itself serially, one thing after another. No, we’re taking
this on in parallel. <br />
[murmurs of agreement] <br />
<span class="fraktur">𝔘𝔱𝔢:</span> I did email
Professor Chandra, and she said the Universal algebra page was not
very specific for what Haskell meant by equational reasoning — and
she gave me another link, which we can look at — but that it
contained a lot of good stuff, and we should try to get the gist of
it. <br />
[rueful murmurs] <br />
<span class="fraktur">𝔘𝔱𝔢:</span> [continuing,
reading from her laptop]
</p>
<p>
⌜… <br />
An <i>algebraic structure</i> consists of a nonempty set \(A\) (called the
<i>underlying set</i>, <i>carrier set</i> or <i>domain</i>), a collection of
operations on \(A\) (typically binary operations such as addition and
multiplication), and a finite set of identities, known as axioms, that
these operations must satisfy. <br />
…⌟
</p>
<p>
<span class="fraktur">𝔘𝔯𝔰𝔲𝔩𝔞:</span> [bringing the
page up on the monitor] Here it is.
</p>
<pre class="code"><code><span class="org-haskell-keyword">import</span> <span class="org-haskell-constructor">Data.Set</span> <span class="org-rainbow-delimiters-depth-1">(</span><span class="org-haskell-constructor">Set</span>, lookupMin, lookupMax<span class="org-rainbow-delimiters-depth-1">)</span>
<span class="org-haskell-keyword">import</span> <span class="org-haskell-keyword">qualified</span> <span class="org-haskell-constructor">Data.Set</span> <span class="org-haskell-keyword">as</span> <span class="org-haskell-constructor">Set</span>
</code></pre>
<pre class="code"><code>Set<span class="org-haskell-definition">.</span>union <span class="org-rainbow-delimiters-depth-1">(</span>Set.fromList <span class="org-rainbow-delimiters-depth-2">[</span>1, 3, 5, 7<span class="org-rainbow-delimiters-depth-2">]</span><span class="org-rainbow-delimiters-depth-1">)</span> <span class="org-rainbow-delimiters-depth-1">(</span>Set.fromList <span class="org-rainbow-delimiters-depth-2">[</span>0, 2, 4, 6<span class="org-rainbow-delimiters-depth-2">]</span><span class="org-rainbow-delimiters-depth-1">)</span>
</code></pre>
<pre class="example">
fromList [0,1,2,3,4,5,6,7]
</pre>
<pre class="code"><code>Set<span class="org-haskell-definition">.</span>union <span class="org-rainbow-delimiters-depth-1">(</span>Set.fromList <span class="org-rainbow-delimiters-depth-2">[</span>0, 2, 4, 6<span class="org-rainbow-delimiters-depth-2">]</span><span class="org-rainbow-delimiters-depth-1">)</span> <span class="org-rainbow-delimiters-depth-1">(</span>Set.fromList <span class="org-rainbow-delimiters-depth-2">[</span>1, 3, 5, 7<span class="org-rainbow-delimiters-depth-2">]</span><span class="org-rainbow-delimiters-depth-1">)</span>
</code></pre>
<pre class="example">
fromList [0,1,2,3,4,5,6,7]
</pre>
<pre class="code"><code>Set<span class="org-haskell-definition">.</span>empty
</code></pre>
<pre class="example">
fromList []
</pre>
<pre class="code"><code>Set<span class="org-haskell-definition">.</span>union <span class="org-rainbow-delimiters-depth-1">(</span>fromList <span class="org-rainbow-delimiters-depth-2">[</span>1,2,3<span class="org-rainbow-delimiters-depth-2">]</span><span class="org-rainbow-delimiters-depth-1">)</span> <span class="org-rainbow-delimiters-depth-1">(</span>Set.empty<span class="org-rainbow-delimiters-depth-1">)</span>
</code></pre>
<pre class="example">
fromList [1,2,3]
</pre>
<pre class="code"><code>Set<span class="org-haskell-definition">.</span>intersection <span class="org-rainbow-delimiters-depth-1">(</span>fromList <span class="org-rainbow-delimiters-depth-2">[</span>1,2,3<span class="org-rainbow-delimiters-depth-2">]</span><span class="org-rainbow-delimiters-depth-1">)</span> <span class="org-rainbow-delimiters-depth-1">(</span>Set.empty<span class="org-rainbow-delimiters-depth-1">)</span>
</code></pre>
<pre class="example">
fromList []
</pre>
<pre class="code"><code><span class="org-haskell-keyword">import</span> <span class="org-haskell-constructor">Data.Ratio</span>
</code></pre>
<p>
<span class="fraktur">𝔘𝔯𝔰𝔲𝔩𝔞:</span> Let’s leave it
for now. So moving on [scrolling].
</p>
</div>
</div>
</div>
<div id="outline-container-orgebc065e" class="outline-3">
<h3 id="orgebc065e">Ordinality</h3>
<div class="outline-text-3" id="text-orgebc065e">
<p>
⌜… <br />
In everyday language the concept of order is conveyed when we say
<i>first, second, third, fourth,</i> etc<label for="22" class="margin-toggle sidenote-number"></label><input type="checkbox" id="22" class="margin-toggle"/><span class="sidenote">
See <a href="https://en.wikipedia.org/wiki/Ordinal_numeral">this</a> brief discussion.
</span>. And we’re done, right? But
again, as seen from set theory — as well as from the computer world
— (re-)establishing order is important and cannot always be taken
for granted. In fact, a great deal of investigation surrounds
ordinality.
</p>
<p>
The counting numbers, the set \(\mathbb{N}\;\), would seem to have order
built in. For example, everybody knows that \(3\) comes after \(2\;\)
etc., they’re in ascending order based on the incrementally greater
amounts they represent. And neither does the set \(\mathbb{N}\;\) have
repeats. Also, if we create a geometric visual for \(\mathbb{N}\;\),
that is to say, we draw a line and mark places on the line for each
number, we can subdivide the line into <i>intervals</i><label for="23" class="margin-toggle sidenote-number"></label><input type="checkbox" id="23" class="margin-toggle"/><span class="sidenote">
Typically, real numbers are represented geometrically by a
“number line” whereby <i>interval notation</i> allows for sections of this
line to be considered, e.g., <i>closed interval</i> \([\,a,b\,]\;\), <i>open
interval</i> \((a,b)\:\), and more exotics like an <i>open ray</i> \((-\infty, a)\:\).
</span> and order is
related to inequalities.
</p>
<p>
But order, and all it’s implications, is not always a given
in real life. What if we wrote the numbers from one to ten on small
squares of paper, put them in a box, and then shook them out on the
floor in a straight line? Would they be in order? Chances are,
no. And what about sets of things that aren’t inherently numerical,
such as colors?
</p>
<p>
So if we don’t have things in proper order—which is often the case
in the real world—we have to put things in order ourselves. And that
means we will need to <i>sort</i> a set of unsorted elements into some
order. Sorting, in fact, is one of the more basic tasks computers do
in the everyday world<label for="24" class="margin-toggle sidenote-number"></label><input type="checkbox" id="24" class="margin-toggle"/><span class="sidenote">
We will eventually investigate how costly in computer time and
resources an operation like sorting is. Stay tuned.
</span>.
</p>
<p>
But to sort we need to compare things. Obviously, ten whole numbers
written clearly on ten squares of paper can be easily sorted by
hand<label for="25" class="margin-toggle sidenote-number"></label><input type="checkbox" id="25" class="margin-toggle"/><span class="sidenote">
A jigsaw puzzle can be seen as a sorting game based on shape,
color, and patterns of the pieces.
</span>. But what if we had thousands of squares of paper, each
with a unique number? Then we’d have a long task ahead of us. But no
matter how big or small the task, we would compare <i>two</i> numbers at a
time and then make a judgement based on whether one number was
</p>
<ul class="org-ul">
<li>greater than</li>
<li>equal to</li>
<li>less than</li>
</ul>
<p>
the other number, then rearranging as needed. <br />
…⌟
</p>
</div>
<div id="outline-container-orgb97fb9b" class="outline-4">
<h4 id="orgb97fb9b">Ordinality in Haskell</h4>
<div class="outline-text-4" id="text-orgb97fb9b">
<p>
Haskell is a typed language with a feature called <i>type
classes</i><label for="26" class="margin-toggle sidenote-number"></label><input type="checkbox" id="26" class="margin-toggle"/><span class="sidenote">
For a quick introduction with examples go <a href="http://learnyouahaskell.com/types-and-typeclasses#typeclasses-101">here</a> in LYAHFGG.
</span>. A Haskell type class encompasses traits, patterns,
concepts, or what we might call a certain “-ness” that can be imparted
to data types. In Haskell, for example, numbers and the characters of
the alphabet can be directly compared for “equal-ness,” and when we
test at the ghci REPL prompt, this seems to be built-in
</p>
<pre class="code"><code><span class="org-rainbow-delimiters-depth-1">(</span><span class="org-rainbow-delimiters-depth-2">(</span>5 <span class="org-haskell-operator">==</span> 3<span class="org-rainbow-delimiters-depth-2">)</span> <span class="org-haskell-operator">||</span> <span class="org-rainbow-delimiters-depth-2">(</span><span class="org-string">'a'</span> <span class="org-haskell-operator">==</span> <span class="org-string">'a'</span><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><span class="org-string">'b'</span> <span class="org-haskell-operator">==</span> <span class="org-string">'B'</span><span class="org-rainbow-delimiters-depth-1">)</span>
</code></pre>
<pre class="example">
True
</pre>
<p>
Mindful of LE, we see that Haskell’s <code>Eq</code> class
housing this equal-ness must have some sort of behind-the-scenes
mechanism that allows us to take two things, analyze them, then return
a decision, true or false (yes they are equal, no they’re not equal),
on whether two said things were equal or not — all of this just for
doing some typing, e.g., <code>5 == 3</code> into the REPL.
</p>
<p>
Something else to consider is how some things don’t necessarily have
the concept of equal or not equal straight out of the box. What if we
created a data type for colors and we wanted to compare the individual
color values for equal-ness? Intuitively, we might say red, yellow,
and blue are equal since they are all primary colors; likewise,
orange, green, and violet are equal because they’re the secondary
colors. But what if we just say each color is equal to itself and not
equal to any of the others? … So how would we establish equal-ness
for colors? If we want to type <code>Green == Blue</code> into the REPL it’s up
to us to have created some sort of equal-ness and told Haskell about
it.
</p>
<p>
Data types that need to establish equal-ness for themselves can apply
to the Haskell <code>Eq</code> type class for membership. Type class membership
is registered with an <i>instance</i> statement. To see all the data types
that have an instance registered with <code>Eq</code> we can use <code>:info</code>
(abbreviated <code>:i</code>) at the REPL<label for="27" class="margin-toggle sidenote-number"></label><input type="checkbox" id="27" class="margin-toggle"/><span class="sidenote">
Go ahead and check out the <a href="https://hackage.haskell.org/package/base-4.17.0.0/docs/Data-Eq.html">hackage.haskell.org</a> entry for <code>Eq</code>
<a href="https://hackage.haskell.org/package/base-4.17.0.0/docs/Data-Eq.html">here</a>. Note the properties <code>(==)</code> should follow: reflexivity, symmetry,
transitivity, extentionality, and negation. We’ll dive into what this
all means when we look closer into the higher algebra of sets and
functions. Note all the built-in, “batteries-included” <code>Eq</code> instances
for the various types. Some are rather exotic.
</span>
</p>
<pre class="code"><code><span class="org-haskell-constructor">:</span>i <span class="org-haskell-constructor">Eq</span>
</code></pre>
<pre class="example" id="orga8c37d2">
type Eq :: * -> Constraint
class Eq a where
(==) :: a -> a -> Bool
(/=) :: a -> a -> Bool
{-# MINIMAL (==) | (/=) #-}
-- Defined in ‘ghc-prim-0.7.0:GHC.Classes’
...
instance Eq Int -- Defined in ‘ghc-prim-0.7.0:GHC.Classes’
instance Eq Float -- Defined in ‘ghc-prim-0.7.0:GHC.Classes’
instance Eq Double -- Defined in ‘ghc-prim-0.7.0:GHC.Classes’
instance Eq Char -- Defined in ‘ghc-prim-0.7.0:GHC.Classes’
instance Eq Bool -- Defined in ‘ghc-prim-0.7.0:GHC.Classes’
...
</pre>
<p>
which gives us a long list (abbreviated above) of data types that have
equal-ness defined<label for="28" class="margin-toggle sidenote-number"></label><input type="checkbox" id="28" class="margin-toggle"/><span class="sidenote">
Quick LE question: Can functions be compared for equal-ness?
Here’s a direct quote from a prominent combinatorics text: <i>When two
formulas enumerate the same set, then they must be equal.</i> But not so
fast in the computer world. To say <code>f x == g x</code> Haskell isn’t
logically set up to actually prove (demonstrate) and accept that <code>f</code>
and <code>g</code> always give the same results given the same <code>x</code> input. We
would literally have to test every possible <code>x</code>, which is not
possible. Still, we’ll examine this idea a bit closer soon. It’s a
real big deal in numerical math.
</span>. Notice the two “prescribed” methods (functions)
<code>(==)</code> and <code>(/=)</code>. These functions are the mechanism used by <code>Eq</code> to
establish equal-ness. They must be custom defined in each instance
declaration in order for a data type to have its own established
equal-ness<label for="29" class="margin-toggle sidenote-number"></label><input type="checkbox" id="29" class="margin-toggle"/><span class="sidenote">
Note <code>{-# MINIMAL (==) | (/=) #-}</code> which is a directive
meaning we may choose to define <b>either</b> <code>(==)</code> <b>or</b> (note the <b>or</b>
pipe <b>|</b> ) <code>(/=)</code>, i.e., we don’t actually have to define both because
by defining one, the other will be automatically generated. Neat.
</span>. And so if you create a new type, you, the
programmer, must come up with your own version of these two functions,
<code>(==)</code> and <code>(/=)</code> to establish the trait, the property of equal-ness
for that new data type. As <i>LYAHFGG</i> notes, the type signature for the
equal-ness function <code>(==)</code> is<label for="30" class="margin-toggle sidenote-number"></label><input type="checkbox" id="30" class="margin-toggle"/><span class="sidenote">
<code>:t</code> is short for <code>:type</code>.
</span>
</p>
<pre class="code"><code><span class="org-haskell-constructor">:</span>t <span class="org-rainbow-delimiters-depth-1">(</span><span class="org-haskell-operator">==</span><span class="org-rainbow-delimiters-depth-1">)</span>
</code></pre>
<pre class="example">
(==) :: Eq a => a -> a -> Bool
</pre>
<p>