Peano's Axiom 1 & 2 in Javascript
October 26, 2019
From Wikipedia: The Peano axioms, also known as the Dedekind–Peano axioms or the Peano postulates, are axioms for the natural numbers presented by the 19th century Italian mathematician Giuseppe Peano.
There are 5 Peano's axioms, and in this blog-post we're going to focus on the first 2 axioms and see how to implement them in Javascript.
The first two axioms are:
-
- The set contains a particular element denoted
0
.0
is therefore a natural integer.
- The set contains a particular element denoted
-
- Each element
n
in the set corresponds to a successor: S(n). Any natural whole has a successor.
- Each element
And their formula looks something like this:
a + 0 = a (1st Axiom)
a + S(b) = S(a + b) (2nd Axiom)
Now let's apply the above formula to represent natural numbers(ℕ
).
Imagine that we have a function that takes as a parameter an integer and applies the formula we just see and returns its result.
This is how the number 5
would look after we apply the above formula:
S(S(S(S(S(Z)))))
So, How'd we implement this in JavaScript?
For the first implementation, we're going to use recursion
.
const fromIntToPeano = n => {
if (n === 0) return "Z";
return `S(${fromIntToPeano(n - 1)})`;
};
The above function takes an integer(x
) as parameter, if it's 0
it'll return Z
otherwise it'll return S(x-1)
.
So if we run the function with an integer of our choice, it should return a string with applied formula.
fromIntToPeano(5); // S(S(S(S(S(Z)))))
We can also create a function that takes a string of S(x)
and turns it into an integer.
const fromPeanoToInt = n => {
if (n === "Z") return 0;
n = n.slice(2).slice(n.lenght - 1, -1);
return 1 + fromPeanoToInt(n);
};
So if we'd run the fromPeanoToInt
and pass to it a string S(S(S(S(S(Z)))))
it should return the number 5
.
While these two recursive functions work fine for small numbers, they quickly run out-of-memory for big numbers (i.e. 10.000).
Loops to the rescue.
To fix the StackOverflow
error, we could implement these functions using a while
or for
loop.
We're going to implement them using a while
loop.
const fromIntToPeano = n => {
let res = "Z";
while (n > 0) {
res = `S(${res})`;
n -= 1;
}
return res;
};
const fromPeanoToInt = n => {
let sum = -1;
while (n !== "") {
n = n.slice(2).slice(n.lenght - 1, -1);
sum += 1;
}
return sum;
};
After fixing the functions, we can then call them with integers greather than 10.000
.