When Kurt Gödel completed his Ph.D. thesis in 1929 he showed that first-order predicate calculus is complete. This was one of three major contributions he made to his field, the other two were his first and second incompleteness theorems. These were not by any means trivial, his incompleteness theorems which he publicly announced in 1931 sent tremors across the scientific community, David Hilbert, Ludwig Wittgenstein, and John von Neumann's views on the foundations of mathematics were completely undermined.
The reason is that the incompleteness theorems aren't just logical or mathematical, they have meta-mathematical implications as well. If our system of arithmetic cannot be both consistent and complete, (the first incompleteness theorem) then there are mathematical truths that cannot be proven in any consistent mathematical system. This suggests, there are some mathematical propositions whose truth value are independent of any human thought, language, or mental states. This can be taken as lending support for a position in the foundations of mathematics known as "mathematical platonism" because it entails a semantic realism about mathematical language.
A semantic realist is someone who believes that mathematical statements are true independently of whether or not anyone believes in them. An object realist is someone who holds that at least some objects or universals have an abstract, mind-independent existence. Although it would be more correct to say Godel’s theorems disprove classic nominalism (the main alternative to platonism).
I'll try and go over some of the philosophical arguments for platonism in more detail in a future post. I'm also planning to go over Godel's interpretation of the second incompleteness theorem and an argument for object realism. Here I'm going to derive the first (this proof is much-simplified) and in particular, I defend the "independence" thesis of platonism. Normally arguments for independence appeal to the necessity of mathematics or the fact that it's counterfactual but I think a good argument can be made based on Gödel’s theorem, too.
Definition One: a formal system
A formal system is based on axioms, without any basic or intuitive assumptions fed into that system. It has its own rules of inference and it’s theorems but lacks any meaningful symbols. There are no functions, or numbers, there are only meaningless signs which are defined by their relation to each other. The syntax of predicate logic is a pretty good example of a formal system.
"Intuition can get no dangerous foothold in a formal system" as one philosopher put it. A formal system doesn't include any statements about numbers, sets, or geometry. It has a lexicon of individual variables, logical connectives like conjunction, disjunction, negation, 'if ... then' and iff. As well as rules for combining its syntax into well-formed formulas (wffs).
Theorem One: There are provably unprovable but nevertheless true propositions in any formal system, complex enough to contain elementary arithmetic, assuming that formal system is consistent.
Consider these two statements:
Statement (G): this very statement is not provable within the system.
Statement (g): The statement (G) is provable within the system
If G were provable, then its negation would be true. However, if $\sim G$ is true, then g is false, yet at the same time if G is provable then it's true. This is the liar's paradox. So if we assume the consistency of the system and G is provable, then it's both true and false. Which means G can't be provable.
That's not quite all, proposition G states that it "is not provable", therefore G is true. It's both unprovable and true.
An expression in the formal system involving some variable x.
Definition Three: Provability of x, Pr(x)
For any natural number n, if $n = GN\left ( p \right )$ for a theorem p of the system then we say that n satisfies the property $Pr\left ( x \right )$, that is to say, that $Pr\left ( n \right )$ is true. Some number will only have the arithmetic property Pr if it is provable within the system.
Definition Four: Diagonal lemma
For any propositional function $F\left ( x \right )$ of one variable, there exists a number n such that the Godel number of $F\left ( n \right )$, turns out to be n itself.
On the left n denotes a normal, natural number. On the right, it represents an expression in the formal system, that represents n something like s(s(s( . . . s(s(0))))).
According to the diagonal lemma, there is some number, such that
Now let's say that:
Theorem One: There are provably unprovable but nevertheless true propositions in any formal system, complex enough to contain elementary arithmetic, assuming that formal system is consistent.
Consider these two statements:
Statement (G): this very statement is not provable within the system.
Statement (g): The statement (G) is provable within the system
If G were provable, then its negation would be true. However, if $\sim G$ is true, then g is false, yet at the same time if G is provable then it's true. This is the liar's paradox. So if we assume the consistency of the system and G is provable, then it's both true and false. Which means G can't be provable.
That's not quite all, proposition G states that it "is not provable", therefore G is true. It's both unprovable and true.
So if our a formal system S is consistent, then it's possible to construct some proposition, call it G, in that system that is both true and unprovable. But if S is consistent then G is provable, since it follows from the consistency of the formal system S, that G is true. Through a novel technique introduced by Kurt Godel, known as "Godel numbering", this proof can be carried out in arithmetic. But this sounds like a contradiction. So it must also follow from the above that the following statement is also true. It is impossible to prove formally, the consistency of arithmetic within that system of arithmetic. This is a statement of Godel’s second incompleteness theorem.
Godel numbering works by assigning each primitive symbol in the alphabet of our formal system, a number. Then one assigns a number to each well-formed formula (wff), based on the numbers of its constituent component parts. Then once this is complete, you assign numbers to sequences of wffs based on some rule.
The set of rules which tell us how to proceed, and how to obtain a unique Godel number, ensure that the same Godel number is not assigned to different wffs or sequences of wffs (proofs).
We now express a rule for assigning Godel numbers to wffs, lets say that:
So consider this following statement:
We want to be able to extract the original proposition from our Godel number, so we need some signal for when one proposition ends and another begins. We'll use zero to play this function.
Through Godel's numbering technique, we can express all the propositions of our formal system as purely arithmetical relations between Godel numbers. So that the Godel numbers of a proof will bear some relation to each other, for example, if one wff is logically entailed from another wff, the Godel number of the derivative is a factor of the Godel number of the original proposition.
Definition Two: Function of x, F(x)Godel numbering works by assigning each primitive symbol in the alphabet of our formal system, a number. Then one assigns a number to each well-formed formula (wff), based on the numbers of its constituent component parts. Then once this is complete, you assign numbers to sequences of wffs based on some rule.
The set of rules which tell us how to proceed, and how to obtain a unique Godel number, ensure that the same Godel number is not assigned to different wffs or sequences of wffs (proofs).
We now express a rule for assigning Godel numbers to wffs, lets say that:
$\left ( \forall x \right )\left ( \forall y \right )\left ( s\left ( x \right ) = s\left ( y \right )\right )\supset \left ( x= y \right )$
This statement reads, for all x, for all y, if the successor of x is the same as the successor of y, then x is identical to y. Lets call this $P\left ( 1 \right )$ and assign a Godel number to it.
$GN\left ( P1 \right ) = 6149761497626975269771569597$
We want to be able to extract the original proposition from our Godel number, so we need some signal for when one proposition ends and another begins. We'll use zero to play this function.
$s\left ( 0 \right )=s\left ( 0 \right )$
An expression in the formal system involving some variable x.
Definition Three: Provability of x, Pr(x)
For any natural number n, if $n = GN\left ( p \right )$ for a theorem p of the system then we say that n satisfies the property $Pr\left ( x \right )$, that is to say, that $Pr\left ( n \right )$ is true. Some number will only have the arithmetic property Pr if it is provable within the system.
Definition Four: Diagonal lemma
For any propositional function $F\left ( x \right )$ of one variable, there exists a number n such that the Godel number of $F\left ( n \right )$, turns out to be n itself.
$n = GN\left ( F\left ( n \right ) \right )$
According to the diagonal lemma, there is some number, such that
$g = GN\left ( \sim Pr\left ( g \right ) \right )$
$G= \sim Pr\left ( g \right )$
$ GN\left ( G \right ) = g $
$\sim Pr\left ( GN\left ( p \right ) \right )$
If and only if p is not provable. By letting $p = G$ and using the fact that $GN\left ( G \right )= g$ we get:
$\sim Pr\left ( g \right )$
If and only if G is not provable. What this statement says is "G if and only if G is not provable". G is an arithmetical statement but it's also simultaneously talking about itself ... and there we have it. A much-simplified version of Godel's first incompleteness theorem.
The key insight here is that if "truth" cannot be reduced to "proof", (a distinction which is trivial on platonism and nonsensical of human dependent theories of mathematical truth or meaning), then any philosophical theory that cannot maintain that difference (e.g., paraphrase nominalism, psychologism, constructivism, etc) is false. In the next part of this series, we’ll cover the Frege and Quine arguments for the "existence" clause of platonism.
Comments
Post a Comment