Is it possible to prove that something is unprovable?

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

sgfw
Posts: 46
Joined: Wed Jun 19, 2013 11:47 pm UTC

Is it possible to prove that something is unprovable?

Postby sgfw » Tue Dec 24, 2013 12:15 am UTC

Mathematicians prove the rules that they use all the time, and some things have been proven false, as well. I can't think of any examples, but do you suppose it would ever be possible to prove that the validity of a conjecture is unprovable either way? Would it be accepted as a rigorous proof? How do you think that the math community would react to this- would most people use the idea as if it were always true, or would they disregard it as something that can't be used rigorously because it may not always be true?

Obviously, there are a lot of ideas that cannot be proven unprovable, such as fermat's last theorem because if you were to prove that it is unprovable, then you would be proving that there is no exception that can be found and used as a proof against it, thereby proving that it is true, which is a paradox. However, not all conjectures have this sort of nature, so could they ever possibly be proven unprovable?

User avatar
eSOANEM
:D
Posts: 3652
Joined: Sun Apr 12, 2009 9:39 pm UTC
Location: Grantabrycge

Re: Is it possible to prove that something is unprovable?

Postby eSOANEM » Tue Dec 24, 2013 12:34 am UTC

Take a look at Goedel's incompleteness theorem. Essentially it says that such conjectures must exist in any sufficiently complex axiomatic system.

Also, incidentally, there's nothing stopping a theorem of the same form as Fermat's last theorem being unprovable. The mere existence of a counter-example is insufficient to guarantee that it is possible to find it (which is one reason why non-constructive proofs are useful). Relatedly, it seems quite likely that not all real numbers are computable and therefore a conjecture about the real numbers could well have an incomputable counter example which might not be discoverable.
my pronouns are they

Magnanimous wrote:(fuck the macrons)

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 26738
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: Is it possible to prove that something is unprovable?

Postby gmalivuk » Tue Dec 24, 2013 12:47 am UTC

eSOANEM wrote:The mere existence of a counter-example is insufficient to guarantee that it is possible to find it
Indeed, and the first similar conjecture I thought of was the continuum hypothesis. Like Fermat, it states that something (a set with cardinality strictly between |N| and |R|) doesn't exist.

It has been proven to be consistent with ZFC set theory, which means that no such set can be constructed in ZFC (because if one could be constructed, that wouldn't be consistent with a hypothesis saying no such set exists).

The tricky thing is that its negation, which says that there is some set with cardinality strictly between that of the naturals and that of the reals, is *also* consistent with ZFC. So no set like that can be constructed, but it is at the same time not inconsistent with the axioms of ZFC set theory that a set like that might exist.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

Dark Avorian
Posts: 546
Joined: Mon May 03, 2010 10:48 pm UTC

Re: Is it possible to prove that something is unprovable?

Postby Dark Avorian » Tue Dec 24, 2013 5:30 pm UTC

Yeah, I suppose it depends what you interpret the statement "of the form of Fermat's last theorem" to mean. Roughly speaking, we can say that no such proof would make sense because

(a) The space over which we are searching is countable, and we know how to ennumerate it exhaustively.
(b) The algorithm for checking if a quadruple (a,b,c,n) is known to yield a decision in finite time.

In this rather restrictive subcase, it doesn't make sense to prove a statement is unprovable, because proving it's unproveable contradicts the existence of any counterexample (which we could find in finite time).
The 62-foot tall statue of Jesus constructed out of styrofoam, wood and fiberglass resin caught on fire after the right hand of the statue was struck by lightning.


meatyochre wrote:And yea, verily the forums crowd spake: "Teehee!"

fishfry
Posts: 135
Joined: Wed Dec 21, 2011 6:25 am UTC

Re: Is it possible to prove that something is unprovable?

Postby fishfry » Tue Dec 24, 2013 11:24 pm UTC

Dark Avorian wrote:Yeah, I suppose it depends what you interpret the statement "of the form of Fermat's last theorem" to mean. Roughly speaking, we can say that no such proof would make sense because

(a) The space over which we are searching is countable, and we know how to ennumerate it exhaustively.
(b) The algorithm for checking if a quadruple (a,b,c,n) is known to yield a decision in finite time.

In this rather restrictive subcase, it doesn't make sense to prove a statement is unprovable, because proving it's unproveable contradicts the existence of any counterexample (which we could find in finite time).


That argument contradicts the fact that there are unprovable statements in number theory, as explicated by Godel. Iteratively searching over an infinite set of possible proofs is not an effective procedure. If you've already gone at it for a million years you still don't know if you're done.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11116
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Is it possible to prove that something is unprovable?

Postby Yakk » Wed Dec 25, 2013 1:42 am UTC

Or, another way of thinking about it (which does not quite work) is that the axioms we are using do not define infinity sufficiently well, and we cannot actually pull that off.

We can prove that both "There exists n from N such that P(n) is true" and "For all n from N, P(n) is false" is consistent for some statement P generated after being given a fixed set of consistent axioms for which we can determine if a statement is an axiom or not which can model adding, subtracting, division and multiplication (ie, is sufficiently strong).

A way to look at this is that for any set of "reasonable" axioms talking about the natural numbers, we fail to actually sufficiently specify what "finite number" means, because there are multiple different consistent extensions which disagree about what natural numbers exist! And we cannot "reasonably" pick the smallest one either (because that would just be a larger "reasonable" axiom system).
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

lorb
Posts: 405
Joined: Wed Nov 10, 2010 10:34 am UTC
Location: Austria

Re: Is it possible to prove that something is unprovable?

Postby lorb » Wed Dec 25, 2013 7:24 pm UTC

There is a long list of undecidable Problems. (Wikipedia Link)
Please be gracious in judging my english. (I am not a native speaker/writer.)
http://decodedarfur.org/

radams
Posts: 90
Joined: Fri May 14, 2010 12:49 pm UTC

Re: Is it possible to prove that something is unprovable?

Postby radams » Wed Dec 25, 2013 9:20 pm UTC

The strengthened finite Ramsey theorem is usually given as the first example of a number-theoretically interesting sentence that has been shown to be undecidable in PA. It states:

"For any positive integers n, k, m we can find N with the following property: if we color each of the n-element subsets of S = {1, 2, 3,..., N} with one of k colors, then we can find a subset Y of S with at least m elements, such that all n element subsets of Y have the same color, and the number of elements of Y is at least the smallest element of Y."

It's provable in ZF. Paris and Harrington proved that it is undecidable in PA (https://en.wikipedia.org/wiki/Paris-Harrington_theorem)

User avatar
notzeb
Without Warning
Posts: 629
Joined: Thu Mar 08, 2007 5:44 am UTC
Location: a series of tubes

Re: Is it possible to prove that something is unprovable?

Postby notzeb » Thu Dec 26, 2013 12:01 am UTC

I feel the need to point out that if ZFC (or whichever axiom system you like best) is inconsistent, then every statement can be proved. Since we can't prove ZFC is consistent (unless it isn't consistent), the only way we could prove that a statement is unprovable is to either find an inconsistency in ZFC (in which case the statement really is provable) or to make the unjustified assumption that ZFC is consistent somewhere in our argument.
Zµ«V­jÕ«ZµjÖ­Zµ«VµjÕ­ZµkV­ZÕ«VµjÖ­Zµ«V­jÕ«ZµjÖ­ZÕ«VµjÕ­ZµkV­ZÕ«VµjÖ­Zµ«V­jÕ«ZµjÖ­ZÕ«VµjÕ­ZµkV­ZÕ«ZµjÖ­Zµ«V­jÕ«ZµjÖ­ZÕ«VµjÕ­Z

