1
$\begingroup$

If $C$ is the nonexistence of non-trivial cycles in the Collaz conjecture, and $CC$ is the Collatz conjecture itself.

  1. If it were proven that $C$ were unproveable, would this mean that $\lnot C$ would be unproveable too?

  2. If so, this would prove that one can never identify a counterexample.

  3. This would prove $C$ - a contradiction. Therefore $C$ cannot be unproveable.

  4. Therefore any proof claiming that $CC$ is unproveable, which does not first prove $C$, is incorrect.

Is my logic correct?

I've highlighted the question to avoid misuse of "Unclear what the question is".

Am I right in thinking this rule does not apply to sequences ascending to infinity, because although any sequence might exist ascending to infinity, it may not be provable that it ascends to infinity - since one cannot follow it all the way. Therefore a proof that one can never find a counterexample wouldn't necessarily imply that no counterexample exists. So step $2$ would be incorrect in respect of $CC$.

But we can deduce that any proof that $CC$ is unproveable, must prove $C$ must it not?

As a corollorary to this question, I'm interested in to what extent the overall power of any logical framework can be augmented by this principle.

For example, it's well known that the strengthened finite Ramsey theorem (which is true) implies the consistency of Peano, meaning it is unproveable within Peano. Knowing this, can we deduce that Peano can generate no counterexample to the strengthened finite ramsey theorem and therefore the strengthened finite ramsey theorem is true?

Finally, how complicated an exercise would it be to attempt to show that Collatz implies the consistency of Peano?

