A concrete example of Gödel's Incompleteness theorem

logic

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?

Solution 1:

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.

Solution 2:

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".