Descondificando CC

Peano's Axiom 1 & 2 in Javascript

October 26, 2019

Javascript
Basic

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:

    1. The set contains a particular element denoted 0. 0 is therefore a natural integer.
    1. Each element n in the set corresponds to a successor: S(n). Any natural whole has a successor.

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.