## Search found 61 matches

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

### 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).
Sun Jul 03, 2016 7:57 pm UTC
Forum: Forum Games
Topic: My number is bigger!
Replies: 1590
Views: 390825

### 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...
Sun Jul 03, 2016 7:20 pm UTC
Forum: Forum Games
Topic: My number is bigger!
Replies: 1590
Views: 390825

### 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 ...
Fri Jul 01, 2016 12:19 am UTC
Forum: Forum Games
Topic: My number is bigger!
Replies: 1590
Views: 390825

### 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...
Thu Jun 30, 2016 7:57 pm UTC
Forum: Forum Games
Topic: My number is bigger!
Replies: 1590
Views: 390825

### 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...
Thu Jun 30, 2016 12:11 am UTC
Forum: Forum Games
Topic: My number is bigger!
Replies: 1590
Views: 390825

### 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 ...
Wed Jun 29, 2016 12:52 am UTC
Forum: Forum Games
Topic: My number is bigger!
Replies: 1590
Views: 390825

### 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...
Sat Jun 25, 2016 8:38 pm UTC
Forum: Forum Games
Topic: My number is bigger!
Replies: 1590
Views: 390825

### 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).
Sat Jun 25, 2016 1:41 am UTC
Forum: Forum Games
Topic: My number is bigger!
Replies: 1590
Views: 390825

### 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...
Mon Jun 13, 2016 1:11 am UTC
Forum: Forum Games
Topic: My number is bigger!
Replies: 1590
Views: 390825

### 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...
Mon Jun 06, 2016 9:50 pm UTC
Forum: Forum Games
Topic: My number is bigger!
Replies: 1590
Views: 390825

### 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...
Wed May 18, 2016 11:38 pm UTC
Forum: Forum Games
Topic: My number is bigger!
Replies: 1590
Views: 390825

### 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...
Wed May 18, 2016 10:27 pm UTC
Forum: Forum Games
Topic: My number is bigger!
Replies: 1590
Views: 390825

### 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...
Tue May 17, 2016 11:02 pm UTC
Forum: Forum Games
Topic: My number is bigger!
Replies: 1590
Views: 390825

### 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...
Tue May 17, 2016 2:17 am UTC
Forum: Forum Games
Topic: My number is bigger!
Replies: 1590
Views: 390825

### 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...
Sun May 15, 2016 1:43 am UTC
Forum: Forum Games
Topic: My number is bigger!
Replies: 1590
Views: 390825

### 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...
Thu May 12, 2016 1:30 am UTC
Forum: Forum Games
Topic: My number is bigger!
Replies: 1590
Views: 390825

### 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...
Tue May 10, 2016 6:24 pm UTC
Forum: Forum Games
Topic: My number is bigger!
Replies: 1590
Views: 390825

### 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...
Mon May 09, 2016 4:23 am UTC
Forum: Forum Games
Topic: My number is bigger!
Replies: 1590
Views: 390825

### 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...
Fri Apr 27, 2012 7:34 pm UTC
Topic: 1048: "Emotion"
Replies: 252
Views: 54625

### Re: 1048: "Emotion"

Sympathy++

TrollFeeding--
Thu Mar 15, 2012 3:29 pm UTC
Forum: Mathematics
Replies: 40
Views: 7243

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...
Thu Mar 15, 2012 7:11 am UTC
Forum: Mathematics
Topic: Compositional square root
Replies: 18
Views: 3330

### Re: Compositional square root

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

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...
Wed Mar 14, 2012 5:56 pm UTC
Forum: Mathematics
Topic: Exercises in Kunen's Introduction to Independence Proofs
Replies: 4
Views: 2181

### 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 (...
Sun Mar 11, 2012 11:00 pm UTC
Forum: Mathematics
Topic: Exercises in Kunen's Introduction to Independence Proofs
Replies: 4
Views: 2181

### 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!
Sun Mar 11, 2012 6:38 pm UTC
Forum: Mathematics
Topic: Formal systems
Replies: 8
Views: 1529

### 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...
Sat Mar 10, 2012 11:52 pm UTC
Forum: Mathematics
Topic: Formal systems
Replies: 8
Views: 1529

### 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...
Sat Mar 10, 2012 9:29 pm UTC
Forum: Mathematics
Topic: Exercises in Kunen's Introduction to Independence Proofs
Replies: 4
Views: 2181

### 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...
Fri Mar 09, 2012 4:48 am UTC
Forum: Mathematics
Topic: Some group theory questions
Replies: 23
Views: 3388

### 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 ...
Sat Mar 03, 2012 6:10 am UTC
Forum: Mathematics
Topic: New types of numbers
Replies: 38
Views: 6392

### 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...
Fri Jan 27, 2012 12:04 am UTC
Forum: Mathematics
Topic: "question theory"?
Replies: 16
Views: 3388

### 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...
Thu Jan 26, 2012 6:26 am UTC
Forum: Mathematics
Topic: Set-theoretic brain fart
Replies: 9
Views: 2092

### 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...
Wed Jan 25, 2012 3:52 pm UTC
Forum: Logic Puzzles
Topic: Stamps
Replies: 13
Views: 2824

### 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 &...
Tue Jan 24, 2012 3:33 am UTC
Forum: Logic Puzzles
Topic: Stamps
Replies: 13
Views: 2824

### 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?
Tue Jan 24, 2012 3:25 am UTC
Forum: Mathematics
Topic: Set-theoretic brain fart
Replies: 9
Views: 2092

### 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...
Tue Jan 24, 2012 1:52 am UTC
Forum: Mathematics
Topic: The natural structure of mathematics
Replies: 7
Views: 1737

### 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...
Tue Jan 24, 2012 1:41 am UTC
Forum: Mathematics
Topic: Obscure branches of math?
Replies: 67
Views: 15906

### 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...
Wed Jan 18, 2012 4:40 pm UTC
Forum: Mathematics
Topic: New types of numbers
Replies: 38
Views: 6392

### 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 ...
Mon Jan 16, 2012 9:36 pm UTC
Forum: Mathematics
Topic: Compositional square root
Replies: 18
Views: 3330

### 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...
Mon Jan 16, 2012 12:37 pm UTC
Forum: Mathematics
Topic: Compositional square root
Replies: 18
Views: 3330

### 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 ...