Dark Avorian
Posts: 546
Joined: Mon May 03, 2010 10:48 pm UTC

Re: Is it possible to prove that something is unprovable?

Postby Dark Avorian » Thu Dec 26, 2013 5:45 am UTC

fishfry wrote:
Dark Avorian wrote:Yeah, I suppose it depends what you interpret the statement "of the form of Fermat's last theorem" to mean. Roughly speaking, we can say that no such proof would make sense because

(a) The space over which we are searching is countable, and we know how to ennumerate it exhaustively.
(b) The algorithm for checking if a quadruple (a,b,c,n) is known to yield a decision in finite time.

In this rather restrictive subcase, it doesn't make sense to prove a statement is unprovable, because proving it's unproveable contradicts the existence of any counterexample (which we could find in finite time).


That argument contradicts the fact that there are unprovable statements in number theory, as explicated by Godel. Iteratively searching over an infinite set of possible proofs is not an effective procedure. If you've already gone at it for a million years you still don't know if you're done.


You've perhaps interpreted my statements too broadly. Would you deny that Fermat's Last Theorem cannot admit a proof of unprovability (ignoring the fact that it is proven, also damn so many negatives)?

You can iteratively search over proofs, and lets assume check them in finite time (er...can you?). I don't care if its efficient, that is completely and utterly irrelevant. I mean what, do number theory statements not hold up when things get too big? First, note that no proof coming up as correct does not imply a statement is incorrect (unless the theory is complete, but uh...Godel).

Actually, here's a question: For any statement P in a theory T, is it possible to show that the provability of P is unprovable? I'd argue that since we can iteratively search all finite proofs (and I'd assume we only care about those(I'm also assuming T is in some sense finite-again, the only realistic case)), that any proof or disproof of P would appear, thus P is unproveable, but this contradicts our assumption. [EDIT: Upon re-reading this argument seems very fallacious to me, but I can't figure out why]

I'll refine my conditions:
(a) The statement P (or equivalently its negation) is true iff some element x of an at most countable set S fulfills conditions C [for brevity C(x) = true].
(b) We may describe an exhaustive search of the space S.
(c) A known algorithm is guaranteed to decide "C(x) =true" or "C(x) = false" in finite time, for any x in S.

Under these conditions P cannot be proven undecidable.
Proof:
(1)Assume we have proven P is undecidable.
(2)Supposee P were true. Then for some fixed x, (with finite index, given countability of S). C(x) = true.
(3)If we were to search S exhaustively, using our algorithm to check each element for C, we would find C(x) = true in finite time (shut up about efficiency).
(4)Thus we've proven P is true. P is decidable
(5)Contradiction. (4) vs. (1)
(6)Thus we have proof by contradiction that P is untrue under the assumption P is undecidable. P is decidable.
(7) Contradiction. (6) vs. (1)
(8) We cannot have proven P is undecidable.

Not the nicest proof. But it works. Note that this doesn't apply to all number theoretic questions. Consider the strengthened Ramsey. We can exhaustively index n, k, m, N, but the statement cannot be equated to a statement about conditions on a single 4-tuple. Or we could exhaustively search n,k,m in which case we may phrase it in such a way, but cannot decide whether C(n,k,m) = true in guaranteed finite time (if its true it appears in finite time, but not if it's false).

