Search found 61 matches

by Desiato
Tue May 22, 2018 11:40 pm UTC
Forum: Logic Puzzles
Topic: Plane colorings
Replies: 53
Views: 20270

Re: Plane colorings

6 year bump, but there's an update: It seems agreed upon now that the chromatic number of the plane is at least 5. Paper proving this can be found here(and googling shows many references to it with non doubting the result).
by Desiato
Sun Jul 03, 2016 7:57 pm UTC
Forum: Forum Games
Topic: My number is bigger!
Replies: 1588
Views: 371436

Re: My number is bigger!

The article gives Peano Arithmetic as an example. PA can be proven with transfinite induction up to epsilon-0. Do you regard such a proof as "a proof by finitary means" or not? If you do, than there's no reason to assume that ZFC can't be proven to be consistent in a similar manner. Since...
by Desiato
Sun Jul 03, 2016 7:20 pm UTC
Forum: Forum Games
Topic: My number is bigger!
Replies: 1588
Views: 371436

Re: My number is bigger!

But by their very nature, Turing machines are about finitary processes, and presumably everything that can be proven about them only requires arguments of finitary nature. Do you have proof of the second half of your statement? No, of course not. It's my intuition, and there's arguments to be made ...
by Desiato
Fri Jul 01, 2016 12:19 am UTC
Forum: Forum Games
Topic: My number is bigger!
Replies: 1588
Views: 371436

Re: My number is bigger!

So to find the value of BB(1919), we'll first need some method to clasify all 1919-state TM's. For those who don't halt, we'll need to prove that they don't halt. Among these machines, of-course, is the ZFC machine. And the only way to prove that the ZFC machine doesn't halt, is to prove that ZFC i...
by Desiato
Thu Jun 30, 2016 7:57 pm UTC
Forum: Forum Games
Topic: My number is bigger!
Replies: 1588
Views: 371436

Re: My number is bigger!

To be honest, I don't really see any relation - either way - between "being independent of ZFC" and "being unknowable". I should clarify that this is not about "being independant of ZFC". The 1919 state Turing machine mentioned above does the following: It enumerates p...
by Desiato
Thu Jun 30, 2016 12:11 am UTC
Forum: Forum Games
Topic: My number is bigger!
Replies: 1588
Views: 371436

Re: My number is bigger!

"Which n is the smallest such that BB(n) cannot be known?" (where "known" is deliberately not restricted to "provabale in some specific theory") I don't believe such n exists. I don't think the question is even meaningful. The phrase "can be known" is hardly ...
by Desiato
Wed Jun 29, 2016 12:52 am UTC
Forum: Forum Games
Topic: My number is bigger!
Replies: 1588
Views: 371436

Re: My number is bigger!

What implications would that have for Eleizers entry? As far as I can tell (and if I recall the nature of his entry correctly), none. This result basically shows something that was already known: BB is more powerful than ZFC (or in fact, any first order theory) by its very nature if we regard the t...
by Desiato
Sat Jun 25, 2016 8:38 pm UTC
Forum: Forum Games
Topic: My number is bigger!
Replies: 1588
Views: 371436

Re: My number is bigger!

There's actually several improvements already - see this for a summary. If it turns out to be correct, they're down to 1919 states (for a machine directly looking for contradictions in ZFC, so no more reliance on large cardinals).
by Desiato
Sat Jun 25, 2016 1:41 am UTC
Forum: Forum Games
Topic: My number is bigger!
Replies: 1588
Views: 371436

Re: My number is bigger!

There's a rather interesting recent result regarding the interaction of ZFC and BB, which seems relevant to this thread (despite computability issues I still claim): For any n, ZFC cannot prove that BB(7918)<=n (note that this refers to the definition of BB, not the actual number, since ZFC triviall...
by Desiato
Mon Jun 13, 2016 1:11 am UTC
Forum: Forum Games
Topic: My number is bigger!
Replies: 1588
Views: 371436

Re: My number is bigger!

