If something is true, can you necessarily prove it's true?

Question

I'm thinking of the Collatz Conjecture and I'm wondering if we will ever know if it's true. If it's true, is there necessarily a proof that can prove it's true? This is more of a general question too: If something is true, does there exist a logically valid proof to prove it's true?

Also, if this is true and there is necessarily a proof for every true conjecture, how can we prove that?

Answer 1

Gödel's incompleteness theorem shows that there exist true statements that cannot be proved.

But more specifically we can say that there are some true statements very similar to the Collatz Conjecture that cannot be proved.

Turing showed that that there are some computer programs that never halt, but for which it cannot be proved that they never halt. Conway showed that functions like Collatz's (in which one of a number of simple arithmetic functions is applied to a number depending on which numbers it divides by) can be used to simulate arbitrary computer programs. By combining these results we can show that there are some conjectures which are like the Collatz Conjecture, just involving different functions than $n\mapsto 3n+1$ and $n\mapsto n/2$, which are true but cannot be proved.

For all we know, the Collatz Conjecture itself could also be one of these undecidable statements.

Answer 2

By Godel's incompleteness theorem, if a formal axiomatic system capable of modeling arithmetic is consistent (i.e. free from contradictions), then there will exist statements that are true but whose truthfulness cannot be proven. Such statements are known as Godel statements.

So to answer your question... no, if a statement in mathematics is true, this does not necessarily mean there exists a proof to show it (of course, this assumes that mathematics is consistent, and that certainly appears to be the case). Hence, if the Collatz Conjecture was a Godel statement, then we would not be able to prove it - even if it was true.

Note that we could remedy this predicament by expanding the axioms of our system, but this would inevitably lead to another set of Godel statements that could not be proven.