3.1.3
Building Basic Operations using the fundamental functions
ADDITION FROM SCRATCH
It might seem odd that we are going to try and define addition. After all, anyone can add right? Well think of it like this: how would you explain addition to a computer? How would you define addition in a way thats completely non-ambiguous. If someone asked you how addition is actually carried out in our minds, would you be able to explain it? The key to all these questions is to have an algorithm. A step-by-step process that leaves no room for guessing.
Earlier we "defined" the four fundamental functions, S(n), P(n), I(n) and u(). By neccesity we had to omit any attempt to explain what is meant by "successor of n", and what is meant by "1" or "u". However we can use these undefined concepts to define addition.
To understand this we are first going to have to get used to a special kind of function notation. It contains two major parts.
The first part establishes the notation, and the parameters. The notation tells us exactly what kinds of expressions will be talking about, and how numbers should be placed within the notation. The parameters tell us what kinds of numbers are acceptable. That is, we will always define our function over a restricted set of values. I almost entirely restrict myself to the Naturals in discussions of large numbers, and I may later omit this part when it is obvious N is the domain of values, but because we're just getting started I will include it.
The second part comprises of a series of ordered rules. Each rule applies to a specific set of circumstances. Each rule has a rule number, followed by conditions for the rule, and lastly a "transformation". You must always look at the rules in order. First you look at the first rule. If it applies you excute the transformation, otherwise you go to the next rule. For any rule after that you check the condition, excute if it's true, and move on to the next rule if it's not. Only 1 rule must be excuted at any point, even if more than 1 applies. Which ever rules condition is met first is the rule that is executed. In the last rule the conditions will always be omitted because it's condition is simply when all other conditions don't apply.
I realize that may sound very confusing, but once I show you how it works you'll see it's a simple and convenient way to define powerful functions.
Here is how we will define addition ...
FORMAL DEFINITION OF ADDITION
--------------------------------------------------------------------------------------------------
Let +(a,b) be defined when a,b e N as follows :
1. if b = 1 then +(a,1) = S(a)
2. +(a,b) = S(+(a,P(b)))
--------------------------------------------------------------------------------------------------
Note that +(a,b) = a+b. Recall that in function notation we use a symbol followed by parathesis. Contained within the parathesis are all the variables seperated by commas. Note the operation of addition is actually a "binary function", that is, it's a function of two variables. Another important thing to note is that addition is defined only by using the fundamental functions S(n), P(n), and itself.
We can say that addition is a "child function" of the "parent functions" S(n) and P(n). As we will soon see, we can repeatly invent new functions by defining them with pre-existing functions.
Evaluating Expressions
To show how this would actually work in practice, consider +(3,3).
+(3,3)
Note: since b = 3 and not 1, rule 1 does not apply, therefore we apply the transformation in rule 2...
Rule 2. +(a,b) = S(+(a,P(b)))
so...
+(3,3) = S(+(3,P(3)))
We will assume that we can take the predecessor and successor of any natural (except of coarse P(1) which is undefined in our system) simply by using the rules of decimal notation thus we can say ...
S(+(3,P(3))) = S(+(3,2))
You might wonder why we can't take the successor of +(3,2). We are not allowed to take the successor of any expression unless it is already in decimal form. Assuming we don't already know what +(3,2) is, we can't take the successor of the expression until we "solve" it. So how do we proceed?
We proceed by solving the inner most expression. In this case b = 2 for +(3,2) and b =! 1 (b DOES NOT equal 1), so rule 2 applies again...
so...
S(+(3,2)) = S(S(+(3,P(2)))) by virtue of rule 2
S(S(+(3,P(2)))) = S(S(+(3,1))) since P(2) = 1
Now b = 1 in the inner most expression so rule 1 applies ...
S(S(+(3,1))) = S(S(S(3))) by virtue of rule 1
Now we can take the various successors ...
S(S(S(3))) = S(S(4)) since S(3) = 4
S(S(4)) = S(5) since S(4) = 5
S(5) = 6 since S(5) = 6
Thus ...
+(3,3) = 6
Which is the result we were looking for since +(3,3) = 3+3
Proof that our definition defines addition
So what exactly is going on? Consider this.
If we have +(a,b) where b > 1 then we are going to be taking the successor of +(a,P(b))
P(b) = b - 1 so we have S( +(a,b-1) ). If b-1 > 1 then we repeat the process and will get
S(S( +(a,b-2)))
if b-2 > 1 then next we get S(S(S( +(a,b-3) )))
Note that the number of "nested" successor functions is also the number being subtracted by b. It follows that ...
+(a,b) = S(S(S( ... S(S(S( +(a, b-k))) ... ))) where there are k copies of "S" provided b+1 - k > 1
We know that since b is finite that at some point b-k will be equal to 1. When it is the final expression will be replaced by S(a). Now imagine we have expanded the expression to ...
S(S(S(...S(S(+(a,1))) ... )))
where there are k copies of "S" it follows that 1 = b- k. So what does k equal ? Using alittle algebra ...
if
1 = b - k
...
k + 1 = b
...
k = b - 1
So we now know that we have b - 1 nested successor functions. When +(a,1) is replaced with S(a) the expression will change from ...
S(S(S(...S(S(S(+(a,1))))...))) with b - 1 nested successors
to...
S(S(S(...S(S(S(S(a))))...))) with b nested successors.
Next note that S(a) = a + 1 , S(S(a)) = S( a + 1 ) = a+1+1
In general S(S(S(...S(S(S(a))) ... ))) where there are k sucessors = a + 1 + 1 + ... + 1 + 1 with k "+1"s.
So we have in the case of
S(S(S(...S(S(S(S(a))))...))) with b nested sucessors = a + 1 + 1 + ... + 1 + 1 with b "+1"s = a + b
But I already know how to add!? : Rote memorization vs. the Algorithmic method.
At this point your probably thinking, that seems like an aweful lot of work just to add two numbers. I already know how to add, 3+3 = 6, I can do that in an instant, so what gives?
The reason you can do 3+3, 2+2 and even 1+1 in an instant is simply because you've memorized the answers. In fact you probably already have many basic binary operations memorized. Remember how in grade school they would make you memorize those times tables? Some people memorized them by studying or practicing, and others didn't bother. But even those who didn't memorize the table could do multiplication (albeit alittle slower). So if you didn't know off the top of your head what 8 x 7 was how would you "solve" this. Most people have ways of going about this. For example if they don't know what 8 x 7 but they happen to know the 8 x 3 = 24, then they can simply add up a pair of 24's , and then add 8 to the sum. We can understand that in this way ...
8 x 7
=
8x3 + 8x3 + 8
=
24 + 24 + 8
=
48 + 8
=
56
Note that we are simply breaking 8 x 7 into smaller operations that we can perform. Those smaller operations themselves may be excuted by memory, or if not, you have to break it down further until you reach operations that you can perform.
But that's multiplication, ... anyone can do addition ?!
If you think back there was probably a time when you used to count on your fingers (or in your head) in order to add. Why do children do this? Because they don't know what something like 5 + 3 is by memory, just like some people don't remember what 8 x 7 or 9^4 is. If you don't have the problem simply filed away in memory then you have to "compute" the answer. But how do we "compute" things like exponents, multiplication and even addition. Through a step by step process, an algorithm.
When children count on their fingers they are actually excuting an algorithm to add. Now how do you actually do this. First you put up the number of fingers for the first number, say 5. Then you count off 3 additional fingers. Then you count the total, 8. Thus 5 + 3 = 8 , and you "computed" it only using your fingers. In fact every time you count off an additional finger your actually taking the successor function of the previous number of fingers. So starting with a fingers and counting off and additional b fingers is the same as a within b nested successor functions. Thus addition is actually built on the successor function.
And what is the successor function? The successor function is essentially counting. In this way we can understand addition as merely an extension on counting.
All the above mathematical formalism is simply a written form of the finger counting. Of coarse if you already have +(3,3) memorized you needn't go through the tedious process, but always remember the fact that +(3,3) = 6 isn't some arbitrary assignment. Once you agree to label the first six numbers, 1,2,3,4,5,6, it becomes a fact that 3+3 = 6. That fact however is built on the system itself, we can not arbitrarily chose to say 3+3 = 7, or 2+2 = 5, they equal the numbers they do because of the process, not because some dictator woke up one morning and said "from now on 2+2 = 4".
I only hammer this point because it is something that student of math often miss. When they learn the rules of math they are often under the impression that the rules and answers are abritrary and make no sense, but in fact there are reasons everything is set up the way it is.
With this in mind note that we can easily find +(3,4) provided we know +(3,3) = 6.
we know that...
+(3,4) = S(+(3,3)) because b > 1
and
S(+(3,3)) = S(6) because +(3,3) = 6
and
S(6) = 7
In this way, even if we only knew how to count, and didn't even know what 1+1 is, we could eventually compute various addition problems, memorize their answers, and then use those results to solve additional problems. Fundamentally, this is what the process of mathematics is all about. Building the new from the old. It is also fundamentally what generating large numbers is about :)
Building Multiplication from Addition
We have finally got the fundamentals out of the way. We can now start building new higher level operations from older operations.
Any function which is defined using fundamental functions and itself I call a "primary function". So addition is one of many possible primary functions.
I define a secondary function as any function defined using fundamental functions , primary functions , and itself.
In general a kth order function is any function defined using k-1 order functions and below, and itself.
Although it might seem that this system would create an orderly hierarchy of functions , it in fact becomes self contradictory. I will get into a theory of function construction later, but for now we will use this simply idea to try to classify functions in terms of "power" or "complexity".
According to this theory multiplication would be a secondary function because it is built from the primary function of addition.
You may have heard it said before that multiplication can be thought of as repeated addition. But what exactly does this mean?
Think of 3 x 4 for a moment, ... yes I know it's 12 ... but how do we "compute" that if we didn't have the answer memorized?
Well basically we would do 3 + 3 + 3 + 3. Ie. we would have a sum of "four" 3's.
In general , we can say if a and b are Natural Numbers ( Naturals) then ...
a x b = a + a + a + ... + a + a where there are b copies of a
Generally speaking however I don't like to use "..." to define a function. Although this kind of definition is clear to a person generally, a computer has to be shown a more explicit process.
Recall that we can write m+n as +(m,n)
In this case ...
a x b = a + a + a + ... + a + a (with b copies of a) = +(a,+(a,+(a, ... +(a,+(a,+(a,a)))... ))) with b copies of a
We can therefore define this in the same way we defined addition with the successor function, with iterations.
Here is a formal definition of multiplication ...
FORMAL DEFINITION OF MULTIPLICATION
--------------------------------------------------------------------------------------------------
Let *(a,b) be expression defined wh. a,b e N as follows :
1. if b = 1 ; *(a,1) = I(a)
2. *(a,b) = +(a,*(a,P(b)))
Note: *(a,b) = a * b = a x b
--------------------------------------------------------------------------------------------------
Note that when b = 1 , *(a,1) = I(a). In other words, if b = 1, then multiplication is simply the Input/Output function. This just means that it returns a.
This makes sense since we know 2 x 1 = 2, and in general a x 1 = a
Now let's try 3 x 3 using our formal addition. This time we'll assume that addition can be carried out routinely. So again we have ...
*(3,3)
since b > 1 rule 2 applies so...
*(3,3) = +(3,*(3,P(3)))
+(3,*(3,P(3))) = +(3,*(3,2))
because P(3) = 2 , Note: I will be omitted the predecessor step from here on.
+(3,*(3,2)) = +(3,+(3,*(3,1))) *(3,2) = +(3,*(3,1)) because b > 1
+(3,+(3,*(3,1))) = +(3,+(3,I(3))) *(3,1) = I(3) by virtue of rule 1 since b = 1
+(3,+(3,I(3))) = +(3,+(3,3)) I(3) = 3 def. of fundamental function I(n)
+(3,+(3,3)) = +(3,6) = 9 executing addition routinely
So *(3,3) = 9. Which makes sense since *(3,3) = 3 x 3 = 9
Why multiplication grows faster than addition...
It should be noted that it is almost always the case that *(a,b) > +(a,b)
that is... the product of two numbers is usually greater than the sum. Take this example ...
3 x 4 > 3 + 4
since
3x4 = 12 and 3+4 = 7
what about 4 and 5 ...
4 x 5 > 4 + 5
since
4x5 = 20 and 4+5 = 9
Will this always be the case. Take this example...
2 x 2 = 2 + 2
since both 2x2 and 2+2 equal 4!
Addition can also be greater than multiplication when a or b = 1 since
a x 1 = a < a+1
and
1 x b = b < 1+b
It turns out axb > a + b any time a,b > 1 and a,b do not both equal 2.
We can easily prove this. Assume the above conditions are met for a and b.
The sum a + b < a x b
It is an imporant fact that a+b = b+a , and axb = bxa. These are called the communitive properties of addition and multiplication respectively.
There are only three possibilities. Either a is greater, b is greater, or they are equal.
Assume a = b. Then ...
a + b = a + a = +(a,a) = +(a,*(a,1)) = *(a,2) = a x 2
Now ...
a x a > a x 2
provided a is greater than 2. If a = 2 that would mean both a and b are equal to 2 and that would contradict our first conditions that a,b>1 and a,b don't both = 2. Therefore if a = b , a > 2, and
a x a > a x 2
What if a > b. Then...
a + b < a + a = a x 2 < a x b provided b > 2
however even if b = 2 , then a cannot be 2. So a x b = a x 2
however according to our first assumption a + b < a x 2 so therefore a+b is still < a x b
Lastly what if a < b. Then...
a + b < b + b = b x 2 < b x a provided a > 2
however even if a = 2, then b cannot be 2. So b x a = b x 2
however according to our first assumption a + b < b x 2 so therefore a+b is still < bxa
Thus we have proved +(a,b) < *(a,b) provided a,b>1 and both are not = 2.
This result is important. It means we can state 234 + 456 < 234 x 456 without doing ANY arithmetic. Another reason this is important for our discussion of large numbers is because when things start getting more complex we are going to want to way to prove which of a pair of very large numbers is larger. If we can not determine which is the largest, it defeats the whole impetus of our large number pursuits.
Building Exponentiation from Multiplication
When we are first introduced to exponentiation we are usually told that it is a kind of short hand for repeated multiplication. The following definition is usually provided:
a^b = a * a * a * ... * a * a where there are "b" copies of "a"
While it is certainly valid to think of it as a kind of short hand notation, it is also equally valid to consider it as a function. We will of coarse want to express it formally in recursive form. Here is a formal definition:
FORMAL DEFINITION OF EXPONENTIATION
Let ^(a,b) be defined when a,b e N as follows:
1. if b = 1 ; ^(a,1) = a
2. ^(a,b) = *(a,^(a,P(b)))
Note: ^(a,b) = a^b
We can also define exponentiation recursively in the following more informal manner:
a^1 = a
a^b = a * a^(b-1) where b =! 1
Using the above definition let's try to resolve 3^3. We will assume that multiplication can be carried out in the usual manner:
3^3 = 3 * 3^2 = 3 * 3 * 3^1 = 3 * 3 * 3 = 3 * 9 = 27
Please note that there is a well established convention of resolving all operations from right to left. This is not the standard order of operations, however, as you'll see, for the purposes of generating large numbers this proves to be a very useful alternative. For now just accept that when evaluating expressions containing only addition, multiplication and exponentiation, we will always resolve from right to left regardless of the operations involved.
Let's look at another example, say 3^4:
3^4 = 3 * 3^3 = 3 * 3 * 3^2 = 3 * 3 * 3 * 3^1 = 3 * 3 * 3 * 3 = 3 * 3 * 9 = 3 * 27 = 81
I have emboldened the pertinent information from this computation. Note that the recursive definition eventually unfolds to establish the informal definition, namely that 3^4 is "four three's". Also note that we can think of 3^4 as 3 times 3^3. Thus we obtain 3*27 = 81. If we continue to 3^5 we will find that it is equal to 3*3^4. In other words, every time the power increases by one, the result triples! That is a significantly fast growth rate. The "3" here is known as the "base", while the power it's being raised to is known as the "exponent" or "power". The power has much more significance than the base. We will be using exponents a lot from this point on, and they form the basis for the majority of large number functions ( the ackermann function is one notable exception, which actually is a powerful extension of the successor function. We'll be looking into that in this chapter in a later article).
Because we'll be making such extensive use of exponents, it may help to familiarize yourself with some of the results ( a bit like memorizing times tables). In fact, people who work with large numbers a lot tend to memorize this numbers automatically because they pop up all the time. So here are some of the important ones:
2^2 = 4
2^3 = 8
2^4 = 16
2^5 = 32
2^6 = 64
2^7 = 128
2^8 = 256
2^9 = 512
2^10 = 1024
3^2 = 9
3^3 = 27
3^4 = 81
3^5 = 243
3^6 = 729
3^7 = 2187
3^8 = 6561
3^9 = 19,683
3^10 = 59,049
4^2 = 16
4^3 = 64
4^4 = 256
4^5 = 1024
4^6 = 4096
4^7 = 16,384
4^8 = 65,536
4^9 = 262,144
4^10 = 1,048,576
5^2 = 25
5^3 = 125
5^4 = 625
5^5 = 3125
5^6 = 15,625
5^7 = 78,125
5^8 = 390,625
5^9 = 1,953,125
5^10 = 9,765,625
6^2 = 36
6^3 = 216
6^4 = 1296
6^5 = 7776
6^6 = 46,656
6^7 = 279,936
6^8 = 1,679,616
6^9 = 10,077,696
6^10 = 60,466,176
7^2 = 49
7^3 = 343
7^4 = 2401
7^5 = 16,807
7^6 = 117,649
7^7 = 823,543
7^8 = 5,764,801
7^9 = 40,353,607
7^10 = 282,475,249
8^2 = 64
8^3 = 512
8^4 = 4096
8^5 = 32,768
8^6 = 262,144
8^7 = 2,097,152
8^8 = 16,777,216
8^9 = 134,217,728
8^10 = 1,073,741,824
9^2 = 81
9^3 = 729
9^4 = 6561
9^5 = 59,049
9^6 = 531,441
9^7 = 4,782,969
9^8 = 43,046,721
9^9 = 387,420,489
9^10 = 3,486,784,401
10^2 = 100
10^3 = 1000
10^4 = 10,000
10^5 = 100,000
10^6 = 1,000,000
10^7 = 10,000,000
10^8 = 100,000,000
10^9 = 1,000,000,000
10^10 = 10,000,000,000
As you can see, these numbers grow quite rapidly. When the base is a fixed number (does not change) and the exponent increases linearly (by one at a time), the grow rate is said to be "exponential". There are a couple examples of exponential growth in the real world. Population grows in a nearly exponential manner, at least initially (it slows down as it approaches maximum capacity). Viruses and chain letters can grow exponentially. Businesses can grow exponentially, etc. People also describe things as growing exponentially when it grows very rapidly. While in the real world exponential growth is extremely fast, in the world of pure mathematics we can create rates of growth even faster than exponential. We can call these rates "Supra-exponential growth rates".
What are recursive functions?
Before we get started I want to make one last thing clear. There is a difference between the general definition of a function, and a recursive definition.
Most of the functions you will study in mathematics, especially in precalculus and calculus are actually continuous functions we can call "explicit functions". They are explicit in the sense that to find out the value for any given input, you merely need to insert the input into some kind of explicit formula. For example:
f(x) = x^2
Is an explicit formula. If we want to find f(3) we simply solve for 3^2 = 9. So f(3) = 9. Note that we do not need to know what f(2) or f(1) is to find f(3). However this formula can also be converted into a "recursive" or "implicit" form. We can say:
f(1) = 1
f(n) = (2n-1) + f(n-1) when n =! 1
Although it might seem surprising, these two definitions are equivalent, in that they define the same function over the domain of the naturals. Let's evaluate f(3) using the recursive formula:
f(3) = (2(3)-1) + f(2) = (6-1) + f(2) = 5 + f(2) = 5 + (4-1) + f(1) = 5 + 3 + f(1) = 5 + 3 + 1 = 5 + 4 = 9
so... f(3) = 9
As you can see we obtain the same value. By the way, the reason this works is because the nth square can always be expressed as the sum of the first n odd numbers, but I won't go into an elaborate proof of this here. However you can observe the difference of consecutive squares to convince yourself. For example 4-1 = 3 (an odd number), 9 - 4 = 5, 16 - 9 = 7, 25-16 = 9, 36-25 = 11, etc.
The important thing to note here, is that while the explicit form allowed us to simply plug into a formula without having to know other values of the function "f", the recursive formula required us to know each lower expression. The key feature of every recursive function is that it makes reference it itself. This is known as "recursion". The image of the mona lisa holding a picture of her own painting seen at the beginning of this chapter is an example of graphical recursion. This is not that different than what we will be doing with numbers very shortly.
The fact that a function can be defined using itself without contradiction may come as a surprise. Interestingly, we do have to be careful how we use a function within its own definition or it does lead to a contradiction. Take this example, that seems no more strange then our previous formula:
Let f(1) = 2
f(n) = f(f(n-1)) when n=!1
So let's see what happens. First off, f(1) = 2 by definition, so there is no problem there. Let's see what happens when we try to evaluate f(2):
f(2) = f(f(2-1)) = f(f(1)) = f(2) = f(f(2-1)) = f(f(1)) = f(2) = f(f(1)) = f(2) = f(f(1)) = ...
Do you see a problem. We keep getting the same expressions over and over again, but we never get to a stage where we can eliminate all of the nested functions. Thus we never find out what the value of f(2) is. The same thing will happen with any value greater than 1. We can say that f(2) does not terminate. In the world of large numbers a function which does not terminate is not "infinite", but rather "undefined". "undefined" is essentially no better than being equal to "zero". That is, it is disqualified from the large number race and not eligible for comparison to other expressions. This is an important point to bring up because non-terminating or infinite valued functions are basically considered a foul within large numbers. If you want to name the largest number ever never say " the largest number is infinitillion which I define as 1 followed by an infinitillion zeroes " because that is an example of a non-terminating recursive definition. It might seem then that we either have "smallish numbers" or "non-terminating infinities" so what's the point. However this is FAR from the truth. The key is to find ways to utilize the very powerful capabilities of legal recursive expressions to generate truly mind-bogglingly sized numbers. If you haven't learned about array notation, conway right arrows, or even steinhaus polygons I guarantee your in for quite a surprise by just how far you can go beyond the "everyday" large numbers that people are familiar with. It is truly a bizaree world of nightmarish scale and unbounded glory. If your curious to find out what I'm talking about proceed to the next article where I finally put all of this new theory in to practice. As you will see, we will quickly be able to have a much clearer perception of what was going on in section II, and more importantly we will easily be able to surpass it and enter into a completely new dimension of scale and size...