Thread for Non-CA Academic Questions

[Macbi]

What is the constant k (if it exists) such that O(log(x!)) is between O(x^k) and O(x^(k-ε)) for some arbitrarily small ε? Does it depend on the base of the logarithm?

Is there a (different) constant k such that there are arbitrarily large integer powers differing by at most k?

Stirling's approximation says that log(x!) = x log(x) - x + 1/2 log(2πx) + O(1/x) (all logarithms base e). So we have k=1 independent of base.

[Moosey]

All n equal to (n-1)!+1 are prime; however this can be trivially modified to show that this can only prove that 2 and 3 are prime since n-1 must equal itself factorial.
Are there any ways to improve this prime test to show that larger values are prime?

[testitemqlstudop]

Well, you have Wilson's theorem...

[toroidalet]

Given a tag system that halts on a halting symbol, is it possible to construct another tag system that only stops when the length of the string is less than the deletion number and iff the first one halts, that simulates it in linear time?
Is it possible to perform the reverse simulation (given an n-tag system T which halts on any string of length less than n, construct a tag system T' which reads a certain symbol iff T halts) in linear time?

(The construction can be a cyclic tag system, since they can be simulated in linear time by regular tag systems.)

EDIT: Is a (noncellular) automaton which enumerates strings and checks if they are valid computations of a Turing machine universal?
An example of this is a system consisting of a pair of nondeterministic pushdown automata that stops only when both of them simultaneously enter a certain state; given infinite input of the form xaxbxaaxabxbaxbbxaaaxaabxabaxabbxbaax, where x is an arbitrary string, such (non-cellular) automata can be created that solve an arbitrary Post correspondence problem (with the additional requirement that such a solution starts with a prefix of x and ends with a suffix of it).

[Moosey]

This is an insane heretical idea, but... suppose we define trans-transfinite values starting with the supremum of all transfinite values (the box of all boxes, but revised to only contain all boxes that are only infinite), which is the famous "absolute infinity" (Ω). Obviously it's not that it's more of a trans-transfinite value (as I said), and it could be defined as the supremum of all finite values and all infinite values, i.e. the cardinality of all finites and transfinites.
I think we better come up with a short name for it so I'll call it τ_0; tau stands for trans-[transfinite] (and yes, I know the Veblen hierarchy uses all Greek letters but let's pretend that doesn't matter)
Obviously if it's an ordinal (and I don't mean a transfinite ordinal I just mean something expressable using a set of any size, including ones of >infinite size.) the next obvious stuff would be τ_0+1, τ_0+2, etc. and then τ_0+w and τ_0 + (literally anything else accepted by anyone who studies transfinite values). Then after a >> Uncountable amount of time you'd get to τ_0*2 (heck, let's just call τ_0 "τ" even though that has mathematical conflicts too. But that's true of any single Greek letter so who cares.) or τ2. Then we pass all this rubbish that we've already covered in the transfinite ordinal stuff and get to much bigger stuff. Like, say, a fixed point analogous to e_0: a=τ^a. Etc.
Anyways, has someone already come up with this, or is there something that's obvious to everyone else as to why this doesn't exist, or...
I thought of this because, as sbiis saibian points out, absolute infinity is so... conflicting. Not only in that the box of all boxes thing is impossible or whatever but also just because Cantor just made up a bunch of infinities but then basically did what everyone else did with finite numbers, but he did it with infinities--he makes up an "end" to exactly what he was trying to demonstrate was not an "end".


While we're at our coming up with this stuff, what if we make trans-3-finite values which are trans-trans-transfinite values (I.e. to what we just made up it is what that is to transfinite values).
Then we can go trans-n-finite values which are extensions of this sequence and then we might as well get to meta-transfinite values which are trans-w-finite; μτ (as I will call the first metatransfinite value) is the supremum of {0,w,τ,2-τ (the first trans-trans-transfinite),3-τ,...}. More extensions are less obvious but certainly exist.

Anyways, better stop here before:

@Moosey has been banned for life because he is a heretic.

Remember, heretics think outside of the box (as we learned from Galileo).

[testitemqlstudop]

Let me just stop to say that I see no real-use application of any form of infinite ordinal.

[Moosey]

Let me just stop to say that I see no real-use application of any form of infinite ordinal.

There's a proof that the Goodstein sequence is finite. It involves e_0.
You cannot prove the goodstein sequence or the hydras are finite without transfinite ordinals.

[testitemqlstudop]

Whoops, I meant real-world application.

