Firstly contradiction 1: $s_1$="There exist distinct integers $a,b,c$ such that $a^n+b^n=c^n$ for some $n>2$"

With this contradiction, we first suppose that it is true. Then we find that doing so introduces a contradiction, so we reject our supposition.

Next, contradiction 2: $s_2=$"This statement is unprovable". First we suppose that it is true. Then we use the fact that, working under the assumption that $s_2$ is true, we can prove $s_2$ by virtue of $s_2\implies s_2$. This act demonstrates that, under the supposition, $s_2$ is provable, contradicting $s_2$. Therefore, the supposition of $s_2$ introduces a contradiction so we reject the supposition.

How, if any, do these two circumstances differ in status?

This question refers to being, provable/true within any reasonable system, not that that is material to the question.

I hold that all statements are first supposed, pending acceptance and therefore the liar paradox and similar statements are simply equally rejectable as untrue statements. The only difference in status that I can see, is that $s_2$ doesn't need to lean upon complex number theorems before it can be rejected.

  • 1
    $\begingroup$ The second statement is not a contradiction. Its analogue in arithmetics (i.e. the Godel statement) is, in fact, true in the standard natural numbers (assuming the consistency of arithmetics) and unprovable. $\endgroup$ – Apostolos Mar 14 '17 at 21:55
  • $\begingroup$ @Apostolos I think it is true in the standard numbers independently of the natural standard numbers, because it is an illogical statement. Can you find a reasonable theory in which it does not have the properties you describe? Any statement which is contradictory under supposition is illogical. $\endgroup$ – samerivertwice Mar 15 '17 at 3:04

To expand on my comment. $ \def\eq{\leftrightarrow} \def\box{\square} \def\nn{\mathbb{N}} $

You have probably been misled by popular accounts of the incompleteness theorems. There is no way to understand them without having a grasp of the distinction between the meta-system MS and the formal system $S$ under study. In what follows I assume that $S$ extends PA$^-$, but in fact completely analogous results hold for any system that interprets PA$^-$ (as described here). A key point is that MS, being used for foundations of mathematics, always has a model of PA which we shall call $\nn$.

In particular, the Godel sentence $G_S$ is constructed in MS such that $S \vdash G_S \eq \neg \box_S G_S$, where "$\box_S P$" denotes a specific kind of arithmetical sentence such that we have (as a theorem proven in MS) that ( $S \vdash P$ ) iff ( $\nn \vDash \box_S P$ ). Observe crucially that $\box_S$ is peculiar to $S$, and hence $G_S$ is crucially dependent on $S$. Change $S$ and you will get a different $G_S$. In particular, you cannot construct an 'absolute' Godel sentence $G$ such that $S \vdash G \eq \neg \box G$, where $\box$ is an absolute version of provability in any sense, simply because such does not exist, unless you want a contradiction.

Put another way, your reasoning shows that you cannot have absolute Godel sentences. And no proof of the incompleteness theorems ever have such a thing either.

  • 2
    $\begingroup$ By the way I'm not the downvoter of your question, but I suggest you learn the technical details behind basic proof theory and the incompleteness theorems, as layman accounts just can't make the cut. Some things are inherently incompressible and this is one of them. $\endgroup$ – user21820 Mar 15 '17 at 7:13

Your second example has multiple errors, which are generating this confusion.

First of all, let's specify a fixed theory we're discussing provability over. (You say this is immaterial, but it actually makes a huge difference; see below.) For any recursively enumerable theory $T$ extending $PA$ in the language of arithmetic, we may prove basic facts about provability in $T$ (e.g. for each $\varphi$ such that $T\vdash \varphi$, we have $T\vdash "T\vdash\varphi"$), and we may write a sentence $G_T$ saying "I am $T$-unprovable." Now we can in fact prove $G_T$, from axioms beyond those of $T$. Namely, if we add to $T$ the axiom asserting that $T$ is consistent, the resulting theory $T'$ can prove $G_T$.

But this is no contradiction at all. And this is the crucial mistake you make in deriving a contradiction from your $s_2$: you prove $s_2$ in the original system expanded by $s_2$ itself as a new axiom. In the language I've used above, you've proved $G_T$ in $T+G_T$. And obviously this isn't a problem, since $G_T$ doesn't say anything about its provability from systems other than $T$! In fact - assuming $T$ is consistent - the sentence $G_T$ is true, but unprovable in $T$. (What is provable in $T$ is the sentence "If $T$ is consistent, then $G_T$ is true", but that's not the same as $G_T$.)

Now you might try to escape this by replacing $G_T$ with some sentence $G_\infty$ which asserts its own "absolute unprovability," that it is unprovable in any "nice" system. Well, the first problem we hit is: what is a "nice" system? One natural guess is that a nice system is one whose axioms are true. This would certainly let your contradiction go through (if $G_\infty$ is true, then $\{G_\infty\}$ is a nice system which proves $G_\infty$, contradiction!).

But here you run afoul of a more fundamental problem: how do you plan to express your sentence in the language of arithmetic (or whatever language you're working in)? Remember, this was the key innovation that Goedel introduced: using Goedel numbering to show that certain statements about sentences could be expressed in the language of arithmetic.

And special emphasis should be placed on the word "certain" in the previous sentence. It is tempting to be vague when we talk about expressing metamathematical statements in arithmetic, on the grounds that "Goedel showed us we can do that." But that's a big mistake. And in fact Tarski's undefinability theorem shows that you won't be able to express the predicate "nice system" inside your language. Similarly, Lob's theorem shows that if a theory $T$ were to prove its own soundness, then $T$ would be complete - so, combined with Goedel's theorem, this shows that no (appropriate) theory $T$ proves its own soundness: there will be lots of sentences $\varphi$ such that $T\cup\{"T\vdash\varphi", "\neg\varphi"\}$ is consistent (although of course that expanded theory will prove its own inconsistency, but that's possible!).

  • $\begingroup$ Is my proposition not then, equivalent to this? That as part of our metatheory, we should have rules about suppositions, which state that we do not permit illogical suppositions, namely suppositions whose properties are self-contradictory irrespective of the system into which they are inserted. It seems to me that the modified liar is a statement which explicitly extends the axioms of any theory, and does so independently of the theory into which it is supposed. We might equivalently write the sentence 'the Godel number of this sentence exceeds itself in all theories.' $\endgroup$ – samerivertwice Mar 15 '17 at 3:19
  • $\begingroup$ @RobertFrost: No that does not work. You can only form statements in the meta-system in the language of the meta-system, and there it is simply meaningless (syntactically invalid) to say "unprovable" without also specifying in what system. And also the meta-system does not permit self-reference, so you cannot use the English word "this". $\endgroup$ – user21820 Mar 15 '17 at 5:56

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.