FANDOM


In this post, I'm going to demonstrate an alternative to Kleene's O that might be easier to understand. It assumes some familiarity with programming.

Kleene's JavaScript is a textual notation for notating any recursive ordinal, defined like so:

  • "0" is a Kleene's JavaScript program. It evaluates to the ordinal 0.
  • Let P be a Kleene's JavaScript program that evaluates to ordinal a. Then if you append "+1" to P, the result is a Kleene's JavaScript program that evaluates to the ordinal a + 1.
  • Let F be JavaScript code that consists of anonymous function f:
    • f takes a single nonnegative integer as an argument. (This is a theoretical variant of JS where integers can be infinitely large.)
    • f is deterministic.
    • f returns a string for every valid argument. That string must always be a valid Kleene's JavaScript program.
    • For all nonnegative n, the value of the Kleene's JavaScript program f(n) must be less than the value of f(n + 1).
    • Then the program "sup(F)" evaluates to the supremum of all f(n).

As always, examples help!

   0
   0+1
   0+1+1
   0+1+1+1

The finite ordinals have the simplest possible programs. I'm sure you can guess what ordinals they evaluate to!

   sup(function (n) {
       var result = "0";
       for (var i = 0; i < n; i++) {
           result += "+1";
       }
       return result;
   })

Here's the first nontrivial one. Notice what the anonymous function does -- for each n, it constructs "0+1+1...+1+1" where there are n copies of "+1". Its outputs for n = 0, 1, 2, 3, ... are 0, 0+1, 0+1+1, 0+1+1+1, ..., which have a supremum of \(\omega\). Therefore, the above program evalutes to \(\omega\). You can think of sup as a magic function that evaluates our anonymous function for infinitely many values and figures out their supremum.

   sup(function (n) {
       var result = "0";
       for (var i = 0; i < n + 1; i++) {
           result += "+1";
       }
       return result;
   })

Look carefully at the condition in the for loop -- this time the function outputs n + 1 copies of "+1". So its outputs are 0+1, 0+1+1, 0+1+1+1, ... which still have a supremum of \(\omega\). So we have constructed two programs that evaluate to \(\omega\), showing that Kleene's JavaScript programs are not unique representations of ordinals.

   sup(function(n){var r="0";for(var i=0;i<n;i++){r+="+1";}return r;})+1

This is \(\omega + 1\). I think it's pretty obvious why!

   sup(function (n) {
       var result = "sup(function(n){var r=\"0\";for(var i=0;i<n;i++){r+=\"+1\";}return r;})";
       for (var i = 0; i < n; i++) {
           result += "+1";
       }
       return result;
   })

Now this is where it gets interesting -- we're starting to put nontrivial Kleene's JavaScript programs into other ones. This one takes our \(\omega\) program and adds increasing copies of "+1". The result is \(\omega \cdot 2\).

   sup(function (n) {var r="sup(function(n){var r=\"0\";for(var i=0;i<n;i++){r+=\"+1\";}return r;})";for(var i=0;i<n;i++){r+="+1";}return r;})

Compressed variant of the above. I think you can see where this is going.

   sup(function (n) {
       var result = "sup(function (n) {var r=\"sup(function(n){var r=\\\"0\\\";for(var i=0;i<n;i++){r+=\\\"+1\\\";}return r;})\";for(var i=0;i<n;i++){r+=\"+1\";}return r;})";
       for (var i = 0; i < n; i++) {
           result += "+1";
       }
       return result;
   })

I sure hope I got all those backslashes right. This is, of course, \(\omega \cdot 3\).

   sup(function (n) {
       function add_omega(program) {
           return "sup(function(n){var r=" + JSON.stringify(program) + ";for(var i=0;i<n;i++){r+=\"+1\";}return r;})";
       }
       var result = "0";
       for (var i = 0; i < n; i++) {
           result = add_omega(result);
       }
       return result;
   })

And we're finally at \(\omega^2\)! To construct it, we have to start with 0 and create nesting programs where each one adds \(\omega\). (JSON.stringify is a JavaScript built-in function. In this case I used it to escape quotes and backslashes.)

Testing out code

Here's a very crude method to test out whether your program works. In a JavaScript interpreter, run this:

   function sup(func) { for (var i = 0; i < 4; i++) { console.log("n = " + i + ": " + func(i)); } }

and then run an example using sup(). It will give you samples of the outputs for n = 0, 1, 2, 3.

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.