Cantor's Diagonal?
in [Math]
|
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.
From: James Burns on 3 Feb 2010 10:10 zuhair wrote: > On Feb 3, 12:39 am, Arturo Magidin <magi...(a)member.ams.org> wrote: >>On Feb 2, 11:26 pm, zuhair <zaljo...(a)gmail.com> wrote: >>Of course it is. If A is *any* countable set, then by definition there >>is a bijection f:A-->N. If t:A-->B is any map from A to the set of >>binary sequences, then since there is no bijection from N to B then tf^ >>{-1} (composing right to left) is not surjective. Since f^{-1} is >>bijective, nonsurjectivity of tf^{-1} implies that t is not >>surjective, thus proving that there can be no surjection from A to B >>either. [...] > Cantor's argument DOES show that every injection f from N to S > *provided that N is ordered in the natural way* and S is the set of > all infinite binary sequences, then f is not surjective. > > I have put an emphasis above on the clause "when N is ordered in the > natural way" > what I mean by that is N is ordered such that 0 is the first of all > members of N > then followed by 1 then followed by 2 then by 3 ,.... Look at Arturo Magidin's argument again, only substitute N', N with some arbitrary ordering, for the set A. (Is there a bijection between N' and N, you may ask. Yes: i: N' -> N, i(n) = n.) It's not clear what your objection to using the standard ordering is. It doesn't stop existing just because you have distracted your audience with some other arbitrary ordering. Jim Burns
From: MoeBlee on 3 Feb 2010 12:01
Zuhair, It seems to me that your problem here is that you are failing to understand the principle of universal generalization. I've been telling you for a long time that your lack of study of the predicate calculus is a huge gap in your studies. Two specific points: The issue is even simpler than you've presented: We know that if there is no surjection from N onto the set of denumerable binary sequences then there is no bijection from N onto the set of denumerable binary sequences. You agree with this, I surmise. So, to prove that there is no bijection from N onto the set of denumerable binary sequences, all we have left to do is prove that, for any f that is a function from N to the set of denumerable binary sequeces, we have that f is not a surjection onto the set of denumerable binary sequences. And we do this by talking about an ARBITRARY f that is a function from N to set of denumerable binary sequences, as we then prove (via Cantor's method) that for this ARBITRARY f, it is not a surjection onto the set of denumerable binary sequences. Thus, since we assumed NOTHING about this f other than what we know about ANY f that is a function from N to the set of denumerable binary sequences, we may conclude that there is NO f that is a surjection from N onto the set of denumerable binary sequences. And so we are FINISHED. PERIOD. Also, in this context, please forget about this thing about "models" that you keep referring to. It is only confusing you and is not immediately relevant to the very simple proof that N is uncountable. MoeBlee |