.md .pdf

Contents

Counting

A Pile of Rocks

What does it mean to count?

There are many representations of numbers. Table below shows multiple ways to write the number 13. Each of these is a representation of the number 13. We have all agreed that these collections of symbols mean 13. You might not be able to read all the different numbers. We can only communicate about numbers using these representations because we all learned what they mean.

Number	Description
13	Base-10 (Integer)
D	Base-16 (HEX)
15	Base-8 (Octal)
XIII	Roman Numerals
	Babylonian Numerals

At root, there has to be some meaning to 13. Something that is universally true about numbers and counting that we can find. We should be able to built up an understanding of numbers from a few basic principles.

We will start the way our ancient ancestors did, making piles of things. Imagine you are a farmer in an ancient society. You want to trade some of your corn for potatoes at a rate of 1 to 1. You could stand with the other farmer. You hand over 1 ear of corn and they pass you back 1 potato. You both know that the same number of items exchanged hands.

Let us abstract this a little further, maybe we have many people making exchanges for us. We send out a number of relatives to exchange corn. When everyone gets back, we want to verify we got back the right amount. In the morning, we make a pile of rocks, one for each piece of corn. Then we send all the corn away with our relatives. At night when they return, we match up the potatoes they brought back with the pile of rocks we have. Each rock represents an ear of corn we had in the morning.

We can build up mathematics on our pile of rocks. What is we want to add to piles? We can just put all the rocks from both piles together. The new pile is the sum of the two original piles. We can also subtract piles by removing rocks.

We can even define multiplication in terms of rocks. To multiply pile A by pile B.

Function mult(Pile A, Pile B)
  For Every Rock in Pile A
    For Every Rock In Pile B
      Put a new rock in Pile C
    EndFor
  EndFor
EndFunction

This function might give you a hint to a big problem in pile of rocks math. You need a lot of rocks! We don’t actually need physical rocks. We abstract one more level. We used a rock to count for a something. We replaced one physical thing with another. What if we just make a mark on something and say it represents a rock?

We can just draw 5 lines and say each represents a rock. A pile of six rocks looks like \(| | | | | |\). What if we use more than one symbol? We could say \(\vee\) is the same as \(| | | | |\). We can build up a whole system of numbers. At a fundamental level are all representation of how many rocks are in a pile.

We need two basic concepts. A rock to count for one of something and a symbol to mean zero (nothing). It took humans until around 3 B.C. to figure out we needed a symbol for zero [Kap07].

Counting with only the one symbol allows us to count \(1,2,3,4,\cdots\). These are called the Natural Numbers. If we add zero then the sequence is called the Whole Numbers.

Peano Arithmetic

We will now formalize the idea of numerical representation. An Italian mathematician, Giuseppe Peano, proposed a set of axioms called Peano’s Axioms [Wikipediacontributors21c]. These can be used to create a system of mathematic called Peano Arithmetic. We can build this number system in Racket!

Peano’s Axioms are given below [WeissteinEW21]. We will build a number system in Racket used by these.

1. Zero is a number.

2. If \(a\) is a number, the successor of \(a\) is a number.

3. Zero is not the successor of a number.

4. Two numbers of which the successors are equal are themselves equal.

5. If a set \(S\) of numbers contains zero and also the successor of every number in \(S\), then every number is in \(S\).

The big picture takeaway here is that every number is either zero or the successor of another number.

We can start building out number system by defining a symbol to mean zero. This will be a special stand alone symbol that just means zero. This aligned with Axiom 1 and Axiom 3. We will use the null list as our representation of zero.

(define zero '())

Axiom 2 says that the successor of a number is a number. A successor is the next number. Looking back on our rocks \(| | | |\) is the successor of \(| | |\). The successor of a number is the next number in sequence. Using whole numbers, \(4\) is the successor of \(3\). The symbols we write don’t matter. The successor means the next value.

We need to assign another symbol to mean successor. We can use \(s\) to mean successor. We can add a successor by adding an s to the list. We are added a new rock to the pile. A pile with one rock is (s). A pile with two rocks is (s s). Each s represents an application of the successor* function. It is one new rock on the pile.

Axiom 2 says that the successor of a number is a number. We already defined zero as a number, since one is its successor one is also a number.

We can create a few numbers using this method.

(define one '(s) )
(define two '(s s) )
(define three '(s s s) )

This doesn’t really give us a general pattern. Writing 38 by hand would be a real pain. We can create a function that generates the successor of a number.

(define (successor x)
  (cons 's x)
)

Using Axiom 2 we can create lots of numbers. Any number that we get by calling successor on another number is a number. This gives us a recursive definition of the numbers.

(define one (successor zero))
(define two (successor one))
(define three (successor two))
(define four (successor three))

Axiom 5 tells us we can make any whole number using just these two commands. We can build a whole system of math based on just zero and the concept of successors.

There is one axiom we haven’t used yet. Axiom 4 tells us how to compare numbers. We can restate this Axiom is a more recursive way. If \(x\) and \(y\) are both the successor of \(z\) then \(x=y\).

The smallest number is zero. It is clearly true that zero is equal to zero. We can make a function to detect zero more easily.

(define (isZero? X) 
  (equal? X zero)
)

If both representations are zero, then they are equal. If one is zero and the other is not, they are definitely not equal. Since equals? is already in Racket we will use equiv?.

(define (equiv? A B)
  (cond
    ;Both values are zero
    [(and (isZero? A) (isZero? B)) #t]
    ;A is zero but B is not
    [(and (isZero? A) (not (isZero? B))) #f]
    ;B is zero but A is not
    [(and (not (isZero? A)) (isZero? B)) #f]
    ;Neither is zero
    [else ...]
  )
)

We don’t know what to do with two non-zero values yet. We know from Axiom 4 there is a relationship. We need to find out “whose successor am I?”. We call this the predecessor. We have no negative numbers in this system. That means zero has no predecessor. All other number’s predecessors can be found by removing one \(s\) symbol.

Note

To represent negative numbers, we would need to add another symbol. For example, we could saw p means \(-1\). We owe the pile one rock. We would then need to account for this symbol in all our functions.

We need to program this concept. We have to return something as the predecessor of zero. We could chose to throw and error, or built a negative number representation. We will return zero as the predecessor of zero. This is useful because our function always returns a number, it is also something easy to detect with our existing functions.

(define (predecessor X) 
  (if (isZero? X) 
    zero 
    (rest X)
  )
)

We can finish out function for equivalence.

(define (equiv? A B)
  (cond
    ;Both values are zero
    [(and (isZero? A) (isZero? B)) #t]
    ;A is zero but B is not
    [(and (isZero? A) (not (isZero? B))) #f]
    ;B is zero but A is not
    [(and (not (isZero? A)) (isZero? B)) #f]
    ;Neither is zero
    [else (equiv? (predecessor A) (predecessor B))]
  )
)

What about \(A \le B\)? A is less than B is A has fewer predecessors than B. If A reaches zero before B, then A is smaller.

(define (less? A B)
  (cond
    ;Both reached zero at same time
    [(and (isZero? A) (isZero? B)) #f]
    ;A reached zero before B
    [(and (isZero? A) (not (isZero? B))) #t]
    ;B reached zero before A
    [(and (not (isZero? A)) (isZero? B)) #f]
    ;Neither is zero
    [else (less? (predecessor A) (predecessor B))]
  )
)

We can use these two functions and logic to create other comparisons.

(define (lessEqual? A B) (or (less? A B) (equiv? A B)))
(define (greater? A B) (less? B A))
(define (greaterEqual? A B) (or (greater? A B) (equiv? A B)))
(define (notEqual? A B) (not (equiv? A B)))

Now we can compare numbers!

How can we add numbers? Think back to the piles of rocks. Adding just means combining the piles. If we want to compute \(A+B\) that means add \(A\) rocks to the \(B\) pile. More specifically, call successor \(A\) times on the value \(B\). If \(A\) is zero, then we don’t need to do anything.

(define (add A B)
  (if (isZero? A)
      B
      (add (predecessor A) (successor B))
  )
)

In essence, we are writing \(A+B=(A-1)+(B+1)\). This is true, but both sides are equal. What is the point? One side is computationally less complex then the other. We have replaced \(A+B\) with something that is easier to compute. By repeatedly moving toward simpler computations, we will compute a solution.

If we execute (add three four) the result is '(s s s s s s s). We computed \(3+4=7\).

If we can add, we must be able to multiply. Peano promised our system produces all whole numbers. We just need to convert multiplication into addition. There are two basic rules.

\( \begin{align} A*0 =& 0 \\ A*B =& A+A*(B-1) \end{align} \)

We are replacing multiplication, which we don’t know how to compute, with addition which we can compute. The inputs to multiplication become computationally simpler and remaining computation is completed by a function we have already defined. The second input will eventually reach zero, the computationally simplest input. We can translate this into Racket.

(define (mult A B)
  (if (isZero? B)
      zero
      (add A (mult A (predecessor B)))
  )
)

Executing (mult two four) gives us '(s s s s s s s s). We can compute \(2*4=8\).

If we can multiply, we can compute exponents. We can define exponents in terms of multiplication.

\( \begin{align} A^0 =& 1 \\ A^B =& A*(A^{B-1}) \end{align} \)

Again, we convert an expression we can’t compute directly, \(A^B\), into something we can compute and a computationally simpler recursive call. The second input will eventually reach zero, the computationally simplest input. In Racket this is written as

(define (exp A B)
  (if (isZero? B)
      (successor zero)
      (mult A (exp A (predecessor B)))
  )
)

We can compute \(3^2\) by executing (exp three two). The result is '(s s s s s s s s s).

Using just two basic symbols zero and successor we can build whole numbers and arithmetic. Once we have meet all of Peano’s Axioms, all other features can be defined.

previous

Induction

next

List Induction