Cantor's Diagonal?
in [Logic]
|
Prev: The set theoretic content of the transfinite recursion theorem
Next: Geometry surface area Contact; related to "flatness"; Pedestal-Geometry #386 Correcting Math
From: zuhair on 3 Feb 2010 07:05 On Feb 3, 6:35 am, "Jesse F. Hughes" <je...(a)phiwumbda.org> wrote: > Marshall <marshall.spi...(a)gmail.com> writes: > >> X= {<O,i>,<H,j>| i is an even natural, j is an odd natural} > > > Can you explain this a bit better? What is the sequence? > > What does <> mean? I would expect a "sequence" to be > > a mapping from the naturals to some target set. > > <,> is ordered pair. Just reverse the ordered pairs he wrote down and > you'll see what sequence he means: > > X = { <0,O>, <1,H>, <2,O>, .... } > > I assume he accidentally wrote the ordered pairs backwards. Yes, I already made this correction. Thanks. Zuhair > > > > >> so X is just an example of a infinite binary sequence. > > > I don't see how. > > -- > Jesse F. Hughes > "Philosophy, Socrates, if pursued in moderation and at the proper age, > is an elegant accomplishment, but too much philosophy is the ruin of > human life." -- Callicles, in "Gorgias"
From: zuhair on 3 Feb 2010 08:04 On Feb 3, 12:38 am, Tim Little <t...(a)little-possums.net> wrote: > On 2010-02-03, zuhair <zaljo...(a)gmail.com> wrote: > > > No, that is a different argument altogether from the Diagonal > > argument. I was speaking specifically about the Diagonal argument and > > not about the other proof, so don't mix the two arguments. > > I was trying to work out why you brought totally superfluous ordinals > into the discussion. > > > I showed that we CANNOT have a diagonal with w+1, the diagonal only > > works with sets that are isomorphic to w, this make this argument > > restricted and not general enough to conclude something like > > uncountability of the set of all infinite binary sequences. > > "X is uncountable" is defined as "there does not exist a surjection > from N to X". The diagonal argument shows that every function > f:N->2^N fails to be a surjection, which *by definition* proves that > 2^N is uncountable. The End. Well that is my question in first place isn't it? you just replied with an assertion, I don't see a proof? Let me put things to you in this way, since I think it would definitely be easier. To show that any set X is uncountable, you need the following: not Exist f ( f:X --> N, f is injective ). Now in the case were X is an infinite set , then the following is enough: not Exist f (f:N --> X, f is bijective) Now lets suppose that N is comparable to X, in other words, lets suppose there exist an injection from N to X, so in this case the following would be enough to prove that X is uncountable For all f ( (f:N-->X, f is injective) -> f is not surjective ). N in all the above is of course the set of all natural numbers. Now is their an injection from N to X were X is the set of all infinite binary sequences? The answer is yes. Simply anyone can see the following with the infinite binary sequences that have only one O at one entry and the rest is H letters for all other entries: 0 <-> O H H H H H............... 1 <-> H O H H H H............... 2<-> H H O H H H.............. .. .. .. .. so there is an injection from N to the set of all binary sequences that have one O letter in them. So there exist an injection from N to X, since the set of all binary sequences that have one O letter in them is a subset of X. Now all what we need is to prove that: For all f ( (f:N-->X, f is injective) -> f is not surjective ). in words, the requirement for proving the uncountablility of X is to prove that *ALL* injections from N to X are not surjective. The question is WERE is the SET of All injections from N to X in Cantor's Diagonal argument? I personally fail to see it. Clarification: when I am saying "All injections from N to X, I mean injections within the model of ZF and not outside it" Cantor's Diagonal argument is illustrating the set of all injections from N to X, that have a special kind of order, which is the following order(see my last reply to Arturo Magidin). (1) there is a starting member, i.e. a member that is not the successor of any member. (2) there is an immediate successor member for each member (3) Except the starting member every member have an immediate predecessor member.. (4) No two members have the same successor. So actually What Cantor's Diagonal is speaking of, is the following: All injections from N to X that has the above arrangement are not surjective. Which is true, since for these particular kind of injections we can always find a diagonal and the counter diagonal would be in X but not in the range any of these injections, thus they fail to be surjective. BUT my question here is that: the set of all injections from N to X that have the above arrangement is NOT the set of all injections (within the model of ZF) from N to X. We can have injections from N to X that has an arrangement similar to that of w+1 and higher ordinals, and for these kind of injections the Diagonal argument of Cantor's fail to show that they are not surjective, simply because we CANNOT define a diagonal for those functions. The way how I see matters, is that it appears to me that the Diagonal argument didn't succeed to prove that: For *all* f ( (f:N-->X, f is injective) -> f is not surjective ). it only proved it for *some* injective functions from N to X, but not for all of them. That's why I am saying that it failed to prove that *all injections from N to X are not surjections" because it is simply not speaking of all these injections. But it seems somehow that there must be a way to prove that if all injections from N to X in the above-mentioned order(see above) are not surjective, then every injection from N to X in any other order would also be not surjective! and it is this proof that I am looking for, since I don't see that directly from the presentation of the Diagonal argument. Do you know this proof? Zuhair > > - Tim
From: Tim Little on 3 Feb 2010 08:05 On 2010-02-03, Marshall <marshall.spight(a)gmail.com> wrote: > On Feb 2, 11:04 pm, zuhair <zaljo...(a)gmail.com> wrote: >> Lets put the 0 to the end of all natural numbers, so lets order N in >> the following manner >> >> N={1,2,3,.....,0 } > > That's not a sequence. It also makes no difference to the diagonal argument. The ordering of N makes no difference whatsoever to either the proof or the result, only in the pretty pictures one might draw to intuitively illustrate the proof. With that ordering, the pretty picture has a last row and last column. A sequence is nothing more or less than a function with domain N. A binary sequence is just a function with domain N and range {0,1}. The diagonal proof makes no use of any ordering that may or may not exist on N. It easily generalises to a proof that for any set A and any set B having at least two distinct elements, there is no surjection from A to B^A, regardless of whether either set is ordered or even *can be* ordered. - Tim
From: William Hughes on 3 Feb 2010 08:53 On Feb 3, 1:26 am, zuhair <zaljo...(a)gmail.com> wrote: > Cantor's claim is of *uncountability* of the set of all infinite > binary sequences, Correct. And to show this it is sufficient to show that there exists one countable set, Q, such that there is no bijection between the set of infinite binary sequences and Q. Note, if the arrangement of Q matters to our proof, then we can choose any arrangement we wish as if there there is no bijection to one arrangement of Q it is trivial to show that there is no bijection to any arrangement of Q. > so the matter is not limited to showing the failure > of that with a specific arrangement of a specific countable set > N. Incorrect. The general case follows trivially from this. You are correct that the diagonal argument does not apply (directly) to an arbitrary arrangement of N. So what? - William Hughes
From: Don Stockbauer on 3 Feb 2010 09:02
On Feb 3, 7:53 am, William Hughes <wpihug...(a)hotmail.com> wrote: > On Feb 3, 1:26 am, zuhair <zaljo...(a)gmail.com> wrote: > > > Cantor's claim is of *uncountability* of the set of all infinite > > binary sequences, > > Correct. And to show this it is sufficient to show > that there exists one countable set, Q, such that > there is no bijection between the set of infinite binary > sequences and Q. Note, if the arrangement of Q matters > to our proof, then we can choose any arrangement we wish > as if there there is no bijection to one arrangement of Q > it is trivial to show that there is no bijection to any > arrangement of Q. > > > so the matter is not limited to showing the failure > > of that with a specific arrangement of a specific countable set > N. > > Incorrect. The general case follows trivially > from this. > > You are correct that the diagonal argument does not > apply (directly) to an arbitrary arrangement of N. > > So what? > > - William Hughes "How I spent an infinite amount of time discussing infinity, when there were corn fields to hoe in Nebraska", by Wally Q. Fenderbasker. |