I want a simple example of Gödel's incompleteness theorems as it applies to Mathematics. I am looking for an example not a proof. If possible a simple example that involves little Mathematical knowledge as possible so that I can understand it. I would also very much appreciate a reference that explains the theorems based on elementary Mathematics as well if you know one. Thanks.


closed as too broad by Lord Shark the Unknown, spaceisdarkgreen, Henrik, Hans Lundmark, user 170039 Aug 18 '18 at 13:32

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 4
    $\begingroup$ It's not clear as to what you're asking. Are you trying to understand the incompleteness theorem? Are you looking for an incomplete theorem, whose incompleteness is proved via Gödel's theorem? Are you looking for some other interesting consequence of Gödel's theorems? What is your mathematical knowledge? $\endgroup$ – Asaf Karagila Aug 18 '18 at 7:40
  • 1
    $\begingroup$ A nice and self-contained exposition on Gödel's theorems can be found in the book Logic and Structure by Dirk Van Dalen (springer.com/book/9781447145578#otherversion=9781447145585). I am not sure whether it is possible to give a correct exposition of Gödel's theorems based on "elementary Mathematics" (whatever this means). $\endgroup$ – Emanuele Bottazzi Aug 18 '18 at 7:58
  • 1
    $\begingroup$ Goodstein's theorem is a nice example for the incompleteness theorem applying to PA, but it is not an "easy" example". An example applying also to ZFC is Hilbert's tenth problem : There is a polynomial having no solution in integers , such that this cannot be proven within ZFC. I do not think that much easier examples exist. $\endgroup$ – Peter Aug 18 '18 at 8:20
  • 5
    $\begingroup$ Repeating unclear statements does not make them clearer. $\endgroup$ – Asaf Karagila Aug 18 '18 at 9:20
  • 1
    $\begingroup$ @user21820 thank you for providing this information. $\endgroup$ – NoChance Oct 2 '18 at 20:58

It is difficult to answer your question because it is not clear what precisely you are asking. I suspect this is because you are not sure either how to make the question more specific.

The thing is this: Gödel's theorems are rather precise technical statements. Perhaps your question is more about the incompleteness phenomenon in general, as manifested in mathematics, as opposed to the incompleteness theorems per se.

The first incompleteness theorem says that any theory that satisfies certain technical requirements is incomplete, meaning that there are sentences $\phi$ such that the theory does not prove either of $\phi$ and $\lnot\phi$.

Are you asking for examples of such theories? If so, Peano Arithmetic is the typical example, although the theorem applies to weaker theories, such as Primitive Recursive Arithmetic or even Robinson's $Q$. It also applies to stronger theories, such as ZFC, the standard system for set theory. Peano Arithmetic is a theory about natural numbers. Note that being stronger is more involved than simply being the theory of a structure larger than $\mathbb N$. For example, the first incompleteness theorem applies to the first-order theory of the integers, because being a natural number is definable there, so we can do Peano Arithmetic "in disguise" when arguing about integeres. On the other hand, the theorem does not apply to the theories of $\mathbb Q$, $\mathbb R$, or $\mathbb C$, in each case for different reasons.

The second incompleteness theorem strengthens the first. It says that under certain technical requirements on a theory $T$, the theory can formulate a statement that we can reasonable interpret as the claim that "$T$ is consistent", and this statement, typically denoted $\mathrm{Con}(T)$, is not provable in $T$.

Perhaps you are asking for examples of theories $T$ where $\mathrm{Con}(T)$ "shows up" in the course of normal mathematical practice? This actually happens rather frequently in set theory, to the extent that we regularly discuss what we call the consistency strength hierarchy and have a way of calibrating the "degree of inconsistency" of natural statements by comparing them with large cardinal axioms. This is a pretty, rather extensive and somewhat technical area, so I will just provide a link here.

Or maybe, given $T$ to which the incompleteness theorems apply, you are asking for examples of statements that $T$ cannot prove.

All these interpretations are natural guesses as to what you are after. Clarifying may help you get the examples you are looking for.

Let me give a brief list of statements that could work as some of these examples. The proof of the undecidability of Hilbert's tenth problem provides us with a template that, given a theory $T$ to which second incompleteness applies, gives us a polynomial $p_T$ in several variables with integer coefficients such that $p_T(\vec x)=0$ has solutions in the integers, but this is not provable in $T$. The template is quite explicit, so this gives you infinitely many examples of concrete number-theoretic questions that are undecidable in the sort of theories that constitute regular mathematical practice. The problem here is that these polynomials tend to be rather monstrous once written down, and it is difficult to imagine they will show up unless one is explicitly looking for them. On the other hand, this suggests the rather interesting possibility that there may be rather concrete polynomials in, say, 3 variables that are undecidable in ZFC or similar systems. See here, here, and here.

Harvey Friedman has a research program trying to identify natural statements that are undecidable. Looking through his page should provide many examples. A nice feature is that these examples are somewhat different in style from the ones one typically finds in discussions of incompleteness, as he has imposed the additional informal requirement that his statements should be as natural as possible.

There are many nice statements independent of Peano Arithmetic. Goodstein's theorem is a good example, or the fact that Hercules wins the Hercules-Hydra game. Paris and Harrington showed that a natural strengthening of Ramsey's theorem provides an example as well. Theirs was in fact the first "natural" example of independence recognized as such (Goodstein formulated his statement in the 40s, but the proof of its independence from Peano Arithmetic came later). Many questions here discuss these examples.

There are also many natural statements independent of ZFC set theory. The continuum hypothesis is the best-known one. Many of these statements appeared in the course of regular mathematical investigations, and their connections to set theory and independence only came later. A good example here is Kaplansky's problem on automatic continuity of homomorphisms between Banach algebras. Naturally, the consistency strength hierarchy and large cardinals show up in these examples as well.

  • 2
    $\begingroup$ ... that's a lot of text to write in response to someone whose idea of clarifying his question was to repeat his original unclear request verbatim. $\endgroup$ – Henning Makholm Aug 18 '18 at 13:59
  • 1
    $\begingroup$ @Henning I think they probably couldn't have clarified or focused the question because they may not have had the required technical knowledge and also may not have known how vast the field is. That said, I agree that responding differently to the request for clarification, even admitting that at the moment they didn't know how, may have gone better. $\endgroup$ – Andrés E. Caicedo Aug 18 '18 at 14:10
  • 1
    $\begingroup$ I can't thank you enough for taking the time to put together this brilliant explanation. This answer will help me research more on the subject as it opened many doors. Also, I want to thank you for your kind manners unlike some unnecessary hostile fellow members. I am totally new to these concepts, and I am an armature not a student, so I don't have formal education on the subject. Your effort is highly appreciated. Thanks again. $\endgroup$ – NoChance Aug 18 '18 at 18:30
  • 1
    $\begingroup$ @NoChance Glad I coud help! $\endgroup$ – Andrés E. Caicedo Aug 18 '18 at 18:33

Not the answer you're looking for? Browse other questions tagged or ask your own question.