Difference of Godel's completeness and incompleteness theorem
Colin Richard Day
In article <6lvgo3$iei$1...@news.seed.net.tw>,
"Wang" <lsw...@tpts5.seed.net.tw> wrote:
>Hello:
> I am new to this group. Can anyone answer my question?
> I am studying the book "An Introduction to Mathematical Logic"
>by Hodel. The book explained first-order logic and Godel's completeness
>theorems, stating that for a set of formulas GAMMA in first-order language
>(1OL),
>GAMMA |- A iff A is true in every model of GAMMA.
> Then the book turned to the incompleteness theorem: every consistent
>axiomatized extension GAMMA of NN (formal numbers) is incomplete (
>there is a sentence in GAMMA that is neither provable nor refutable.)
> Here is my question: the language of NN is that, the rules of which
>are those of 1OL, and the axioms of which are the logic axioms of 1OL
>plus the closures of some other formulas in natural numbers. Since the
>extension is a consistent set of formulas of 1OL, according to the
>completeness theorem it should be complete.
> Can you explain where my thoughts went wrong? Thank you!
>
>
Are you sure that a consistent extension of a complete theory is complete?
Doesn't seem obvious.
Colin cd...@ix.netcom.com
Wang
ull...@math.okstate.edu
Very refreshing to have you ask for an explanation of where
you went wrong. Well, when you say "according to the completeness
theorem it should be complete" it's hard to say _where_ you are
going wrong exactly, but no, the completeness theorem simply
does not say that.
Take a simpler example: first order group theory. We have
first-order logic with equality, we add a special binary function
denoting the product of two elements of the group, we write the
product function as an operator * instead of a function, and
we add the exioms
Ax Ay Az ((xy)z = x(yz))
Ex Ay (xy = y & yx = y) //there exists an identity element x
Ax ((Ay xy = y & yx = y) -> Az Ew(zw = x & wz = x))
//every element z has an inverse y; the first bit just says x is the identity.
Now the theorems of first-order group theory are the statements you
can prove from these axioms. A group is a model of group theory.
The soundness and completeness theorems say that a statment
can be proved if and only if it is true in every group:
This says the proof system is sound (everything provable is
actually true in every group) and the proof system is
"complete" in the sense that everything true in every group
is actually provable from the axioms. The proof system is
"complete" in that every that _should_ be provable actually
_is_ provable.
This simply does not say that first-order group theory
is complete in the sense of the incompleteness theorem - it
does not say that every sentence is either provable or disprovable!
The sentence
Ax Ay (xy = yx)
is not provable (it cannot be provable since there exist
non-abelian groups) and it is also not disprovable (it
cannot be proved false because there exist abelian
groups.) So first-order group theory is "incomplete",
because there are statments that cannot be proved
or disproved. But the proof system is conplete:
everything that _is_ true in every group is provable.
David C. Ullrich
-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/ Now offering spam-free web-based newsreading
Wang
> This says the proof system is sound (everything provable is
>actually true in every group) and the proof system is
>"complete" in the sense that everything true in every group
>is actually provable from the axioms. The proof system is
>"complete" in that every that _should_ be provable actually
>_is_ provable.
(Some paragraph is cut)
> This simply does not say that first-order group theory
>is complete in the sense of the incompleteness theorem - it
>does not say that every sentence is either provable or disprovable!
>The sentence
>
>Ax Ay (xy = yx)
>
>is not provable (it cannot be provable since there exist
>non-abelian groups) and it is also not disprovable (it
>cannot be proved false because there exist abelian
>groups.) So first-order group theory is "incomplete",
>because there are statments that cannot be proved
>or disproved. But the proof system is conplete:
>everything that _is_ true in every group is provable.
Thank you for your explanation. There is still one thing I don't
understand. Is the difference of completeness and incompleteness
theorem whether the sentence under consideration is true for
every model, or the sentence is not true (true in some models, while
not true in some other models.) The book by Hodel says there
is a sentence that is "neither provable nor refutable". But I
remember that I have read "there is a sentence that is true
but not provable" somewhere in another book.
A sentence (by definition) is true when it's true in every model.
If it is true in only some models, isn't it 'neither true nor false'?
KRamsay
>A sentence (by definition) is true when it's true in every model.
Oh, no. It's true when it's true in a model which you have already
specified, explicitly or implicitly. For instance, we say an statement
in first-order arithmetic is "true" when it is true for N={0,1,2,...}.
>If it is true in only some models, isn't it 'neither true nor false'?
No. This is confusing truth with validity. Valid is true in all models,
true is just true.
Goedel's completeness theorem tells us that if we have a set of axioms
A, and we have a sentence X which is true in all models of A, then
there is a proof (in first-order logic) of X from some of the axioms
of A. Or to put it another way, that if there is no proof of X from A,
then there exists a model M in which all the axioms of A are true, but
X is false.
Goedel's incompleteness theorem implies that if we have a recursively
enumerable set of axioms A which hold true for N, then there are
statements Y which are true (for N) but which cannot be proven from
the axioms A.
Combining the two theorems, we see that there must be a model M in
which the axioms A are true, but Y is false _in M_, in spite of the
fact that Y is true _in N_. This is reasonable, since M is not the
same as N. The model M is some kind of cousin of N, which is enough
like N that it satisfies all the axioms in A (and consequently
satisfies all the first-order theorems provable from A), but which is
not the nonnegative integers N. It will typically contain N, but have
extra stuff in it, elements which are not integers.
We still say Y is true, because unless we specify otherwise, a
statement in first-order number theory is about the "intended" model,
N, of integers. Just because we can cook up a strange model
in which it is false, but a bunch of first-order axioms A are true,
doesn't make it less true. It shows that you need something
besides first-order axioms to specify which model N is.
Keith Ramsay "Thou Shalt not hunt statistical significance with
kra...@aol.com a shotgun." --Michael Driscoll's 1st commandment
Pierre Asselin
"Wang" <lsw...@tpts5.seed.net.tw> writes:
>[How to reconcile the Goedel completeness and incompleteness theorems?]
The word "complete" is used with different meanings. In the
completeness theorem: "complete" means that all the valid sentences
are provable. In the incompleteness theorem: "complete" means that
every sentences is either provable, or refutable.
First-order arithmetic is "complete" in the first sense, because of
its underlying logic. It is not complete in the second sense.
--
--Pierre Asselin, Westminster, Colorado
l...@netcom.com
Pierre Asselin
"Wang" <lsw...@tpts5.seed.net.tw> writes:
>The book by Hodel says there
>is a sentence that is "neither provable nor refutable". But I
>remember that I have read "there is a sentence that is true
>but not provable" somewhere in another book.
Missing context. "True" means "true in the integers". Seen in this
light, the incompleteness theorem means that no first-order
formalization of arithmetic can capture all arithmetic truths.