Skip to content

Latest commit

 

History

History
766 lines (600 loc) · 26.8 KB

OM4-1.org

File metadata and controls

766 lines (600 loc) · 26.8 KB
Raw

#

#

Bibliography

Discrete Math according to Martin Aigner

Rabbit holes

⌜🐇 Rabbit holes to get started with CIMMIC are:

  1. Learn You a Haskell for Great Good! (LYAHFGG) is a widely-used, often-suggested beginners site for starting out with Haskell. Work through at least chapters 1 and 2 to understand a lot of what we’ll be doing with Haskell below[fn:1]. Pay particular attention to lists and list comprehensions. (RC-hole)
  2. Another big favorite for Haskell starters, but slightly more challenging is A Gentle Introduction to Haskell 98. AGITH was written by elite school professors (Yale) and uses more math terminology than LYAHFGG. Which is what we’ll be doing, but usually with a shallower on-ramp. (RO-hole)
  3. The Haskell Wiki [fn:2] is full of knowledge gems, but don’t expect to fully understand it yet. Maybe start with this article and peruse through the rest of the “99 Questions.” (RO-hole)
  4. We need to learn mathematical logic, since logic is simply baked into every programming language. Try this LibreTexts series on logic. Pay particular attention to the notation used on logic operators and the terminology as well. This stuff comes up all the time in programming. (RC-hole)
  5. These basic set theory slides with their tie-in to Haskell at the end are very good as well. Do something between a grok and a skim. We’ll eventually be covering all the material therein. (RO-hole)
  6. Read through this Wikipedia Set[fn:3] article, paying special attention to the Basic Operations section—maybe even rabbit-hole into the union article to understand some basic algebraic operations on sets. You’ve probably seen this stuff before with Venn diagrams; this is some of the algebra behind the diagrams. (RO-hole)
  7. Another big-league site for the serious-minded is the Rosetta Code site. Here you can search on hundreds algorithms and numerical analysis articles, each task done in the code of dozens of programming languages[fn:4]. (RFYI-hole)

🐇⌟

Introduction

With this section we’ll do a quick warm-up with some ideas in Haskell, i.e., just a feel for the math and Haskell we’ll be exploring. In the next section we’ll get started proper, and, yes, we’ll be more detail-oriented and explanation-rich. But do get started on the rabbit-holing above.

Peano arithmetic

Discussion

Some things in mathematics must be assumed as a starting point, as axiomatic/[fn:1]. One great example would be the /natural or counting numbers. These are the whole numbers starting typically with $0$ and going, as we assume, out to infinity. The symbol commonly used to denote the /set/[fn:2] of natural numbers is $\mathbb{N}$, i.e.,

\begin{align*} \mathbb{N} = \{\text{all the whole numbers starting with zero}\} \end{align*}

By whole numbers we mean whole and atomic[fn:3], as in not rational (fractional), decimal-places real, or transcendental, or irrational numbers. But what is meant by all and, even worse, starting with? For example, is there any sort of order implied, or are these whole numbers just in whatever order as long as they’re after zero? Obviously, this is not our intuitive understanding of the counting numbers.

Around the time of Kindergarten we learned a sort of nursery rhyme of the first ten numbers—probably using our fingers as aides. Next, we learned to write the numeric symbols from $1$ to $10$. Next, we stepped into our first real contact with mathematical abstraction when we learned about numbers having two places or more: ten, eleven, twelve, then the teens. This required an understanding of /positional notation/[fn:5] using the ten basic Arabic numerals, $0$ to $9$, and placing them in increasing powers-of-ten columns. But this was all done at an intuitive level meant to cement in our minds the fundamental idea that distinct amounts have distinct designations, i.e., names and numeric symbols.

But how could we indicate five things without the numerical symbol $5$ or the word five? We might imitate a watch and bark out tick! five times[fn:6], hoping that someone, something is in some way noting how many ticks there were.

Unary numeral system

There is the unary numeral system (UNS) where numbers are represented in a /unary/[fn:7] 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 our decimal system[fn:8].

How would we add or subtract in our UNS system? Ironically, we could invent a sort of columnar subtracting borrowing from decimal vertical subtraction

