Thread for Non-CA Academic Questions

[fluffykitty]

That changes nothing since |e| is already illegal so |e b||c d| is also illegal. I'm not sure if there's any good way to fix MATRIXPARTY without making it boring, but reducing the number of dimensions to 1 probably makes the function finite. With that restriction, VECTORPARTY(1)=1, VECTORPARTY(2)=3, and VECTORPARTY(3) is at least 15 (2, 10, 001, 0111, 011, 01, 0, 11111111...1). Also, you really should join the Googology Discord server at https://discord.gg/V6R4hRJ
Edit: VECTORPARTY is equivalent to TREE but restricted so every node has at most one child, so its maximum possible FGH level is the SVO (however, it is most likely sub-e0)

[testitemqlstudop]

All versions of MATRIXPARTY(3) and CUBEPARTY(3) are infinite. The sequence is

Code: Select all

|2|
|1 1|
|1 1|

followed by extensions of

Code: Select all

|1 1 0 0 0|
|1 0 1 0 0|
|0 1 0 1 0|
|0 0 1 0 1|
|0 0 0 1 1|

(Element (x,y) is 1 iff x=y=0, x=y=max, or abs(x-y)=1)

No, cubeparty is finite.
I said you can take the cube, CUT it, TRANSLATE it, and ROTATE it, and if after some cutting/rotating/translating one piece (one cut piece) matches a previous cube it's disallowed.

[Moosey]

All versions of MATRIXPARTY(3) and CUBEPARTY(3) are infinite. The sequence is

Code: Select all

|2|
|1 1|
|1 1|

followed by extensions of

Code: Select all

|1 1 0 0 0|
|1 0 1 0 0|
|0 1 0 1 0|
|0 0 1 0 1|
|0 0 0 1 1|

(Element (x,y) is 1 iff x=y=0, x=y=max, or abs(x-y)=1)

No, cubeparty is finite.
I said you can take the cube, CUT it, TRANSLATE it, and ROTATE it, and if after some cutting/rotating/translating one piece (one cut piece) matches a previous cube it's disallowed.

I’m afraid that doesn’t change anything. It still is infinite, unless you can cut out of the middle, which you don’t allow.

[testitemqlstudop]

Yes you can cut out the middle through this process: cut front side, cut behind side, cut top, cut bottom, cut left, cut right, and then you have the middle.

[Moosey]

Yes you can cut out the middle through this process: cut front side, cut behind side, cut top, cut bottom, cut left, cut right, and then you have the middle.

I mean remove the middle to have the outside, somehow turning

Code: Select all

| a b c |
| d e f |
| g h i |

To

Code: Select all

| a c |
| g i |

[fluffykitty]

That doesn't help either:

Code: Select all

x = 20, y = 5, rule = //3
2B3A2.2BA.A4.2B2A$BAB2A2.BAB.A4.BABA$ABABA2.ABA.A4.AB2A$2ABAB11.3AB$
3A2B2.3A.B!

If you use symmetric matrices with entries of 0 and 1 only, it reduces to the subcubic graph function without the subcubic restriction and with a much more relaxed definition of embedding. With this interpretation, the sequence of matrices after the first becomes a path of length n-2 with loops at the ends.

[praosylen]

Consider an extension of TREE(N), which we will call TREE*(M,N), in which instead of requiring each tree in the sequence to have at most i nodes, where i is the tree's 1-index in the sequence, we require each tree in the sequence to have at most i+m nodes. (This is in effect a combination of both tree(N), equivalent to TREE*(N,1) and TREE(N), equivalent to TREE*(0,N).) It's fairly trivial to show that TREE*(1,N) = TREE*(0,N+1)-1 = TREE(N+1)-1, and only slightly less trivial to furthermore show that TREE*(M,N) < TREE*(0,M+N) = TREE(M+N) for all nonzero M and all N. It's also simple to derive a stronger bound ensuring that TREE*(0,M+N) ≥ TREE(M) + TREE*(TREE(M),N) for all nonzero M and all N. What other bounds can be derived?

[Moosey]

Can somebody explain BEAF to me?
I get that {x 1 anything} = x
And {x y} = {x y [any amount of 1s] } = x^y
But that does the other rule mean?

I’m also guessing that {anything 1} = {[that same anything]}, like on BAN (which I need an explanation on too)

EDIT:
After reading the introduction to BEAF article on the Googology Wiki, I have a less shaky idea of it (though it would be more intuitive once I read it without skimming or going off to find that ζ_0 is (it’s the first c such that c = ε_c))
Why do I use nested parentheses?!?