First of all, Mahlo cardinals? Why that? Because a weakly Mahlo cardinal is weakly inaccessible, weakly ω-inaccessible, weakly hyper-inaccessible, weakly hyper-hyper-...-hyper-inaccessible, and so on. The χ function collapses down onto some layer of inaccessibility (for instance, γ↦χ(M 2 +γ) enumer...
by Desiato
Mon Jun 06, 2016 9:50 pm UTC
Forum: Forum Games
Topic: My number is bigger!
Replies: 1588
Views: 371436

Re: My number is bigger!

First of all, sorry for the late reply. I was on the road, and this sort of thing is nothing I like to type out on my phone. I did take some time to look into your definitions more deeply, though, and am pretty certain I now understand what you're trying to do. I still have doubts you succeed, thoug...
by Desiato
Wed May 18, 2016 11:38 pm UTC
Forum: Forum Games
Topic: My number is bigger!
Replies: 1588
Views: 371436

Re: My number is bigger!

Restrict π to uncountable regular cardinals and λ to limit ordinals, and let M be the least weakly Mahlo cardinal. We restrict ourselves to ordinals ≤ε M+1 . http://latex.codecogs.com/gif.latex?%5C%5C%20C_0%28%5Calpha%2C%5Cbeta%29%20%3A%3D%20%5Cbeta%5Ccup%5C%7B0%2C%5Ctext%20M%5C%7D%20%5C%5C%20C_%7B...
by Desiato
Wed May 18, 2016 10:27 pm UTC
Forum: Forum Games
Topic: My number is bigger!
Replies: 1588
Views: 371436

Re: My number is bigger!

Well, as mentioned in my previous post, my concern regarding Turing machines in ZFC etc is that I find it highly likely that listing all states and steps the machine goes through until it halts IS the shortest halting proof. Basically, bounded busy beavers might well be their own Kolmogorov complex...
by Desiato
Tue May 17, 2016 11:02 pm UTC
Forum: Forum Games
Topic: My number is bigger!
Replies: 1588
Views: 371436

Re: My number is bigger!

Well, certainly - but it doesn't have to be here. I'd be satisfied with a reference as well, as long that seems conclusive for the question here. [various proof checking languages] Still, Kruskal's Theorem is not all that hard, writing up the proof in Metamath should be doable, especially since ver...
by Desiato
Tue May 17, 2016 2:17 am UTC
Forum: Forum Games
Topic: My number is bigger!
Replies: 1588
Views: 371436

Re: My number is bigger!

...I've only seen handwaving regarding proof length... Well, any rigorous limit on the proof length of a proof length that a given Turing machine halts would require delving into the minutia of formal ZFC proofs and programming a specific Turing machine that can do what you want, which I think is b...
by Desiato
Sun May 15, 2016 1:43 am UTC
Forum: Forum Games
Topic: My number is bigger!
Replies: 1588
Views: 371436

Re: My number is bigger!

First, I want to recommend this page by Robert Munafo to anyone interested in the subject.It provides a very understandable, yet far reaching survey of the topic (even though it goes well into the uncomputable range). Second, I specifically find interesting a briefly mentioned reference regarding Be...
by Desiato
Thu May 12, 2016 1:30 am UTC
Forum: Forum Games
Topic: My number is bigger!
Replies: 1588
Views: 371436

Re: My number is bigger!

So, just to spice this up, I submit this number: Defined f(x) as x if x<=e, xf(ln(x)) for x>e. Consider the series \sum_1^\infty 1/f(n). This series is divergent (see Putnam 2008 A4). That means that "g(n) = lowest number of terms in that series to exceed n" is a total function on the natu...
by Desiato
Tue May 10, 2016 6:24 pm UTC
Forum: Forum Games
Topic: My number is bigger!
Replies: 1588
Views: 371436

Re: My number is bigger!

(*My expectations are based on that I would not expect some part in the proof to increase the length more than exponentially, and that the proof we would want would likely contain a subtetrational amount of these.) That's just the point. I think it's not only possible, but actually likely that a pr...
by Desiato
Mon May 09, 2016 4:23 am UTC
Forum: Forum Games
Topic: My number is bigger!
Replies: 1588
Views: 371436

Re: My number is bigger!

I've actually been reading through the whole thread, and I submit a different concern regarding numbers submitted as some sort of proof enumeration in ZFC or stronger. So far, as I can see, I've only seen handwaving regarding proof length. Note that proof length is crucial since the limit on proof l...
by Desiato
Fri Apr 27, 2012 7:34 pm UTC
Forum: Individual XKCD Comic Threads
Topic: 1048: "Emotion"
Replies: 252
Views: 52366

Re: 1048: "Emotion"

Sympathy++

TrollFeeding--
by Desiato
Thu Mar 15, 2012 3:29 pm UTC
Forum: Mathematics
Topic: Probability paradox?
Replies: 40
Views: 7099

Re: Probability paradox?

While it seems kinda nitpicky, I'm not sure if the result that it's consistant with ZF that countable unions of countable sets need not be countable is irrelevant here. I'm pretty sure it isn't, because couldn't a Godel-like numbering scheme enumerate the algorithms, and then we/d just number their...
by Desiato
Thu Mar 15, 2012 7:11 am UTC
Forum: Mathematics
Topic: Compositional square root
Replies: 18
Views: 3266

Re: Compositional square root

For anyone still interested in this topic I've posted a followup discussion of this on stackexchange, here.
by Desiato
Thu Mar 15, 2012 5:44 am UTC
Forum: Mathematics
Topic: Probability paradox?
Replies: 40
Views: 7099

Re: Probability paradox?

Finite algorithms in a finite language gives countably many algorithms. Each finite algorithm can only print out countably many outputs. A countable set of countable sets is still countable, so you can never get uncountably many results from finitely-specified algorithms with a finite alphabet. Whi...
by Desiato
Wed Mar 14, 2012 5:56 pm UTC
Forum: Mathematics
Topic: Exercises in Kunen's Introduction to Independence Proofs
Replies: 4
Views: 2152

Re: Exercises in Kunen's Introduction to Independence Proofs

And I already have another problem in the next exercise; specifically, this: "Show that if K is an uncountable cardinal, then K is an epsilon number and there are K epsilon numbers below K". For reference, an ordinal alpha is an epsilon number if and only if omega alpha =alpha. The other (...
by Desiato
Sun Mar 11, 2012 11:00 pm UTC
Forum: Mathematics
Topic: Exercises in Kunen's Introduction to Independence Proofs
Replies: 4
Views: 2152

Re: Exercises in Kunen's Introduction to Independence Proofs

Deedlit wrote:There are probably better ways to prove the (D)=>(C) direction, but that is what I came up with.

Maybe, but this certainly is clear and concise, so thanks!
by Desiato
Sun Mar 11, 2012 6:38 pm UTC
Forum: Mathematics
Topic: Formal systems
Replies: 8
Views: 1507

Re: Formal systems

Proof: not light() v happy(Basil) Great that you noticed my typo (I had left out the "not")! I did thought of trying to proof light(Basil) v happy(Basil), but from the question light doesn't seem to have a direct connection with Basil. I don't quite understand the difference between light...
by Desiato
Sat Mar 10, 2012 11:52 pm UTC
Forum: Mathematics
Topic: Formal systems
Replies: 8
Views: 1507

Re: Formal systems

Well, if you're doing this as a formal system using the language of logic, I assume you're actually looking for a proof in formal logic. Formal logic has a few ways to get valid formulas from already proven formulas (or assumed formulas = axioms) such as modus ponens (a and (a->b) => b). Note that I...
by Desiato
Sat Mar 10, 2012 9:29 pm UTC
Forum: Mathematics
Topic: Exercises in Kunen's Introduction to Independence Proofs
Replies: 4
Views: 2152

Exercises in Kunen's Introduction to Independence Proofs

Let me start by clarifying this is not homework. While I got a math degree, that was quite a few years ago, and these days I work in a completely unrelated area. However, I've always been fascinated with the big topics of logic and set theory, and so I'm now working my way through Kunen's book, incl...
by Desiato
Fri Mar 09, 2012 4:48 am UTC
Forum: Mathematics
Topic: Some group theory questions
Replies: 23
Views: 3328

Re: the reals are a non-hopfian group

L(R) is every subset of the reals is measurable. I was thinking that R being non-hopfian would imply the existence of a non measurable set, as I think that any Q-linear, non R-linear transformation from R to R must be non measurable. Leaving aside the question of whether this is true in ZF for the ...
by Desiato
Sat Mar 03, 2012 6:10 am UTC
Forum: Mathematics
Topic: New types of numbers
Replies: 38
Views: 6299

Re: New types of numbers

Maybe you get more numbers if you look at solutions for equations 0=\sum\limits_{i=0}^n a_i\, x^{b_i} with algebraic a i and b i . Maybe. This set is still countable. I don't see this, are you able to prove it? Certainly there are only countably many equations, but I don't see how you'll prove a co...
by Desiato
Fri Jan 27, 2012 12:04 am UTC
Forum: Mathematics
Topic: "question theory"?
Replies: 16
Views: 3257

Re: "question theory"?

If a computer could ask questions, we could just tell it: "Here you have a set of axioms and definitions. Go ahead, find some interesting propositions!". We could have a computer writing a math thesis. I think that would be great! This is already being done, but the outcome is not exactly...
by Desiato
Thu Jan 26, 2012 6:26 am UTC
Forum: Mathematics
Topic: Set-theoretic brain fart
Replies: 9
Views: 2032

Re: Set-theoretic brain fart

I find that I didn't phrase my problem clear enough. While I actually am a realist in the sense mentioned, that's not what I was aiming at - in fact, from that perspective, the issue is only half as unclear and reduces to not quite understanding the formalism involved. My issue is that in pretty muc...
by Desiato
Wed Jan 25, 2012 3:52 pm UTC
Forum: Logic Puzzles
Topic: Stamps
Replies: 13
Views: 2770

Re: Stamps

Nitrodon is correct. By placing the points P, Q, and R colinearly, all orthogonal directions are equivalent to each other by symmetry. It is therefore sufficient to consider the plane formed by the x-axis and any arbitrary orthogonal direction, such as the y-axis. Since we have already shown that &...
by Desiato
Tue Jan 24, 2012 3:33 am UTC
Forum: Logic Puzzles
Topic: Stamps
Replies: 13
Views: 2770

Stamps

You get a magic stamp that hits all points of the area that has transcendental distance from the origin.

How often do you need to stamp to cover the entire plane?

Extending to an n-dimensional stamp, how often do you have to stamp to cover the entire R^n?
by Desiato
Tue Jan 24, 2012 3:25 am UTC
Forum: Mathematics
Topic: Set-theoretic brain fart
Replies: 9
Views: 2032

Set-theoretic brain fart

So, Löwenheim-Skolem implies that any first order theory that has an infinite model has a countable model. This is, for some, considered a paradox. I undertand the reasons why this is not, in general, a paradox - notably, the difference of the notion of countability "outside" of our theory...
by Desiato
Tue Jan 24, 2012 1:52 am UTC
Forum: Mathematics
Topic: The natural structure of mathematics
Replies: 7
Views: 1699

Re: The natural structure of mathematics

Various types of set theories can provide a foundation for mathematics but there are also people who prefer alternative foundations so I don't think it's right to say mathematics is founded on the principles of logic and set theory. More than anything I think foundations are largely useful as pedag...
by Desiato
Tue Jan 24, 2012 1:41 am UTC
Forum: Mathematics
Topic: Obscure branches of math?
Replies: 67
Views: 15291

Re: Obscure branches of math?

It is, in a sense, more of a sign that esoteric pure mathematics ends up having applications despite the best efforts of the subject area than evidence that it is applied mathematics. This. For example, one of the areas that I'm rather interested in and have at least a vague concept of an idea abou...
by Desiato
Wed Jan 18, 2012 4:40 pm UTC
Forum: Mathematics
Topic: New types of numbers
Replies: 38
Views: 6299

Re: New types of numbers

Due to Gödel's incompleteness theorem, any sufficiently powerful formal system of numbers (e.g. anything that includes the integers) has equations that cannot be solved. So if you define "number" as the solution to an equation, then you can always have more types of numbers. One needs to ...
by Desiato
Mon Jan 16, 2012 9:36 pm UTC
Forum: Mathematics
Topic: Compositional square root
Replies: 18
Views: 3266

Re: Compositional square root

Another interesting idea is that if square roots come in pairs, then maybe compositional square roots come in pairs too. Let f(x) be our original function, and let g(x) and h(x) be a pair of compositional square roots of f(x), and let i(x)=g(h(x)), what would i(x) look like? Knowing one of the squa...
by Desiato
Mon Jan 16, 2012 12:37 pm UTC
Forum: Mathematics
Topic: Compositional square root
Replies: 18
Views: 3266

Re: Compositional square root

Deedlit: Dang, of course you're right. I was just considering preimage of a single element, but not noticing that as soon as we have more than one "branch", collapsing isn't trivial. Now I'm thinking that there won't be a simpler condition for the general case than some sort of "tree ...

Go to advanced search