\begin{array}{r} &11111
-\!\!\!\!\!\!&11\ \hline &11100 \end{array}

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?

\begin{align*} 11111 + 11 = 1111111 \end{align*}

We could also remove the $+$ and run together or concatenate the $1$’s. Now we’ll do some Haskell code that might shed some light. First, a real cheating way

(length [1,1,1,1]) - (length [1,1])
2

uns1 list1 list2 = (length list1) - (length list2)
uns1 [1,1,1,1] [1,1]
2

As with all computer-numerical treatments of mathematics, we must first decide which data structure to use. As is often the case with Haskell, we will utilize lists to do our work. This may seem ironic in some cases, since so much of math can be seen as, e.g., set theory-based. Yes, Haskell has a library for sets, but beginners in most programming languages start with lists and arrays as the go-to data structure. Hence, we will manipulate our UNS with lists. This means a set or string of ones will be represented as a list with integer ones as its sole elements, e.g., [1,1,1,1,1] is $11111$.

Binary number system

  • cite:&chamberlandsingle

The unary system

Or we could say “the number after four.” But that’s just the number after three—and so on until we arrive at zero, which we call, yes, zero, and write as $0$. So in this system, $5$ would be…

…the next, next, next, next, next number after zero.

But just to check this for accuracy, we again fall back on numerical symbols and names. So we count the number of next’s and translate this chain of next links back into $5$.

So we seem to be stuck with names and symbols, our numbering system, so to speak, to even get off the ground with numbers as representative of amounts. However, mathematics will want to take us much further into the conceptualization of numbers, abstractions far beyond the simple notion of how many. In abstract algebra, operations on numbers such as addition and subtraction have consequences beyond number names or symbols. So the subtraction of one natural number from another is a “taking away” of one amount from another. But what if we try to take $3$ from $2\;$? To take $3$ from $2$ would land us outside the counting whole numbers $\mathbb{N}\;$, would it not? After all, $2 - 3$ is $-1$, i.e., we went past $0$ and landed one tick below in “negative territory.” The integers (denoted by $\mathbb{Z}$) abstracts $\mathbb{N}\;$ by symmetrically mirroring, duplicating all its positive whole numbers into their negative counterparts. However, the operation of addition in $\mathbb{N}$ would not ever take us into negatives. Any two (sic) natural numbers we might add together would produce another member of the natural numbers somewhere further up the list of $\mathbb{N}\;$. But now we’re concerned with where in the list. Hence, order is our next abstraction beyond just naming amounts. And as you might suspect, the most basic ordering of numbers is to “line them up” according to their amounts[fn:9].

When we played with the notion of next above, it was as if we started by feeding a basic starting thing, a zero, into a next machine, and out came “the next thing after zero”. We might have noted that to be $1$. Then if we feed our zero adorned with next into the next machine again we get “the next, next thing after zero” And we write that down somewhere as $2$. In effect, we’re constructing a way to string ticks together into a chain, forging a new chain link for each new tick. Then instead of having a name or symbol, we could just show the whole chain. Odd and awkward? But this is exactly what the Italian mathematician Giuseppe Peano (following up on work done by the German mathematician Richard Dedekind) formulated in order to put the notion of natural numbers on a more mathematically-sound footing.

Peano axioms

According to a modern treatment, there are five basic Peano axioms[fn:10]. The first axiom states

  1. $0$ is a natural number, i.e., $0 ∈ \mathbb{N}$

This is our starting point. Peano then gives four axioms to establish equality

  1. For every natural number $n$, $S(n)\;$ is a natural number. That is, the natural numbers are closed under $S\;$. Or $x ∈ \mathbb{N} → Sx ∈ \mathbb{N}\;\;$.
  1. For all natural numbers x and y, if x = y, then y = x. That is, equality is symmetric.

Sets

Set beginnings

  • cite:&van2010computational

To check whether two sets are the same one has to check that they have the same members. The fact that membership is all there is to set identity, or that sets are fully determined by their members, is called the principle of extensionality.

Set comprehensions are math shorthand for declaring sets

𝖟𝕭: The set of all natural numbers multiplied by $2$

\begin{align*} E = \{2n \; | \; n ∈ \mathbb{N}\} \end{align*}

