Thread for Non-CA Academic Questions

[gameoflifemaniac]

hey, i'm working on a project in Scratch and need a formula for finding intersection points between a line and a circle (x1,y1,x2,y2 - points the straight is going through, x3,y3,x4,y4 - center and 'radius' of circle) and two circles (x1,y1,x3,y3 - centers, x2,y2,x4,y4 - 'radii'). Asking on their forum takes forever.
Nevermind, they did.

[fluffykitty]

(a,b)=
(ω^a)+b, ω^a >= b
b+(ω^a), ω^a < b
()= 0

Would be one way to do it, in a function notation.

You only need one of the pair cases to represent all ordinals, and using b+(ω^a) makes FS functions simpler.

How does one turn the fgh level into a function without using the fgh itself?

You can also use f_(x+1)(n)=f_x(n^n) or some other strictly increasing function of n. This loses some power, but it doesn't really matter once you reach e0.

[examples of num->ord function]

I think every ordinal, finite or infinite, but < ε_0, can be expressed this way.

Correct, since every ordinal <ε_0 is either 0 or equal to b+w^a for some b and a.

Every finite number is, I think, mapped to a different tree (since every finite number has a unique prime factorization.)

It's not related to prime factorizations (that's the 2^a*3^b*5^c... encoding), but yes, every tree has a unique representation as a nonnegative integer.

I think every finite number c is represented exactly once (or perhaps 0 times) as ord(k), that is, c = ord(k) for only one k if c is finite.

This is because n = (0, n-1) — thus no n = (0, n-c) for any c un= 1 since n-c+1 = (0, n-c) and n-c+1 = n iff c = 1
And no finite number n is (c, k) for any c > 0 and any k >= 0, otherwise n >= ω

Also only certain odd primes n make ord(n) finite (as well as 0 and 1 which are not primes)— namely, at least a subset such that, if n = 2c+1 c is prime (or 0 or 1) and satisfies the same property.
3 and 7 are some of these, I’m not sure there are any others. However, other non-prime numbers work, such as 15.

In general, are these just powers of 2, -1?

Yes, since pair(0,2^n-1)=2^(n+1)-1

Every finite number maps to a unique tree, if that helps. Ergo:
If there is only a single way to represent a value as a binary tree in fluffykitty’s way, then that value is in š if you can find an integer that maps to that tree. That is do not need to worry about extra integers mapping to that tree.
I’m not sure whether every tree is mapped to by some integer, but I feel that there is a proof for that. Something along the lines of:
There is a countably infinite amount of binary trees, and there is a countably infinite amount of integers, thus every tree is mapped to.
This is not a good proof, since you can define a function which maps all integers to the same tree, but for our purposes I think some proof like that would work.

You can prove it by induction on tree size.

[Moosey]

So, having defined ord(n) (perhaps someone else can provide a formula; EDIT: I did), what do I do to make a function which takes an ordinal and some other arguments and returns a very very very very large value?

EDIT:
oddpart(n)=

Code: Select all

oddpart(n/2), n/2 ∈ natural numbers
n, n/2 ∈ not-natural numbers

twoeypart(n)=

Code: Select all

n/oddpart(n)

ord(n)=

Code: Select all

(ord(log_2(twoeypart(n))),ord((oddpart(n)-1)/2)), n>0
0, n=0

Can anyone logically extend ord(n) so that:
It can tolerate countably infinite input values
It still always returns a finite or countably infinite value, with no bounds on the largest countably infinite value it returns (that is, there is an input that evaluates to, say, Γ_0 or the Bachmann–Howard ordinal. Not that you necessarily need to map numbers specifically to those values, but you get the idea.)

I’m fine with partial results for ord*(n) that satisfy only the first condition, or, say, satisfy the first but only go up to Γ_0, especially since it seems like some people say it’s incredibly difficult to devise a system which reaches Γ_0

I mean, that would make ord*(n) pretty crazy already—
f_(Γ_0) grows insanely quickly (but slower than TREE(n)).
For no good reason, I cannot stumble across a function in the googology wiki with a place in the FGH of Γ_0.

[fluffykitty]

Any ordinal can be written in the form 2^a*(2b+1) (remember, ordinal addition and multiplication are not always commutative, but other rules still hold) for ordinals a and b. For example, w=(w,0), w+2=(1,w), w2=(w+1,0), w^2=(w2,0), and w^w=(w^2,0). However, repeated unpacking of infinite inputs does not terminate, so you need to be more careful if you use this to convert ordinals to trees. If you map 0 to a 0 node, w to a 1 node, and ε_x to a (2+x) node, you can map ordinals to trees with ordinal labelled leaves.

[Moosey]

Any ordinal can be written in the form 2^a*(2b+1) (remember, ordinal addition and multiplication are not always commutative, but other rules still hold) for ordinals a and b. For example, w=(w,0), w+2=(1,w), w2=(w+1,0), w^2=(w2,0), and w^w=(w^2,0). However, repeated unpacking of infinite inputs does not terminate, so you need to be more careful if you use this to convert ordinals to trees. If you map 0 to a 0 node, w to a 1 node, and ε_x to a (2+x) node, you can map ordinals to trees with ordinal labelled leaves.

