Three Theorems of Godel
Helene....@wanadoo.fr
the First and Second Incompleteness Theorems - assume so little that
they are reasonably indisputable. A version of the Completeness
Theorem, for instance, can be proven in RCA0, which is the weakest
system studied extensively in Simpson's encyclopaedic "Subsystems of
Second Order Arithmetic". And it often seems that the minimum
requirements for a system just to express the Incompleteness Theorems
are sufficient to prove them. However, it will be shown that a
particular sub-system of Peano Arithmetic is powerful enough to express
assertions about syntax, provability, consistency, and models, while
being too weak to allow the standard proofs of the theorems to go
through. An alternative proof is available for the First
Incompleteness Theorem, but is of such a different nature that the
import of the theorem changes. And there are no alternative proofs
for (certainly) the Completeness and (apparently) the Second
Incompleteness Theorems. It is therefore perfectly rational for
someone to be skeptical about Godel's results.
Jesse F. Hughes
Let's see if I follow you.
Godel has three major theorems.
One of them has an alternative proof very different than the one Godel
gives.
The other two have no alternative proofs. (?)
*Therefore* it is rational to be skeptical regarding these three
theorems.
Let's ignore that very odd claim that there are no alternative proofs
of completeness and the second incompleteness theorems. How does that
"therefore" work?
--
"Looking at their behavior I see them endangering not only their own
futures, but that of their families, and now, considering my latest
result, the future of people all over the world." -- James S. Harris,
on the shortsightedness of his mathematical critics
zzbunker
"Jesse F. Hughes" <je...@phiwumbda.org> wrote in message
news:874q6kc...@phiwumbda.org...
> Helene....@wanadoo.fr writes:
>
>> It might seem that three of Godel's results - the Completeness and
>> the First and Second Incompleteness Theorems - assume so little that
>> they are reasonably indisputable. A version of the Completeness
>> Theorem, for instance, can be proven in RCA0, which is the weakest
>> system studied extensively in Simpson's encyclopaedic "Subsystems of
>> Second Order Arithmetic". And it often seems that the minimum
>> requirements for a system just to express the Incompleteness Theorems
>> are sufficient to prove them. However, it will be shown that a
>> particular sub-system of Peano Arithmetic is powerful enough to express
>> assertions about syntax, provability, consistency, and models, while
>> being too weak to allow the standard proofs of the theorems to go
>> through. An alternative proof is available for the First
>> Incompleteness Theorem, but is of such a different nature that the
>> import of the theorem changes. And there are no alternative proofs
>> for (certainly) the Completeness and (apparently) the Second
>> Incompleteness Theorems. It is therefore perfectly rational for
>> someone to be skeptical about Godel's results.
>
> Let's see if I follow you.
>
> Godel has three major theorems.
>
> One of them has an alternative proof very different than the one Godel
> gives.
Goedel actually only has one theorem as Von Neumann showed.
The theorem is called Omega-Consistency.
His proves are so obvious from the assumptions,
that he had to call Hilbert to tell him that this
ain't gonna work since Cantor already proved the theorems.
And so mathematicians should from hence forth be
be called Legrangian automatons, rather than
intelligence specimens of evolution.
Helene....@wanadoo.fr
Jesse F. Hughes wrote:
> Let's ignore that very odd claim that there are no alternative proofs
> of completeness and the second incompleteness theorems. How does that
> "therefore" work?
>
There cannot be an alternative proof for the Completeness Theorem (in
the framework of the sub-theory), that is, one can show the
Completeness Theorem is false in a model of the sub-theory.
There apparently cannot be an alternative proof of the Second
Incompleteness Theorem - sorry, can't do better than that assertion.
That's how the "therefore" works!
zzbunker
<Helene....@wanadoo.fr> wrote in message
news:1131657515....@g43g2000cwa.googlegroups.com...
There's not only alternate proofs of the incompletess theorems,
there's an uncountabably infinite nnumber of them that
don't contain moron Internet Descartes philosopers and scientioons
that don't contain exclaimation points.
Since the theorem depends only on Goedel numbering,
and idiots like Chomsky, not logic.
>
Torkel Franzen
> It is therefore perfectly rational for
> someone to be skeptical about Godel's results.
It is of course open to you to be skeptical about anything not
provable in this or that theory, but why single out Godel's results?
Helene....@wanadoo.fr
First, it is probably of more interest to most people. As you know
there is a kind of knee-jerk resistence by some to Godel's methods or
results, and this paper shows a concrete assumption which they can
reject and thereby reject Godel.
Secondly, the three theorems are probably some of the most elementary
results where the use of the Successor Axiom (SA), the assumption which
is left out in the sub-theory I am discussing, appears essential. That
is, SA may be necessary to prove a sentence S, but it is essential only
if it is not possible to reformulate S with an S' which *can* be
provable without SA.
For example, the assertion that there is an infinity of primes (call
this P) is equivalent to SA over the base theory, so SA is necessary
to prove P. However, it is possible to reformulate P in ways which
keep its spirit, e.g. "between (inclusive) any non-zero numbers n and
m, where m = n! + 1, there is a prime number" (call this P'). Then it
is possible to prove P' without SA.
The same is true of e.g. the Deduction Theorem. It's equivalent to SA
over the base theory, but it can be reformulated and proven without SA.
This option doesn't appear available to e.g. the Completeness Theorem.
There's no reformulation of the theorem which keeps its spirit and
which is provable without SA.
It is this essential use of SA which is worrisome.
Obviously, this kind of assertion depends on what what means by
"reformulate", but I think it can be made precise (although I will not
do it here!).
Torkel Franzen
> First, it is probably of more interest to most people. As you know
> there is a kind of knee-jerk resistence by some to Godel's methods or
> results, and this paper shows a concrete assumption which they can
> reject and thereby reject Godel.
I think those people will be disappointed when they find that your
criticism of Godel boils down to rejecting the successor axiom.
> Secondly, the three theorems are probably some of the most elementary
> results where the use of the Successor Axiom (SA), the assumption which
> is left out in the sub-theory I am discussing, appears essential.
In that case, surely a better showcase for your successorless theory
would be book or article entitled "Elementary number theory without the
successor axiom".
Ross A. Finlayson
Hi Torkel, Andrew,
It seems obvious: the French lack a sense of humor.
Did you hear about the dyslexic who sold his soul to Santa?
Andrew, if you say to discard Goedel, do you mean completeness _and_
incompleteness? I think instead you are saying completeness is
trivial.
Andrew, I wonder, are you Helene? Who is Helene? That's immaterial to
the discussion.
The notion of incompleteness is that there are theorems of objects in
the theory that are true but unprovable in the theory, eg in Peano
unresolvable number theory questions. While I certainly accept that
there are infinitely many specific number-theoretic statements that
have not been verified, the simple notion that all the true ones have
been with such minimal machinery makes it seem obvious that there is a
lot of strength, and if any true statement about the natural integers
as only natural integers will be provable in Peano, ie for any, then
for all. To have statements about anything else, the theory broadens.
I've heard Presburger called complete, and Peano incomplete, but a
finite proof in Peano is a finite proof in Presburger.
On page 9, you have "concatentation" instead of "concatenation". Ah,
deduction as an "Ad Infinitum" axiom for F, that is a very useful
notion, to give a maximal element. That makes a third-order theory? I
think everything is first-order.
That's a very excellent paper, thanks for explaining your notation and
usage.
The null axiom theory: it has no axioms.
Ross
Helene....@wanadoo.fr
Torkel Franzen wrote:
> Helene....@wanadoo.fr writes:
>
> > First, it is probably of more interest to most people. As you know
> > there is a kind of knee-jerk resistence by some to Godel's methods or
> > results, and this paper shows a concrete assumption which they can
> > reject and thereby reject Godel.
>
> I think those people will be disappointed when they find that your
> criticism of Godel boils down to rejecting the successor axiom.
Drats!
>
> > Secondly, the three theorems are probably some of the most elementary
> > results where the use of the Successor Axiom (SA), the assumption which
> > is left out in the sub-theory I am discussing, appears essential.
>
> In that case, surely a better showcase for your successorless theory
> would be book or article entitled "Elementary number theory without the
> successor axiom".
First, that's already done, only the articles are called "'True'
Arithmetic Can Prove Its Own Consistency"
(www.andrewboucher.com/papers/consistency.pdf) and "Proving Quadratic
Reciprocity" (www.andrewboucher.com/papers/quadratic_reciprocity.pdf).
Maybe you don't like the titles? Anyway, your title makes it sound
like the only interesting thing is what can be proven in the theory.
Of course, it is also interesting what cannot be, and indeed what
cannot be in an essential way. That's the gist of the present paper,
although again, perhaps you don't like the title !
Helene....@wanadoo.fr
Ross A. Finlayson wrote:
> Torkel Franzen wrote:
> > Helene....@wanadoo.fr writes:
> >
> > > It is therefore perfectly rational for
> > > someone to be skeptical about Godel's results.
> >
> > It is of course open to you to be skeptical about anything not
> > provable in this or that theory, but why single out Godel's results?
>
> Hi Torkel, Andrew,
>
> It seems obvious: the French lack a sense of humor.
The French have a different sense of humor. See Feydeau.
>
> Did you hear about the dyslexic who sold his soul to Santa?
No, what happened to him?
>
> Andrew, I wonder, are you Helene?
Sort of. That is, it's Andrew who is writing this.
>Who is Helene?
My wife!
>
> On page 9, you have "concatentation" instead of "concatenation".
Any and all proof-reading welcome. Thank you, I'll correct it
tonight...
> That's a very excellent paper, thanks for explaining your notation and
> usage.
Thank you!
Jesse F. Hughes
"zzbunker" <jimhu...@comcast.net> writes:
> <Helene....@wanadoo.fr> wrote in message
> news:1131657515....@g43g2000cwa.googlegroups.com...
>>
>> Jesse F. Hughes wrote:
>>
>>> Let's ignore that very odd claim that there are no alternative proofs
>>> of completeness and the second incompleteness theorems. How does that
>>> "therefore" work?
>>>
>>
>> There cannot be an alternative proof for the Completeness Theorem (in
>> the framework of the sub-theory), that is, one can show the
>> Completeness Theorem is false in a model of the sub-theory.
>>
>> There apparently cannot be an alternative proof of the Second
>> Incompleteness Theorem - sorry, can't do better than that assertion.
>>
>> That's how the "therefore" works!
That didn't answer the question.
Even supposing that this nonsense above shows that there are not
alternative proofs of the completeness and second incompleteness
theorems, why should that make us skeptical that Godel's theorems are
correct?
--
Jesse F. Hughes
"There's a thrill that's gone that I'll probably not have in quite the
same way again. After all, FLT was a unique animal, and we had a
great dance." -J.S. Harris on "proving" Fermat's last theorem
Torkel Franzen
> Maybe you don't like the titles? Anyway, your title makes it sound
> like the only interesting thing is what can be proven in the theory.
> Of course, it is also interesting what cannot be, and indeed what
> cannot be in an essential way.
For all I know, successorless arithmetic may attract the interest
of lots of people, but hardly that of Godel skeptics.
Torkel Franzen
> Even supposing that this nonsense above shows that there are not
> alternative proofs of the completeness and second incompleteness
> theorems, why should that make us skeptical that Godel's theorems are
> correct?
Because they are seen to depend on the highly dubious successor
axiom.
Ross A. Finlayson
C'est vrai? Mon Dieu, c'est incroyable.
The French and their spectacular humor is obviously well represented:
Jerry Lewis. I don't know if much more needs to be said about that.
(Cursory research notes that it has been some time since the height of
popularity of that zany Jerry Lewis in France.) French humor is a guy
shaking a bottle of Dubonnet on the audience, like sophisticate
Gallagher, drunk. Maybe that's just drunk French humor. Gallagher was
basically a proto-Carrottop, except the Redneck guy, his motif was
splattering watermelons over the crowd, and Splatterhouse was an
unprecedentedly gory video game of the late 80's, fantasy horror.
Steve Martin, now that guy's actually funny, Ruprecht, jabbing himself
on the eyepatch with the corked fork, it's hard to compete with Robin
Williams on a good day, the guy's funny, Eddie Murphy. Happy Gilmore,
that had some funny moments, like Adam Sandler in a fistfight with Bob
Barker, the host of "The Price is Right." There was a time in America
when television was situation comedies, and Bill Cosby was the shiznit.
(Lisa Bonet, of the Cosby show, was in an explicit sex scene with
Mickey Rourke, that was the most explicit sexual thing in the general
R-rated movies there had ever been, about ten years before the
"In-ter-net", and was viciously scandalized.) In these mad-cap days
humor on television is rolling bums in thong bikinis in shopping carts
off skate ramps into tubs of slugs, there are eighty billion copies of
the same 725 jokes on the In-ter-net, and Lisa Bonet looks like a
non-debauched mild-mannered schoolgirl that doesn't get naked.
Kundera: "Then, every sentence had to resound in both English and
French, which made the discussion take twice as long, or rather more
than twice as long, since all the French had some English and kept
interrupting the interpreter to correct him, disputing every word."
Unfortunately, that gives me ideas about logic, roots and foundations
of mathematical logic.
Thanks for the clarification, I have thought in times past that Andrew
was a pseudonym, er, patropseudonym, pseudopatronym?
Levity aside, and the above is all quite irrelevant, there are quite a
few learned people who are accepting Goedel's incompleteness theorems
as fact, to reject them is somewhat of a countercultural expression,
counternomenclatural.
So, are you telling everybody that Goedel's wrong?
Ross
Rupert
Why not? They need to adopt a foundation for arithmetic in which the
theorems don't go through. They should be interested in the options
that are available to them. Andrew's foundation may or may not
philosophically appeal to them.
Helene....@wanadoo.fr
Ross A. Finlayson wrote:
>
> Levity aside, and the above is all quite irrelevant, there are quite a
> few learned people who are accepting Goedel's incompleteness theorems
> as fact, to reject them is somewhat of a countercultural expression,
> counternomenclatural.
>
> So, are you telling everybody that Goedel's wrong?
Godel (sorry, I'm incorrigible and I don't spell with the "e") isn't
wrong, in the sense that if one accepts his assumptions, then the
conclusion follows. But I think one of these assumptions is
unwarranted, and one should be skeptical about the conclusions (or, in
the case of the First Incompleteness Theorem, the self-referential
aspect).
Ross A. Finlayson
Honh honh honh!
Ha ha ha ha.
I interpret similar notions to hold that the only complete theory is
the null axiom theory, with ubiquitous ordinals and dually minimal and
maximal dually-self-intraconsistent dialethic paraconsistent
ur-element, thus dually universally axiomatized.
Then again, I think infinite sets are equivalent, as the universe is
infinite. In considering Cantor's powerset results, they're proof not
of uncompleteable iteration, instead conflation of the infinite and
void, thus in resolution that notion's irrelevancy, in the Liar's
irreverency, towards guiltless acceptance of truth.
That levity again aside, what benefits or options will your notion
allow that are not now? Are you saying PA is complete, that is to say,
are you saying that the axioms of PA are enough to prove all true
number theoretic statements about the natural integers, or just that
Goedel does not prove it incomplete?
I would spell Goedel Godel but I'm not very good with accents.
Ross
Torkel Franzen
> > For all I know, successorless arithmetic may attract the interest
> > of lots of people, but hardly that of Godel skeptics.
> Why not?
It's not their style.
Helene....@wanadoo.fr
Ross A. Finlayson wrote:
>
> That levity again aside, what benefits or options will your notion
> allow that are not now? Are you saying PA is complete, that is to say,
> are you saying that the axioms of PA are enough to prove all true
> number theoretic statements about the natural integers, or just that
> Goedel does not prove it incomplete?
>
Recall that I am skeptical about the Successor Axiom, and that the
negation of the Successor Axiom is that there is a maximum number (call
this number Max); also that Godel's proofs (for all three theorems) use
SA. In the case of the First Incompleteness Theorem, one can prove
that there is an undecidable sentence in the case (not SA), by
considering a simple very long true sentence whose length is almost
Max. Then there exists no proof of this sentence (any proof would have
to use a sentence which is longer than Max) and clearly no proof of the
negation.
The theorem goes through, but I would say the import changes. No
self-referential trick or appeal to undefinability of truth or etc.
The First Incompleteness Theorem holds because proofs take more
resources than the sentences which they are proving.
Ross A. Finlayson
Consider: are there not some proofs that are shorter than the
statements of their theorem? For example, "N contains 1, 2, 3, 4,
...", an infinitely long statement, is a theorem proven by, in your
notation, N0 and SA. So, sometimes the proofs are shorter than the
statements, and that is so about lots of statements about infinite sets
of integers in PA, the proofs are finite. The length of the sentence
there is basically max, and the length of the proof is basically zero.
Consider reversing that.
How can a statement be true without being provably true? If it's not
provable, it's negation is not provable, either. There is no more
justification that some putatively true but unprovable statement is not
the negation of some other true but unprovable statement than that it
is true or false. For it to be a true statement, it would have to be
expressible in terms of the objects of the (consistent) theory.
To be sure, that is not a widely accepted notion and many who think
that Goedel's incompleteness is a metatheoretical fact may find reason
to disagree with that.
Ross
Helene....@wanadoo.fr
Ross A. Finlayson wrote:
> Helene....@wanadoo.fr wrote:
> >
> > Recall that I am skeptical about the Successor Axiom, and that the
> > negation of the Successor Axiom is that there is a maximum number (call
> > this number Max); also that Godel's proofs (for all three theorems) use
> > SA. In the case of the First Incompleteness Theorem, one can prove
> > that there is an undecidable sentence in the case (not SA), by
> > considering a simple very long true sentence whose length is almost
> > Max. Then there exists no proof of this sentence (any proof would have
> > to use a sentence which is longer than Max) and clearly no proof of the
> > negation.
> >
> > The theorem goes through, but I would say the import changes. No
> > self-referential trick or appeal to undefinability of truth or etc.
> > The First Incompleteness Theorem holds because proofs take more
> > resources than the sentences which they are proving.
>
> Consider: are there not some proofs that are shorter than the
> statements of their theorem? For example, "N contains 1, 2, 3, 4,
> ...", an infinitely long statement, is a theorem proven by, in your
> notation, N0 and SA. So, sometimes the proofs are shorter than the
> statements, and that is so about lots of statements about infinite sets
> of integers in PA, the proofs are finite. The length of the sentence
> there is basically max, and the length of the proof is basically zero.
> Consider reversing that.
Proofs always end with the sentence they are proving, so they must
always use no fewer resources than the sentence (so okay, I should
strictly have said "no fewer" rather than "more", since there are, of
course, one-line proofs...)
If "N contains 1,2,3,4,..." is an infinitely long sentence, then it is
not statable in the theory which I discuss, and so it is not provable.
You might be thinking of some particular if not idiosyncratic theory of
your own and I am unable to say how my comments may apply to it.
>
> How can a statement be true without being provably true?
Consider a theory with no axioms; then it can't prove anything, but
surely there are truths in the world. So clearly you have have to
disassociate "true" from "provable." I am unsure what you mean by
"provably true," so I can't comment more.
Ross A. Finlayson
Quod erat demonstrandum?
Is N = {0, 1, 2, ...} the statement and N0, SA the axioms or N={0, 1,
2, ...} and N0, SA the statement?
That statement is also the statement that each subset of the naturals
contiguous in its normal ordering is a set.
First-order predicate logic, and the rules of inference are generally
not considered to be proper axioms. In theory, true means provable.
When you say it is reasonable to be skeptical of Goedel, what does that
mean?
Ross
Shmuel (Seymour J.) Metz
11/11/2005
at 10:23 PM, Helene....@wanadoo.fr said:
>Godel (sorry, I'm incorrigible and I don't spell with the "e")
_
Without an e it would be Godl or Gödl.
>unwarranted,
What do you mean by "unwarranted"? It's Mathematics, not Engineering
or Physics, so what matters is whether his work is consistent and
interesting. The fact that it has been debated here so often certainly
demonstrates that it is interesting.
--
Shmuel (Seymour J.) Metz, SysProg and JOAT <http://patriot.net/~shmuel>
Unsolicited bulk E-mail subject to legal action. I reserve the
right to publicly post or ridicule any abusive E-mail. Reply to
domain Patriot dot net user shmuel+news to contact me. Do not
reply to spam...@library.lspace.org
Helene....@wanadoo.fr
Ross A. Finlayson wrote:
>
> Is N = {0, 1, 2, ...} the statement and N0, SA the axioms or N={0, 1,
> 2, ...} and N0, SA the statement?
>
> That statement is also the statement that each subset of the naturals
> contiguous in its normal ordering is a set.
Each subset (sub*set*) of the naturals is clearly a set.
>
> When you say it is reasonable to be skeptical of Goedel, what does that
> mean?
It means one can rationally refuse to believe in the conclusions (in
the case of the First Incompleteness, this means the conclusion that
the self-referential-like G is undecidable, and not the less specific
"There *is* an undecidable sentence").
I don't know, but I have the feeling this conversation is advancing...
My apologies if the problem is on my side.
Helene....@wanadoo.fr
Helene.Bouc...@wanadoo.fr wrote:
>
> I don't know, but I have the feeling this conversation is advancing...
> My apologies if the problem is on my side.
That should have been:
I don't know, but I have the feeling this conversation is not
柑\/b
i mean this:"
I'm reading the Godel theory
if H is the set of all proposition of theory he seems to define a
function g: {proposition in Theory}-> N
where theory == set teory + N
consider {0,1}^N={f: f:{0,1}->N}
define x_i e.g.
x_0={(0,0), (1,0)}
1 proposition: x_0e{0,1}^N
x_1={(0,0), (1,1)}
2 proposition: x_1e{0,1}^N
x_3={(0,0), (1,2)}
3 proposition: x_3e{0,1}^N
the proposition x_ie{0,1}^N of each function in {0,1}^N can not hold
every possible function in {0,1}^N because seems |{0,1}^N|=|R|>|N|
So how build g:{proposition in Theory}-> N for these propositions?
Then I think every axioms like
x=y => y=x
have the maximum power because I can say this for every each single
element of
({0,1}^({0,1}^N))^({0,1}^N) etc
"
and this
"
g: {proposition in Theory}-> N
such that
if e= "is an element of"
book define g
g( ( )=3;
g( ) )=5;
g( , )=7;
g( not_sybol )=9;
g( => )=11
g( x_k )= 5 + 8k [variable]
g( a_k )= 7 + 8k [costants?]
g( f_(n, k) )= 9 + 8(2^n)(3^k) [function symbol -> number]
g( P_(n, k) )= 11 + 8(2^n)(3^k) [propositions?]
g( u_1, u_2, ..., u_m) = 2^g(u1)3^g(u2) ... p_(m-1)^g(u_m)
when p is a prime number
in this g: wff -> N (you have written *this* so i suppose you know
what it mean, right? I would like to say that this g() can not exist)
in 'wff' there is the set theory so is it possible define functions
like these
(n , k )eNxN
f( x ) = x^n + 3*x^k xeN
?
if this is true
if (n, k)eNxN define
define f_(n, k)
f_(n, k)={( x, x^n + 3*x^k ) : xeN}
or if you prefer
f_(n, k)(x) = x^n + 3*x^k xeN
N^N = {f: f:N->N}
we have propositions f_(n,k)eN^N n,keN
or if you want f_(n, k)(0) = 0 n,keN
and the Godel number for these propositions
but how assign a number to the function
h={(x, 2*x): xeN}
h(x)= 2x xeN
(every number n, k is already assigned)
?
and what about Godel number for proposition
heN^N
or if you want the proposition h(0)=0
?
"
i'm all eyes for see the answer for this
Ross A. Finlayson
"Where do we go now?"
Peut etre c'est dans petite parte a cause de mon inabilite en votre
langues, des logiques, logiciels, qui devenus des computers, et
theorems. Aussi, nous comprisons seules deux participants dans les
conversations, factions et equippes, le monde est grand. Aussi, mon
Francais est tres mauvais. Je dois y etudier beaucoup pour etre
conversant, il aura de temps avant je pourrais y correcter.
In Peano, 4 only exists because 3 exists, so before you can prove the
even (Peano) integers exist, it is necessary to show that all the
integers exist. It obviously follows that they do.
You describe reasoning to refuse that G, the Goedel sentence G or G_0,
generally derived by diagonalization, is undecideable, that it is in
fact decideable. To some extent that is due to the evaluation of a
maximal element in PA, is that so? Why then upon that refusal would
there be any undecideable statements of objects of the theory?
A finite sentence in Peano is a finite sentence in Presburger.
Ross
Ross A. Finlayson
here and it is some good reading, Aatu has done some good work on that.
So, I am interested in the Goodstein theorem, that his confabulations
go to zero, and am interested in a note about the Paris and Kirby
result that apparently claims a statement about the naturals requires a
"nonstandard countable" model of the natural integers. I'm interested
in reading that, I should get a hold of a copy and check it out.
I think that means that the infinite collection of natural integers is
more than the sum of its parts. It's similar in a way to considering
Cantor's first to show sequential reals, and the powerset result to
show Ord = -1, or Goedel to demand no non-logical axioms.
As I have said, I'm definitely not conventional when it comes to
Goedel.
Ross
H. Enderton
>Godel (sorry, I'm incorrigible and I don't spell with the "e") isn't
>wrong, in the sense that if one accepts his assumptions, then the
>conclusion follows. But I think one of these assumptions is
>unwarranted, and one should be skeptical about the conclusions (or, in
>the case of the First Incompleteness Theorem, the self-referential
>aspect).
From my point of view, the self-referential aspect is a red herring.
Where the first incompleteness theorem really lives is in the fact
that the set of truths of arithmetic is not recursively enumerable.
Of course, AB has a different point of view. It's not just that
"red herring" won't translate easily into French, but he has a more
finitist attitude toward the natural numbers.
--Herb Enderton
Helene....@wanadoo.fr
> Where the first incompleteness theorem really lives is in the fact
> that the set of truths of arithmetic is not recursively enumerable.
In the system in which I framed the problem, namely second-order
arithmetic without the Successor Axiom (call this system F), I don't
think this fact helps (but I could well be mistaken). It may be that,
while F can't enumerate the truths of arithmetic, it can't enumerate
the theorems, either.
How to explain? Well, F has as models all the initial segments, as
well as the standard model, of the natural numbers: {0}, {0,1},
{0,1,2}, ..., {0,1,2,3,4...}. It represents syntactic elements with a
second-order entity. Terms, wffs, proofs, are all second-order
entities. But in second-order logic a second-order entity cannot be
the value of a function, so in order to ask which sets of syntactic
entities can be enumerated, one needs to be able to code the entities
with a first-order entity. Unfortunately, the set of syntactic
entities will always be much bigger than the codes.
For instance, consider the case of the initial segment
{0,1,2,3,...,30}. A wff then has length up to 31 (31 not 30, because
the segment begins with 0). So coding wffs by natural numbers only
leaves 31 possible codes. So any enumeration could only enumerate, at
most, 31 wffs. But there will be more than 31 theorems and more than
31 truths of length <= 31. Hence, while there isn't any enumeration
of the truths, there isn't any of the theorems, either.
I could well be mistaken in this reasoning. But, for the moment
anyway, I don't think the argument from non-enumeration of truths,
helps. Or at least it doesn't seem automatic.
In brief, the fundamental problem with both the self-referential
statement and the recourse to truth is that some form of coding is
needed, and coding requires very big numbers, which are not necessarily
at F's disposition.
Aatu Koskensilta
> <Helene....@wanadoo.fr> wrote:
>
>>But I think one of these assumptions [used in the proof of Gödel's theorem]
>>the case of the First Incompleteness Theorem, the self-referential
>>aspect).
>
> From my point of view, the self-referential aspect is a red herring.
> Where the first incompleteness theorem really lives is in the fact
> that the set of truths of arithmetic is not recursively enumerable.
I, too, think that the whole self-referential asept is a red herring.
However, I would choose the fact that the set of arithmetical truths is
productive as the proper home for the first incompleteness theorem
rather than it's being merely non-r.e.
--
Aatu Koskensilta (aatu.kos...@xortec.fi)
"Wovon man nicht sprechen kann, daruber muss man schweigen"
- Ludwig Wittgenstein, Tractatus Logico-Philosophicus
Aatu Koskensilta
> I, too, think that the whole self-referential asept is a red herring.
Asept is, obviously, a type for aspect. A self-refential object that is
not a division of a clan or a family, or lacks such a division, might or
might not have relevance in the debate about validity of Gödel's theorems.
H. Enderton
>> From my point of view, the self-referential aspect is a red herring.
>> Where the first incompleteness theorem really lives is in the fact
>> that the set of truths of arithmetic is not recursively enumerable.
And then Aatu Koskensilta <aatu.kos...@xortec.fi> wrote:
>I, too, think that the whole self-referential aspect is a red herring.
>However, I would choose the fact that the set of arithmetical truths is
>productive as the proper home for the first incompleteness theorem
>rather than it's being merely non-r.e.
Yes, you have a point (and I think Emil Post would have agreed with you).
The fact that truths are "merely non-r.e." provides the *existence* of
a sentence undecidable in the theory. The fact that they are productive
actually *produces* such a sentence (for a recursively axiomatized
true theory).
--Herb Enderton
MoeBlee
> I would choose the fact that the set of arithmetical truths is
> productive as the proper home for the first incompleteness theorem
> rather than it's being merely non-r.e.
What does 'productive' mean?
Thanks,
MoeBlee
peter...@hotmail.com
>
> Is N = {0, 1, 2, ...} the statement and N0, SA the axioms or N={0, 1,
> 2, ...} and N0, SA the statement?
>
> That statement is also the statement that each subset of the naturals
> contiguous in its normal ordering is a set.
>
> First-order predicate logic, and the rules of inference are generally
> not considered to be proper axioms. In theory, true means provable.
>
> When you say it is reasonable to be skeptical of Goedel, what does that
> mean?
'N={0,1,2,...}' is not a statement in this situation. It's not finitely
long unless you claim some finite containment of {0,1,2,...}. Which
means you appeal to the SA, essentially, which is what's under debate.
AFAICS, if you choose to assume SA you must accept Godel, but you get
normal maths. If you choose to not accept SA you can reject Godel, but
you do so at a cost of being unable to prove (or even state!) many
'obvious' things.
I don't think Andrew's English, or your French, is the issue.
Peter
Rupert
A set S is productive if there's an algorithm which, given any
recursive enumeration of a subset T of S, will produce an element that
is in S but not in T.
MoeBlee
> A set S is productive if there's an algorithm which, given any
> recursive enumeration of a subset T of S, will produce an element that
> is in S but not in T.
Thanks.
If you feel so inclined, would you say something about how that bears
upon incompleteness?
I'm purely guessing here: Is it because we can recursively enumerate
the theorems but also there is an algorithm to show a sentence that is
true in the standard model but that is not a theorem? Is there such an
algorithm? (Here T is the set of theorems and S is the set of sentences
true in the standard model?)
Am I close or completely off?
MoeBlee
Chris Menzel
> Rupert wrote:
>
>> A set S is productive if there's an algorithm which, given any
>> recursive enumeration of a subset T of S, will produce an element
>> that is in S but not in T.
>
> Thanks.
>
> If you feel so inclined, would you say something about how that bears
> upon incompleteness?
>
> I'm purely guessing here: Is it because we can recursively enumerate
> the theorems but also there is an algorithm to show a sentence that is
> true in the standard model but that is not a theorem? Is there such an
> algorithm?
Yes, it's called Gödel's proof. ;-)
> (Here T is the set of theorems and S is the set of sentences true in
> the standard model?)
>
> Am I close or completely off?
Close, you just need to generalize a bit. Let S be the true sentences
of arithmetic. An axiomatization of arithmetic can be thought of as
providing a recursive enumeration of a subset T of S, viz., its
theorems. The contruction in Gödel's theorem can be thought of as
providing an algorithm for producing, for any recursive enumeration T of
S, a sentence in S that is not in T. To make this all formally correct
we'd have to talk in terms of Gödel numbers instead of sentences, but
that's the basic idea.
Star...@earthlink.net
> Goedel actually only has one theorem as Von Neumann showed.
> The theorem is called Omega-Consistency.
>
> His proves are so obvious from the assumptions,
> that he had to call Hilbert to tell him that this
> ain't gonna work since Cantor already proved the theorems.
> And so mathematicians should from hence forth be
> be called Legrangian automatons, rather than
> intelligence specimens of evolution.
>
>
What are you talking about? Could you be more specific?
Star...@earthlink.net
> I think that means that the infinite collection of natural integers is
> more than the sum of its parts.
Take I to be the collection of natural integers. Take E to be the
collection of even natural integers, and O to be the collection of odd
natural integers. Every integer is either even or odd, therefore E+O=I.
How exactly I>O+E? I'm curious.
Star...@earthlink.net
> From my point of view, the self-referential aspect is a red herring.
> Where the first incompleteness theorem really lives is in the fact
> that the set of truths of arithmetic is not recursively enumerable.
>
mathematics? Are there similar, proovable theorums akin to Goedel for
things outside of mathematics? I am curious about that.
Rupert
I'm not aware of any.
Ross A. Finlayson
I guess I mean I think it's more than the sum of its discernible parts.
That's along the lines of the statement N E N, that N contains itself.
Similarly to how a universal set would contain itself, N, the set of
natural integers or some most fundamental infinite collection, would
contain itself.
That's similar to a notion that any infinite set for some result as
basically a consequence of induction, contains itself. Then, where
Russell asks for the set of all sets that don't contain themselves,
they are only finite sets. Somehow, instead of Russell precluding the
universe's existence and thusly any approximation thereof, Russell
observes that something along the lines of N E N.
That seems indefensible, the predicate P(n) for n E N is P(n) -> n is a
natural integer. While it might seem that way, it is not necessarily,
in a realm of unrestricted comprehension. To say unrestricted
comprehension, that still seems to have a violation of the subset rule,
because in asking for the subset of the naturals with no non-finite
element, or sets that don't contain themselves, it might only be that
Russell's antinomy is put off instead of resolved, put off to the
paraconsistent ur-element.
That might seem counterintuitive, but having a maximal element as
Andrew has been describing in this thread is a similar notion.
There is only one theory with null axioms.
Ross
MoeBlee
> Yes, it's called Gödel's proof. ;-)
So the proof does not just show a specific undecidable sentence, but it
also provides an algorithm for showing a specific undecidable sentence
no matter what consistent axioms we add. Right?
> > (Here T is the set of theorems and S is the set of sentences true in
> > the standard model?)
> >
> > Am I close or completely off?
>
> Close, you just need to generalize a bit. Let S be the true sentences
> of arithmetic. An axiomatization of arithmetic can be thought of as
> providing a recursive enumeration of a subset T of S, viz., its
> theorems. The contruction in Gödel's theorem can be thought of as
> providing an algorithm for producing, for any recursive enumeration T of
> S, a sentence in S that is not in T. To make this all formally correct
> we'd have to talk in terms of Gödel numbers instead of sentences, but
> that's the basic idea.
I follow you, but what, or how, did I miss generalizing?
Thanks,
MoeBlee
H. Enderton
> I have a question. Do Goedel's laws apply to things outside of
> mathematics? Are there similar, proovable theorums akin to Goedel for
> things outside of mathematics? I am curious about that.
Newton da Costa has some work claiming undecidability results in
physics. I don't have the reference immediately at hand.
--Herb Enderton
Chris Menzel
> Chris Menzel wrote:
>
>> Yes, it's called Gödel's proof. ;-)
>
> So the proof does not just show a specific undecidable sentence, but it
> also provides an algorithm for showing a specific undecidable sentence
> no matter what consistent axioms we add. Right?
Right.
>> > (Here T is the set of theorems and S is the set of sentences true in
>> > the standard model?)
>> >
>> > Am I close or completely off?
>>
>> Close, you just need to generalize a bit. Let S be the true sentences
>> of arithmetic. An axiomatization of arithmetic can be thought of as
>> providing a recursive enumeration of a subset T of S, viz., its
>> theorems. The contruction in Gödel's theorem can be thought of as
>> providing an algorithm for producing, for any recursive enumeration T of
>> S, a sentence in S that is not in T. To make this all formally correct
>> we'd have to talk in terms of Gödel numbers instead of sentences, but
>> that's the basic idea.
>
> I follow you, but what, or how, did I miss generalizing?
Well, it sounded like you were just talking about the theorems of some
one specific axiomatization -- though I grant you might have been simply
talking about any *arbitrary* axiomatization. The important thing is
that, for *any* recursive enumeration of a subset of S, we can produce a
sentence of S not in that enumeration.
Herman Jurjus
Do you mean:
Newton C. A. da Costa, Francisco A. Doria: Undecidability,
incompleteness and the Arnol'd problems. Studia Logica 55(1): 23-32 (1995)
--
Cheers,
Herman Jurjus
MoeBlee
> Well, it sounded like you were just talking about the theorems of some
> one specific axiomatization -- though I grant you might have been simply
> talking about any *arbitrary* axiomatization. The important thing is
> that, for *any* recursive enumeration of a subset of S, we can produce a
> sentence of S not in that enumeration.
I see the importance of that emphasis. But I'm unclear on something:
The incompleteness proofs are usually given with respect to a certain
kind of system, such as that of PM or, alternatively, that of a first
order axiomatization (I understand that the proof is not confined to a
particular first order axiomatization, but I wonder how the result
generalizes to other systems that might not be first order or might not
be based on a predicate calculus even). So what is the synopsis of the
argument that the generalization extends to ANY system that meets the
requirements of recursive axiomatization, consistency, and sufficient
richness? How do we back away from an axiomatization in a particular
kind of system, such as first order, and generalize to other kinds of
systems? I suspect that what we do is move the investigation to
recursion theory and show that certain predicates and functions can
express things about arithmetic, then we show that no matter what
system and no matter what kind of language, if the system can be shown
to express arithmetic, then there is an algorithm that takes any
recursive enumeration of the thereoms of the system and produces a
formula that expresses a true arithmetical statement but is not in the
enumeration. But what is the synopsis of how that generalization is
made (if I've even stated this correctly)? I'll be going over this
subject in, hopefully, the not too distant future. But any forecast
will help when I arrive.
Thanks,
MoeBlee
Chris Menzel
> Chris Menzel wrote:
>> Well, it sounded like you were just talking about the theorems of some
>> one specific axiomatization -- though I grant you might have been simply
>> talking about any *arbitrary* axiomatization. The important thing is
>> that, for *any* recursive enumeration of a subset of S, we can produce a
>> sentence of S not in that enumeration.
>
> I see the importance of that emphasis. But I'm unclear on something:
> The incompleteness proofs are usually given with respect to a certain
> kind of system, such as that of PM or, alternatively, that of a first
> order axiomatization (I understand that the proof is not confined to a
> particular first order axiomatization, but I wonder how the result
> generalizes to other systems that might not be first order or might
> not be based on a predicate calculus even). So what is the synopsis of
> the argument that the generalization extends to ANY system that meets
> the requirements of recursive axiomatization, consistency, and
> sufficient richness? How do we back away from an axiomatization in a
> particular kind of system, such as first order, and generalize to
> other kinds of systems?
The proof is typically given with respect to a weak, finitely
aximatizable system Q of arithmetic, and the usual form of the theorem
(as strengthened by Rosser) is that *any* consistent, axiomatizable
theory containing Q is incomplete. So in one fell swoop we get the
incompleteness of PA, ZF (in virtue of the former's intrepretability in
the latter), second-order PA, etc. First-order, higher-order, it
matters not, so long as it contains Q -- the system PM that was Gödel's
target in his original paper after all is an omega-order logic. As for
your suggestion that it might even apply to systems not based on
predicate calculus, I'm not sure what you have in mind.
> I suspect that what we do is move the investigation to recursion
> theory
Typically accounts of the theorem already involve recursion theory
intimately, though there are more semantically oriented treatments that
avoid it, e.g., Smullyan's rendition in his book on incompleteness,
IIRC.
MoeBlee
> The proof is typically given with respect to a weak, finitely
> aximatizable system Q of arithmetic, and the usual form of the theorem
> (as strengthened by Rosser) is that *any* consistent, axiomatizable
> theory containing Q is incomplete. So in one fell swoop we get the
> incompleteness of PA, ZF (in virtue of the former's intrepretability in
> the latter), second-order PA, etc. First-order, higher-order, it
> matters not, so long as it contains Q -- the system PM that was Gödel's
> target in his original paper after all is an omega-order logic.
I follow you, except: I know what a first order theory is. And, for any
given kind of system, I know that we can define 'theory' for that kind
of system. But we can define 'recursively axiomatizable theory' in
complete generality, no matter whether it uses a predicate calculus or
a different kind of formal symbol game (which even though it is not in
a predicate calculus, it still might code arithmetical statements). So
how is it shown that incompleteness applies to any such sufficiently
rich theory?
The definition of a 'recursively axiomatized theory': There is a
recursive set of axioms (certain symbol strings), recursive relations
that are the inference rules, and the theory is the set of formulas
derivable from the inference rules. So what I'm guessing is that
somewhere along the way we show that no matter how the arithmetical
statements are expressed, if they're expressed in ANY kind of theory,
then either there is a true arithmetical statement that is not coded by
a member of the theory or both an arithmetical statement and its denial
are coded by two members, respectively, of the theory. So what I'm
wondering is whether somewhere along the way we specify what it means
for a system (such that the set of axioms is recursive and the
inference rules are recursive) to express (code) arithmetical
statements and then we show that either there is a true arithmetical
statement not expressed (coded) by the system or the theory has both a
formula that expresses (codes) an arithmetical statement and a formula
that expresses (codes) the negation of that arithmetical statement.
> your suggestion that it might even apply to systems not based on
> predicate calculus, I'm not sure what you have in mind.
The possible systems I just mentioned don't have to use predicate
calculi do they? In principle it is not ruled out that one could
express arithmetical statements in a system that does not use a
predicate calculus. No? It is not known a priori that one could not
show that formulas (words or symbol strings) in a system that is not a
predicate calculus can be decoded so that they express arithmetical
statements, right? I mean, maybe creatures on other planets code
arithmetical statements in formal systems that aren't predicate
calculi. (And we can stipulate that the coding must be recursive in the
sense that there is an algorithm to determine, per the coding scheme or
rules, whether a given formula codes an arithmetical statement, and if
so, what statement that is.) So this leads me to wonder how the
incompleteness theorem is generalized to any possible system (with a
recursive set of symbol strings that are axioms and recursive relations
that are inference rules) that can "code" arithmetical statements.
Perhaps this is done by referencing Turing machine computability or
just computability in general?
Much of that may not be stated correctly, but I hope you see the gist
of what I'm wondering about.
But another thing I don't understand is that proofs of incompleteness,
such as Godel's own (and Rosser's strenghtened version?) are said to
use only principles or assumptions that are intuitionistically
impeccable. Have I stated that correctly? As I understand, these are
methods of reasoning that are finitistic (as well as meeting other
criteria?). But, first, I haven't found a definition of 'finitistic'
that is even close to being a precise definition (and I realize that,
since it is not a formal notion, complete precision may not be
possible). Second, don't we have to use a fair amount of set theory,
even if in an informal meta-theory (which, in principle, can be
completely formalized), and doesn't this set theory assume the
existence of infinite sets and depend upon use of the law of excluded
middle regarding infinite sets (which is not intutionistically
acceptable)? The proof of the incompleteness theorem can be, arguably
should be, itself completely formalizable in a formal theory. But just
from the git-go, we talk about languages that have infinite sets of
symbols and we use recursion over these infinite sets to define
functions on these infinite sets and we use induction to prove things
about these infinite sets. Is that finitistic and intuitionistically
unobjectionable? This is quite hazy for me.
> Typically accounts of the theorem already involve recursion theory
> intimately, though there are more semantically oriented treatments that
> avoid it, e.g., Smullyan's rendition in his book on incompleteness,
> IIRC.
Thanks, I had planned to read that book eventually, and you've given me
a theme to attach to it.
MoeBlee
Torkel Franzen
> Is that finitistic and intuitionistically
> unobjectionable?
Yep.
> Thanks, I had planned to read [Smullyan, "Gödel's incompleteness
> theorems"] eventually, and you've given me
> a theme to attach to it.
A good plan. A study of Smullyan's book will answer most of your
questions.
MoeBlee
> A good plan. A study of Smullyan's book will answer most of your
> questions.
My plan is to finish Enderton's logic and set theory books,
supplemented by Suppes's set theory book. Then Shoenfield's book, also
integrating from van Dalen's 'Logic And Structure'. I'd also like to
get a good grip on Quine's 'Mathematical Logic' and 'Set Theory And Its
Logic'. Also, Smullyan's 'First-Order Logic', his incompleteness book,
his set theory book, and his recursion theory book (though I haven't
seen the later two but merely trust that they're good ones). Also
Kleene's 'Mathematical Logic'. And for more set theory, I want to do
Levy's 'Basic Set Theory'. Meanwhile, I should work through Martin
Davis's 'Computability And Unsolvability'. Also, Chang and Keisler's
'Model Theory' (over a period of time). There's also an out of print
book co-written with Henkin about the number systems, which I'd love to
get a copy of.
As I start to get my logic on a firmer basis, I'll turn to algebra, for
which I have Serge Lang's tome and Warner's 'Modern Algebra'. For
analysis and topology I have several books to choose from. And I have a
geometry book that I think will be a good introduction for me. And I'd
like to learn some intuitionistic math, and modal logic too, which
reminds me that I want to do Boolos's book on provability too.
I read and relished your 'Godel's Theorem' and much of your web site. I
know you've touched on some of my questions, but I haven't been clear
on this only because I haven't worked through it systematically yet.
Anyway, 'Godel's Theorem' is great reading and extremely helpful. It's
a book to recommend. I've also read parts of 'Inexhaustibility' but I
will return to it after I'm more competent with math.
I expect to complete all of this in the next two months or the next
twenty years, whichever comes first...I mean...last.
Any other recommendations would be heartily welcomed.
Thanks,
MoeBlee
P.S. What do you think of Mary Tiles's 'The Philosophy Of Set Theory'?
Torkel Franzen
> My plan is to finish Enderton's logic and set theory books,
> supplemented by Suppes's set theory book. [A number of other
> books mentioned]
That's a lot of reading. Those books certainly contain the answers
to your questions.
> P.S. What do you think of Mary Tiles's 'The Philosophy Of Set
> Theory'?
I haven't read it.
Chris Menzel
It's pretty solid. Somewhat deeper, IMO, both philosophically and
historically, are Michael Hallett's terrific Cantorian Set Theory and
Limitation of Size and Shaughan Levine's Understanding the Infinite.
MoeBlee
> >> P.S. What do you think of Mary Tiles's 'The Philosophy Of Set
> >> Theory'?
> It's pretty solid. Somewhat deeper, IMO, both philosophically and
> historically, are Michael Hallett's terrific Cantorian Set Theory and
> Limitation of Size and Shaughan Levine's Understanding the Infinite.
The Shaughan Levine rings a bell. I think I read it but am not sure.
Does he propose theories with no infinite sets? He discusses Cantor and
Zermelo for most of the book, then argues for his own finite-only view,
then gives an outline of a theory?
MoeBlee