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?
Best Answer
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.