EDIT: I've realized that one of the key conceptual barriers I was dealing with is that every statement here has an added proof-layer. That is to say the original argument was not actually about the provability of FLT, but about the provability of the provability. And that the argument I gave about general theorys was about the provability of provability of provability.
The 62-foot tall statue of Jesus constructed out of styrofoam, wood and fiberglass resin caught on fire after the right hand of the statue was struck by lightning.


meatyochre wrote:And yea, verily the forums crowd spake: "Teehee!"

fishfry
Posts: 135
Joined: Wed Dec 21, 2011 6:25 am UTC

Re: Is it possible to prove that something is unprovable?

Postby fishfry » Thu Dec 26, 2013 8:43 pm UTC

Dark Avorian wrote:You've perhaps interpreted my statements too broadly. Would you deny that Fermat's Last Theorem cannot admit a proof of unprovability (ignoring the fact that it is proven, also damn so many negatives)?


I deny it emphatically. I do think I sort of understand what you're getting at, but I think you are mistaken. Let's pretend nobody's proved FLT. Now if someone were to come up with a proof that FLT is independent of the rest of mathematics, that would imply (by meta-reasoning) that FLT is true. That's because if FLT is false, there is a counterexample. Therefore if there is no proof of truth or falsity, then FLT must be true.

This meta-reasoning always applies to any specific statement in number theory. The Goldbach conjecture, for example. If GC should be proved to be independent of the standard axioms of mathematics, then it must be true. For if it's false, then there is a proof ... namely, the existence of a counterexample.

Is this what you are talking about?

Your idea of iteratively looking at all possible proofs simply fails. You have a countably infinite list of all possible proofs. You start checking them one by one. After a trillion years, you're not done. You can never conclude that the proposition is unprovable simply because you haven't found the proof yet. And there's no proof that your proof-checking procedure will ever terminate. It's not an effective procedure.




Dark Avorian wrote:You can iteratively search over proofs, and lets assume check them in finite time (er...can you?).


Of course you can check one proof in finite time. But there are countably many possible proofs given a finite or countable axiom system. You have all the proofs of length 1, all the proofs of length 2 (lengths being the number of symbols in the proof), number of proofs of length 3, dot dot dot. All together, countably many proofs. You can't examine them all in finite time.


Dark Avorian wrote:I don't care if its efficient, that is completely and utterly irrelevant. I mean what, do number theory statements not hold up when things get too big? First, note that no proof coming up as correct does not imply a statement is incorrect (unless the theory is complete, but uh...Godel).


You're flailing here and I'm not following your train of thought. I haven't said a word about efficiency. But I have shown that you can not assure that your algorithm of checking each possible proof one-by-one will ever halt.

Dark Avorian wrote:Actually, here's a question: For any statement P in a theory T, is it possible to show that the provability of P is unprovable? I'd argue that since we can iteratively search all finite proofs (and I'd assume we only care about those(I'm also assuming T is in some sense finite-again, the only realistic case)), that any proof or disproof of P would appear, thus P is unproveable, but this contradicts our assumption. [EDIT: Upon re-reading this argument seems very fallacious to me, but I can't figure out why]


It's fallacious because even though each individual proof is a finite-length string that can be reliable examined for validity; the collection of all possible proofs is countably infinite. You can't examine them all in finite time.

Dark Avorian wrote:I'll refine my conditions:
(a) The statement P (or equivalently its negation) is true iff some element x of an at most countable set S fulfills conditions C [for brevity C(x) = true].
(b) We may describe an exhaustive search of the space S.
(c) A known algorithm is guaranteed to decide "C(x) =true" or "C(x) = false" in finite time, for any x in S.


You can't "exhaustively search" S, any more than manually checking every 4-tuple of positive integers (a,b,c,n) is a good way to resolve FLT. A proof is a finite string of symbols. You can't have an infinitely-long proof consisting of "I checked 1, I checked 2, I checked 3, ..."


Dark Avorian wrote:Under these conditions P cannot be proven undecidable.
Proof:
(1)Assume we have proven P is undecidable.
(2)Supposee P were true. Then for some fixed x, (with finite index, given countability of S). C(x) = true.
(3)If we were to search S exhaustively, using our algorithm to check each element for C, we would find C(x) = true in finite time (shut up about efficiency).
(4)Thus we've proven P is true. P is decidable
(5)Contradiction. (4) vs. (1)
(6)Thus we have proof by contradiction that P is untrue under the assumption P is undecidable. P is decidable.
(7) Contradiction. (6) vs. (1)
(8) We cannot have proven P is undecidable.


I'm sure that if you would apply your own common sense you would see that this argument's wrong. You are saying that we could check FLT by checking every possible input. That's not how proof works, I'm sure you know that.

Dark Avorian wrote:Not the nicest proof. But it works. Note that this doesn't apply to all number theoretic questions. Consider the strengthened Ramsey. We can exhaustively index n, k, m, N, but the statement cannot be equated to a statement about conditions on a single 4-tuple. Or we could exhaustively search n,k,m in which case we may phrase it in such a way, but cannot decide whether C(n,k,m) = true in guaranteed finite time (if its true it appears in finite time, but not if it's false).



Before whipping out Ramsey theory, it would be well to nail down the basics. Your idea that we can solve number theory problems by iteratively trying every possible example is of course not how math works, and you know that. Likewise, the idea that we can resolve math questions by examining each of the infinitely many possible proof-strings is also false.

Am I misunderstanding your point? How do you square your own theory with the fact that you are contradicting Godel?

