9:13 AM
CMC: Find a polynomial function from NxN to N that is bijective.
Spoiler Alert: I'm astonished that such a thing exists, and how easy some examples are: spoiler

@flawr N×N?

N = {1,2,3,...}

what is N×N

N x N = {(1,1),(1,2),(2,1),(1,3),(2,2),(3,1),...} = {(a,b) | a,b in N}

isn't what you just mentioned basically bijective :P

9:21 AM
I did not mention any function? Or what do you mean?

oh polynomial function .-. how is this even possible

@ASCII-only yep, polynomial :)

O_o how do you have polynomial from N×N to N

That is the challenge:)

looks at spoiler
oh it's a polynomial in terms of x and y

9:27 AM
WHAAAT

This polynomial actually produces the usual diagonal enumeration:
I didn't expect this to be expressible as a polynomial!!!

Ah this makes it a lot less surprising (this is the generalization to NxNx...xN -> N)
But amazing none the less!
@MartinEnder You've been looking for such bijections (^) at some point, haven't you?

Yes, but I was looking at Z, not N.

9:36 AM
Z = complex?

Integers

oh >_> oops
does that not work for Z×Z to Z

@MartinEnder ah, sorry!
@ASCII-only That is probably not as simple because you'd somehow need to take care of the signs. Basically for Z x Z you have "four times" the N x N

4

I know that it's simple enough to map the integers, $\mathbb{Z}$, to pairs of integers, $\mathbb{Z}^2$, in a bijective way (i.e. a one-to-one mapping). You can wrap the integers around the origin of the 2D Cartesian grid like a spiral, or you can use some space filling curve, or you can map the i...

@MartinEnder Perhaps one could find an nice bijection between Z and N?
x -> (((-1)^x*x)+((-1)^x-1)/2)/2

9:53 AM
Yeah I was just trying to do the same with cos(x*pi)

ah you can replace (-1)^x with cos(x*pi), which is just the real part

Yeah

and now an inverse, hmm...
x -> 2*abs(x) - (abs(x)+x)/(2*abs(x)) = 2*abs(x) - (1+sign(x))/2 (the first only works for x!= 0)
ah here sign(0) = 0 #fail
Ok butI think I cannot find any really nice examples =/
Ah have you tried using @minxomat's compiler that "compiles" some sort of BASIC programs to "explicit" formulae?
Ah if I recall correctly this also relies on the convention that 0^0 = 1 and 0^x = 0 for x!=0
which also isn't nice

10:29 AM
@flawr x -> -1/2 + abs(-2*x - 1/2) is a way to write it that doesn't have wieidness with 0. Derived using max(a,b) = (a+b+abs(a-b))/2

10:43 AM
@flawr doesn't it basically replace BASIC statements with its mathematical equivalent

11:18 AM
@ASCII-only I don't know, I doubt you could always find a direct "mathematical equivalent". I mean many very mathematical things are not very explicit.

2 hours later…
1:21 PM
8

Ruby, 348 bytes, fψ0(ψ9(9))(9) where f is the fast growing hierarchy and ψ is an ordinal collapsing function described below. Try it online! def f(b,n=0,x=0)c,d=b;n<1?(b.class!=Array):x>0?(n.times{n+=b==1?n:f(f(b,n),n,1)};n):f(b)?(b>1?b-1:n):b.size>2?h(n,c,d):f(d)?(d>1?[c,d-1]:d>0?c:[c,n]):[c,...

Does anyone think my explanation is too advanced/complicated and that I need to dumb it down?

3 hours later…
4:16 PM
Is there an easy proof why TREE(n) is finite? It's non-obvious to me.

33

I am not a mathematician but I am interested in big numbers. I find them to be really interesting, almost god-like. I am watching a series of videos from David Metzler on youTube. I have a basic understanding of some fast growing functions. David does not cover Tree(n) which I've read is one ...

It's not obvious at all.

See I just want to know it's finite.
I'm hoping that has an easier proof than actualyl estimating the size.
I'm hoping it can be done without reading a lot of ordinal theory.

xD
Well, unfortunately, I myself have a fairly limited understanding of TREE(n)
I just know some upper bounds to it in the fast growing hierarchy.

5:09 PM
Oh, I had thought you were going to reference my answer to the TREE(3) problem

@SimplyBeautifulArt What is that?

It's a beautiful thing called an ordinal collapsing function.

@SimplyBeautifulArt What is that?

I assume you don't know what ordinals are?

@SimplyBeautifulArt nth?

5:11 PM
Sorta. But I'm talking about transfinite ordinals
Basically, ordinals have an "order".

the php answer also seems invalid to me I think tree(3) is way larger than some <100 bytes notice * exp(99)

@SimplyBeautifulArt That funny w?
$\aleph_0$ and that sort of thing?

0, 1, 2, 3, ..., ω, ω+1, ω+2, ...
@wizzwizz4 Those are cardinals.

@wizzwizz4 it's called an omega

@EriktheOutgolfer That's what lower-case omega looks like. TIL.

5:13 PM
Perhaps we should chat about this in Primes and Squares?

@SimplyBeautifulArt If I have a link I can move the conversation there.

### Primes and Squares

For discussion about programming, math, linguistics, music, sc...

19 messages moved from The Nineteenth Byte

So
We have some basic recursion
I'm going to use the Hardy Hierarchy to explain this stuff
H(n,0) = n
H(n,a+1) = H(n+1,a)
For any ordinal a
We also have H(n,a) = H(n,a[n])
You can imagine a[n] means the "nth element of the array a"

I've got that it's a function that returns an array, where each item of the set has a recursive definition.

5:17 PM
n is a natural number

looks to me more like it returns a number

@SimplyBeautifulArt Is that the triangular numbers?

H(n,a) returns natural numbers
@wizzwizz4 No

@EriktheOutgolfer I meant C.

H(3,2)
= H(4,1)
= H(5,0)
= 5

5:17 PM
btw @SimplyBeautifulArt that looks like it's just addition?

Fairly basic recursion so far
@EriktheOutgolfer And then we get into the sets/arrays
Basically, ω is in infinitely large set.
ω = {0, 1, 2, 3, 4, ...}

@SimplyBeautifulArt The set of natural numbers / integers / primes?

And ω[n] returns the nth element of this set. (ω[0] being the first)
@wizzwizz4 whole numbers.

@SimplyBeautifulArt Non-negative?
Or does it have negative indexes?

Yes. Ordinals can't be negative.

5:19 PM
@SimplyBeautifulArt eternal confusion
should say "non-negative" instead to avoid confusion :-p

:P
Okay, so if a is a set, then H(n,a) = H(n,a[n])

Why isn't ω[n] === n?

@wizzwizz4 It is

But the point of the notation is that you can get more complicated with bigger sets

5:21 PM
@SimplyBeautifulArt Does that apply to sets of sets?

So... for example,
H(3,ω)
= H(3,ω[3])
= H(3,3)
= ...
= 6
@wizzwizz4 Yes
Okay, so the next step requires a leap of faith
You'll want to imagine that ω+1 is a thing

@SimplyBeautifulArt Done.

And no, ω+1 is not equal to {1, 2, 3, ...}

Have we just taken the axiom of choice?

ω+1 is simply the next "ordinal" after ω.
@wizzwizz4 No idea, I only use ordinals to construct extremely large finite numbers and/or extremely large ordinals. :P
So H(3,ω+1) = H(4,ω)

5:23 PM
@SimplyBeautifulArt Is ω+1 = {\aleph_0 + 0, \aleph_0 + 1, ...}?

@wizzwizz4 Nope, ω+1 is simply ω+1, the smallest ordinal after ω.

@wizzwizz4 I guess $\omega+1$ doesn't reduce to anything
it's just a thing in your imagination

@SimplyBeautifulArt Like \aleph_n?

5:24 PM
@wizzwizz4 Aleph numbers are cardinals, which are completely separate from ordinals.

Ok.

but I think $\omega+\omega$ reduces to $2\omega$ which is $[0,2,4,6,8,...]$

@EriktheOutgolfer Nope
x'D Stay with the program for me

@SimplyBeautifulArt Ordinals are sets, and cardinals are non-negative integers.

@wizzwizz4 No, cardinals represent "how much", while ordinals represent "ordering"

5:26 PM
@SimplyBeautifulArt We're hobbyist programmers. Staying with the program is what we are worst at. :-)

lol
Well, so do we agree that H(3,ω+1) = H(4,ω) = H(4,4) = ... = 8?

What's \omega + \aleph_0?
@SimplyBeautifulArt No.

@wizzwizz4 You can't add them together :-/
11 mins ago, by Simply Beautiful Art
H(n,0) = n
H(n,a+1) = H(n+1,a)
11 mins ago, by Simply Beautiful Art
For any ordinal a
So do we agree that H(3,ω+1) = H(4,ω)?

@SimplyBeautifulArt Why can't you do H(3, (ω+1)[3])?
8 mins ago, by Simply Beautiful Art
Okay, so if a is a set, then H(n,a) = H(n,a[n])
10 mins ago, by Simply Beautiful Art
Basically, ω is in infinitely large set.

@wizzwizz4 Then what sort of set would ω+1 be?
ω is {0, 1, 2, ...} but what then is ω+1?

5:29 PM
@SimplyBeautifulArt I don't know. I don't know what ω+1 is.
7 mins ago, by Simply Beautiful Art
And no, ω+1 is not equal to {1, 2, 3, ...}
is all I know about it.

ω+1 is the next ordinal after ω, and it itself is called a successor ordinal.
Literally speaking, "next ordinal" describes the ordering between ω and ω+1.

@SimplyBeautifulArt Are successor ordinals not sets then?

ω+1 comes after ω. That's all there is to it.

If so, why are they ordinals?

@wizzwizz4 For simplicity here, they are not.
@wizzwizz4 Because they represent order.

5:30 PM
@SimplyBeautifulArt So why are some ordinals sets and others not sets?

@wizzwizz4 Because some ordinals cannot be described as "the smallest ordinal that comes after x", which would be x+1.
Is there any x such that ω is the smallest ordinal after it?

@SimplyBeautifulArt Is that like "you can't take a non-integer power of a negative number"?
@SimplyBeautifulArt No.

@wizzwizz4 Yeah

@SimplyBeautifulArt But why does that make it a set?

@wizzwizz4 Then the simplest way to describe it is "the smallest ordinal that comes after every element in some set"

5:33 PM
9 mins ago, by wizzwizz4
@SimplyBeautifulArt Is ω+1 = {\aleph_0 + 0, \aleph_0 + 1, ...}?
Why not then?

@wizzwizz4 First of all, aleph numbers are a no.

Am I conflating "the smallest ordinal that comes after every element in some set" with "the set of numbers that come after every number in a set"?

@wizzwizz4 Maybe. Note that there is no "set of all ordinals", rather its called a class.
If there were a set of all ordinals, that set would be an ordinal itself, and be greater than all ordinals, a contradiction.

@SimplyBeautifulArt A class of ordinals... I know about classes and I am making an assumption about why they can form a class and not a set.
That assumption seems to be a Promise type... :-(
I will do some independent research later.

You can imagine we start at zero.
Adding 1 takes us to the smallest ordinal greater than 0.
Adding 1 again takes us to 2, then 3, etc.
ω is then the set of all non-negative ints.

5:38 PM
Like polynomials...

Yeah, eventually like polynomials
ω+1 is to ω as 1 is to 0

So there's the class of polynomials with integer coefficients and there's the class of ordinals.
Can those form a bijection?

It is simply the next ordinal after ω.

Is 0 an ordinal?

@wizzwizz4 No
The class of ordinals far surpasses what is displayed above.
@wizzwizz4 Yes, it is considered the smallest ordinal.

5:40 PM
@SimplyBeautifulArt Does it eventually get to ω^ω?

So you can imagine the picture above paints a really long road.
@wizzwizz4 What do you mean?

@SimplyBeautifulArt An incredibly infinite road...

The step:
H(n,a+1) = H(n+1,a)
means that if you can go one step backwards through the spiral, do so, and add 1 to n.

@SimplyBeautifulArt Well, if you go n_0 w^0, n_1 w^1 + n_0 w^0... do you eventually reach w^w as a term?
@SimplyBeautifulArt Oh.

@wizzwizz4 Yeah.

5:42 PM
That's big.
That's really big.
Is that TREE?

Is TREE bigger?

Hehe, it takes a really long while to get anywhere near TREE(n)
But wait! Lemme finish!

@SimplyBeautifulArt for $n>2$

The step:
H(n,a) = H(n,a[n])
means that if you can't go one step backwards through the spiral, go to the nth step that is below a.

5:43 PM
because $TREE(1)=1\land TREE(2)=2$ iirc

@EriktheOutgolfer You know this already? :envy:

@EriktheOutgolfer No. The relation between ordinals and functions are as n → ∞. We don't talk about particular values.
So is this making more sense to you?

@SimplyBeautifulArt I understand the stuff we've talked about.

And I finally understand that diagram from Wikipedia. ;-)

5:45 PM
So after ω and ω+1, you get to ω+2, ω+3, etc.
And then you get:
ω∙2 = {ω, ω+1, ω+2, ...}
(not 2∙ω)
(Order of operations matter)
I don't want to go through the details, but 1+ω = {1,2,3,...} and 2∙ω = {0,2,4,...}
Which both equal ω
(1+ω is the smallest number larger than 1,2,3,..., which must be equal to the smallest number larger than 0,1,2,...)
Anyways...
Try expanding H(3,ω∙2)
And see what you get.

What's w*2-1?
Wait, ignore me.
I've got this.
Erm...
H(3,w+3)
H(6,w)
12

Yup.
Fairly basic so far.
What do you imagine ω∙3 is?

@SimplyBeautifulArt Like w*2 but with w*2 instead of w?

Yup
Btw, do you feel comfortable with me saying that ω = {1,2,3,...}?
Because if you think about it, this means that ω[n] is not well-defined.

@SimplyBeautifulArt I don't understand.

5:53 PM
So what a[n] really means is not "the nth element of the set", but rather, "the nth element of the fundamental sequence"

w_n = n

@wizzwizz4 ω[n] = n+1 if you use ω = {1,2,3,...}
The point I'm trying to make is that a[n] is not defined until you choose it's fundamental sequence.
Here, I used ω = {0,1,2,...}

Oh... I see.

Yeah.
So you can't just go around making these functions without explaining how your ordinals break down.
A common problem for those who first learn about ordinal hierarchies.
Okay, so now onto ω^2.

I've got to go - I might be back within an hour but otherwise I'll not be back within 11 hours.

5:56 PM
Okay, cya
ω^2 = {0, ω, ω∙2, ω∙3, ...}
You can probably imagine how it keeps going from here.

Is there a +k factor?

@wizzwizz4 Not in my choice of fundamental sequence for ω^2

@SimplyBeautifulArt Ok.

You get "+k" when you expand the ω∙n parts.

Is there a way of defining all of the expansions?
sudo gtg now. o/

5:59 PM
No
Ordinals go beyond... everything?
You can define all expansions less than some maximum ordinal
For example, Cantor normal form let's us easily define all expansions less than {0, 1, ω, ω^ω, ω^ω^ω, ...}
In particular, you want to define it based on addition, multiplication, and exponentiation.

6:12 PM
Hey @fejfo

Hey

Any particular part you find confusing?

about the fgh aproximation of TREE(3)? I guess I mainly need a refresher on what the phi function does exactly, it was something with defining ordinals as the n-th fixed point of the previous ordinal set

It's not a phi function that was presented for an approximation, but rather a theta function

@SimplyBeautifulArt I'm still at the start of the messages you linked me too but for me it seems to help to imagen a succesor function S(a) = lambda x:a so ω+1 is just {ω,ω,ω,...} to me

6:16 PM
@fejfo Oh lol, that's an interesting interpretation.

It could be usefull to golf the fgh to but we're getting of topic

@fejfo I always forget this tip, but don't golf the fgh. Instead, use the Hardy hierarchy for ordinals greater than or equal to ε_0
Hardy Hierarchy is the one I've defined above. It has H(n,a+1) = H(n+1,a)
Mentioned in the footnotes of my answer, H(n,ω^a) = f(n,a)

I'm vaguely familar with the hardy hierachy but it seems pretty simple to me H(0,n)=n
H(a,n)=H(a(n),n) (if you use that successor thing you don't even need to handle integers separately)

@fejfo It ought to be H(a,n) = H(a[n],n+1)

ofcourse otherwise you just go down to 0 without ever increasing n

6:23 PM
That's your typo, so don't "ofcourse" me :P
Um, so your problem is you don't know how large ϑ((Ω^ω)ω)+1 is?

no it's good you corrected me, I was just saying it makes sense to me that that +1 needs to be there. And yes I guess that is the problem

Well, we have the multi-variable Veblen function
which returns fixed-points, as you've mentioned.

yes

φ(0,x) = ω^x
φ(1,x) = xth fixed point of y = φ(0,y)
...
etc. for φ(a,b)
φ(1,0,x) = xth fixed point of y = φ(y,y)
φ(1,1,x) = xth fixed point of y = φ(1,0,y)
etc.
φ(1,0,0,x) = xth fixed point of y = φ(y,y,y)
φ(1,0,0,0,...) = Small Veblen Ordinal

It's not entirely clear to me how you know what the xth fixed point is.

φ(1,x) for example I know it's supposed to be around epsilon_x but how do you know the fundamental sequence from just know it is a fixed-point?

6:31 PM
φ(ω,0,0,0,...) = ϑ((Ω^ω)ω)
@fejfo In general, the first fixed point of x = f(x) is {0, f(0), f(f(0)), f(f(f(0))), ...}
The second fixed point of x = f(x) is {y+1, f(y+1), f(f(y+1)), ...} where y is the first fixed point.
etc.

That makes sense, does it have to start with 0? what if f(0) happens to be 0 but f(1) is huge?

If f(0) = 0, then 0 is trivially the first fixed point.
So start with 0 to be safe.
Otherwise, you'll probably be able to produce a sort of squeezing. Something along the lines of
0 < 1 < f(0) < f(1) < f(f(0)) < f(f(1)) < ...
In which case starting with 1 or 0 makes no difference.

Yes that seems to work, but φ(1,0,x) = xth fixed point of y = φ(y,y) seems to imply y is an ordinal how do you go about φ(ω,x)=? φ(ω[x],x)?

@fejfo I prefer to say that φ(ω,x) is the xth ordinal which is a fixed point to y = φ(z,y) for all z < ω.

that's better because otherwise φ(ω,ω²) would equal φ(ω[ω²],ω²) and I have no idea what ω[ω²] would mean.

6:42 PM
@fejfo Usually, we say φ(ω,x)[n] = φ(ω[n],x)
Er no

φ(ω,0,0,0,...) = ϑ((Ω^ω)ω): how exactly do these notations translate?
φ(a,0,0,0,...) (n zero's)= ϑ((Ω^n)a) ?

φ(ω,x)[n] = φ(ω[n],y+1), where y = 0 if x=0 or y = φ(ω,x-1) if x is a successor or φ(ω,x)[n] = φ(ω,x[n]) if x is a limit ordinal.
@fejfo Not n zeros. If you had n zeros, it would translate into ϑ((Ω^n)a)
In general, φ(a0, a1, a2, ..., an) = ϑ((Ω^n)a0 + (Ω^n-1)a1 + ... + an)
If I remember correctly.
@wizzwizz4 A polynomial of Ω's :-)

@SimplyBeautifulArt I'm back.

Cool :-)
We were just at ω^2 if I do recall.
54 mins ago, by Simply Beautiful Art
ω^2 = {0, ω, ω∙2, ω∙3, ...}
Try expanding H(3,ω^2)

@SimplyBeautifulArt so why did you go way past the Bachmann-Howard ordinal in your answer? Isn't the Bachmann-Howard ordinal much much huger than the Small Veblen Ordinal? (after this I will let you explain to wizzwizz4 (or even try to help if I can))

6:53 PM
@fejfo Because going past it is safer than going just a little bit past it, and plus, the simpler the expression, the golfier.
OH SHOOT!
I can golf it a bit real quick...
Anyways...
@wizzwizz4 Feel free to write out your steps a few at a time.

Erm....
(w*3)[3]

Yup
Oh, you are confused?
ω[3] = 3
ω∙2[3] = ω+3
ω∙3[3] = ?
ω = {0, 1, 2, ...}
ω∙2 = {ω, ω+1, ω+2, ...}
ω∙3 = {ω∙2, ...?}
ω∙3 = {ω∙2, ω∙2+1, ω∙2+2, ...} @wizzwizz4

No, just trying to think.
I'm starting to struggle. I don't usually work on new stuff so I'm not used to it. :-)
Lag.

Lol, "lag" is an interesting description.

I can't talk.
My connection's gone.
Lag.

7:02 PM
Perhaps its a good time to define all fundamental sequences involving addition, multiplication, and exponentiation?

A more explicit definition might be helpful:
ω[n]=n
(ω*(k+1))[n]=ω*k+ω[n]=ω*k+n
(ω^(k+1))[n]=ω^k*ω[n]=ω^k*n

Ah. My messages aren't sending so easily either.
I usually use the following definition:

ω[n] = n

(a+b)[n] = a+(b[n])
(a∙b)[n] = a∙(b[n])
(a^b)[n] = a^(b[n])

a∙(b+1) = a∙b+a
a^(b+1) = (a^b)∙a
In this case, ω∙3 = ω∙(2+1) = ω∙2+ω
(ω∙2+ω)[3] = ω∙2 + (ω[3]) = ω∙2 + 3
Btw, fun fact.
You can use ordinals to show that my simplified Goodstein sequence always goes to zero eventually.
You can also use ordinals to show that most modifications of my sequence will eventually go to zero.

I don't think I can talk at the moment. Perhaps in ~10 hours my connection will be back. I'm having a storm right now and my phone line is probably down half the time.
Bye. o/

@wizzwizz4 Bye! My connection is also funky.