Beyond Incompleteness
in [Logic]
|
From: Jesse F. Hughes on 28 Jun 2010 09:29 Charlie-Boo <shymathguy(a)gmail.com> writes: > On Jun 27, 3:23 pm, "Jesse F. Hughes" <je...(a)phiwumbda.org> wrote: >> Charlie-Boo <shymath...(a)gmail.com> writes: >> > Yes. That is the first conclusion in Godel's 1st Incompleteness >> > Theorem based on Soundness in the introduction to the 1931 paper. >> >> > The second conclusion was that not all sentences are provable or >> > refutable ("incompleteness".) The theorem based on w-consistency in >> > the body of the paper came next, then the 2nd theorem. Later was >> > Rosser's and Smullyan's versions. >> >> > Then C-B showed how to shrink all of these proofs to one short English >> > sentence, in at least two different ways, as well as how to generate >> > proofs from simple properties of 3 specific sets of wffs. >> >> Yes, CBL is a great advance in logic. I've always said so. >> >> Congrats! > > Thanks. And BTW do you know what would be cool? If sarcasm were > replaced by specific valid mathematical points. Some time in the past, I tried to make sense of CBL. I couldn't do it. As far as I recall, each application of CBL required certain axioms that contained the meat of the mathematical insight of the original proofs. I won't defend this half-remembered opinion, nor spend any more time on what I recall was a waste of my time previously. Nonetheless, good luck convincing others that what you have is exciting and new. -- "[ISPs] have to comply with privacy regulation which, ironically, require you to keep track of who your users are so you can send them annual notices telling them that you are not storing personal information about them." -- Ed Felten explains new FCC policy.
From: Charlie-Boo on 28 Jun 2010 20:24 On Jun 28, 9:29 am, "Jesse F. Hughes" <je...(a)phiwumbda.org> wrote: > Charlie-Boo <shymath...(a)gmail.com> writes: > > On Jun 27, 3:23 pm, "Jesse F. Hughes" <je...(a)phiwumbda.org> wrote: > >> Charlie-Boo <shymath...(a)gmail.com> writes: > >> > Yes. That is the first conclusion in Godel's 1st Incompleteness > >> > Theorem based on Soundness in the introduction to the 1931 paper. > > >> > The second conclusion was that not all sentences are provable or > >> > refutable ("incompleteness".) The theorem based on w-consistency in > >> > the body of the paper came next, then the 2nd theorem. Later was > >> > Rosser's and Smullyan's versions. > > >> > Then C-B showed how to shrink all of these proofs to one short English > >> > sentence, in at least two different ways, as well as how to generate > >> > proofs from simple properties of 3 specific sets of wffs. > > >> Yes, CBL is a great advance in logic. I've always said so. > > >> Congrats! > > > Thanks. And BTW do you know what would be cool? If sarcasm were > > replaced by specific valid mathematical points. > > Some time in the past, I tried to make sense of CBL. I couldn't do it. > As far as I recall, each application of CBL required certain axioms > that contained the meat of the mathematical insight of the original > proofs. Not possible. As I mentioned, each theorem in CBL is actually a theorem in each base. -~P/P tells us that the programs that don't halt on themselves is not r.e., that there is no set that contains those sets that do not contain themselves, that the set of non- theorems is not representable. So there is no single "insight in the original proof" as there are several original proofs or in some cases (e.g. Russell's Paradox) no agreed-upon "proof". Maybe you also forgot that one CBL theorem is actually several theorems in a variety of branches of Computer Science. Name your favorite theorem and/or branch of Computer Science and I can show you examples. It would be a shame if your last words were quoting a memory that has degraded over time to the point of becoming inaccurate. C-B > I won't defend this half-remembered opinion, nor spend any more time on > what I recall was a waste of my time previously. > > Nonetheless, good luck convincing others that what you have is exciting > and new. > > -- > "[ISPs] have to comply with privacy regulation which, ironically, > require you to keep track of who your users are so you can send > them annual notices telling them that you are not storing personal > information about them." -- Ed Felten explains new FCC policy.- Hide quoted text - > > - Show quoted text -
From: Charlie-Boo on 29 Jun 2010 05:21 On Jun 28, 9:29 am, "Jesse F. Hughes" <je...(a)phiwumbda.org> wrote: > Charlie-Boo <shymath...(a)gmail.com> writes: > > On Jun 27, 3:23 pm, "Jesse F. Hughes" <je...(a)phiwumbda.org> wrote: > >> Charlie-Boo <shymath...(a)gmail.com> writes: > >> > Yes. That is the first conclusion in Godel's 1st Incompleteness > >> > Theorem based on Soundness in the introduction to the 1931 paper. > > >> > The second conclusion was that not all sentences are provable or > >> > refutable ("incompleteness".) The theorem based on w-consistency in > >> > the body of the paper came next, then the 2nd theorem. Later was > >> > Rosser's and Smullyan's versions. > > >> > Then C-B showed how to shrink all of these proofs to one short English > >> > sentence, in at least two different ways, as well as how to generate > >> > proofs from simple properties of 3 specific sets of wffs. > > >> Yes, CBL is a great advance in logic. I've always said so. > > >> Congrats! > > > Thanks. And BTW do you know what would be cool? If sarcasm were > > replaced by specific valid mathematical points. > > Some time in the past, I tried to make sense of CBL. I couldn't do it. > As far as I recall, each application of CBL required certain axioms > that contained the meat of the mathematical insight of the original > proofs. So it doesn't make sense and it's just a copy of the original proof. Ergo the original proof doesn't make sense. How many times do I have to tell people KEEP YOUR CRITICISMS CONSISTENT! (Common: "It all wrong." and "Everybody already knows it.") Also remember (if you can) that CBL provides lots of proofs of famous theorems. It's not one proof that is a copy of the original! This is true in part because it generalizes the individual notions of recursively enumerable, expressible, representable, is a set, etc. into one expression. In the standard treatment, each of these is a kludge with a separate definition and the connection is not immediate. For example, the set of nontheorems is expressible (through construction) but not representable (through diagonalization.) In CBL that is expressed as ~PR/TW and -~PR/PR [PR=provable wffs, TW=true wffs]. Then we have the common set ~PR/a which is the set of "bases" in which ~PR is characterized, call it R(a). So R(a) means ~PR/a and the two premises are R(TW) and ~R(PR). The TW base characters non- theorems but the PR base does not. So TW differs from PR, i.e., true does not equal provable, Godel's 1st Incompleteness theorem. We can also say PR/PR, the set of theorems is representable (Godel), and -TW/TW the set of true sentences is not expressible (Tarski.) The latter is a theorem due to the fact (rule of inference) that P/TW => ~P/TW and axiom -~P/P. TW/TW => ~TW/TW violates -~P/P so -TW/TW, truth is not expressible. So we can let R(a) mean a/a and we have R(PR) and ~R(TW), and again we prove that provable does not equal true. This also shows a formal relationship between Godel and Tarski's (-TW/ TW) results, a topic often discussed - including in a recent post here. Any statement concerning truth, provability or refutability can be generalized this way into a property of each set, and when that property does not apply to another set, we have proven that the two sets differ, as in the two examples above. Yes, CBL does generate the original proof. But it also generates many others - including those no more that 1-2% the size of the original proof. And it does so at a higher level so that one proof can be applied to many different domains (branches of Computer Science.) Personally I think it's pretty cool. C-B > I won't defend this half-remembered opinion, nor spend any more time on > what I recall was a waste of my time previously. Should you say something you cannot - and will not - defend? > Nonetheless, good luck convincing others that what you have is exciting > and new. > > -- > "[ISPs] have to comply with privacy regulation which, ironically, > require you to keep track of who your users are so you can send > them annual notices telling them that you are not storing personal > information about them." -- Ed Felten explains new FCC policy.- Hide quoted text - > > - Show quoted text -
From: Charlie-Boo on 29 Jun 2010 05:46 On Jun 25, 10:45 am, Frederick Williams <frederick.willia...(a)tesco.net> wrote: > "Jesse F. Hughes" wrote: > > From my modern perspective, then, it doesn't make much sense to say that > > Euclid's postulate is either true nor false. It seems to me, though I > > could be wrong, that the same observation was clear in Hilbert's time. > > > Thus, in Hilbert's time, it should have been clear that not ever > > mathematical statement really *is* either true or false. > > > The most doubtful bits of this are that my own interpretation relies > > heavily on model theoretic notions (truth in an interpretation, in > > particular) and so post-dates Hilbert. Again, it would be nice if > > someone more knowledgeable would say whether the Wikipedia > > characterization of decidability really is a feature Hilbert aimed for. > > It may be a misunderstanding of Hilbert's famous 'In mathematics there > is no ignorabimus.' and 'For us there is no ignorabimus' remarks. No no no. Hilbert described his beliefs in detail and in mathematical terms. It's not from his famous quote alone - he spent years advocating and discussing it. > One doesn't have to have an understanding of model theory al a Tarski > or Robinson to know that there are models of geometry in which the > fifth postulate is true and models in which it is false: that is 19th > century stuff. That doesn't say anything about something being neither true nor false (or both). In each context it is true or it is false. Don't try to discredit the whole notion of truth just to attack a single use of it. That trick is all too common and a way to avoid the original point. C-B > I hasten to point out that I am not the 'someone more knowledgeable' > whom you seek. > > -- > I can't go on, I'll go on.
From: Aatu Koskensilta on 29 Jun 2010 08:47
"Jesse F. Hughes" <jesse(a)phiwumbda.org> writes: > I'm no expert on Hilbert's Program, but as I recall, the standard > refutation is to show that PA cannot prove every true arithmetic > statement. This standard refutation may well be based on a popular > misunderstanding of Hilbert. The central aim of Hilbert's program was to show that infinitary, abstract mathematics is conservative over finitary mathematics, for finitistically meaningful mathematical statements, i.e. If P is a finitistically meaningful statement provable using abstract, infinitary mathematics, then P can be proved true by finitary methods. Since we can prove e.g. Zermelo set theory consistent using infinitary, abstract mathematics, we obtain by the proof of the first incompleteness theorem a finitistically meaningful statement, the G�del sentence of Zermelo set theory, that we can prove using infinitary, abstract mathematics but not by finitary methods (provided all finitary methods are captured in Zermelo set theory). So, the first incompleteness theorem, together with a bit of conceptual analysis, refutes Hilbert's program. The fact that PA can't prove every true arithmetical statement alone is not quite sufficient to show the central goal of the program can't be achieved. (We also don't need the second incompleteness theorem, as sometimes claimed.) -- Aatu Koskensilta (aatu.koskensilta(a)uta.fi) "Wovon man nicht sprechan kann, dar�ber muss man schweigen" - Ludwig Wittgenstein, Tractatus Logico-Philosophicus |