THE HOLY GRAIL ~ CANTOR DISPROOF
in [Logic]
|
Prev: "Book Smart" NP-Complete Method: Musatov is closing in... Gaining... People are starting to talk...
Next: Was Einstein Guilty of Scientific Fraud?
From: |-|ercules on 25 May 2010 21:59 "Aatu Koskensilta" <aatu.koskensilta(a)uta.fi> wrote > "|-|ercules" <radgray123(a)yahoo.com> writes: > >> Aren't you the logician who proved that there is a formal proof for >> every informal proof.... errr... with an informal proof? > > You're thinking of someone else. Another Aatu Koskensilta? Aatu Koskensilta wrote: All mathematical proofs can be formalised, after all. Is that a statement of incontrovertible fact, or a statement of faith? Yes. Good. Yes. That all mathematical proofs can be formalised is in a sense a triviality these days -- we simply would regard an argument we don't see how to formalise as falling short of the standard of rigour in mathematics, thinking there must be something obscure in it, that some steps must be spelled out more fully, that some detail has eluded us, and so on. This we have learned from experience, a habit mathematicians acquire by osmosis during their formative years. But it can also backed up by various general considerations the sort of which I alluded to in the posts I referred you to. One must be skeptical when the proof that all informal proofs can be made into formal proofs, is itself just an informal proof. Herc
From: Aatu Koskensilta on 25 May 2010 22:01 "|-|ercules" <radgray123(a)yahoo.com> writes: > Aatu Koskensilta wrote: All mathematical proofs can be formalised, > after all. This is hardly something I've claimed to have a proof of. It's just an observation. > One must be skeptical when the proof that all informal proofs can be > made into formal proofs, is itself just an informal proof. Why? -- Aatu Koskensilta (aatu.koskensilta(a)uta.fi) "Wovon man nicht sprechan kann, dar�ber muss man schweigen" - Ludwig Wittgenstein, Tractatus Logico-Philosophicus
From: LauLuna on 26 May 2010 18:25 On May 23, 1:22 am, Herc7 <ozd...(a)australia.edu> wrote: > BONUS POINTS ~ GODEL DISPROOF > > Roger Penrose's argument is that a computer can never be as smart as a > person because you can ask the computer a question, "IS 'THIS CANNOT > BE PROVEN BY COMPUTER123' TRUE?". Humans know it is true, but > COMPUTER123 can never prove it. > > But I can equally ask Roger Penrose "IS 'THIS CANNOT BE PROVEN BY > ROGER PENROSE' TRUE?". Everyone else can prove it, but Roger Penrose > can never prove it. You are overlooking the possibility that 'this cannot be proven by Roger Penrose' express no proposition, that it be paradoxical just like the Liar sentence. Penrose will surely know that if he proves it, then it is not true; so he must know he cannot prove it; in fact he has proved that the sentence cannot be proven by Roger Penrose; but if your sentence expressed a proposition, it would express exactly the same Penrose has proved, which is impossible. So here's the difference between a computer and a human: you could never produce a paradoxical sentence about a computer's ability to prove something (because it is a well-defined mathematical fact) while you can produce such a sentence about a human's ability to prove sentences. Best.
From: Marshall on 26 May 2010 20:33 On May 26, 3:25 pm, LauLuna <laureanol...(a)yahoo.es> wrote: > On May 23, 1:22 am, Herc7 <ozd...(a)australia.edu> wrote: > > > BONUS POINTS ~ GODEL DISPROOF > > > Roger Penrose's argument is that a computer can never be as smart as a > > person because you can ask the computer a question, "IS 'THIS CANNOT > > BE PROVEN BY COMPUTER123' TRUE?". Humans know it is true, but > > COMPUTER123 can never prove it. > > > But I can equally ask Roger Penrose "IS 'THIS CANNOT BE PROVEN BY > > ROGER PENROSE' TRUE?". Everyone else can prove it, but Roger Penrose > > can never prove it. > > You are overlooking the possibility that 'this cannot be proven by > Roger Penrose' express no proposition, that it be paradoxical just > like the Liar sentence. > > Penrose will surely know that if he proves it, then it is not true; so > he must know he cannot prove it; in fact he has proved that the > sentence cannot be proven by Roger Penrose; but if your sentence > expressed a proposition, it would express exactly the same Penrose has > proved, which is impossible. Right. > So here's the difference between a computer and a human: you could > never produce a paradoxical sentence about a computer's ability to > prove something (because it is a well-defined mathematical fact) while > you can produce such a sentence about a human's ability to prove > sentences. Wrong. Marshall
From: Transfer Principle on 27 May 2010 00:10
On May 24, 5:39 pm, William Hughes <wpihug...(a)hotmail.com> wrote: > On May 24, 9:04 pm, Herc7 <ozd...(a)australia.edu> wrote: > > You are selecting specific diagonals based on the list. > > The probability of fitting a random diagonal to the list of computable > > numbers resulting in a different set of numbers is 0. > There are however an infinite number of counterexamples. Hmmm. Let's look at Herc/Cooper's post again. > > The _probability_ of fitting a _random_ diagonal to the list of computable > > numbers resulting in a different set of numbers is 0. (emphasis mine) Probability? Random? We know that in standard analysis, probability is usually defined in terms of the Lebesgue measure. > Interestingly this set is uncountable. But what's the Lebesgue measure of this set? Is it zero? If so, then we can vindicate Herc/Cooper's claim after all. So let us restate the claim. Question: Let X be the subset of [0,1] such that a real number x is in X iff no permutation of the set of computable reals, written in ternary, can produce that number on the diagonal. What is the Lebesgue measure of X? Or we may write this even more formally: Let F : omega^2 -> 3 (the von Neumann ordinal 3) be a function such that for every function g : omega -> 3, there exists a unique natural number m such that F(m,n) = g(n) for all n if and only if g is a computable function. Then let X be the subset of [0,1] such that for every real number x, x is in [0,1] iff for every h : omega -> omega bijective, the sum of F(h(n),n)/3^(n+1) as n ranges 0 to infinity is not x. What is the Lebesgue measure of X? William Hughes tells us that X is uncountable, but we are interested in its measure. There are three cases: Case 1. X has zero Lebesgue measure. Case 2. X has positive Lebesgue measure. Case 3. X is not Lebesgue measurable. But I doubt that Case 3 applies, for otherwise we would have produced a nonmeasurable set X without AC -- which would render ZF+~AC (hence ZF by Cohen) inconsistent. So either Case 1 or Case 2 applies. If Case 1 holds, then Herc/Cooper would be right to say that the probability of choosing a real that can't be on the diagonal of the list of computable reals is _zero_. But I'm not sure how to decide this question. Let us start out by looking at some elements of X. From the argument involving 1/2 (0.111... in ternary) above, we know that any real whose ternary expansion contains only zeros and twos is in X. This is a well known set, the Cantor set, and it is uncountable yet has measure zero. For every computable real, the set of all reals with no digit in common with the given real (and thus must be in X) is also an uncountable null set (and the proof of this is similar to that for the Cantor set). There are only countably many computable reals, and the union of countably many null sets is still null. Thus, so far, the reals found to be in X still form a set of Lebesgue measure zero. Notice that X contains all computable reals. This is because for every computable real x, there exists another computable real y such that x and y have no digits in common. If x is in [0,1/2], consider y = x+1/2 or x+0.111..., where we add either 1 to each digit of x, or 2 if there's a carry. If x is in [1/2,1], we can consider y = x-1/2 = x-0.111... instead. But for the remaining reals (all of which must be uncomputable) having at least one digit in common with every real, there's still no guarantee that we can find a permutation of the list such that the target real lies on the diagonal. Suppose there's some real which has only one digit in common with a computable real -- let's call the diagonal d, call the computable real x, and say that the first digit is the common digit. Then x must appear first on the list. But then we can find another real with only the first digit in common with d -- namely y, where y = x+1/6 = x+0.0111... (unless this causes a carry in the first digit, in which case we consider y = x-1/6 = x-0.0.111... instead). Then y must also appear first on the list -- but evidently x and y can't both be first on the list! So every real with has only one digit in common with some computable real must be in X as well. Indeed, I suspect that every real which has only finitely many digits in common with some computable real must be in X as well. But by now, there might be so many reals in X that it is no longer null. |