Re: Another Reason Why Collatz is Unprovable


Craig Feinstein wrote:
GJ Woeginger wrote:
Craig Feinstein <cafeinst@xxxxxxx> wrote:
#> My proof on arXiv.org rules out a proof by contradiction because it
#> rules out any proof. It is a completely logical proof. No one on usenet
#> has found any flaws in the proof. The only things people have been
#> doing are claiming that my definition of "random" is not rigorous
#> (because it does not specify a formal language, which is really
#> irrelevant in the context of my proof) and giving straw-man arguments
#> which prove false statements and claiming that my proof uses the same
#> type of arguments. If you have faith in logic, then you should have
#> faith in my proof.
#
# My proof never claims that you have to treat every integer
# individually. My proof says: let's pretend that we have a proof of
# Collatz with L bits. It then shows that there is a specific n for which
# any proof that Collatz halts at one with input n requires at least L+1
# bits. From this, I conclude that any proof of Collatz must have at
# least L+1 bits, so we have a contradiction, as our pretend proof only
# has L bits. Therefore, Collatz is unprovable.

In your paper, you do not discuss at all the axiom system that
your are using. All your statements on "proofs" are absolute
statements, that do not even touch the question of the underlying
axiom systems in the slightest way.

Suppose, that I use as axiom system PA plus the axiom that the
Collatz algorithm always reaches 1.
In this axiom system, there is a very short and very trivial
proof that the Collatz algorithm always reaches 1.
This horribly collides with your absolute statement that
"Collatz is unprovable".

Using this line of reasoning, you can make 2+2=5 an axiom and then
prove 2+2=5, contradicting the well-established fact that 2+2=5 is
unprovable, i.e., that it is impossible to prove that 2+2=5.

Whenever provability is mentioned, it has to be put in contest. The
last part of the previous sentence should read:

"... contradicting the well-established fact that 2+2=5 is unprovable
_in the standard mathematical model_ [etc]."

If you ignore context, then the fact "the sum of the angles of a
triangle is 180 degrees" is both provable (in Euclidean geometry) and
unprovable (in non-Euclidean geometry).

Now, there is nothing wrong with an axiom system where you take
standard mathematics and add the axiom 2+2=5. It turns out that in this
system, _every_ proposition is provable. However, the system is not
"consistent" -- that is, you can prove statements which are false -- so
it's not useful.

If you
think mathematics is some kind of game, then this is perfectly OK, but
if you believe like me that mathematics is more than just a game, then
your argument is very weak.

I, for one, take mathematics seriously.

The only axiom needed for my proof to work is the axiom that in order
to prove that T^k(n)=1, it is necessary to specify the formula for
T^k(n) in the proof.

An axiom is an assumption, and you haven't stated this in your paper.
If you had stated:

"There is no proof of T^k(n) = 1 which includes a formula for T^k(n) in
it."

Then I would agree with this. But to prove that Collatz is unprovable,
you need to _prove_ your axiom, not just _state_ it.

For instance, the following is true and provable:

"There is no proof of T^k(n) = 1 if 2 = 0.5"

(Proof: Suppose n > 0. If n is odd, then T(n) = 3n+1 > n; if n is even,

T(n) = n/2 = n/0.5 = 2n > n. Thus T^k(n) >= n + k for all nonnegative
k, and so is never 1.)

But it doesn't count as a proof of Collatz, because I would need to
justify the axiom
2 = 0.5.

Another example is Euclidean versus non-Euclidean geometry that I
mentioned above.

I don't know anyone who doesn't accept this axiom as obviously true.

And the reason I don't accept the axiom is because of the principle of
generalization:

Suppose you have a proof that object X has property P. If every step of
the proof is valid for the object Y, then Y has property P (and this is
provable).

Once again, let U be the modified Collatz function

U(n) = n/2, if n is even,
U(n) = (n-1)/2, if n is odd.

I now claim that your proof can be used, step by step, to prove that
the statement "U(n) is eventually 0" is unprovable, using the principle
of generalization above.

Another reason the axiom is questionable is because a proof could
proceed by establishing that

(1) T^k(n) <= F(k,n), for some formula F (maybe for "big enough" n and
k),
(2) limsup F(k,n) <= C for some "small" constant C (where the limit is
as k goes to infinity).

Part (1) could be established without an explicit formula for T^k(n)
(by induction, for instance).

--- Christopher Heckman

.

Relevant Pages

  • Re: Another Reason Why Collatz is Unprovable
    ... # any proof that Collatz halts at one with input n requires at least L+1 ... # least L+1 bits, so we have a contradiction, as our pretend proof only ... axiom systems in the slightest way. ... that I use as axiom system PA plus the axiom that the ...
    (sci.math)
  • Re: Another Reason Why Collatz is Unprovable
    ... # any proof that Collatz halts at one with input n requires at least L+1 ... # least L+1 bits, so we have a contradiction, as our pretend proof only ... axiom systems in the slightest way. ... that I use as axiom system PA plus the axiom that the ...
    (sci.math)
  • Re: Another Reason Why Collatz is Unprovable
    ... # any proof that Collatz halts at one with input n requires at least L+1 ... # least L+1 bits, so we have a contradiction, as our pretend proof only ... that I use as axiom system PA plus the axiom that the ... that the Pythagorean Theorem is wrong by claiming that if one were to ...
    (sci.math)
  • Re: Another Reason Why Collatz is Unprovable
    ... # any proof that Collatz halts at one with input n requires at least L+1 ... that I use as axiom system PA plus the axiom that the ... standard mathematics and add the axiom 2+2=5. ... that the Pythagorean Theorem is wrong by claiming that if one were to ...
    (sci.math)
  • Re: Another Reason Why Collatz is Unprovable
    ... # any proof that Collatz halts at one with input n requires at least L+1 ... that I use as axiom system PA plus the axiom that the ... standard mathematics and add the axiom 2+2=5. ... that the Pythagorean Theorem is wrong by claiming that if one were to ...
    (sci.math)