Sad observation: Cantor/Godel/Turing/Tarski
in [Logic]
|
Prev: Why can no one in sci.math understand my simple point?
Next: Yet Another SD Rodrian Prediction True: Gravity is NOT an attractive force between bodies
From: Frederick Williams on 21 Jun 2010 08:28 Bill Taylor wrote: > > > > 1. Cantor's theorem about the uncountability of the reals. > > > 2. Godel's incompleteness theorem. > > > 3. Turing's theorem about the unsolvability of the halting problem. > > > 4. Tarski's theorem about the undefinability of truth. > > Just enlighten me quickly and briefly, whoever is so disposed. > > But is (4) provable without recourse to (2)? > > Or is (2) a pretty-much-necessary precursor to (4)? > > Could (4) have successfully been proved in 1930, > all other history being as is? You may wish to look at http://www.staff.amu.edu.pl/~rmur/hpl1.ps. -- I can't go on, I'll go on.
From: Daryl McCullough on 21 Jun 2010 08:56 Bill Taylor says... > >> > 1. Cantor's theorem about the uncountability of the reals. >> > 2. Godel's incompleteness theorem. >> > 3. Turing's theorem about the unsolvability of the halting problem. >> > 4. Tarski's theorem about the undefinability of truth. > >Just enlighten me quickly and briefly, whoever is so disposed. > >But is (4) provable without recourse to (2)? > >Or is (2) a pretty-much-necessary precursor to (4)? > >Could (4) have successfully been proved in 1930, >all other history being as is? Yeah, it always seemed to me that the proof of Godel's theorem and the proof of Tarski's theorem were almost the same. Tarski's theorem *implies* Godel's theorem (since if all truths were provable, then provability would be the same as truth, and that would violate Tarski's theorem). The real technical accomplishment that makes everything possible is the existence of fixed points. For any formula in the language or arithmetic Phi(x) with one free variable, there is a sentence G such that G <=> Phi(#G) If you assume that Phi(#G) is a formulation of "G is not provable", then you get Godel's theorem. If you assume that Phi(#G) is a formulation of "G is not true", then you get Tarski's theorem (that there is no such Phi). -- Daryl McCullough Ithaca, NY
From: George Greene on 21 Jun 2010 19:50 It turns out that this is the usual quantifier dyslexia. I think (for the benefit of anybody who is trying to characterize cranks and crank-threads) that we should just make this the first primary default explanation for why people are so on-the-warpath vs. Cantor's Theorem. WM is also notoriously on that warpath and he also equally notoriously (equally to Herc) refuses to use formal language and acts as though the fact that FOL *successfully* proves Cantor's Theorem refutes FOL itself. This was Herc, 2 years ago: > But the set of CR does contain this sequence of digits. Well, No, actually, it doesn't, but in any case, while the SET is one thing, this set HAS to be denumerable, so it is small enough to be LISTED (and it's the list that counts here), EVEN if that list is not computable. And once THAT happens, THAT list does NOT contain its own anti-diagonal -- this is of course true of ALL square lists OF ALL sizes, finite OR NOT. > ALL sequences of digits to oo are computable. No, they're not. All sequences are computable to all finite lengths And I think that's good enough to refute the existence of sets that are uncountably larger than oo. FACT: All sequences of digits are computable to infinite length. On Jun 15, 5:16 pm, stevendaryl3...(a)yahoo.com (Daryl McCullough) wrote: > I'm not going to name any names, but I recently found that I was > arguing the same arguments, in the same way, with the same people, > as I argued 4 or 5 years ago. Clearly, this is a pointless endeavor. > So I have kill-filed the people and the argument threads. This isn't > because of any hostility towards those people, nor because of disgust > with the topics, but just as a self-discipline measure to try to keep > myself from staying in the same rut forever. I don't want to be > like Sisyphus forever pushing a boulder up a hill, only to have it > roll back down again. > > -- > Daryl McCullough > Ithaca, NY
From: Frederick Williams on 22 Jun 2010 06:41 Bill Taylor wrote: > > > > 1. Cantor's theorem about the uncountability of the reals. > > > 2. Godel's incompleteness theorem. > > > 3. Turing's theorem about the unsolvability of the halting problem. > > > 4. Tarski's theorem about the undefinability of truth. > > Just enlighten me quickly and briefly, whoever is so disposed. > > But is (4) provable without recourse to (2)? > > Or is (2) a pretty-much-necessary precursor to (4)? No, if you want to see text book proofs of Tarski's theorem followed by Godel's theorem then see Chapter 7 of Bell and Machover's 'A Course in Mathematical Logic', North-Holland, 1977. > Could (4) have successfully been proved in 1930, > all other history being as is? > > -- Befuddled Bill -- I can't go on, I'll go on.
From: Bill Taylor on 25 Jun 2010 02:17
On Jun 22, 12:56 am, stevendaryl3...(a)yahoo.com (Daryl McCullough) wrote: > >> > 2. Godel's incompleteness theorem. > The real technical accomplishment that makes everything possible > is the existence of fixed points. Yes! (Though even to outline a method for mathematizing meta-mathematics was a major triumphal step before this.) The existence of fixed points is something that is highlighted in recursive function theory, which makes Godel's theorem much plainer, and qualifies it as giving the "proper" proof of it. (There are several different non-equivalent proofs.) It is also the existence of fixed points which was mangled in the first book I ever read about this, in my student days, bamely Nagel and Newman's book "Godel's Proof", which I have ever since been strident in steering people away from - it'll rot your brain! -- Warning William ** The concept of definability is necessarily undefinable. |