$\endgroup$
  • $\begingroup$ You need to be more careful about which theory is that proves or doesn't prove the claims you're talking about. Thanks to Gödel and Rosser we know that if PA proves "PA does not prove $C$", then PA is inconsistent -- in particular, in that case it does prove $C$, as well as $\neg C$ and $CC$. So the very first part of your point 1 should probably be something like "If PA proves that (if PA is consistent then PA does not prove C), would this mean ...". And suddenly there's a new premise that can upset your cart. $\endgroup$ – Henning Makholm Feb 11 '17 at 16:14
  • 1
    $\begingroup$ " it's well known that the finite ramsey theorem (which is true) implies the consistency of Peano, meaning it is unproveable within Peano." That's not correct; the finite Ramsey theorem is provable in PA. Maybe you're thinking of the Paris-Harrington theorem, which asserts that a Ramsey-like principle isn't provable in PA? $\endgroup$ – Noah Schweber Feb 11 '17 at 16:15
  • 1
    $\begingroup$ However, ignoring all that, I don't see how you get "if $C$ is unprovable, then $\neg C$ is unprovable too" in the first point. With simpler claims this is not the case -- for example, $1=2$ is (hopefully!) not provable, but $\neg(1=2)$ has an easy proof. You may be forgetting to distinguish between "unprovable" and "independent". $\endgroup$ – Henning Makholm Feb 11 '17 at 16:16
  • 1
    $\begingroup$ @RobertFrost There are several grounds on which to dismiss this attempt as nonsense. First, as per your comment the paper argues that CC is undecidable in every axiom system, which is of course nonsense as we've observed. Second, the argument they've given would apply equally well to variations of CC which have been proved. Third, their argument makes unwarranted assumptions about what a proof of CC would have to be; in fact, this error is also present in their attempted (one page!) proof of the unprovability of the Riemann hypothesis. (cont'd) $\endgroup$ – Noah Schweber Feb 11 '17 at 18:36
  • 2
    $\begingroup$ Fundamentally, their attempts (and many others' at other major open questions, especially for some reason with respect to P vs NP) rely on a misunderstanding of how to prove universal statements: to prove "$\forall xP(x)$," it is not necessary in general to verify $P(x)$ separately for every $x$. Rather than the provability issues (which are of course fundamental), I'd argue that this is the most important error the author makes. (I normally wouldn't spend this time addressing proof attempts, but I think it's instructive to do so in this particular case.) $\endgroup$ – Noah Schweber Feb 11 '17 at 18:38
4
$\begingroup$

A caveat, worth keeping in mind in all such questions: "provability" is meaningless. It is only meaningful to speak of "provability in some axiom system." E.g. the Goedel sentence of PA is unprovable in PA (assuming PA is consistent!), but it is easily provable in the stronger theory PA+Con(PA). This issue doesn't play a huge role here, but it's always worth keeping in mind.

It does help answer your title question, though: such a proof need not be false as long as it refers to a different system than it is taking place in. For instance, PA+Con(PA) could conceivably prove "the nonexistence of nontrivial finite cycles is undisprovable in PA", without contradiction. That said, there are currently no known methods which come close to proving that CC is undecidable in PA; and you may be interested in this paper as a survey of what methods there are currently for proving unprovability/undecidability from PA.

If the Collatz function has a nontrivial finite cycle, then PA (or much less) can prove this. So if you prove "The existence of a nontrivial finite cycle is unprovable in PA", then you've proved that there is no nontrivial finite cycle.

However, a proof of "The existence of a nontrivial finite cycle is unprovable in PA" can't occur in PA unless PA is inconsistent: any statement of the form "PA doesn't prove ---" implies the consistency of PA (since any inconsistency lets you prove anything), so by Goedel's Second PA can't prove any such statement (unless PA is inconsistent). So what we've really said above is:

If $T$ is a theory which proves "PA doesn't prove 'There is a nontrivial finite cycle'," then $T$ proves that there is no nontrivial finite cycle.

However, this doesn't mean that PA proves that there is no nontrivial finite cycle! The non-existence of nontrivial finite cycles could well be unprovable in PA.


When you get to step (4), you're a little turned around. What you can conclude is:

Any proof that CC is un-disprovable in PA, also yields a proof that C is true.

I think you are conflating "unprovable" and "undecidable" here.


Your later question - about the difference in character between finite cycles and infinite chains - is spot-on. Whereas finite cycles are verifiable in PA, infinite chains need not be - and indeed this is pointing to a difference in levels in the arithmetic hierarchy. Basically, PA proves any true $\Sigma_1$ sentence, but does not prove every true $\Pi_1$ or higher sentence (e.g. the consistency of PA is a $\Pi_1$ sentence); the existence of infinite chains is a $\Sigma_2$ sentence, even more complicated than the consistency of PA, so there is no reason to believe that its un-disprovability (in PA) implies its truth.


Re: your second to last paragraph, note that the Paris-Harrington theorem really states:

The strengthened finite Ramsey principle is true iff PA is consistent.

In this form it is provable in PA. But since PA doesn't prove itself to be consistent, this leaves open the possibility (from the point of view of PA) that the strengthened finite Ramsey principle is false. Meanwhile, if $T$ is a theory extending PA which proves that PA is consistent, then $T$ proves that the strengthened finite Ramsey principle is true.

$\endgroup$
  • 1
    $\begingroup$ @RobertFrost No, not at all - it could easily be the case that $C$ is undecidable in PA! However, if $T$ is a (reasonable) theory which proved "$C$ is undecidable in PA," then $T$ would prove "$C$ is true." (In particular, if someone claims to prove in PA that PA doesn't decide C, they're wrong.) And since CC is $\Pi_2$, the answer to your second question is also no. Even if $T$ proved "PA doesn't decide CC," $T$ would gain no information about CC's truth: it could be that CC is false, because of an infinite chain, whose existence might not be detectable in PA. $\endgroup$ – Noah Schweber Feb 11 '17 at 17:07
  • 1
    $\begingroup$ Okay I think I have worked out what I was getting at... If $C$ is undecidable in "all reasonable theories", then that would imply no $C$ may be identified by any means, proving $C$ - a contradiction. So $C$ must be decidable in some "reasonable" theory... because we know any contradiction to $C$ would be a finite, followable loop, and therefore provable in Peano, if true. $\endgroup$ – samerivertwice Feb 11 '17 at 19:03
  • 1
    $\begingroup$ @RobertFrost Yes, that's true. And in fact we can even get a sense of what such a "reasonable theory" might look like! We can consider extending PA by consistency statements - e.g. PA, PA+Con(PA), PA+Con(PA)+Con(PA+Con(PA)), etc. - and with some work continue this process into the transfinite. It turns out that every true $\Pi^0_1$ sentence is proved by some such extension; so one of these extensions proves $C$, if $C$ is true! $\endgroup$ – Noah Schweber Feb 11 '17 at 19:18
  • 1
    $\begingroup$ @RobertFrost Yes, but we don't know what theory decides it; and in this sense, every sentence is decidable! $\endgroup$ – Noah Schweber Feb 11 '17 at 19:53
  • 1
    $\begingroup$ @RobertFrost Yes, and in the case of C, since it's a $\Pi_1$ sentence, it is decided by some consistency extension of PA. So the situation is better than for an arbitrary sentence, but it takes a bit of work to express how it's better. $\endgroup$ – Noah Schweber Feb 11 '17 at 19:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.