[Moosey]

Whoops, I meant real-world application.

Well, if you happen to be fighting an unusual hydra and you're really desperate to kill it but you don't have time to refer to the official hydra-killing rulebook™ then you can always just chop heads off randomly and you'll always kill it even if your random chops take the worst path, strategically speaking.
That's not a real world application but perhaps there are some ones you can think of that are related.
Considering that we're in a forum discussing a part of mathematics that even the most experienced users occasionally doubt has a use in reality, "no real application" is a terrible reason to not be interested in something.


Also, my "new" ordinals are more than just transfinite; they are more-than-infinitely large (by definition, since τ_0 is the supremum of the infinities (a modification on the well ordering theorem may show that even this "set" is well order-able and thus fairly easy to take the supremum, but that would require larger-than infinite sets. If you had ZFC + well ordering theorem + "sets can be larger than infinite" as your chosen axioms then τ_0 should be trivial to define as the supremum of a well ordered set--just pretend there's a "last" member and call whatever is larger τ_0--this is more or less how you make w but obviously w doesn't have the weird axiom stuff. Well ordering would just make a nice, easy way to see a pattern and thus... you know.) and so they probably don't have many uses (though I'm sure there's a clever way to use them in some weird OCF thing and then in the FGH).

[fluffykitty]

If you're using them in an OCF you can probably find a smaller cardinal that does the same thing. Also, those aren't really a new concept. https://googologyforeveryone.fandom.com ... le_Ordinal

[Moosey]

[typical fluffykitty funfact] Also, those aren't really a new concept. https://googologyforeveryone.fandom.com ... le_Ordinal

Well, hey-- at least I have a better way to prove they exist than an axiom which asserts they do.
ZFC + well ordering theorem + "sets are allowed to be larger than infinite" -> trans-transfinites/Hyperuncountables exist. I have posted a comment on that page.

[fluffykitty]

The well ordering theorem is equivalent to the axiom of choice under ZF and thus provable in ZFC, so you can omit it. Also, I have posted comments on that page, including a reply to your comment.

[Moosey]

The well ordering theorem is equivalent to the axiom of choice under ZF and thus provable in ZFC, so you can omit it. Also, I have posted comments on that page, including a reply to your comment.

Alright, well, in that case, which paradoxes would I need to circumvent that could potentially be caused by the axiom "sets can be larger than infinite"?

[fluffykitty]

Well, first you need to define what "larger than infinite" means more concretely. For example, which kind of "infinite" are you referring to? If it's countably infinite, then this axiom is equivalent to asserting the existence of an uncountable set, which is easily proven in ZFC.

[Moosey]

Well, first you need to define what "larger than infinite" means more concretely. For example, which kind of "infinite" are you referring to? If it's countably infinite, then this axiom is equivalent to asserting the existence of an uncountable set, which is easily proven in ZFC.

larger than uncountable--literally larger than all uncountable infinities, i.e. the supremum of them

[Macbi]

There's a thing called a "large cardinal" which means that it's so large that it can't be reached from anything below it using the operations that are well defined in ZFC. In particular a cardinal C is one such that if A is smaller than C then the power set of A is also larger than C, and such that if we have a family of sets B_d indexed by a set D which is also smaller than C, then the union of the B_d over d in D is smaller than C. These properties mean that any large cardinal is larger than all of the sets we usually use in mathematics (since we form these sets by taking powerset and unions and then passing to subsets). It also means that it's undecidable in ZFC whether or not any large cardinals actually exist.

In fact, if we let C be a large cardinal we can define V_C to be the set of sets which are smaller than C and all of whose elements are smaller than C, and so on recursively. Then it turns out that V_C is a model of ZFC, meaning that we can do all of ordinary mathematics inside V_C. Then we can think of elements of V_C as being our ordinary sets, and C as being some cardinal that is larger than all of them.

[calcyman]

There's a thing called a "large cardinal" which means that it's so large that it can't be reached from anything below it using the operations that are well defined in ZFC. In particular a cardinal C is one such that if A is smaller than C then the power set of A is also larger than C, and such that if we have a family of sets B_d indexed by a set D which is also smaller than C, then the union of the B_d over d in D is smaller than C. These properties mean that any large cardinal is larger than all of the sets we usually use in mathematics (since we form these sets by taking powerset and unions and then passing to subsets). It also means that it's undecidable in ZFC whether or not any large cardinals actually exist.

In fact, if we let C be a large cardinal we can define V_C to be the set of sets which are smaller than C and all of whose elements are smaller than C, and so on recursively. Then it turns out that V_C is a model of ZFC, meaning that we can do all of ordinary mathematics inside V_C. Then we can think of elements of V_C as being our ordinary sets, and C as being some cardinal that is larger than all of them.

This is all true, but I'd make a minor terminology change: s/large cardinal/strongly inaccessible cardinal/

'Large cardinal' is a more general (and less precise) term: https://en.wikipedia.org/wiki/List_of_l ... properties

[Macbi]

This is all true, but I'd make a minor terminology change: s/large cardinal/strongly inaccessible cardinal/

'Large cardinal' is a more general (and less precise) term: https://en.wikipedia.org/wiki/List_of_l ... properties

Good point.

[Moosey]

What would
Quine is a liar! He lies, "Quine is a liar! He lies,"
Imply? It seems to be a form the liar paradox since it ultimately reduces to claiming that quine is liar who states he is-- essentialy, Quine lies, but Quine tells the truth.

[testitemqlstudop]

If "Quine is a liar" then that would imply that the next statement is false. So the effective way to deal with this is to define even infinity and odd infinity (more formally W_1m2 === 1 (mod 2) and W_0m2 === 0 (mod 2)).

Let the statement "Quine is a liar and he lies ' Quine is a liar and he lies ' ...'' be X_1. So, X_1 => !X_2, and X_2 => !X_3, even though X_1 = X_2 = X_3.

But clearly they are distinct, as you can't remove some letters from a statement and have it be the same statement.
Hence, X_1 => X_3 => X_5 ... and X_2 => X_4 => X_6...
So here we make the conclusion X_1 != X_2 and X_1 has implication chain length of W_0m2 and X_2 has implication chain length of W_1m2.

Of course this may also be an effective way of fixing the "This statement is false" paradox:

define S = "S is false"
=> define X_i = "X_i+1 is false"
=> X_i != X_i+1
=> X_i = X_i+2
=> S = "S is true"
=> which is essentially the identity statement S = S, so hence, S cannot have a defined value.

[toroidalet]

Is there some radius r>0 where, given an infinite grid of circles of radius r centered on integer points, infinitely many slopes of lines exist that are either tangent to or pass through the center of every circle they touch?

Can someone provide the 12-relation group with an undecidable word problem? (the only explicit construction of it I could find is the original paper in Russian, which I don't understand)

[BlinkerSpawn]

Is there some radius r>0 where, given an infinite grid of circles of radius r centered on integer points, infinitely many slopes of lines exist that are either tangent to or pass through the center of every circle they touch?

No. [EDIT: Except possibly for lines that don't pass through any centers, but not likely.]
We require a Theorem:

The nearest integer point (x,y) to a line segment from (0,0) to (a,b) lies at distance (a^2 + b^2)^(-1/2) from the segment.

For any positive r, there are only a finite number of pairs (a,b) such that (a^2 + b^2)^(-1/2) >= r, and thus a finite number of possible slopes, Q.E.D.

[Moosey]

e = Σ(infinity)(x=0)(1/x!)
What's Σ(infinity)(x=1)(1/2^^x)? It looks to be about 0.8125...

EDIT: fun fact: Π(n)(x=1)(1+1/x) = n+1
What's Π(infinity)(x=1)(1+1/(2^x))?
And Π(infinity)(x=1)(1+1/(x!))? that seems to be ~3.68215...

Those are my questions.
Additionally, what is Σ(infinity)(x=0)(sin((x/x+1)π))?

[Moosey]

How is S(K(SII))(SII)α different from Sααα
Or is it not?

[Moosey]

A question involving fractals and minecraft.
whilst making a hilbert curve for a rollercoaster in minecraft, a question popped into my mind.
Rules of the question:
1. a hilbert curve's straight parts (not corners) must be happy. However, ends of the curve need not be happy.
2. An uninterrupted straight line must be connected to at least one vendor in order to be happy. A single vendor is enough in all cases.
3. A vendor can only make one line happy. This line must have at least one segment in the vendor's range-1 von neumann neighborhood.
4. At most one vendor or piece of hilbert curve can be put in any 1x1 space.
5. The grid is infinite. However, note that it doesn't help to have arbitrarily distant vendors

Question: what is the smallest order of hillbert curve whose parts cannot all be supplied with happiness? Or is there no limit?
here is a demonstration of why it must be > order 3:

note that all rails are powered. The levers are vendors

n=3.png (407.1 KiB) Viewed 8840 times