4
$\begingroup$

Could someone show me a simple example of something being proved unprovable?

Pretty much what the title says, I want to understand a proof of some statement being proved unprovable.

E: Please read properly the question before marking as duplicates, I'm asking for a proof of a statement being proved unprovable, not examples of unprovable/indecidable statements.

|cite|improve this question
$\endgroup$
  • 6
    $\begingroup$ The sentence $\forall x\forall y(xy=yx)$ is neither provable nor refutable from the axioms of Group Theory. Proof: There are groups that are Abelian, and groups that are not. $\endgroup$ – André Nicolas Sep 18 '15 at 21:41
  • 1
    $\begingroup$ I don't understand how that's irrefutable, isn't it enough to provide a counter-example? $\endgroup$ – YoTengoUnLCD Sep 18 '15 at 21:44
  • 1
    $\begingroup$ @YoTengoUnLCD: A refutation would be a proof that it is false from the axioms of group theory. In a very broad sense, the Continuum Hypothesis has the same nature with respect to ZFC. For ZFC has models in which it is true and models in which it is false. But Group Theory by design is incomplete, while the axioms of ZFC, or first order Peano Arithmetic are designed to be strong. $\endgroup$ – André Nicolas Sep 18 '15 at 21:50
  • 1
    $\begingroup$ In Douglas Hofstader's "Gödel, Escher, Bach" Godel numbering is used to create self referential propositions - he demonstrates incompleteness by forming the mathematical equivalent of "This statement is false" $\endgroup$ – WW1 Sep 18 '15 at 21:56
  • 1
    $\begingroup$ math.stackexchange.com/questions/1052299/… $\endgroup$ – Asaf Karagila♦ Sep 18 '15 at 21:57
3
$\begingroup$

If you are willing to take the completeness theorem for granted, then it can be quite easy.

If $T$ is a first-order theory, then $T\vdash\varphi$ if and only if $T\models\varphi$.

This means that in order to prove that $\varphi$ is unprovable from $T$, then we only need to exhibit a model of $T$ in which $\varphi$ is false.

For example, we can prove that as a field $\Bbb R\models\exists x(x\cdot x=1+1)$, but the Greek also proved that $\sqrt2$ is not a ratio of two integers, therefore $\Bbb Q\models\lnot(\exists x(x\cdot x=1+1))$. And so we proved that the theory of fields does not prove the existence of $\sqrt2$.

Andre suggested in the comments a similar example with group theory and the statement "multiplication is commutative".

Other even easier examples may include things like a language $\cal L$ with a single constant symbol $c$, and the empty theory. Then $\forall x(x=c)$ is not provable, since in any structure for $\cal L$ with more than one element $\exists x(x\neq c)$ is a true statement.

Or even without constants, just look at $\forall x\forall y(x=y)$.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ All you need here is soundness, not completeness: no sound theory of fields can prove $\exists x\cdot x^2 = 2$. That aside, I think this is very much the right answer to the OP's question. $\endgroup$ – Rob Arthan Sep 19 '15 at 0:47
  • $\begingroup$ You mean, once that you know that $\sqrt2$ is irrational? $\endgroup$ – Asaf Karagila♦ Sep 19 '15 at 0:54
  • $\begingroup$ No, I mean that there are fields in which $\exists x\cdot x^2 = 2$ is false, so no sound theory of fields can include that sentence. $\endgroup$ – Rob Arthan Sep 19 '15 at 0:56
  • 1
    $\begingroup$ My point was that your answer shouldn't mention completeness. It's just about soundness: (i) the first-order theory of fields is sound for fields; (ii) there are fields in which $\exists x\cdot x^2 = 2$ is false; hence (iii) $\exists x\cdot x^2 = 2$ is provably unprovable in the theory of fields. Maybe we can mop this up another day. Cheers. $\endgroup$ – Rob Arthan Sep 19 '15 at 1:35
  • 2
    $\begingroup$ Rob's right. You only need soundness, which is that provability over $T$ implies truth in all models of $T$. So your sentence cannot be provable over $T$ because it is not true in some model of $T$. And also your sentence is not disprovable since it is true in some model of $T$ and hence its negation cannot be proven, again by soundness. I am sure you know all this very well so you must have misinterpreted Rob's comment. =) $\endgroup$ – user21820 Sep 19 '15 at 7:16
0
$\begingroup$

Consider statement, $P$:
"It is impossible to prove statement $P$."

Suppose it's true. Then, as per $P$, it's impossible to prove statement $P$, even though it's true.

Suppose it's false. Then, as per $P$, it's possible to prove statement $P$, even though it's false.

Asserting either the truth or the falsehood of the statement leads to a contradiction.

The statement appears to be impossible to prove. (Although, perhaps we shouldn't come right out and say it.)

|cite|improve this answer
$\endgroup$
  • 4
    $\begingroup$ You can have a statement which talks "about itself", but it's not at all simple to do so. In general $P$ is not part of the language, but rather a sentence in the language. And in order to talk about statements you need things like Godel numbering and so on. So some nontrivial amount of information needs to be established first. $\endgroup$ – Asaf Karagila♦ Sep 19 '15 at 0:10
  • $\begingroup$ Indeed. The OP is looking for a simple example. I don't know if this is too simple for their needs. Your response is at least mathematical, which may meet the OP requirement. $\endgroup$ – Adam Hrankowski Sep 19 '15 at 0:14
  • 2
    $\begingroup$ My point is that your example is either wrong, or misleading when you dress it as "simple". $\endgroup$ – Asaf Karagila♦ Sep 19 '15 at 0:21
  • $\begingroup$ Hmm... I'll have to consider that $\endgroup$ – Adam Hrankowski Sep 19 '15 at 0:25

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.