What’s the largest ordinal you can map an infinite number to using this method (ord(w)=1)? What would I map, say,

Code: Select all

w+1

Or

Code: Select all

w^2

Or

Code: Select all

w^w

To?
Is there a formula to map any ordinal n to a certain node?

[fluffykitty]

What’s the largest ordinal you can map an infinite number to using this method (ord(w)=1)?

Still any x<e0 since you can replace all occurrences of w in the tree with 1. Setting ord(w)=e0, ord(e0)=e1... gets you up to ew, but that can still be easily beaten by better encodings.

What would I map, say,

Code: Select all

w+1

Or

Code: Select all

w^2

Or

Code: Select all

w^w

To?

All of those reduce to smaller ordinals when applying the unpairing function, so they map to trees with multiple leaves.

Is there a formula to map any ordinal n to a certain node?

If you just want to map ordinals to nodes, you can map x to an x node, but that isn't very useful. It's better to only map ordinals which do not reduce when unpaired (0, w, ε_x)

[Moosey]

...
Setting ord(w)=e0, ord(e0)=e1... gets you up to ew, but that can still be easily beaten by better encodings.

Such as...?

What is the best encoding, and how large can it get?

EDIT:
Also, using the ord(w) = 1, ord(e_n) = n+2 system, is ord(ζ_0)= ζ_0+2?
After all, ζ_0 = e_(ζ_0)

What about larger ordinals, like, say, Γ_0?

[Moosey]

Is ord(n) new, if not a new concept?

[fluffykitty]

Also, using the ord(w) = 1, ord(e_n) = n+2 system, is ord(ζ_0)= ζ_0+2?
After all, ζ_0 = e_(ζ_0)

What about larger ordinals, like, say, Γ_0?

I said 2+x, not x+2. There is a difference when using transfinite ordinals, since for example 2+w=w≠w+2. Fixed points of the epsilon function map to the node with that label, and Γ_0 is a fixed point of the epsilon function (and many more), so ord(Γ_0)=(Γ_0). Encodings can be constructed that go up to the first uncountable ordinal, but if you want your encodings to be computable you can't go past the Church-Kleene ordinal.

Is ord(n) new, if not a new concept?

Probably not.

[Moosey]

How can ord(n) be used to construct fast-growing functions? Can I define an f(n) or something with more arguments which grows really really fast? (Faster than, say, ggç)


Also, you’re saying that ord(n) is probably not a new concept, but you can’t tell whether it has been described or defined before?

[fluffykitty]

How can ord(n) be used to construct fast-growing functions? Can I define an f(n) or something with more arguments which grows really really fast? (Faster than, say, ggç)

Ordinal argument ord(n) only converts ordinals to trees. You need some other function to convert the trees to bigger ordinals first.

Also, you’re saying that ord(n) is probably not a new concept, but you can’t tell whether it has been described or defined before?

It seems too simple to be completely new.

[Moosey]

How can ord(n) be used to construct fast-growing functions? Can I define an f(n) or something with more arguments which grows really really fast? (Faster than, say, ggç)

Ordinal argument ord(n) only converts ordinals to trees. You need some other function to convert the trees to bigger ordinals first.

What exactly do you mean by that?
ord(2) = w, for instance, and ord(2^^n)= w^^n; I used your function to convert the trees to ordinals.

[fluffykitty]

Repeated unpairing of w gives you a single 1 node. What ordinal does that correspond to?

[Moosey]

Repeated unpairing of w gives you a single 1 node. What ordinal does that correspond to?

1, right? Or do I not know the function you are referring to when you ask that question?

[testitemqlstudop]

Okay I read several wikipedia pages about ordinals and my head is spinning

[Moosey]

Okay I read several wikipedia pages about ordinals and my head is spinning

Why?

[fluffykitty]

Repeated unpairing of w gives you a single 1 node. What ordinal does that correspond to?

1, right? Or do I not know the function you are referring to when you ask that question?

A tree with a single 1 node is probably not equal to 1.

[Moosey]

Repeated unpairing of w gives you a single 1 node. What ordinal does that correspond to?

1, right? Or do I not know the function you are referring to when you ask that question?

A tree with a single 1 node is probably not equal to 1.

Alright, so what function are you using to evaluate the trees?

[fluffykitty]

One possible function is (with (0)=single 0 node, ((0),(1))=node with a 0 child and a 1 child, etc) f((0))=w, f((x+1))=f(x)^^w, f((x))[n]=f((x[n])) if x is a limit ordinal, and f((x,y))=f(y)+w^(f(x)). Here, f(treeify(w))=f((1))=w^^w=e0, f(treeify(e0))=f((2))=e0^^w=e1, etc. and the first fixed point is f(treeify(e_w))=f((w))=e_w (and all later epsilon ordinals).

[Moosey]

