0
$\begingroup$

I am pretty sure there are statements about natural numbers that cannot be proven. But is there a statement that can be proven for any concrete natural number and cant be proven in general.

For example, Goldbach conjecture says that every even number greater than 2 can be written as sum of two prime numbers. As far as i know we dont know if Goldbach conjecture is provable. But if we take concrete number lets say 2425582 than we can check if it can be written as sum of two primes in finitely many steps.

Another example that comes to mind is not about natural numbers, but its also interesting. That is continuum hypothesis. It is proven that it can not be proven in ZF, but here I dont see a way for a concrete set $S$ how we could determine if its cardinality is strictly greater than $\aleph_0$ and strictly smaller than $c$.

$\endgroup$
6
  • 6
    $\begingroup$ (Comment instead of an answer since I'm pretty sure this is a duplicate:) Yes, this does indeed happen: consider $\varphi_\mathsf{ZFC}(x)\equiv$ "$x$ is not the code for a proof of contradiction in $\mathsf{ZFC}$." Assuming $\mathsf{ZFC}$ is consistent, $\varphi_\mathsf{ZFC}(x)$ can be $\mathsf{ZFC}$-verified for each specific $x$, but by Godel's second incompleteness theorem we don't have $\mathsf{ZFC}\vdash\forall x\in\mathbb{N}\varphi_\mathsf{ZFC}(x)$. And of course there's nothing special about $\mathsf{ZFC}$ here: any "Godel-appropriate" theory would do in its place. $\endgroup$
    – Noah Schweber
    Commented Jan 17, 2023 at 18:01
  • $\begingroup$ Ok, thank you. That is a bit counter intuitive at least for me. $\endgroup$
    – Goki
    Commented Jan 17, 2023 at 18:07
  • $\begingroup$ Assume that Goldbach is true , but unprovable in ZFC. Then, we can show it for every concrete case, but not that it is true. This is surely a possibility. Noone knows whether ZFC can prove Goldbach , if it is true. $\endgroup$
    – Peter
    Commented Jan 17, 2023 at 19:06
  • 1
    $\begingroup$ In fact, the continuum hypothesis differs from Goldbach : There is no way to decide for every possible set whether it is a counterexample to the continuum hypothesis. $\endgroup$
    – Peter
    Commented Jan 17, 2023 at 19:10
  • 1
    $\begingroup$ This is literally the type of statement that Godel created. It was a statement for which each P(k) was a basic arithmetic statement (addition, multiplication, equality, propositional logic) . But $\forall k . P(k)$ has no proof. Also keep in mind "unprovable" is only ever relative to a logic, no statement is intrinsically unprovable. $\endgroup$
    – DanielV
    Commented Jan 17, 2023 at 20:24

1 Answer 1

Reset to default
3
$\begingroup$

Goldbach's conjecture and $\text{Con}(ZFC)$ are both examples of what I believe are called $\Pi_1^0$ statements, meaning they are arithmetic statements of the form $\forall n : P(n)$ where $P(n)$ is a statement about a natural number $n$ that can be verified by a finite computation. In the Goldbach conjecture case $P(n)$ says that e.g. $2n + 2$ can be written as the sum of two primes, and in the $\text{Con}(ZFC)$ case $P(n)$ says that $n$ is not the Gödel number of a proof of a contradiction in ZFC.

A general fact about $\Pi_1^0$ statements is that they are either provably true, true but unprovable, or provably false (so they cannot be false but unprovable). The reason is that if they are false then there is a specific natural number $n$ which provides a counterexample to them, and then writing this natural number down and verifying that $P(n)$ is not true constitutes a disproof.

However, it is possible for $\Pi_1^0$ statements, such as Goldbach's conjecture and $\text{Con}(ZFC)$, to be true but unprovable. To get a sense for how this could possibly be the case, recall that by the completeness theorem, to say that an arithmetic statement is unprovable (in first-order Peano arithmetic) is exactly to say that there exists a model of PA in which it's true and a model of PA in which it's false. So, a true but unprovable statement is a statement which is true in the "standard model" of PA, the "actual natural numbers," but false in some nonstandard model of arithmetic. For a $\Pi_1^0$ statement $\forall n : P(n)$ this means exactly that $P(n)$ is true of every standard or "actual" natural number, but that it has some "nonstandard counterexample."

In the case of $\text{Con}(ZFC)$, for example, this means there is some nonstandard model of arithmetic containing a "nonstandard proof" (more precisely, a nonstandard number which is rigged up to have the property that PA thinks it's the Gödel number of a proof) of an inconsistency in ZFC. Such models must exist if you believe that ZFC is consistent, by the incompleteness theorems.

$\endgroup$
2
  • $\begingroup$ Thank you, does this mean we cant show that $\Pi_1^0$ statement is unprovable? Because if we could show that, it would mean it is true since it cannot be false and unprovable. $\endgroup$
    – Goki
    Commented Jan 17, 2023 at 22:15
  • $\begingroup$ @Goki: if you believe that ZFC is consistent, then you believe $\text{Con}(ZFC)$ is true but (by the incompleteness theorem) that it is unprovable (from ZFC). You have to believe that ZFC is consistent for some other reason, if you do, so this argument doesn't supply any kind of independent proof of $\text{Con}(ZFC)$. $\endgroup$
    – Qiaochu Yuan
    Commented Jan 18, 2023 at 3:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .