Chapter 2 - Addition of multiplications
Addition and multiplication are the first operations that they teach in school. They are somehow related, for example when when you look at the multiplication table it is clear that in each row numbers are being ADDED repeatedly.
|2 +2→||4 +2→||6 +2→||8 +2→||10 +2→||12 +2→||14 +2→||16 +2→||18|
How does addition work? Or if you prefer, what are properties of the operation we call "addition"?
And if I know the properties of addition, can I then from them the properties of multiplication? Are they related? How?
Finally, if addition and multiplication are related, as operations on numbers, would it make sense to use both of them in the same math expression? And in what situations would that be needed or even be meaningful?
To answer these questions we will need to take a step back, and look at whole numbers again, and focus on another one of the core tricks of math: once you find a good, solid idea, repeat repeat repeat!
Repeating a good idea is clever, also considering what we said in chapter 1, that math is a creation of people to understand and work with counting and numbers. Numbers are an abstraction, they are no longer sheep or dots, they live in a world of their own, and have rules and properties that are idealizations of those of sheep or dots. Because they are abstract from the specific items that we are counting, numbers can be SEEN in many different situations, hence, it makes sense that we will be able to reuse the same ideas about numbers in a lot of contexts. And even the most basic math activity of all, counting, is a repetitive activity... think of "counting sheep" to fall asleep!
Addition, one step at the time
According to a definition by Peano (the so called Peano's axioms) whole numbers can be written starting by zero and then adding one repeatedly. For example, 3 = 0 +1 +1 +1.
Note: we are considering only positive whole numbers for now.
According to Peano the action of adding one can be called "calculating the successor of a number". So 3 would be uniquely identified by saying "it is the number that is the successor of the successor of the successor of zero"; uniquely because no other number is exactly three steps away from zero. OK, fine, but... this looks very similar to unary numbers (see chapter 1), only that here we have a way to express that a number is zero! Let's write a few numbers in the Peano way, using Z for 0 and S for successor (or +1): Z = 0 , SZ = 1, SSZ = 2 , ... , SSSSSZ = 5, ... OK, so any whole number can be written as a Peano number (excluding negative numbers for now), and these numbers look pretty primitive, meaning that they are very close to counting sheep: 3 sheep are represented here by SSSZ; so apart from the Z character, to know what is the meaning (value) of a Peano number, you just count how many Ss there are. In general, if a is a whole number, then: a = S ... SZ = 0 +1 ... +1
Fine, now that I know that a number is a repeated addition of +1s, what does that tell me about adding two numbers?
Well, as usual let's build some intuition of what happens with a concrete example, then we can think of a general rule... We can start with an addition like 5 + 3, and we could try just putting two Peano numbers together... that worked for unary numbers. Unfortunately that won't work here, because 5 + 3 becomes: SSSSSZ + SSSZ and when I attach them together I get SSSSSZSSSZ which is not a Peano number (it has two Z for instance, and it should not). So a better idea would be: drop the Z at the end of the first number, then add by attaching them together: SSSSSZ + SSSZ → SSSSS
Z and SSSZ → SSSSSSSSZ.
Interesting. Another way to look at addition is that it looks like the successor operation repeated many times. For example, if 3 is also "+1 repeated 3 times", then 5 + 3 must also be 5 + 1 + 1 + 1. More in general then, if I have two numbers to add, called them a and b, it is also correct to say:
a + b = a +1 ... +1
A different definition of addition However we decide to define the addition of Peano numbers, the addition operation will have some specific properties. When I'm adding numbers, it does not matter in which order I put them together. For example, calculating 5 + 3 and 3 + 5 I will get the same result. Using Peano's notation in fact: 5 + 3 → SSSSS
Z and SSSZ → SSSSSSSSZ
3 + 5 → SSS
Z and SSSSSZ → SSSSSSSSZ
And in the general case a + b is just a bunch of Ss representing a put together with another bunch making up b, then clearly it does not matter in what order I put them together, the result will be the same:
a + b = b + a
And this is true for any two numbers!
Really?! What about if b is 0? Or 1? Let's see. I can try putting b = 0 in the formula above, and I get: a + 0 → S...SZ and S...SZ → S...SZ and Z = a
because what is "Ss repeated 0 times"? It must be nothing, right?
So it is true for all (whole) numbers that adding zero to any number has no effect: the result is just the same number. Not a big surprise there, but good that now we could SEE where these properties of the addition come from.
And what about b = 1? What do you think?
A whole number a plus one is... a + 1 → S...SZ and SZ →
Z and SZ →
the successor of the number a. Again nothing too surprising here, but at least our intuition of what it means to add two numbers holds when we express it in terms of Peano numbers.
So this is it for the addition? Not really, there is one more thing we might want to consider: is the addition a REVERSIBLE operation? After having added two numbers together we get a new number: can we find the two original numbers, starting only from the new one?
As an example consider this: 3 + 5 = 8, but 8 = 1 + 7 and 8 = 2 + 6 and also
8 = 4 + 4. So the answer is "no", addition is not reversible. The numbers added up are somehow mixed beyond any possibility of reconstructing them back from their sum.
It is like taking the letters of two words, putting them together, then create an anagram with all the letters available; given the resulting anagram it would be very difficult to find surely and exactly the two original words. For example knowing that I got the anagram SUPERMAN, can you guess/find the two words I started with?
Solution at the end of this chapter.
What does it mean to multiply?
OK, so now, thanks to Peano numbers, we have a definition of numbers and addition that is based on the idea of repeating something many times. We also found some properties of addition (as an operation).
Now there is one thing we have not considered when adding to numbers: what if they are the same? Or, if you like "what is a + a?" for some whole number a, that is greater or equal to zero (because we are still not sure if this Peano-stuff works with negative numbers). And since we are asking this kind of questions, what is a + a + a, etc. ?
Since we have not defined what it means to multiply two Peano numbers (but we do know what it means to multiply two regular, base 10 numbers) the best we can do is try and figure out what happens to a + a using the rule we have for adding Peano numbers and perhaps the properties of addition. Remember that a Peano number is a repetition of +1s, so for any whole number a we can write: a → +1 ... +1
a → S...SZ
But what about a + a? a + a → S...SZ and S...SZ = S...SZ = "2-times a"
or "a added to itself 2 times". And what about a + a + a? a + a + a = S...SZ = "3-times a"
Interesting! So in general adding a number a to itself b-times would look like this: a + ... + a = "b-times a"
and that is precisely a * b. So for us a * b means "a added to itself b-many times".
Also for the multiplication we can try to build an intuition of how it works. First of all we could try and visualize additions as counting lines of dots. For example: 3 + 2 = 5 could be visualized as ••• + •• = •••••
Then "multiplication" becomes synonymous of "counting all dots in an area", and
5 * 4 = 20 becomes the number of dots in this rectangle
• • • •
• • • •
• • • •
• • • •
• • • •
We can also do something else: calculate this multiplication using our rule for addition: 5 * 4 = 5 + ... + 5 = 20
OK, it works. So multiplication of two numbers is really a repeated addition of one of the numbers, as many times as the second.
But if multiplication (as an operation) is just "repeated addition", does it mean I can derive
the properties of the multiplication from the properties of addition?
Perhaps not... because it is not so clear how to go from a + b = b + a, or a + 0 = a, to something about multiplication... But we could reason in the same way we did for addition, and ask: "what happens when I multiply a and b?" and "what about multiplying b and a instead?". Also interesting are the questions: "what happens when I multiply a number times 0? or times 1?". Luckily we can find answers for all these questions using what we have found so far about Peano numbers, addition and multiplication!
So, let's cut to the chaise: is a * b = b * a?
Well, if we go back to the idea that "multiplication is counting all dots in an area", then the same area can be seen in two ways. In our example of 5 * 4 we could see it as:
• • • •
• • • •
• • • •
• • • •
• • • •
S...SZ and ... and S...SZ
and we also can write: b * a = b + ... + b →
So adding a with itself b times or adding b with itself for a times, must be the same. And that is true for any two numbers. Terrific!
OK, but what about a * 0 and a * 1? That should be simple: just take a * b, put b = 0 and then b = 1, and use our definition of multiplication! Doing that we get: a * 0 → a + ... + a → "do not add anything" → 0
and: a * 1 → a + ... + a → a
Which means that a number times one remains the same as itself. All in all, not very surprising. But at least we got to confirm our intuition that the multiplication properties that are similar to those of the addition, and they make sense with our intuition of what multiplication should be. And I feel I gained something in the process: now I get why these rules and properties are as they are.
Finally, multiplication is also not reversible, like addition, because for example 20 can be the result of MANY multiplications: 5 * 4 = 20 = 2 * 10 = 1 * 20 = etc.
What happens when we use addition and multiplication together?
If multiplication is a repeated addition, how much sense does it make to mix the two operations?
Well, we can look at two possible ways to mix + and * in the same calculation:
( a + b ) * c = ?
( a * b ) + c = ?
Let's look at the first expression: ( a + b ) * c. It can be seen as the area of a rectangle with one side ( a + b ) and the other side c.
As an example, take: ( 3 + 2 ) * 4, draw it as a rectangle and count the dots:
And in the general case, for any three numbers a, b and c I can write: ( a + b ) * c = ( a * c ) + ( b * c )
In math this is called "the distributive property of multiplication", because you take a multiplication of an addition (of some terms in brackets), and what you get is the addition of two multiplications. Read the last sentence again... doesn't it sound a bit circular, like a magical formula?
It says that: add times add = times add times, or in symbols: (+) * (+) = (*) + (*) so what we are doing is swapping one operation with another, or if you like distributing the multiplication across the two additions.
As we will see in this and next chapters, this is a very useful property of expressions that contain both additions and multiplications. We will find lots of examples where this or something similar will help us.
The second case in which we mix additions and multiplications is:
( a * b ) + c
It turns out that there isn't much we can do to simplify or ever rewrite this expression: it is what it is. However, it looks similar to one of the linear combinations we talked about in chapter 1, a weighted sum of a and b, with c acting as weight. For example, if I pick b to be seven, I have: a * 7 + c. What happens here when I change the values of a and c? Try experimenting with the playground below.
What happens if you change c to 7 or more?
Now keep c fixed, for example c=3, and change a from 0 to 10. What kind of sequence of numbers do you get now?
Finally, pick a number, for example 23, and try to reach it by using a and c as dials. Start with a=0 and c=0, and NEVER allow c to be 7 or more.
If you can find 23, try with a few more target numbers. See how linear combinations work?
Interesting. When b is 10, the linear combination
( a * b ) + c
becomes ( a * 10 ) + c which is the same as a number base 10 with two digits: a and c.
For example, if a=2 and c=3, then ( a * 10 ) + c gives 23. This linear combination works just like an abacus (see previous chapter).
And from the abacus I know that if c is kept always between 0 and 9 (AKA b-1), then I can surely REVERSE the process, and go from 23 to ( 2 * 10 ) + 3. Moreover, 2 and 3 are the two numbers that will ever generate 23, so the representation of numbers on an abacus is unique.
Wait... so it seems that addition and multiplication are INDIVIDUALLY not reversible, but when used together, they can be reversible!
Together, and reversible!
A linear combination can also be a way to re-order, to count numbers in a different order.
In the playground below, experiment with different weights: try for example with
a*10 + c, and with a*2 + c. Change the values of a and c, too see how the numbers are re-ordered by the linear combination.
Which values of a and c generate the result 51?
Now try highlighting the number 6. Take a note of the values of both a and c, then move the cursors to the number 7. What happened to a and c? Why did they change the way they did?
The interesting thing here is that when the weight is large enough, each number comes from exactly ONE value of a and c. For example if I set the weight to 7, then the number 51 can only come from a=7 and
c=2. No other pair of values for a and c can generate fifty-one, only 7 and 2; and vice versa: fifty-one can be rewritten as
7*7+2 without any leftover, and it is the only way.
Even better, all numbers in the table above have this property!
Combine things while keeping them separated
So now we know that a linear combination can be used to ensure that things are reversible ...
But linear combinations can do something more for us.
Suppose I want to work with four numbers, combine them, but be able to remember each one separately too. What I could do is use a linear combination (AKA a weighted sum) like: A * weight1 + B * weight2 + C * weight3 + A
and FIND some large enough weights so that I don't risk mixing my four numbers A, B, C and D.
Also, when we only had two numbers to mix, but keep separated (taking advantage of the reversibility of certain linear combinations) we used the expression a * 10 + c. And the whole thing was reversible, provided c was always smaller than a.
So why not try with the same idea, and even repeated it over and over, for all my four numbers? (this is math after all, and math loves repetition!). The idea with the two numbers was then to SCALE one 10 times, and then add the other. What does that look like, with four numbers?
I want to start with only A and B (because I know what I'm doing with two numbers), then put in the other numbers, one at the time. What I get is:
A → + B → + C → + D
This might look weird, but it is what we said: "scale 10 times, and add a number, then repeat". OK? So, is this formula revealing anything about the weights we were searching for? Sure, let's try to make the two formulas look the same: A * weight1 + B * weight2 + C * weight3 + D and ( (A * 10 + B) * 10 + C ) * 10 + D
We can simply calculate the last formula: ( (A * 10 + B) * 10 + C ) * 10 + D →
( A * 100 + B * 10 + C ) * 10 + D →
A * 1000 + B * 100 + C * 10 + D Bingo! I just have to build my weights as 10 (which incidentally is our base here) multiplied by itself repeatedly.
And in fact: 1000 = 10*10*10, 100 = 10*10, and 10 = 10... Cool.
What is interesting here is also that this linear combination of four numbers will convert them to a single number, but given that number I can work in reverse and always find for sure the original four numbers. And if the numbers A, B, C and D are larger than 10 I can still use a linear combination to keep them mixed but separable: I just have to use larger weights! For example if I know that my four numbers can be any number from 0 to 15, I simply have to choose my base to be 16 and I would get a linear combination like: A * 16*16*16 + B * 16*16 + C * 16 + D To see the use of such a linear combination, consider these four numbers: 0, 0, 12, 14 (which I choose because they are interesting but simple). If I substitute them to A, B, C and D in the expression above, I get: 0 * 16*16*16 + 0 * 16*16 + 12 * 16 + 14 →
12 * 16 + 14 →
206 Well, starting from 206 I am guaranteed to be able to work my way back and find the original values of A, B, C and D. Try it yourself, using the playground in the previous section: put 16 in the weight and see what two numbers you will need to combine to find 206. (spoiler! they are 12 and 14, so the numbers that generated 206 are 0, 0, 12, 14)
Even money works this way, only that with money we combine the different coin denominations to reach a specific amount; and in general we are OK with having multiple ways to combine the various coins to reach an amount. Looking at the coin denominations are weights we can see that they are not spread enough to ensure reversibility, which means also that there is no unique way to break an amount in coins. Money as linear combination
Using weights to give meaning
So far we worked with weights that are simply numbers... and we just saw that choosing a good set of weights can help keeping numbers separated in a linear combination.
But what happens if I want to use my weights to represent different quantities of ingredients, for example, like in the following recipe for pancakes:
1 * egg + 2 * dlMilk + 3 * hgFlour = 5 * pancakes
This is a linear combination of the variables egg, dlMilk, hgFlour and pancakes), where I am not interested in deciding which value to assign to the variables. In this case in fact 1 * egg is interesting because it is about eggs, not because egg has a certain value (say 123).
This way of using linear combinations brings us to polynomials. More about polynomials as great way to keep separated things of different type (chapter 5). We will use polynomials also to write mathematical questions and finding mathematical answers in chapter 6.
Moral of the story so far: numbers can be seen as repetition of +1s. The addition a+b becomes a repetition: I have to perform +1 to a, b-many times.
And finally, the multiplication a*b is a repeatedly added by itself, b-many times.
There are two basic ways to mix additons and multiplications in the same math expression. One leads to a remarkable property called "the distributive property of multiplication", which is and will be very useful when calculating and simplifying math expressions. The other way to mix additons and multiplications brings us to linear combinations, and the clever way they can combine many numbers while keeping them separated (or at least separable).
What if I repeat multiplication?
Addition is repetition of the +1 operation (according to Peano's view of whole numbers), and multiplication is also repetition, but of additions this time. So could I do a repetition of multiplication?
What would I get? Consider something like this:
2 * 2 * 2 * 2 = 2 * ... * 2 = "2 multiplied by itself 4 times" = 24
This operation is called POWER, and 2*2*2*2 can be read as "2 to the power of 4" which gives a result of 16. Power is repeated of multiplication, just like multiplication is repeated addition! In the general case, "a to the power of b" works like this: ab = a * ... * a = "a multiplied by itself b-many times"
What are the properties of the power operation, you might ask? Is it true that for any two numbers a and b, ab = ba? (AKA "does the order count?") Is power a reversible operation? And what happens if b is 0 or 1?
Well, we can start checking if the order of the operands count. I find it a bit improbable that ab = ba could be true for any two numbers a and b... so instead of trying to prove (AKA convince you) that it is true, I might look for a counter-example. If even a single example contradicts the rule that ab = ba, then it would be enough to conclude that the property is NOT TRUE in general. So here is the counter-example: 23 → 2*2*2 → 8 but 32 → 3*3 → 9 so no luck this time. In fact 23 ≠ 32 because the first is 8 and the second is 9.
Even if I found a counter-example and I KNOW that the property cannot be true for any two numbers, there might be pairs of numbers for which it is true. For example, it is true for: 24 → 2*2*2*2 → 16
42 → 4*4 → 16
Fine, but what about being reversible? Given the result of a power operation, can I find for sure which two numbers were used? Again, I can use 24 and 42 as an example; both we know that expression give 16 as result, so if I know that the result is 16 I cannot be sure if it came from "two to the power of four" or "four to the power of two". And that shows that the power operation is also not reversible, at least not in general.
Finally, I want to know what happens for values like 0 and 1. I know how to derive this: just put b=0 and b=1 in the definition (AKA the rule) for the power operation. When b=0 I get: a0 = a * ... * a → "a multiplied by itself 0 times" → ?
Well that is puzzling... what number should be the result of that calculation? Not clear.
So, let me try instead with b=1, see if I have better luck. When b=1: a1 = a * ... * a → "a multiplied by itself 1 times" → a
then the result is simply a, which is fine and makes some kind of sense. I still don't know what to do with a0, but perhaps it can help to look at other stuff that is true for the power operation. For example with addition and multiplication we were interested in mixing the two operations and see what happened. For example we know that a+a is 2*a and a+a+a is 3*a, etc.
I could do the same here, but with multiplication and power, and look at: a*a, which is a2, or a*a*a which is a3. I can even be a bit more general than that, and look at: ab * ac Surely that must be: ab+c because I can expand ab and ac, and write ab * ac as: a * ... * a * a * ... * a
and then I can GROUP all a together and get b+c of them: a * ... * a * a * ... * a
This is good and very interesting! And if for any a, b and c, it is true that: ab * ac = a(b+c) then I can choose c=0, and get: ab * a0 = a(b+0) = ab OK, but wait a minute there... If I know that something * a0 = something then it must be true that a0 = 1, from the properties of the multiplication! (Because one is the ONLY number that you can multiply by something, and get the same something as result)
So in a weird sense, math tells us that "a number multiplied by itself 0 times" is equal to 1, go figure... but it is true and we have just proven it.
Hint: use the rule of the power operation.
And by the way, how would you calculate ab * cb?
Where a, b and c can be ANY three whole numbers.
Moral of the story so far: now that we have worked out the POWER operation, we have three interesting operations that work on whole numbers: addition, multiplication and power. They are built incrementally, each new one is a repeated version of the previous, and we know some of their properties, which are also tied and intertwined, very much in the same way in which the operations are defined. For example when calculating an expression like ab * ac (AKA a multiplication of two power operations) we end up using addition, since the result is a(b+c).
One last thing... "a to the power of b" even makes sense when b is a negative number. What is a to the power of -1 ?
Beyond based 10
So by now you should be able to anticipate the next questions...
What happens when I mix all THREE operations in the same math expression? In which situations is that relevant or needed?
Well if you remember the numbers in base 10 (above), the weighted sum that allowed us to calculate a number given its digits IS an expression with addition, multiplication and powers (of 10). In base 10 the weights are 1, 10, 100, etc., and we restrict the digits to be numbers from 0 to 9. A base 10 number with four digits A, B, C and D is a certain number n, and I can calculate n using the expression: A * 103 + B * 102 + C * 101 + D * 100 → n For example the number with digits 1,2,3, and 4 is the number n=1234, because:
1 * 103 + 2 * 102 + 3 * 101 + 4 * 100 →
1 * 1000 + 2 * 100 + 3 * 10 + 4 * 1 →
1234 And this operation is REVERSIBLE, since the ONLY number that can be generate by 1,2,3, and 4 is in fact 1234, therefore, 1234 can be rewritten uniquely as
But what happens if we try with weights built using some other number instead of 10? The smallest number that we use for the weights is 2 (because 1 would make no sense, and we would loose reversibility). A number with digits a, b, c and d will then be written as a linear combinations of powers of two: a * 23 + b * 22 + c * 21 + d * 20 →
a * 8 + b * 4 + c * 2 + d * 1 and by analogy with the case of base 10, we might expect that a, b, c and d here can only be 0 or 1.
Welcome to base 2 (or binary numbers)! This way of writing numbers might seem weird, but it is perfectly legitimate and if we think in terms of spike abaci (see chapter 1), it is like saying that every spike can only have no bead or one bead: a very simple abacus indeed.
Let's see what happens when we take a number and write in the base 2 notation. For example to write 13 in base 2 we have to ask ourselves: "how can I build 13 using only powers of 2?". I can try, starting with the lowest powers of 2 and coming up. Remember that my target is 13: 1 = 1 less than 13 → 1 + 2 = 3 less than 13 →
1 + 2 + 4 = 7 less than 13 →
1 + 2 + 4 + 8 = 15 more than 13 oops! This strategy is not very good. I will try starting from the larger powers of 2, and going DOWN instead: 16 more than 13, nope! →
8 less than 13, good! →
8+4 = 12 less than 13 →
8+4+2 = 14 more than 13, nope! →
8+4+1 = 13 Found it: 13 is 1 * 8 + 1 * 4 + 0 * 2 + 1, so 13 in base 10 is also 1101 in base 2!
OK, but how do I read "1101 in base 2"? For example, 13 is read as "thirteen".
In base 2 it was decided not to read numbers as they look, so 1101 IS NOT "one thousand one hundred one", because we are not using base 10 here. We simply should read 1101 as "one one zero one"... kind of silly, but that is the correct way to read it.
An alternative way to write a number in base 2 would be to use our box notation (see chapter 1); the previous example 1101 would then become 1101.
Now let's look at the reverse problem: how to find the base 10 version of a binary number. Again, let's try just using the formula for the weighted sum. Let's start from any binary number, for instance 10011101 (in Computer Science it is typical to use groups of 8 binary digits, AKA 8 bits, or 1 byte), and plug them into the formula: a * 23 + b * 22 + c * 21 + d * 20 First we notice that the formula needs more terms: here I have eight binary digits, not only four, so I need to extend the formula to eight. digit8 *27 + digit7 *26 + digit6 *2 + digit5 *24 +
digit4 *23 + digit3 *22 + digit2 *21 + digit1 *20 And my digits are 10011101, so digit8, the leftmost one, should be 1; then digit7 is the next one going right, and should be 0, etc. OK, so to calculate the resulting base 10 number, I just need to replace each of the eight binary digits with its value: 1 *27 + 0 *26 + 0 *25 + 1 *24 + 1 *23 + 1 *22 + 0 *21 + 1 *20 →
1 *27 + 1 *24 + 1 *23 + 1 *22 + 1 *20 →
27 + 24 + 23 + 22 + 1 →
128 + 16 + 8 + 4 + 1 = 157 in base 10
Multiplying by 0 or 1 is interesting in itself! Here for instance it looks like a way to filter the powers of two: some will be multiplied by 0 and disappear, others will be multiplied by 1 and remain in the final calculation.
Another interesting observation here is that the weighted sum (AKA linear combination) can be seen at the same time as two things:
Try to see what the powers of 2 look like: for example what is 16 in base 2?
Then try the numbers near the powers of 2: for 16, you might try 15 and 17. How do they look like in base 2?
Combinations, but using multiplication and power
A linear combination is a mix of additions and multiplications, or more precisely it is an addition of multiplications. One of the most desirable features of some linear combinations is that they can be reversible.
Interestingly, we can combine numbers in other ways, and still get that nice reversibility. For example we can define a combination based on a multiplication of powers (instead of addition of multiplications), and what we get is the rather powerful Gödel numbering. Gödel numbering were created by Gödel to show that a list of numbers can be compressed into a single number. And that the process can be reversed.
The main idea is to start with a list of numbers, say 1, 2 and 3, and use powers of prime numbers to combine them: 21 * 32 * 53 → n
Note: we will talk more about prime numbers in the next chapter, when we explore subtraction and division. Just to get an idea how they look like, the first one thousand prime numbers are listed here.This way of combining numbers tends to create HUGE numbers, so ever for our small list of numbers n is probably already pretty big, and for slightly larger or longer lists the result will be even larger. Here n is 2 * 3*3 * 5*5*5 = 2250.
Fine, but is the process REVERSIBLE? If I only know n, can I find the original list 1, 2 and 3 again? According to Gödel the trick here is to rewrite n as the product of prime numbers (AKA perform the "prime factorization of n"), then look at the exponents of the primes, and presto! they will form the original list. Here I have to FACTORIZE 2250 in primes, and that will get me: 2250:2 = 1125 →
1125:5 = 225 →
225:5 = 45 →
45:5 = 9 →
9:3 = 3 →
3:3=1 where "2250:2" stands for "2250 divided by 2".
The result is 2250 rewritten as 2*5*5*5*3*3, and since the order does not count with multiplications, I can reorder the factors from small to large and get: 2250 = 2*3*3*5*5*5 = 21 * 32 * 53 which is exactly the list I started from: 1, 2 and 3. Wow.
Wait, wait, wait. Are we sure this method works for any list? After all for linear combinations we had to be clever about choosing the right set of weights... otherwise the combinations might not be reversible.
No worries. For Gödel numbering there is in fact a theorem that garantees that the factorization is always unique, so we cannot fail with this combination: it will always be reversible. Thanks very much Gödel.
So Gödel numbering works like a SUPER abacus, or if your prefer, a generalization of base 10
(see chapter 1), where multiplication and power are used instead of addition and multiplication.
To be precise a linear combination is an addition of multiplications. An addition
smtg + smtg + smtg
(smtg * smtg) + (smtg * smtg) + (smtg * smtg)
where all the smtg are different somethings, like values or variables.
A Gödel numbering is instead a multiplication of powers. Multiplication smtg * smtg * smtg of powers (smtgsmtg) * (smtgsmtg) * (smtgsmtg) Surprisingly Gödel numbering works whatever the numbers in the list are: we are not limited to pick small numbers, like in the case of linear combination (such as ordinary numbers in base 10). Gödel numbering has no problem compressing a list of any size, and containing arbitrary large numbers into a SINGLE (possibly humongous) number! For example, the list 4, 6, 7, 8, 12 becomes 24*36*57*78*1112, which is 16'486'713'209'345'820'741'011'250'000 and that huge number, incredibly enough, can be factorized in ONLY ONE way: precisely 24*36*57*78*1112 after eventually reordering the primes.
To get an idea how HUGE these numbers tend to become, try lists with larger numbers, for example: 77, 0, 123, 9.
Interestingly, this number system is positional: try 1,0,2 , then 1,2 and 2,0,1.
Finally, try a long list of small numbers; try for instance these lists:
3,1,4,1,5,9,2,6,5,3,5 (which are the first few digits of PI). Notice how fast the Gödel numbers grow!
Moral of the story so far: in mathematics there many ways to repeat the same idea or process.
Even something basic like numbers can be seen as repetitions of adding one, starting from zero.
A rule to add numbers is then defined that says:
a+b means a + "add one, repeated b-times"
It turns out that addition has certain properties, that we can derive by the way repetitions work. Multiplication is just a repetition of additions: a*b is simply a+...+a, repeated b-times. Also multiplication has properties similar to those of the addition.
It is also possible to combine many numbers in a single number, using a mix of addition and multiplication (in a linear combination), in such a way that we can reverse the process. This means that linear combinations when used in a clever enough way allow to go from many numbers to one, but also backwards, from a single number to the many. And it turns out that the trick required is the same that we discussed in chapter 1 with the abacus numbers (AKA base 10, our usual notation for numbers).
Furthermore, changing the way we generate the weights in the linear combination, we get alternative notations for numbers; for example instead of powers of 10, I can use powers of 2, and that gives us numbers made of only 0s and 1s: the so called base 2, or binary numbers.
We can even go further and keep repeating: repeated multiplications give us the power operation, which also has its properties, somehow similar and related to those of addition and multiplication.
And finally, we can even define a new kind of combinations based on a multiplication of powers (instead of the linear combination, that is an addition of multiplications): the very powerful Gödel numbering.
(1) Work with Peano numbers.
Convert all numbers in the following expressions in Peano's notation, the calculate the results of the expression, still using only Peano's notation. Only at the end, convert results from Peano number to ordinary, base 10 number.
- Example 1+2 = ?
1 → SZ
2 → SSZ
SZ + SSZ → S
Zand SSZ → SSSZ
SSSZ → 1+1+1+0 = 3
- 1+2+3 = ?
- 3*4 = ?
- 4*3 = ?
- 2*10+1 = ?
(2) Count like in the cartoons.
The characters in cartoons often have only eight fingers (four per hand). It makes sense that their abaci can only have 0 to 7 beads per spike, at any moment (instead of 0 to 9 in our case). This way of counting is known as base 8 and it works very much like base 10 or base 2.
To convert a number of three digits in base 8 to one in base 10 you just have to use the right linear combination of powers of 8: a * 82 + b * 81 + c * 80 where a, b, and c are the three base 8 digits. (NOTE: 82=64, and 80=1)
Convert the following base 8 numbers to base 10:
- 7 in base 8 is ? in base 10
- 8 in base 8 is ? in base 10
- 123 in base 8 is ? in base 10
- And finally, the largest number that you can write with three digits in base 8 is 777, or 777. What is that in base 10?
Solution: SUPERMAN = SPUR NAME, but also MAPS RUNE, and MA PRUNES.