One possible function is (with (0)=single 0 node, ((0),(1))=node with a 0 child and a 1 child, etc) f((0))=w, f((x+1))=f(x)^^w, f((x))[n]=f((x[n])) if x is a limit ordinal, and f((x,y))=f(y)+w^(f(x)). Here, f(treeify(w))=f((1))=w^^w=e0, f(treeify(e0))=f((2))=e0^^w=e1, etc. and the first fixed point is f(treeify(e_w))=f((w))=e_w (and all later epsilon ordinals).

then 1 of course becomes e_0

I still don't get limit ordinals;
what does f((x))[n]=f((x[n])) mean exactly?

[fluffykitty]

Brackets indicate fundamental sequences, so f((x))[n]=nth element of the fundamental sequence of f((x)) and f((x[n]))=f of the node containing the nth element of the fundamental sequence of x

[Moosey]

I need a tutorial—how do I define a function that grows faster than ggggggggggggggg....ç_x,x,x...(x,x,x)?
i.e >= w^w

I’m still hung up on your explanations and am not sure how these ordinal functions can help make a really fast growing function, so I’d like a tutorial on how to construct one.

[Moosey]

Came across this by defining a different Ord-type function:
if I define Ξ (Greek letter Xi) as the smallest (?) ordinal such that n= w^((w^n)2)
In the intuitive sense:
Ξ loosely equals w^((w^(w^(w^w...2))2), or a branching version of e_0, like this:

Code: Select all

...
w+w w+w
w    w
w+w
w
w

1.
Is Ξ or w^Ξ smaller? Obviously e_0 & other epsilon numbers (and the related zeta numbers and beyond) are defined on the premise that n = w^n but Ξ is not = w^Ξ, and thus is not an epsilon number.
2.
What are the best lower/upper bounds to Ξ? So far I have that Ξ>>(e_0)^w
Verify:
(a^b)^c= a^(bc)
(e_0)^w= w^((e_0)w) which eventually simplifies to far fewer 2s than Ξ— it’s not infinitely branching.

I think that Ξ is probably not > (e_0)^(e_0), and I’m even more sure that it’s < e_1

I found Ξ by finding that for that ord(n) relative function, orditree#1(n), as n approaches w, orditree#1(n) approaches (some value less than or = to) Ξ + w^Ξ




Also yesterday I realized there’s a proof that you can’t map the natural numbers to all of themselves & infinitely many transfinite ordinals AND still make it so that if a>b, f(a)>f(b)

Which is consistent with the two functions I’ve made so far, Ord and orditree#1. (See the latter bit of this post for orditree#1)

[Moosey]

Can someone explain inaccessible cardinals? Apparently they are κs such that κ= an uncountable κ such that it is the ב_κ th regular cardinal—
What’s a regular cardinal?
I know that ב_n+1 = 2^(ב_n) so I sorta understand that.

The other thing I understand is that κ is 1-inaccessible if it is the κth inaccessible cardinal, and I guess it’s probably n+1 inaccessible if it’s the κth n-inaccessible cardinal.
The other other thing I get is that κ is hyper-inaccessible if it’s κ-inaccessible.
The other other other thing I think I get is that κ is 1-hyper-inaccessible if it’s the κth hyper-inaccessible number, and
it’s n+1-hyper-inaccessible if it’s the κth n-hyper-inaccessible number.
I love the jargon at the end of this page:
http://cantorsattic.info/Inaccessible#D ... essibility

κ is hyper^a-inaccessible if it is hyper-inaccessible and for every b<a it is κ-hyper^b-inaccessible where κ is a-hyper^b-inaccessible if it is hyper^b-inaccessible...

I suppose the logical continuation is that κ is actually-hyper-hyper-inaccessible if it’s hyper^κ inaccessible, whether that’s even possible or not.


EDITLATERTHANTHERESTOFPOST:
Oh, I get it— inaccessible numbers are to aleph_n what epsilon numbers are to w^n:
All inaccessible numbers κ = aleph_κ.
</late edit>
Also, can somebody describe (cue laughtrack) indescribable cardinals? (I don’t expect you to speak of the ineffables, of course.)

Also reflection and regular cardinals and pretty much everything else building up to indescribables, in a comprehensible way?

Speaking of comprehensibility, someone should define incomprehensible cardinals. I’ll take a crack at it maybe...

Attempt I:
An incomprehensible cardinal is a cardinal κ such that κ is the κth compressed-κ-inaccessible cardinal
A compressed-n-inaccessible cardinal is defined as follows:
A compressed-0-inaccessible cardinal is a hyper^κ-inaccessible cardinal.
A compressed-n+1-inaccessible cardinal κ is the κth compressed-n-inaccessible cardinal

Inc_0 (the 1st incomprehensible cardinal) is the Inc_0th compressed-Inc_0-inaccessible cardinal.

[Moosey]

It seems that ρ_0,2 is really weird
it is the 1st solution to n= (w^n)2
And (ρ_0,2)^(ρ_0,2)= (w^((ρ_0,2)^2+ρ_0,2))2, I think. If I did the calculation right.