1
$\begingroup$

So I have to give a talk on Godel's Incompleteness Theorem in which I have to give a brief proof of Godel's Incompleteness Theorem in a non-techincal simple English way. The problem is I am not really too sure on how to take such a technical concept and make it non-technical while keeping the essence of the proof.

This is how I am stating the theorem:

Each computably axiomatizable L-theory extending Peano Axioms is incomplete.

Any help will be appreciated. (If you want me to provide any more info, like the technical proof I have let me know)

$\endgroup$
7
  • 2
    $\begingroup$ See Gödel's Incompleteness Theorems. $\endgroup$ Commented Mar 27, 2017 at 21:06
  • 1
    $\begingroup$ Do you state, explicitly, what incomplete means? In particular, do you state it before or during your statement of the theorem. The statement of the theorem would be, pardon me because I can't help myself, incomplete without this. $\endgroup$ Commented Mar 27, 2017 at 21:15
  • 1
    $\begingroup$ But in English can't we explain this as having to do with whether or not we can prove or disprove certain statements? Perhaps you could speak about it along these lines? $\endgroup$ Commented Mar 27, 2017 at 21:25
  • 1
    $\begingroup$ Ok I see what you mean there. I can explain that something is incomplete if we cannot prove or disprove a statement. $\endgroup$ Commented Mar 27, 2017 at 21:38
  • 1
    $\begingroup$ For my two penn'orth, the key ingredients in a beermat presentation of the incompleteness theorem are (1) the arithmetization of syntax (which makes mathematical reasoning about logical deduction possible) and (2) the diagonalization lemma (which says that given any property, $P(x)$ of numbers $x$, there is a sentence $D$ that says (when understood using arithmetized syntax) that "I, $D$, am equivalent to $P(D)$, i.e., $P(me)$"). So with a suitable choice for $P(x)$ (1) and (2) give you a sentence that is equivalent to its own unprovability. $\endgroup$ Commented Mar 27, 2017 at 21:40

1 Answer 1

Reset to default
2
$\begingroup$

For a non-technical talk, I would stick to this:

"There is no complete axiomatization of arithmetic"

That is, there is no finite set of axioms for arithmetic such that arithmetical truths can be derived from them.

(Godel showed there is no such recursive set, but for simplicity sake I would just stick to finite)

And for a proof sketch:

Assume you have a finite and sound (meaning that only arithmetical truths can be derived from it) set of axioms $A$ that is 'at least as strong as the Peano axioms'.

Then, show the basic idea of arithmetization, i.e. a way of assigning numbers to logical symbols, expressions, and derivations, so that statements about arithmetic can be treated as statements about logical statements and proofs. Just show some very basic examples of how such a coding scheme could work, and then just wave your hands and say that we can create a formula that effectively says 'the statement with Godel number $x$ is not provable from A', where the fact that we can have such a formula depends on $A$ being 'at least as strong as PA' and being finite.

Next (and again without any further proof) mention the Diagonal Lemma through which Godel established that for every formula there is a sentence that is true if and only if that formula is true for the godel number of that sentence. Thus, in particular, there will be a Sentence G (the Godel sentence) that ends up saying "I am not provable from A"

And now do the grand finale! If $G$ is false, then G is provable from $A$, but given that $A$ is sound, that means $G$ is true. Ok, so G cannot be false, so it is true. And so $G$ is indeed not provable from $A$. So, there is something that is true, but not provable from $A$, and thus $A$ is not complete.

Finally, you should probably mention that this works for any finite $A$. Thus, if someone says "So why don't we just add $G$ to $A$", then you say "Well, that means we have axiom set $A'$, and $A'$ has its own Godel sentence $G'$ that is true but cannot be proven from $A'$.

$\endgroup$
3
  • $\begingroup$ @TillermansTea You're welcome! Another thought: the relevance of the Peano Axioms for the proof of Godel's incompleteness theorem is rather technical, and again too technical for a lay audience. So instead, I would bring up the Peano Axioms just to demonstrate the very idea of axiomatization. So maybe you could do a quick example how a very basic theorem (like $\forall x (s(x) * s(0) = x) can be derived from the axioms, and then say: "Cool! so we can prove various arithmetical theorems from these axioms ... are there any theorem that cannot be derived? (i.e. is this a complete set of axioms?) $\endgroup$ Commented Mar 28, 2017 at 17:34
  • $\begingroup$ @TillermansTea And then you of course bring up Godel's Incompleteness theorem, which shows the answer is: No!! And not only are the Peano Axioms not complete ... but there is no finite and complete set of axioms at all! $\endgroup$ Commented Mar 28, 2017 at 17:36
  • $\begingroup$ This answer basically refers to the "simplified proof sketch" that appeared in the first section of Godel's paper. It uses soundness (which is a more stringent requirement) rather than consistency. I think this is an excellent choice for somebody who has to present a (relatively) non-technical explanation of Godel's result. $\endgroup$ Commented Mar 25 at 15:05

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.