We could now have a variation such as

\begin{align*} O = \{n \;|\; n ∈ \mathbb{N}, n ∉ E\} \end{align*}

If every member of a set $A$ is also a member of set $B$ we say that $A$ is a subset of $B$, written as $A \subseteq B$. If $A \subseteq B$ and $B \subseteq A$ then it follows by the principle of extensionality that $A$ and $B$ are the same set. Conversely, if $A = B\;$ then it follows that $A \subseteq B$ and $B \subseteq A$.

let s1 = Set.fromList ["a", "b"]
s1
fromList ["a","b"]

What about a descriptive definition such as

\begin{align*} \text{For allx } x ∈ P\text{, there existsy } y > x \text{ such that } y ∈ P. \end{align*}

➝ For all $x ∈ P$, there exists $y > x$ such that $y ∈ P$. 

[(x,y,z) | x <- [True,False], y <- [True,False], z <- [True,False]]
[(True,True,True),(True,True,False),(True,False,True),(True,False,False),(False,True,True),(False,True,False),(False,False,True),(False,False,False)]

[y > x | x <- [1..10], y <- [1..15]]
[if y > x then y else 0  | x <- [1..10], y <- [1..15]]
fromList ["a","b"]

[x | x <- [1..10], y <- [5..20], x < y ]
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,6,6,6,6,6,6,6,6,6,6,6,6,6,7,7,7,7,7,7,7,7,7,7,7,7,7,8,8,8,8,8,8,8,8,8,8,8,8,9,9,9,9,9,9,9,9,9,9,9,10,10,10,10,10,10,10,10,10,10]

filter even [1..10]
[2,4,6,8,10]

[x | x <- [1..10], (even x)]
[2,4,6,8,10]
03
16
212
324
448
596
6192
7384
8768
 
reset
set term svg font "Garamond,25"
set title "Exponential growth" font "CMU serif,15"
set style line 1 lc krgb '#0060ad' lt 1 lw 2 # --- blue
set yrange[0:800]
set xrange[0:10]
set terminal svg size 300,500
plot data with lines ls 1 notitle smooth csplines
1234567
248163264128
-2-101234567
0.250.51248163264128

If some process is increasing at an exponential rate, it means that for each unit of change the rate is growing or decreasing by a common ratio. In the example above, the common ratio is $2$.

independent varfirst dependent varsecond dependent var
0.10.4250.375
0.20.31250.3375
0.30.249999930.28333338
0.40.2750.28125
0.50.260.27
0.60.258333380.24999993
0.70.246428450.23928553
0.80.231250.2375
0.90.233333230.2333332
10.22250.22
1.10.209090750.22272708
1.20.199999980.21458333
1.30.196153680.21730748
1.40.185714330.21071435
1.50.190000080.2150001
1.60.18281250.2046875
1.70.180882530.1985296
1.80.179166750.18888898
1.90.193421030.21315783
20.190.21625
2.10.182142680.20714265
2.20.177272750.2022727
2.30.17391310.1989131
2.40.167708330.1916667
2.50.1640.188
2.60.157692380.18076923
2.70.15925910.1888887
2.80.15982140.18928565
2.90.156034530.1844828
00000000000000000
00000000000000000
00000000000000000
00110010000011100
01001010000100010
01001010000100010
01001010000101110
01001010000100000
01001010000100000
01001010000100010
01001011010100010
00110010110011100
00000000000000000
00000000000000000

Rational numbers

In Haskell rational numbers are handled by Data.Ratio

import Data.Ratio

The basic “give back the simplest form” function is %

50 % 10
5 % 1

numerator (60 % 20)
3

:{
-- combRatio :: Ratio
combRatio r = show (numerator (r)) ++ "/" ++ show (denominator (r))
:}
combRatio (60 % 20)
3/1

⇲ Tip: Put an infix operator in parentheses to use as prefix

r1 = (%) 50 10
:t r1
r1 :: Integral a => Ratio a

60 % 20 :: (Integral a) => Ratio a
3 % 1

60 % 20 :: Rational
3 % 1

First, the data type

data  (Integral a) => Ratio a = !a :% !a  deriving (Eq)

The :% is a data constructor (the : insures it’s a constructor and not just an operator function) that is placed between the two Integral parameters. But in the source % calls ~reduce~[fn:11]

reduce ::  (Integral a) => a -> a -> Ratio a
{-# SPECIALISE reduce :: Integer -> Integer -> Rational #-}
reduce _ 0              =  ratioZeroDenominatorError
reduce x y              =  (x `quot` d) :% (y `quot` d)
                           where d = gcd x y
(%) :: (Integral a) => a -> a -> Ratio a
x % y =  reduce (x * signum y) (abs y)
quot 6 3 -- returns the quotient, discards the remainder, if any
2

GCD and the Euclidean algorithm

The built-in Haskell gcd was used to reduce the rational number, e.g., fraction, to its lowest terms.

𝖟𝕭. Find the lowest terms of $42/56$

gcd 42 56
14

i.e., $14$ is the greatest common divisor of both $42$ and $56$

\[ \frac{42}{56} \]

Euclid’s algorithm, is an efficient method for computing the greatest common divisor (GCD) of two integers (numbers), the largest number that divides them both without a remainder.

:{
eGCD :: Integral i => i -> i -> i
eGCD 0 b = b
eGCD a b = eGCD (b `mod` a) a
:}
eGCD 60 25
5

Perfect numbers

This code give the first four /perfect numbers/[fn:12]

:{
main = do
  let n = 4
  mapM_ print $
    take n [candidate | candidate <- [2 .. 2 ^ 19], getSum candidate == 1 ]
    where
      getSum candidate =
        1 % candidate + sum [1 % factor + 1 % (candidate `div` factor)
                            | factor <- [2 .. floor (sqrt (fromIntegral candidate))]
                            , candidate `mod` factor == 0 ]
:}
main
6
28
496
8128

Power series

Something[fn:13] else[fn:14]

Footnotes

[fn:1] Truthfully, this will be your go-to reference/tutorial for the immediate CIMMIC future. Get going with it and try to self-pace your way through it all. It’s not in-depth per se but will get you in the Haskell ballpark, so to speak.

[fn:2] Grokking Haskell Wiki articles can be like trying to drink from a full-blast fire hose, but good can be gained from them by the brave and virtuous.

[fn:3] Mathematics as experienced in Wikipedia’s articles can also be a firehose experience, but again good can be gleaned.

[fn:4] Check out this article and then its Haskell answer here … although this would be graduate-level Comp-Sci stuff. Notice, perhaps, the list of 19 languages. These are the biggest of the big in the realm of doing math with computers.

[fn:5] See Positional notation.

[fn:6] My mechanical pocket watch has a face with Roman numerals evenly positioned around a circle, twelve main numbers for the hours with five little marks between each number for the minutes and seconds. But internally, the mechanics only know about ticking; they know nothing of the numbers and their positions on the watch face. So the steady ticking is mapped to the watch face dumbly. Is ticking, therefore, the most fundamental sort of counting?

[fn:7] Unfortunately, unary here has two meanings. It means we’re only using one numeral to do our counting, and 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 unary operator where only one thing is operated on. For example, addition is a binary operation since it takes two 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.

[fn:8] More on the binary number system later.

[fn:9] How would you order a box of crayons? One way would be by their colors. But is brown ahead or behind green? Crayon colors don’t seem to have an ahead or behind, maybe just a “beside” or “along with” perhaps?

[fn:10] 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 relations, a more general concept above functions.

[fn:11] quot returns the quotient, discards the remainder; gcd is the built-in greatest common divisor; signum gives back 1 if argument is greater than zero, -1 if less than zero, zero if zero.

[fn:12] In number theory, a perfect number is a positive integer that is equal to the sum of its positive divisors, excluding the number itself. For instance, $6$ has divisors $1$, $2$ and $3$ (excluding itself), and $1 + 2 + 3 = 6\;$, so $6$ is a perfect number.

[fn:13] This is the crummier, brute-force version

0 min10 min20 min30 min40 min50 min
20.010.5.2.51.250.625

[fn:14] Another attempt

0 min10 min20 min30 min40 min50 min
20.010.5.2.51.250.625