Dark Avorian wrote:EDIT: I've realized that one of the key conceptual barriers I was dealing with is that every statement here has an added proof-layer. That is to say the original argument was not actually about the provability of FLT, but about the provability of the provability. And that the argument I gave about general theorys was about the provability of provability of provability.


Why don't we just nail down provability first, then get meta later? If the status of FLT were unknown, it would definitely be possible for it to be independent of the axioms. So your very first statement is wrong. Let's start there.

User avatar
dudiobugtron
Posts: 1098
Joined: Mon Jul 30, 2012 9:14 am UTC
Location: The Outlier

Re: Is it possible to prove that something is unprovable?

Postby dudiobugtron » Thu Dec 26, 2013 10:42 pm UTC

notzeb wrote:I feel the need to point out that if ZFC (or whichever axiom system you like best) is inconsistent, then every statement can be proved. Since we can't prove ZFC is consistent (unless it isn't consistent), the only way we could prove that a statement is unprovable is to either find an inconsistency in ZFC (in which case the statement really is provable) or to make the unjustified assumption that ZFC is consistent somewhere in our argument.

This seems pretty odd - surely we can tell if axiomatic systems are consistent with themselves?
Image

fishfry
Posts: 135
Joined: Wed Dec 21, 2011 6:25 am UTC

Re: Is it possible to prove that something is unprovable?

Postby fishfry » Thu Dec 26, 2013 11:09 pm UTC

dudiobugtron wrote:
notzeb wrote:I feel the need to point out that if ZFC (or whichever axiom system you like best) is inconsistent, then every statement can be proved. Since we can't prove ZFC is consistent (unless it isn't consistent), the only way we could prove that a statement is unprovable is to either find an inconsistency in ZFC (in which case the statement really is provable) or to make the unjustified assumption that ZFC is consistent somewhere in our argument.

This seems pretty odd - surely we can tell if axiomatic systems are consistent with themselves?


No, sadly not. Independence results are always stated in relative terms: IF ZF is consistent, THEN AC is independent. After all if ZF is inconsistent, then it proves AC.

Dark Avorian
Posts: 546
Joined: Mon May 03, 2010 10:48 pm UTC

Re: Is it possible to prove that something is unprovable?

Postby Dark Avorian » Fri Dec 27, 2013 1:45 am UTC

I continue to maintain that Fermat’s Last Theorem, and now I’ll also include the Goldbach conjecture, cannot be proven undecidable. My exposition was not the clearest. Forgive me for that. I’ll try once more to state what I’ve been thinking about, and hopefully to more successfully convey the full extent of the conditions I’ve put on it. As a first change, I will try to make a distinction between the decidability, and the provability/disprovability of a proposition P. I will use provable (disprovable) to mean that there exists a proof of P being true (false). I will use decidable to mean that P is either provable or disprovable. Undecidable means that no proof exists for either. Obviously, in any system we assume is consistent and representative of truth a statement being provable implies it is true.

I will, by and large, attempt to move from general to specific in this exposition. I am, at the most general level about which I have thought concerned with propositions P where we know that P being false (true) implies P is disprovable (provable) and thus implies P is decidable. Therefore, it follows that if P is undecidable, then P is true (false); this being a simple application of the contrapositive. In particular, it would follow that if it is provable that P is undecidable, then it is also provable that P is true (false), so P is provable (disprovable) and thus in either case decidable. We thus would have a paradox. Thus it is unprovable that P is undecidable.

Now, we consider a couple of things this argument does not claim. Note that P may well be undecidable. More interestingly, if it is undecidable, it is necessarily true, but of course, there is some barrier preventing us from ever showing that fact explicitly, or even divining that fact. Further, it is even possible that we could prove “P is unprovable”. But because we cannot prove “P is undisprovable” (again, contrapositive would imply P is true) we cannot prove it is undecidable (unprovable AND undisprovable).

Now, with the meta-gibberish completed, we consider a particular situation in which we might be able to prove the implication condition from the second paragraph. Now, this is a very restrictive condition. We return to our conditions from the previous post:

(a) The statement P (or equivalently its negation) is true iff some element x of an at most countable set S fulfills conditions C [for brevity C(x) = true].
(b) We may describe an exhaustive search of the space S.
(c) A known algorithm is guaranteed to decide "C(x) =true" or "C(x) = false" in finite time, for any x in S.

I do claim that these conditions yield the implication above. If P is true, the there is finitely indexed x in S such that C(x) = true, and our algorithms for exhausting and deciding will, in finite time, affirmatively locate this x. Therefore P is provable, so P is decidable.

Now we move to specific problems. I’d first like to formulate a number theoretic postulate that cannot easily be reduced to these conditions: “For all N > 1, there is a sum of N prime numbers which is a perfect square.” For the positive case, in order to affirm the postulate, we have to check infinite cases of N, so we can’t reduce it easily to a finite problem. The negation also cannot be so reduced, while the negation being true would imply the existence of a finite N for which the postulate failed, showing that it fails would require checking over an infinite set of possible sums. Note that I’ve been careful to add the word easily to most of the claims here. That is because of course it is entirely possible that this admits a simple proof/disproof, but those are not the types of mechanical algorithms I would describe as being considered in my claims about Goldbach/Fermat.

The Goldbach conjecture however, like FLT, fulfills the conditions I’ve described. First, we know we can exhaustively check all evens, reaching any even in a finite number of “checks”. It remains to be seen whether we can check any even in finite time. But this is also fairly obvious, since we simply need two positive integral summands, and for 2n there are at most 2n sums to check, (index by lesser summand), without even attempting to reduce this using density of primes, and each sum is an arithmetic problem, which I hope we can check in finite time.

