Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Gödel's incompleteness theorem says "Any effectively generated theory capable of expressing elementary arithmetic cannot be both consistent and complete. In particular, for any consistent, effectively generated formal theory that proves certain basic arithmetic truths, there is an arithmetical statement that is true,[1] but not provable in the theory."

I liked the theorem, but had a hard time finding an example. Here, I am proposing an example for Gödel's theorem. Please tell me if it is correct or point out the flaws.

Consider an axiomatic system where all the regular axioms regarding real valued functions hold. In particular, this system is concerned with integrals. One additional constraint is that existence of any integral is 'provable' if the indefinite integral can be expressed in terms of elementary functions. Now, given the fact that the integral for error function converges i.e. existence is true, but can't be expressed in terms of elementary functions i.e. not provable, can I say that this is an example wherein a statement is known to be true, but not provable?

share|improve this question
    
What do you mean by an "additional constraint"? –  joriki Sep 9 '11 at 6:47
    
The 'additional constraint' implies an axiom here. –  Nikhil Bellarykar Sep 9 '11 at 6:50
1  
Does anyone know of a first order theory where this can be expressed? Any way, "provable" is not something that you can define. It means a sentence in the first order language of your theory follows from the axioms of the theory and logical axiom of first order logic. Assuming there is a first order theory that captures what you want to say above, an example of a sentence that may be provable or not is "Every integral can be expressed as elementary functions". –  William Sep 9 '11 at 6:56
    
Thanks for the correction, William. –  Nikhil Bellarykar Sep 9 '11 at 6:58
    
In regard to the question I asked in the above comment, I think you can formalize this in set theory or possibly second order arithmetic. Probably, you can not express this in any first order theory where the domain is intended to be the real numbers themselves. –  William Sep 9 '11 at 7:06

5 Answers 5

up vote 12 down vote accepted

Yes, your example does give an example of an incomplete system. This is because you took an intentionally weak axiom system but a strong semantics. Another way to get an example is just to take any semantics and throw away all the inference rules. Then nothing is provable.

The reason that the incompleteness theorems are more interesting than this is that they apply to every effective set of inference rules for arithmetic, no matter how strong we try to make the rules.


Here is how to make you question more precise. In general, a formal system consists of:

  • A formal language $L$ (set of sentences)

  • A set of inference rules (and axioms, which are a type of inference rule for this purpose)

  • A semantics, which provides a set of models, or at least a set of valuation functions from $L$ to $\{T,F\}$

Completeness of the system says that if a sentence is sent to $T$ by every valuation function in the semantics, then that sentence is provable from the inference rules.

In the incompleteness theorem, when it says "true", it means "true in a particular, distinguished, standard model". It doesn't mean "true in every model" because every first-order theory is complete in that sense, with its usual inference rules and semantics.

In your framework, you could take $L$ to be the language of ZFC enhanced with an extra unary predicate $I$. For the inference rules, you take the axioms of ZFC, an axiom that says $I$ can only hold of a function $\mathbb{R}\to\mathbb{R}$, axioms that let you prove that every elementary function is integrable, and the usual inference rules for first-order logic. For the distinguished model (valuation function) you take the standard model of ZFC and make $I$ hold of all integrable functions.

In that set-up, there are many functions $f$ for which $I(f)$ is true, and such that you can express $I(f)$ in the language at hand, but where your inference rules can't prove that $I(f)$ holds. For example, $\sin(x)$ is definable in ZFC, so you could let $f = \sin(x)$. You just have to be able to express $I(f)$ without $f$ in the language of ZFC with the extra symbol $I$.

The next problem is that you might wonder about making the inference rules stronger, in an attempt to prove more functions are integrable. In the context of set theory, this will lead you to some more interesting things, like the distinction between extensional and intensional definitions.

share|improve this answer
    
Thanks for the clear elucidation, Carl. Really cleared up things. –  Nikhil Bellarykar Sep 9 '11 at 11:53

You are confusing syntax and semantics.

The axiomatic system you're outlining has some predicate $I$ whose "meaning" is being integrable. Your derivation rules for $I$ only allow proving $I(f)$ when $\int f$ is elementary. So syntactically, $I(f)$ rather expresses the property of having an elementary antiderivative. While your intended semantics is different, semantics is not part of the formal system proper. A good axiomatization of a particular subject will have the property that its theory corresponds to the required semantics. Your axiomatization, for example, is bad in that account - if you were intending to axiomatize integrability.

