## FANDOM

10,835 Pages

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) {
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++) {
}
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.