Also, if you want to have a more intuitive grasp on some of those ordinal things (Γ_0 in a nutshell! It’s the first c such that c=Φ_c(0), or, according to the googology wiki, {ω,ω,1,2} in ordinal BEAF), I highly recommend reading this series of blog posts that I found on the web by John Carlos Baez

[praosylen]

Similarly to the difference between tree(N) and TREE(N), can we define a function LSSCG(N) (standing for labeled SSCG) which is SSCG(0) calculated with N available labels for nodes? If this function is finite, I can derive that LSSCG(1) = SSCG(0) = 2, LSSCG(2) = SSCG(1)+1 = 6, and LSSCG(3) ≥ SSCG(SSCG(3)+2)+SSCG(3)+2. I don't know enough about the topic to know whether the results that conclude that TREE(N) and SSCG(N) are finite still hold for labeled graphs, so I don't know for sure whether LSSCG is finite (although I am fairly sure LSSCG(3) is).

[fluffykitty]

I don't think anyone has thought of that before and I'm not sure if it's finite. If it is, it's probably much stronger than SSCG(n). One method to demonstrate FGH lower bounds for this type of function is to create a transfinite list of graphs/trees/vectors/whatever such that no element is contained in an earlier element. If you can construct a list of length x, then the function is stronger than f_y for any y<x (this does not imply that it is stronger than f_x itself however). This method has been applied to SSCG and SCG to prove growth rate lower bounds on the Googology Wiki, and the SSCG results can also be applied to LSSCG fairly easily.

[Moosey]

Is ggç (See bottom of this post) ω^ω in the FGH?

[fluffykitty]

It's probably at most w^3.

[praosylen]

It occurred to me that LSSCG(3) (if it is finite) is actually much larger than the lower bound I calculated previously — I had been operating under the assumption that the longest sequences would be of the form

Code: Select all

3

Code: Select all

1--2

followed by the optimal SSCG(3) sequence using label 2 and then the optimal SSCG(SSCG(3)+2) sequence using label 1. However, there are two things I missed:

1. That the second term in the sequence is not a minor of graphs containing isolated islands each consisting of a single label, but for which different islands can have different labels (as in the following example):

   Code: Select all

   2--2--2--2--2
   
   1--1--1
   
   2  2  2
   
   1  1

   Hence the sequence that would have generated SSCG(3) now generates a far larger number, although probably not approaching the order of SSCG(4) or even TREE(3).
   
   And,
2. That taking the second term to be

   Code: Select all

   2-2

   can actually lead to very long sequences consisting of vanilla-SSCG-type graphs with a single substituted 2-labeled node, similarly to the following:

   Code: Select all

   3

   Code: Select all

   2--2

   Code: Select all

   2  2  2

   Code: Select all

   2  2

   , followed by the optimal SSCG(5) sequence with one arbitrary node in each graph labeled as 2 instead of 1 (for instance). This gives a phenomenally weak lower bound for LSSCG(3) as SSCG(SSCG(5)+4)+SSCG(5)+4. (Obviously the singly-substituted version of SSCG(5) will almost certainly be much larger than the standard SSCG(5).)
   
   Eliminating the

   Code: Select all

   2  2

   term and continuing with a doubly-substituted sequence yields a much stronger lower bound (possibly an actual approximate value) for LSSCG(3) on the order of SSCG(SSCG_s(SSCG_s(4, 2),1)), with SSCG_s(M, N) referring to the exactly-N-times-substituted version of SSCG(M) with at most one substitution per island, but even determining any kind of bound on SSCG_s(4, 2) or whether or not it is greater than SSCG(4) is too much for my ability to visualize.