Incompleteness is a different phenomenon. Some (very simple) axiom system have the property that each statement either follows from them or its negation does. An example is the propositional calculus - every quantifier-free formula is either true or false. Gödel showed that Peano arithmetic and its supersets are not complete (as long as they're consistent). This is like the situation with groups mentioned in the comments - the axioms of group do not determine commutativity. In the same way, the axioms of PA don't force the ontology to be the natural numbers - you could have an "infinite" number for example. If you find this interesting, look up "non-standard arithmetic".

share|improve this answer
    
Interesting food for thought, thanks Yuwal! I will certainly look at nonstandard arithmetic. –  Nikhil Bellarykar Sep 9 '11 at 11:51

You may want to take a look at continues logic (e.g. check papers on Ben Yaacov's website).

The idea is that a non-classical logic can better capture analytical structures while avoiding some problems of classical first-order logic.

share|improve this answer
    
thanks for the suggestion, Kaveh. –  Nikhil Bellarykar Sep 12 '11 at 5:51

The “laid-back” version of Godel’s Theorem is, “Every non-trivial system is either inconsistent or incomplete.”

A real-world example of this “laid-back” version is page numbering of a document. Where are you going to put the page numbers – at the top, or at the bottom of the page? If there is only one page in the document, then the document is trivial (from a pagination standpoint of course – I realize that many great items of literature would fit on one page!). If the document is more than one page, however, then any complete pagination will be inconsistent. Since the pagination is complete, that means that the first page, which is the title page, must also have a page number. However, you cannot put the page number at the top without being inconsistent, because no one puts the page number at the top of the first page (for obvious aesthetic reasons). Therefore, the page number must go at the end of the page. Therefore, the page number of the last page must also go at the end of the page. However, a document is not complete unless it includes a message, or delimiter, indicating to the reader that the end of the document has been reached. However, the page number, for consistent pagination, must follow this message/delimiter (since it is the last thing on every other page). But then the message/delimiter is not telling the truth (i.e., is inconsistent), because part of the document (namely, the page number of the last page) is yet to come.

share|improve this answer
    
A cool example from a different angle indeed. –  Nikhil Bellarykar Jan 5 '12 at 11:46
4  
This has very little to do with Gödel's theorem. –  Dan Petersen Jan 5 '12 at 11:50

Another example of the principle that every non-trivial system is either inconsistent or incomplete is that of specifying a line (in plane analytic geometry).

Before we consider this example, however, it should first be noted that the pair existence/uniqueness is synonymous, in a respective manner, with the pair completeness/consistency, and is sometimes more appropriate linguistically/conceptually. That is true in the present example, and so we will speak of “existence” and “uniqueness” instead of “completeness” and “consistency”, respectively. Thus, a synonymous wording of the principle is that every non-trivial system comes up short in regard to existence or uniqueness.

Although there are a number of ways of specifying a line, they all boil down to two ways: the slope-intercept form and the general form. The slope-intercept form (y = mx + c) is unique, but comes up short in regard to existence, in that it does not give us vertical lines. On the other hand, the general form (ax + by + c = 0) gives us all lines, and therefore gives us existence, but comes up short in regard to uniqueness, in that multiplying it through by any non-zero constant, other than unity, results in an equation apparently different from the original, but which, in fact, specifies exactly the same line. For example, the line specified by the general equation 3x – 2y + 9 = 0 is exactly the same line as specified by the general equation -6x + 4y -18 = 0 (having multiplied the original equation through by -2).

share|improve this answer
    
-1: As with your other ‘example’, this is not an instance of Gödel's incompleteness theorem. –  Zhen Lin Jan 7 '12 at 3:10
    
@Zhen Lin: You're picking up the wrong end of the stick. Godel's Theorem is an instance of this general principle. –  Hexagon Tiling Jan 7 '12 at 10:53
1  
The question asks for an example of GIT, not some general principle of which GIT is supposedly an instance –  user16299 Jan 8 '12 at 8:18

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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