EDIT (The meta-gibberish strikes back): It is an amusing fact that the statement P = "Q is decidable" may be of the above mentioned class. Again, the set of potential proofs is countable, and I imagine with a bit of imagination we could devise an exhaustive search. (I mean, go through strings in increasing length by dictionary order on any particular length). If we can check proofs in finite time (note that I'm not just asking we check for validity, but we also actually need to be able to extract the result and check that it affirms "Q true"). In a final spray of meta-gibberish: We cannot prove that it is undecidable whether Q is decidable.
The 62-foot tall statue of Jesus constructed out of styrofoam, wood and fiberglass resin caught on fire after the right hand of the statue was struck by lightning.


meatyochre wrote:And yea, verily the forums crowd spake: "Teehee!"

fishfry
Posts: 135
Joined: Wed Dec 21, 2011 6:25 am UTC

Re: Is it possible to prove that something is unprovable?

Postby fishfry » Fri Dec 27, 2013 4:22 am UTC

Dark Avorian wrote:I continue to maintain that Fermat’s Last Theorem, and now I’ll also include the Goldbach conjecture, cannot be proven undecidable.


It seems that I have indeed understood your argument and explained twice already why you're wrong, so I have nothing new to add. You can't "prove" a statement in number theory by appealing to the idea that you can iterate through the positive integers one by one. That's the opposite of how math proofs work.

I did find this article where the possible undecidability of the Goldbach conjecture is discussed. You might find it enlightening.

http://mathoverflow.net/questions/27755 ... unprovable

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 26738
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: Is it possible to prove that something is unprovable?

Postby gmalivuk » Fri Dec 27, 2013 5:28 am UTC

Dark Avorian wrote:I am, at the most general level about which I have thought concerned with propositions P where we know that P being false (true) implies P is disprovable (provable)
But no such implication exists. Incompleteness means there are true statements which are not provable.

The entire rest of your argument, as it relies on this fundamental misunderstanding, is thus refuted.

Being provable implies being true, and being disprovable implies being false, but the opposite implications don't hold for suffficiently powerful consistent systems.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

User avatar
chridd
Has a vermicelli title
Posts: 840
Joined: Tue Aug 19, 2008 10:07 am UTC
Location: ...Earth, I guess?
Contact:

Re: Is it possible to prove that something is unprovable?

Postby chridd » Fri Dec 27, 2013 7:57 am UTC

gmalivuk wrote:
Dark Avorian wrote:I am, at the most general level about which I have thought concerned with propositions P where we know that P being false (true) implies P is disprovable (provable)
But no such implication exists. Incompleteness means there are true statements which are not provable.
No such implication exists in general for all statements, but I think Dark Avorian is talking about a subset of statements where there is such an implication.
~ chri d. d. /tʃɹɪ.di.di/ (Phonotactics, schmphonotactics) · she · Forum game scores
Avatar from phillip1882
mittfh wrote:I wish this post was very quotable...

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 26738
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: Is it possible to prove that something is unprovable?

Postby gmalivuk » Fri Dec 27, 2013 1:18 pm UTC

Well then in that case isn't the argument trivial? The heavy lifting wasn't done by the rest of Dark Avorian's post, but by the assumption itself. And it remains to be seen which problems are in that particular subset.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

Dark Avorian
Posts: 546
Joined: Mon May 03, 2010 10:48 pm UTC

Re: Is it possible to prove that something is unprovable?

Postby Dark Avorian » Fri Dec 27, 2013 1:40 pm UTC

gmalivuk wrote:
Dark Avorian wrote:I am, at the most general level about which I have thought concerned with propositions P where we know that P being false (true) implies P is disprovable (provable)
But no such implication exists. Incompleteness means there are true statements which are not provable.

The entire rest of your argument, as it relies on this fundamental misunderstanding, is thus refuted.

Being provable implies being true, and being disprovable implies being false, but the opposite implications don't hold for suffficiently powerful consistent systems.


I'm not sure why I keep returning here. It seems like I'm spinning my wheels against people determined to misinterpret my statements. Where in the passage you quoted did I ever say such implications existed in general? I never did. The entire point of everything I've posted here was exploring the SUBSET of propositions that do have that property. I do hold that there are some propositions for which the implication holds.

fishfry wrote:
Dark Avorian wrote:I continue to maintain that Fermat’s Last Theorem, and now I’ll also include the Goldbach conjecture, cannot be proven undecidable.


It seems that I have indeed understood your argument and explained twice already why you're wrong, so I have nothing new to add. You can't "prove" a statement in number theory by appealing to the idea that you can iterate through the positive integers one by one. That's the opposite of how math proofs work.

I did find this article where the possible undecidability of the Goldbach conjecture is discussed. You might find it enlightening.

http://mathoverflow.net/questions/27755 ... unprovable


I suppose you're now leaving, but that was actually quite helpful. I would note however that Knuth's intuition is that it might not be provable, not that we could prove it's not provable.

I guess I was somewhat wrong, as apparently logicians have legitimately hoped that we might show such things as Goldbach or Fermat independent. In fact, as one poster pointed out, FLT has only been proven in the far extended world of ZFC + Universes, so it might be independent of PA. I guess the problem I have with that is more philosophical. It seems in bad faith for Fermat/Goldbach to fail on some exotic version of N satisfying PA but including exotic objects beyond the finite natural numbers. I suppose then all my reasoning lies in that blurry region of meta reasoning that appeals to some Platonic notions of mathematical truth. That's an uncomfortable place to be.


EDIT: to gmalivuk's most recent post. Yeah, that was the big ask. The rest of my post was trying to determine propositions that might satisfy that implication. In light of the overflow post, I guess I've more been doing some wierd meta-reasoning that would show that if say ZFC could show FLT independent of PA, then in a sense we'd have a proof of Fermat from some platonic viewpoint, though the far more interesting thing to look at would be the new system of arithmetic violating it.


EDIT2: Upon doing a bit of reading it appears my claims fail in the first-order formulation of PA, since my countability condition doesn't even make sense. The original, second order formulation, which has been shown to determine a model up to isomorphism (obviously this done in some other system) might still allow this type of proof.
The 62-foot tall statue of Jesus constructed out of styrofoam, wood and fiberglass resin caught on fire after the right hand of the statue was struck by lightning.


meatyochre wrote:And yea, verily the forums crowd spake: "Teehee!"

fishfry
Posts: 135
Joined: Wed Dec 21, 2011 6:25 am UTC

Re: Is it possible to prove that something is unprovable?

Postby fishfry » Sat Dec 28, 2013 4:17 am UTC

Dark Avorian wrote:I'm not sure why I keep returning here. It seems like I'm spinning my wheels against people determined to misinterpret my statements.


I hope I'm not doing that. You are writing relatively long posts that contain a couple of core misunderstandings; things you take for granted that aren't so. It can be tricky to try to engage on these core misunderstandings while ignoring all the other heartfelt verbiage. It would be helpful to me if you'd write less and be specific about your assumptions. Hope it's ok to say that.

Dark Avorian wrote:I suppose you're now leaving, but that was actually quite helpful. I would note however that Knuth's intuition is that it might not be provable, not that we could prove it's not provable.


This is a good place to focus for a moment. If something is provable, that means by definition that there is a proof. A proof by the way is a finite finite sequence of statements that proceeds logically from premises and reaches a particular conclusion. If a proof exists for proposition P, then we say P is provable. It makes no sense to prove that P is provable. If there's a proof, it's provable.

I'm a little confused by your bringing in provability of provability at this point.

Dark Avorian wrote:I guess I was somewhat wrong, as apparently logicians have legitimately hoped that we might show such things as Goldbach or Fermat independent. In fact, as one poster pointed out, FLT has only been proven in the far extended world of ZFC + Universes, so it might be independent of PA.


More likely than not I'm the source of that. I seem to recall posting about it on a couple of forums. But there's less there than meets the eye. Wiles used the universe framework, but as they say, "nobody doubts" that someone could write a proof in ZF if required. So don't read too much into that.


Dark Avorian wrote: I guess the problem I have with that is more philosophical. It seems in bad faith for Fermat/Goldbach to fail on some exotic version of N satisfying PA but including exotic objects beyond the finite natural numbers.


I'm not sure what you mean by that. Why do you think FLT and GC are "failing in some exotic version of N?" As matter of actual fact, FLT is proven and eventually someone will knock down GC. You seem to be worried or concerned that some familiar proposition of number theory will turn out to be independent, therefore true in one exotic model and false in another. But we already have that going on in set theory, where AC and CH are both natural-sounding propositions whose truth can't be determined from the other axioms. It's just part of the nature of axiomatic systems.

Dark Avorian wrote: I suppose then all my reasoning lies in that blurry region of meta reasoning that appeals to some Platonic notions of mathematical truth. That's an uncomfortable place to be.


It seems clear to me that if there is a Platonic realm of math, then the problem is with the limitations of axiomatic systems. They're just a tool, not the be-all and end-all people hoped they'd be. That seems like an obvious point of view for a Platonist to take.

Dark Avorian
Posts: 546
Joined: Mon May 03, 2010 10:48 pm UTC

Re: Is it possible to prove that something is unprovable?

Postby Dark Avorian » Sat Dec 28, 2013 3:51 pm UTC

fishfry wrote:
Dark Avorian wrote:I'm not sure why I keep returning here. It seems like I'm spinning my wheels against people determined to misinterpret my statements.


I hope I'm not doing that. You are writing relatively long posts that contain a couple of core misunderstandings; things you take for granted that aren't so. It can be tricky to try to engage on these core misunderstandings while ignoring all the other heartfelt verbiage. It would be helpful to me if you'd write less and be specific about your assumptions. Hope it's ok to say that.



Sorry, that was more a momentary frustration. You haven't really been doing that. Also, yeah, it's fine to be a bit more focused.

fishfry wrote:
Dark Avorian wrote:I suppose you're now leaving, but that was actually quite helpful. I would note however that Knuth's intuition is that it might not be provable, not that we could prove it's not provable.



This is a good place to focus for a moment. If something is provable, that means by definition that there is a proof. A proof by the way is a finite finite sequence of statements that proceeds logically from premises and reaches a particular conclusion. If a proof exists for proposition P, then we say P is provable. It makes no sense to prove that P is provable. If there's a proof, it's provable.

I'm a little confused by your bringing in provability of provability at this point.

Right, so I'm noting a distinction here between two types of "unprovability". Mathematicians obviously like to prove things, so if a statement is independent we'd like a proof of that fact, though it probably relies on appeals to stronger yet axiomatic systems. But there's also a possibility, for example, that Goldbach is true, but not provably true, and further there's no reason to think that we'd necessarily be able to prove it independent.

(As I understand it, Knuth's intuition is that the heuristic justification for the Goldbach conjecture, combined with the verification of a huge number of finite cases, means that it may well just be true for no good reason. That is to say, in some strange sense it's not really some deep statement about the structure of the integers but just a probabilistic truth. Therefore there might not be a proof from the axioms in any particular system, even if it does happen to be true. I mean the whole point of Godel is that there are true statements in any sufficiently strong system that we can't prove. And it might even be something as "mundane" as the claim that every even is the sum of two primes.)

So basically, there's provable independence, and then there's just not being provable.


fishfry wrote:
Dark Avorian wrote:I guess I was somewhat wrong, as apparently logicians have legitimately hoped that we might show such things as Goldbach or Fermat independent. In fact, as one poster pointed out, FLT has only been proven in the far extended world of ZFC + Universes, so it might be independent of PA.


More likely than not I'm the source of that. I seem to recall posting about it on a couple of forums. But there's less there than meets the eye. Wiles used the universe framework, but as they say, "nobody doubts" that someone could write a proof in ZF if required. So don't read too much into that.


Dark Avorian wrote: I guess the problem I have with that is more philosophical. It seems in bad faith for Fermat/Goldbach to fail on some exotic version of N satisfying PA but including exotic objects beyond the finite natural numbers.


I'm not sure what you mean by that. Why do you think FLT and GC are "failing in some exotic version of N?" As matter of actual fact, FLT is proven and eventually someone will knock down GC. You seem to be worried or concerned that some familiar proposition of number theory will turn out to be independent, therefore true in one exotic model and false in another. But we already have that going on in set theory, where AC and CH are both natural-sounding propositions whose truth can't be determined from the other axioms. It's part of the nature of axiomatic systems.

o
The problem, I suppose, is that I have some sense (which is definitely going away now that I know there are models of first-order PA with arbitrary cardinalities) captures the entire natural numbers much more than I have a sense that ZF captures the entire essence of sets. Although AC is natural-sounding enough (I don't know how CH sounds natural, it doesn't sound unnatural or particularly surprising, but it doesn't have quite the "duh" quality of "The Cartesian product of an arbitrary collection of non-empty sets is itself non-empty")
fishfry wrote:
Dark Avorian wrote: I suppose then all my reasoning lies in that blurry region of meta reasoning that appeals to some Platonic notions of mathematical truth. That's an uncomfortable place to be.


It seems clear to me that if there is a Platonic realm of math, then the problem is with the limitations of axiomatic systems. They're just a tool, not the be-all and end-all people hoped they'd be. That seems like an obvious point of view for a Platonist to take.

[/quote]
[quote="fishfry"]
The 62-foot tall statue of Jesus constructed out of styrofoam, wood and fiberglass resin caught on fire after the right hand of the statue was struck by lightning.


meatyochre wrote:And yea, verily the forums crowd spake: "Teehee!"

Dark Avorian
Posts: 546
Joined: Mon May 03, 2010 10:48 pm UTC

Re: Is it possible to prove that something is unprovable?

Postby Dark Avorian » Sat Dec 28, 2013 3:55 pm UTC

fishfry wrote:
Dark Avorian wrote:I'm not sure why I keep returning here. It seems like I'm spinning my wheels against people determined to misinterpret my statements.


I hope I'm not doing that. You are writing relatively long posts that contain a couple of core misunderstandings; things you take for granted that aren't so. It can be tricky to try to engage on these core misunderstandings while ignoring all the other heartfelt verbiage. It would be helpful to me if you'd write less and be specific about your assumptions. Hope it's ok to say that.



Sorry, that was more a momentary frustration. You haven't really been doing that. Also, yeah, it's fine to be a bit more focused.

fishfry wrote:
Dark Avorian wrote:I suppose you're now leaving, but that was actually quite helpful. I would note however that Knuth's intuition is that it might not be provable, not that we could prove it's not provable.



This is a good place to focus for a moment. If something is provable, that means by definition that there is a proof. A proof by the way is a finite finite sequence of statements that proceeds logically from premises and reaches a particular conclusion. If a proof exists for proposition P, then we say P is provable. It makes no sense to prove that P is provable. If there's a proof, it's provable.

I'm a little confused by your bringing in provability of provability at this point.

Right, so I'm noting a distinction here between two types of "unprovability". Mathematicians obviously like to prove things, so if a statement is independent we'd like a proof of that fact, though it probably relies on appeals to stronger yet axiomatic systems. But there's also a possibility, for example, that Goldbach is true, but not provably true, and further there's no reason to think that we'd necessarily be able to prove it independent.

(As I understand it, Knuth's intuition is that the heuristic justification for the Goldbach conjecture, combined with the verification of a huge number of finite cases, means that it may well just be true for no good reason. That is to say, in some strange sense it's not really some deep statement about the structure of the integers but just a probabilistic truth. Therefore there might not be a proof from the axioms in any particular system, even if it does happen to be true. I mean the whole point of Godel is that there are true statements in any sufficiently strong system that we can't prove. And it might even be something as "mundane" as the claim that every even is the sum of two primes.)

So basically, there's provable independence, and then there's just not being provable.


fishfry wrote:
Dark Avorian wrote:I guess I was somewhat wrong, as apparently logicians have legitimately hoped that we might show such things as Goldbach or Fermat independent. In fact, as one poster pointed out, FLT has only been proven in the far extended world of ZFC + Universes, so it might be independent of PA.


More likely than not I'm the source of that. I seem to recall posting about it on a couple of forums. But there's less there than meets the eye. Wiles used the universe framework, but as they say, "nobody doubts" that someone could write a proof in ZF if required. So don't read too much into that.


Dark Avorian wrote: I guess the problem I have with that is more philosophical. It seems in bad faith for Fermat/Goldbach to fail on some exotic version of N satisfying PA but including exotic objects beyond the finite natural numbers.


I'm not sure what you mean by that. Why do you think FLT and GC are "failing in some exotic version of N?" As matter of actual fact, FLT is proven and eventually someone will knock down GC. You seem to be worried or concerned that some familiar proposition of number theory will turn out to be independent, therefore true in one exotic model and false in another. But we already have that going on in set theory, where AC and CH are both natural-sounding propositions whose truth can't be determined from the other axioms. It's part of the nature of axiomatic systems.

o
The problem, I suppose, is that I have some sense (which is definitely going away now that I know there are models of first-order PA with arbitrary cardinalities) captures the entire natural numbers much more than I have a sense that ZF captures the entire essence of sets. Although AC is natural-sounding enough (I don't know how CH sounds natural, it doesn't sound unnatural or particularly surprising, but it doesn't have quite the "duh" quality of "The Cartesian product of an arbitrary collection of non-empty sets is itself non-empty")
fishfry wrote:
Dark Avorian wrote: I suppose then all my reasoning lies in that blurry region of meta reasoning that appeals to some Platonic notions of mathematical truth. That's an uncomfortable place to be.


It seems clear to me that if there is a Platonic realm of math, then the problem is with the limitations of axiomatic systems. They're just a tool, not the be-all and end-all people hoped they'd be. That seems like an obvious point of view for a Platonist to take.



I'm not exactly a Platonist. I sort of float somewhere between. I'd say I believe that there is some mathematical system present in the Real World (TM) but that that doesn't exclude my acceptance of systems inconsistent therewith. Nevertheless, I believe that there is a model of the natural numbers that probably rigidly resides in the model of the world, in which Goldbach either is or isn't true.
The 62-foot tall statue of Jesus constructed out of styrofoam, wood and fiberglass resin caught on fire after the right hand of the statue was struck by lightning.


meatyochre wrote:And yea, verily the forums crowd spake: "Teehee!"

korona
Posts: 495
Joined: Sun Jul 04, 2010 8:40 pm UTC

Re: Is it possible to prove that something is unprovable?

Postby korona » Sun Dec 29, 2013 11:48 am UTC

So basically, there's provable independence, and then there's just not being provable.

Take any proposition P. Let Q = "our axioms are consistent -> P is independent".

It could happen that this proposition Q is independent from our axioms. Your second case "and then there's just not being provable" means just that.

Moole
Posts: 93
Joined: Sun Jan 08, 2012 9:52 pm UTC

Re: Is it possible to prove that something is unprovable?

Postby Moole » Sun Dec 29, 2013 6:17 pm UTC

korona wrote:
So basically, there's provable independence, and then there's just not being provable.

Take any proposition P. Let Q = "our axioms are consistent -> P is independent".

It could happen that this proposition Q is independent from our axioms. Your second case "and then there's just not being provable" means just that.


Sadly, though, there can never be a proof (with the axioms) that Q is independent:

Suppose that there were a proof that Q is independent. Note that, for this to hold, P must be independent, since were it not, Q would be provably false (since a proof or disproof of P disproves Q). However, this creates a contradiction as it shows that a proof that Q is independent proves also that P is independent (which is Q). So a proof that Q is independent proves Q and therefore that Q is not independent.

This is rather annoying, I think, since it means we can't actually ever know if a statement is in the "just not provable" category. I am curious, though, is there a "reasonable" axiom system where, for any statement P, there is a proof of:

P
not P
P is independent?
Mathematical hangover (n.): The feeling one gets in the morning when they realize that that short, elementary proof of the Riemann hypothesis that they came up with at midnight the night before is, in fact, nonsense.

Dark Avorian
Posts: 546
Joined: Mon May 03, 2010 10:48 pm UTC

Re: Is it possible to prove that something is unprovable?

Postby Dark Avorian » Sun Dec 29, 2013 10:51 pm UTC

Moole wrote:
korona wrote:
So basically, there's provable independence, and then there's just not being provable.

Take any proposition P. Let Q = "our axioms are consistent -> P is independent".

It could happen that this proposition Q is independent from our axioms. Your second case "and then there's just not being provable" means just that.


Sadly, though, there can never be a proof (with the axioms) that Q is independent:

Suppose that there were a proof that Q is independent. Note that, for this to hold, P must be independent, since were it not, Q would be provably false (since a proof or disproof of P disproves Q). However, this creates a contradiction as it shows that a proof that Q is independent proves also that P is independent (which is Q). So a proof that Q is independent proves Q and therefore that Q is not independent.

This is rather annoying, I think, since it means we can't actually ever know if a statement is in the "just not provable" category. I am curious, though, is there a "reasonable" axiom system where, for any statement P, there is a proof of:

P
not P
P is independent?


Not if you'd like your definition of reasonable to be at least as strong as Godel's "encode the essentials of number theory". As I understand it, the Godel sentence in a given theory roughly is P = "There is no proof in this theory of P" where we've used a numerical encoding of the theory to allow us to apply number theory to its statements. P is true iff we cannot prove P is true. In particular, if our axioms are consistent and strong enough to allow the construction of a Godel sentence, then the Godel sentence cannot be proven, disproven, or shown independent without introducing an inconsistency.
The 62-foot tall statue of Jesus constructed out of styrofoam, wood and fiberglass resin caught on fire after the right hand of the statue was struck by lightning.


meatyochre wrote:And yea, verily the forums crowd spake: "Teehee!"


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 6 guests