All the above of course assumes LSSCG(3) is finite, which it may or may not be. If it is, though, I am fairly confident that it is much larger than any value that can reasonably be obtained using the vanilla SSCG function. If it turns out that LSSCG in general is finite, then LSSCG(3) itself will obviously pale in comparison to LSSCG(4), LSSCG(5) and so on in much the same way that SSCG(3) pales in comparison to SSCG(4). Of course, I have no real idea whether LSSCG is finite — my best guess would be that LSSCG(3) at least is (since the number of inhomogeneous nodes is bounded at two unless I missed a possible starting sequence, and it seems like that wouldn't be enough to allow infinite sequences), but since my guess is based on nothing but intuition with very little experience to back it up, I could easily be wrong. Even LSSCG(4) has such a rich variety of possibilities that I find it difficult to even begin to contemplate whether or not it is finite.

[fluffykitty]

SSCG(3) with 2 node colors and 1--2 forbidden is at least SSCG(SSCG(3)) since you can construct SSCG(3) graphs using only color 1 and SSCG(SSCG(3)) graphs using only color 2, which is far larger than SSCG(4). (Also, SSCG(3)>TREE(3) as demonstrated by APG in a cp4space post) My best sequence for LSSCG(3) is 3, 1--2, (triangle of 2s), (T tetromino of 2s), 2--2--2--2--2, (SSCG(2) graphs containing only 1s except for a 2--2--2--2 in each graph), (SSCG(3) graphs containing only 1s except for as many 2--2--2s as possible in each graph)... with the multisets of 2 graphs being computed using a similar procedure to the one APG used in https://cp4space.wordpress.com/2013/01/13/graph-minors/ to compute SSCG(2), except with a few nodes reserved for an SSCG run using a few initial nodes (x+2 on the xth iteration, although other options may work better). This obviously gets at least 3*2^(2*2^95-1)-9 iterations of SSCG (which is what would happen if you used SSCG(2)'s sequence for the 2 graphs), but goes much farther since in each step the maximum nodes gains SSCG(n) instead of just 1. However, this probably doesn't even beat f_((whatever SSCG's ordinal is)+w) for small arguments. (The maximum possible FGH level for this technique would be f_(SSCG^n) for LSSCG(n+1)) To go farther, we could use a mapping from ordinals to LSSCG(3) graphs such that if x<y then f(y) does not contain f(x) for ordinals x,y.

[Moosey]

It's probably at most w^3.

Oh. How do I get to ω^ω level?

[fluffykitty]

You either need infinitely many arguments (which will lead you down the array notation path) or more complex methods.

[Moosey]

You either need infinitely many arguments (which will lead you down the array notation path) or more complex methods.

I choose the latter.

What would I do?

[fluffykitty]

Well, you can do something like my f function, where you encode FGH levels as numbers, or do stuff like VECTORPARTY or TREE. I don't think there's any other way to get high FGH levels without doing one of those or using array notation methods like in BEAF.

[Moosey]

Well, you can do something like my f function, where you encode FGH levels as numbers, or do stuff like VECTORPARTY or TREE. I don't think there's any other way to get high FGH levels without doing one of those or using array notation methods like in BEAF.

How would I encode a level as a number?

[fluffykitty]

One thing that may be useful is that p(a,b)=2^a*(2b+1) is different for all (nonnegative integer) values of a and b, so you can encode two numbers into one. Also, it never outputs 0, so you can do something different in that case. Using that, you can encode arbitrary binary trees into nonnegative integers.

[Moosey]

One thing that may be useful is that p(a,b)=2^a*(2b+1) is different for all (nonnegative integer) values of a and b, so you can encode two numbers into one. Also, it never outputs 0, so you can do something different in that case. Using that, you can encode arbitrary binary trees into nonnegative integers.

Okay, sow how would I turn that into a vgç_n(x,y,z) (very generalized ç)?
Obviously I’d want something along the lines of a function which is f_n (x,y,z) = f_inverse p of its inputs (x,y,z) to expand back the inputs, but here I’m a little clueless.

[fluffykitty]

One possible method of encoding ordinals as binary trees is to use a leaf node to represent 0 and a branch node to represent b+w^a, where a and b are its children. For example, 1=0+w^0 would be (()()) using a linear representation of trees. 2=1+w^0=(()(()())), w=0+w^1=((()())()), w+1=w+w^0=(((()())())()), etc. Using this representation, you can get a function that grows faster than any FGH level below e0 (=w^w^w^...). For levels of the form 0 or a+1, you can do what you normally do, and for other levels you can use fundamental sequences. The rules for fundamental sequences are (b+w^(a+1))[n+1]=((b+w^a)+w^(a+1))[n], (b+w^a)[n]=b+w^(a[n]) if the previous rule doesn't apply, and (b+w^a)[0]=b if the previous rules don't apply. The useful property of fundamental sequences is that for any ordinal a, an ordinal b is less than a if and only if it is less than a[n] for some n. If you set n=x, then the resulting function will eventually outgrow any instance with lower ordinal input for large enough x, since a[x] will eventually be greater than any ordinal less than a. A method like this one is used in my f, but with a much stronger ordinal notation based on ordinal collapsing functions.

[Moosey]

One possible method of encoding ordinals as binary trees is to use a leaf node to represent 0 and a branch node to represent b+w^a, where a and b are its children. For example, 1=0+w^0 would be (()()) using a linear representation of trees. 2=1+w^0=(()(()())), w=0+w^1=((()())()), w+1=w+w^0=(((()())())()), etc. Using this representation, you can get a function that grows faster than any FGH level below e0 (=w^w^w^...). For levels of the form 0 or a+1, you can do what you normally do, and for other levels you can use fundamental sequences. The rules for fundamental sequences are (b+w^(a+1))[n+1]=((b+w^a)+w^(a+1))[n], (b+w^a)[n]=b+w^(a[n]) if the previous rule doesn't apply, and (b+w^a)[0]=b if the previous rules don't apply. The useful property of fundamental sequences is that for any ordinal a, an ordinal b is less than a if and only if it is less than a[n] for some n. If you set n=x, then the resulting function will eventually outgrow any instance with lower ordinal input for large enough x, since a[x] will eventually be greater than any ordinal less than a. A method like this one is used in my f, but with a much stronger ordinal notation based on ordinal collapsing functions.

So how would I use that to make a vgç function? Or would it be better just to define a new, simpler function?


Just to verify that I understand this, w^w^w=
((((()())())())())

If I typed it correctly.



I think I still need help in how to do all this.

[fluffykitty]

trees

So how would I use that to make a vgç function? Or would it be better just to define a new, simpler function?

A good start would be to make a function for computing fundamental sequences in this tree representation. Also, if possible, simplifying functions is usually a good idea.
[quote="Moosey]
Just to verify that I understand this, w^w^w=
((((()())())())())

If I typed it correctly.
[/quote]
Yes.

[Moosey]

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

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

A good start would be to make a function for computing fundamental sequences in this tree representation. Also, if possible, simplifying functions is usually a good idea.

I’m not sure I understand.


If we do make a thing like this, how would one use the p(a,b) = (2^a)(2b+1) to encode an fgh level?

I get that presumably we’d need the inverse operation, which would make binary trees. Presumably, we would do this to all leaves with a value > 0, then iterate (a,b) to get the ordinal encoded by the integer.

That, I suppose, would let you encode an fgh level, but then what?

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


Regardless, I guess we have a function which returns an ordinal given a finite number, sort of like a reverse ordinal collapsing function (but ordinal collapsing functions take uncountable values and make them countable rather than taking countable values and making them finite.)
Call it ord(n). It seems a little difficult to represent using function notation.

ord(0) =

Code: Select all

()

= 0

ord(1)=

Code: Select all

(()())

=1

ord(2)=

Code: Select all

(ord(1), ord(0))

= ω

ord(3) =

Code: Select all

(ord(0), ord(1))

= 2

ord(4)=

Code: Select all

(ord(2), ord(0))

= ω^ω

ord(5) =

Code: Select all

(ord(0),ord(2))

= ω+1

ord(6)=

Code: Select all

(ord(1), ord(1))

= ω+1 again, I think

ord(7)=

Code: Select all

(ord(0),ord(3))

= 3

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


ord(8)=

Code: Select all

(ord(3),ord(0))

= ω^2

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

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?


It seems that for k= (2^n)-1, ord(k) = n

EDIT:
ord(9) =

Code: Select all

(ord(0),ord(4))

= ω^ω +1

ord(10)=

Code: Select all

(ord(1),ord(2))

=ω2


I think there’s a set, call it Š, of finite numbers and countable ordinals such that any value k in the set has exactly one corresponding finite n such that ord(n)=k. This is true for all finite numbers. How many countably infinite values are there in it though? 0? Infinitely many?

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.

Anyways, now:
ord(11)=

Code: Select all

(ord(0),ord(5))

= ω+2
ord(12) =

Code: Select all

(ord(2)ord(1))

= ω^ω + 1
ord(13)=

Code: Select all

(ord(0),ord(6))

= ω+2
I feel the omega+3s will have three or four things in between.
ord(14)=

Code: Select all

(ord(1),ord(3))

= ω+2
Or not; maybe there’ll be 4 of them though

ord(15)=

Code: Select all

we all know what’s going on for a Mersenne not-necessarily-a-prime

=4

ord(16)=

Code: Select all

(ord(4),ord(0))

ω^(ω^ω)
In general, ord(2^^n) = ω^^n

ord(17)=

Code: Select all

(ord(0),ord(8))

=(w^2)+1
This is getting to be a whole lotta fun


ord(18)=

Code: Select all

(ord(1),ord(4))

=(w^w) + w

ord(19) =

Code: Select all

(ord(0),ord(9))

=w^w +2

Just one more
ord(20) =

Code: Select all

(ord(2),ord(2))

= (w^w) + w


I think Š= Positive integers U limit ordinals, if I understand limit ordinals correctly.

Edit:
I think (w^w)+w, for instance, might be a limit ordinal, in which case Š ⊂ (Positive integers U limit ordinals)

Ord(currently largest known prime)=
82589933