Re: Cantor's Diagonal
On Fri, Dec 21, 2007 at 01:08:38PM +0100, Günther Greindl wrote: Hi Russell, Russell Standish wrote: In your first case, the number (1,1,1,1...) is not a natural number, since it is infinite. In the second case, (0,0,0,...) is a natural number, but is also on the list (at infinity). Why is (1,1,1,...) not in the list but (0,0,0,...) in the list at infinity? This seems very arbitrary to me. Quentin replied correctly on the first point. On the second point, the list is assumed to contain all natural numbers. If that is true, the 0, which maps to the sequence (0,0,0...) must lie at infinity on the list. If you don't accept this, then the enumeration given is not an enumeration of the naturals, since 0 is then not on the list. Either way falsifies the argument. I am becoming more and more an ultra-finitist. Arguments with infinity seem to be very based on the assumptions you make (about platonia or whatever) Regards, Günther -- Günther Greindl Department of Philosophy of Science University of Vienna [EMAIL PROTECTED] http://www.univie.ac.at/Wissenschaftstheorie/ Blog: http://dao.complexitystudies.org/ Site: http://www.complexitystudies.org -- A/Prof Russell Standish Phone 0425 253119 (mobile) Mathematics UNSW SYDNEY 2052 [EMAIL PROTECTED] Australiahttp://www.hpcoders.com.au --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to [EMAIL PROTECTED] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: Cantor's Diagonal
Hi, Because zero even repeated an infinity of time is zero and is a natural number. (1,1,1,...) can't be a natural number because it is not finite and a natural number is finite. If it was a natural number, then N would not have a total ordering. Ok agreed: I was caught up in viewing it simply as an indexing scheme, but viewed constructively I of course agree. My error. I am becoming more and more an ultra-finitist. Arguments with infinity seem to be very based on the assumptions you make (about platonia or whatever) Finite and infinite concepts are dual concepts you can't leave one without leaving the other. Could you elaborate some more on this? Regards, Günther -- Günther Greindl Department of Philosophy of Science University of Vienna [EMAIL PROTECTED] http://www.univie.ac.at/Wissenschaftstheorie/ Blog: http://dao.complexitystudies.org/ Site: http://www.complexitystudies.org --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to [EMAIL PROTECTED] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: Cantor's Diagonal
Hi, Le Friday 21 December 2007 13:08:38 Günther Greindl, vous avez écrit : Hi Russell, Russell Standish wrote: In your first case, the number (1,1,1,1...) is not a natural number, since it is infinite. In the second case, (0,0,0,...) is a natural number, but is also on the list (at infinity). Why is (1,1,1,...) not in the list but (0,0,0,...) in the list at infinity? This seems very arbitrary to me. Because zero even repeated an infinity of time is zero and is a natural number. (1,1,1,...) can't be a natural number because it is not finite and a natural number is finite. If it was a natural number, then N would not have a total ordering. I am becoming more and more an ultra-finitist. Arguments with infinity seem to be very based on the assumptions you make (about platonia or whatever) Finite and infinite concepts are dual concepts you can't leave one without leaving the other. Regards, Günther Regards, Quentin Anciaux -- All those moments will be lost in time, like tears in rain. --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to [EMAIL PROTECTED] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: Cantor's Diagonal
Hi Russell, Russell Standish wrote: In your first case, the number (1,1,1,1...) is not a natural number, since it is infinite. In the second case, (0,0,0,...) is a natural number, but is also on the list (at infinity). Why is (1,1,1,...) not in the list but (0,0,0,...) in the list at infinity? This seems very arbitrary to me. I am becoming more and more an ultra-finitist. Arguments with infinity seem to be very based on the assumptions you make (about platonia or whatever) Regards, Günther -- Günther Greindl Department of Philosophy of Science University of Vienna [EMAIL PROTECTED] http://www.univie.ac.at/Wissenschaftstheorie/ Blog: http://dao.complexitystudies.org/ Site: http://www.complexitystudies.org --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to [EMAIL PROTECTED] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: Cantor's Diagonal
Le 19-déc.-07, à 21:09, Barry Brent a écrit : Excellent, Bruno, Thanks! Well thanks. I will send a next diagonalization post and some references next week, Best, Bruno http://iridia.ulb.ac.be/~marchal/ --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to [EMAIL PROTECTED] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: Cantor's Diagonal
Hi Barry, Le 18-déc.-07, à 18:52, Barry Brent a écrit : Bruno-- Ahh, my amateur status is nakedly exposed. I'm going to expose my confusion even further now. That is the courageous attitude of the authentic scientists. I like amateur because they have less prejudices, they have inner motivations, and rarely follow authoritative arguments. Never heard of a universal language. I thought I was familiar with Church's thesis, but apparently no. As I said a while ago, coming back from an international meeting on computability (in Siena, where my Plotinus' paper has been accepted), I got the feeling that few people really grasp Church Thesis, including some experts. My Brussels thesis has been criticized for being too much pedagogical on Church thesis, but each time people try to debunk my work, soon enough I realize they have a problem with Godel or Church, never (yet) with my contribution. The worst is that most people *feel* at ease with CT but apparently are not. I take as an honor to explain this too you, I *do* appreciate your work in Number Theory, as far as I understand it. Possible links could emerge. (You make me discover also the nice paper on prime percolation by Vardi: I love percolation. Not just because I am an amateur of good coffe, but because exact percolation problem have led to the Temperley Lieb algebra/category; which makes links between knot theory, combinators/lambda-calculus, quantum computations, and eventually number theory, if not the number 24 itself). I thought it was the claim that two or three or four concepts (including recursive function and computable function) were extensionally equivalent. I have heard of the lambda calculus, but I don't know what it is, or what its connection is with Church's thesis. I have a rough guess, based on what you're saying. I'm surprised. I imagine that the claim of existence of a universal language must be made in the context of a theory of languages? Never heard of that theory. This happens because the expression theory of languages is used in the context of non universal languages, like in the Chomsky hierarchy of languages for example. Universal languages and machines appears in what is called computability theory or recursion theory. Well, if I imagine such a theory, it must involve both syntax and semantics, yes? Semantics connects a language to a world, right? (The experts are cringing, I'm sure) Can one language encompass all possible worlds? Can't we imagine worlds, the structures of which are so dissonant, that their languages could never be consistently subsumed under some single larger (universal) language? (More cringing, no doubt) Or, is it that when we restrict the worlds in question to some suitable realm--say, numbers-- all these things work out? (Cringes redoubled!) I can imagine other ways out. Maybe we're concerned with just one world, suitably described. Maybe structural inconsistencies of possible worlds are no more an impediment to being expressible in one language than logical inconsistencies? (But how do we know?) We have to distinguish logic and computability. In logic we will have language in which sentences are to be interpreted in some world/model. But in computability we can go very far by just interpreting them in some procedural way. The expressions in computer language are really basic instruction like in the coffee-bar machine. Eventually we can describe them all in term of NAND gates, delay and electrical current. A computing language is then universal if all computable functions (from N to N, or from finite things coded in N to finite things coded in N) can be computed by following a finite set of instructions in the language. What about cardinality? From your remarks, I imagine that the number of elementary symbols in any language, including the universal language, is supposed to be finite, Yes. so that the set of algorithms is countable? Yes. And so are the computable functions. If there are lots of worlds and languages, I wonder how people make that work. Because all the languages or machines which have been invented for computing (computable) functions from N to N, have been shown equivalent, and that the closure of the set of computable functions by those machines, for the (transcendental) diagonalization procedure, give a powerful argument that those language/machine are universal. Careful: they are universal with respect to the class of computable functions. They are not universal with respect to the propositions they can express or prove. A universal language/machine is not a theory. Most universal language don't even have a way to assert propositions, just some sort of commands (cf the coffee-bar instructions as example). Is such a language going to be adequate for expressing propositions about all possible worlds? How do we know? In computing, well ... like in Number theory,
Re: Cantor's Diagonal
Excellent, Bruno, Thanks! Barry On Dec 19, 2007, at 7:57 AM, Bruno Marchal wrote: Hi Barry, Le 18-déc.-07, à 18:52, Barry Brent a écrit : Bruno-- Ahh, my amateur status is nakedly exposed. I'm going to expose my confusion even further now. That is the courageous attitude of the authentic scientists. I like amateur because they have less prejudices, they have inner motivations, and rarely follow authoritative arguments. Never heard of a universal language. I thought I was familiar with Church's thesis, but apparently no. As I said a while ago, coming back from an international meeting on computability (in Siena, where my Plotinus' paper has been accepted), I got the feeling that few people really grasp Church Thesis, including some experts. My Brussels thesis has been criticized for being too much pedagogical on Church thesis, but each time people try to debunk my work, soon enough I realize they have a problem with Godel or Church, never (yet) with my contribution. The worst is that most people *feel* at ease with CT but apparently are not. I take as an honor to explain this too you, I *do* appreciate your work in Number Theory, as far as I understand it. Possible links could emerge. (You make me discover also the nice paper on prime percolation by Vardi: I love percolation. Not just because I am an amateur of good coffe, but because exact percolation problem have led to the Temperley Lieb algebra/category; which makes links between knot theory, combinators/lambda-calculus, quantum computations, and eventually number theory, if not the number 24 itself). I thought it was the claim that two or three or four concepts (including recursive function and computable function) were extensionally equivalent. I have heard of the lambda calculus, but I don't know what it is, or what its connection is with Church's thesis. I have a rough guess, based on what you're saying. I'm surprised. I imagine that the claim of existence of a universal language must be made in the context of a theory of languages? Never heard of that theory. This happens because the expression theory of languages is used in the context of non universal languages, like in the Chomsky hierarchy of languages for example. Universal languages and machines appears in what is called computability theory or recursion theory. Well, if I imagine such a theory, it must involve both syntax and semantics, yes? Semantics connects a language to a world, right? (The experts are cringing, I'm sure) Can one language encompass all possible worlds? Can't we imagine worlds, the structures of which are so dissonant, that their languages could never be consistently subsumed under some single larger (universal) language? (More cringing, no doubt) Or, is it that when we restrict the worlds in question to some suitable realm--say, numbers-- all these things work out? (Cringes redoubled!) I can imagine other ways out. Maybe we're concerned with just one world, suitably described. Maybe structural inconsistencies of possible worlds are no more an impediment to being expressible in one language than logical inconsistencies? (But how do we know?) We have to distinguish logic and computability. In logic we will have language in which sentences are to be interpreted in some world/model. But in computability we can go very far by just interpreting them in some procedural way. The expressions in computer language are really basic instruction like in the coffee-bar machine. Eventually we can describe them all in term of NAND gates, delay and electrical current. A computing language is then universal if all computable functions (from N to N, or from finite things coded in N to finite things coded in N) can be computed by following a finite set of instructions in the language. What about cardinality? From your remarks, I imagine that the number of elementary symbols in any language, including the universal language, is supposed to be finite, Yes. so that the set of algorithms is countable? Yes. And so are the computable functions. If there are lots of worlds and languages, I wonder how people make that work. Because all the languages or machines which have been invented for computing (computable) functions from N to N, have been shown equivalent, and that the closure of the set of computable functions by those machines, for the (transcendental) diagonalization procedure, give a powerful argument that those language/machine are universal. Careful: they are universal with respect to the class of computable functions. They are not universal with respect to the propositions they can express or prove. A universal language/machine is not a theory. Most universal language don't even have a way to assert propositions, just some sort of commands (cf the coffee-bar instructions as example).
Re: Cantor's Diagonal
Le 17-déc.-07, à 19:04, meekerdb (Brent Meeker) wrote: Bruno wrote: Exercise: What is wrong with the following argument. (I recall that by definition a function from N to N is defined on all natural numbers). (false) theorem: the set of computable functions from N to N is not enumerable. (erroneous) proof: let us suppose (by absurdum) that the set of computable functions from N to N is enumerable. Thus there exist an enumeration f_1, f_2, f_3, ... f_i, of the computable functions from N to N. But then I can define the following computable function g, from N to N, by: g(n) = f_n(n) + 1 g is computable: to compute it just search in the enumeration the function f_n, which is computable, and then apply it on n, and then add 1. But then g has to be in that enumeration f_i of the computable function. Thus there is a k such that g = f_k. In particular g(k) = f_k(k). But g(k) = f_k(k) + 1, by definition of g. Thus f_k(k) = f_k(k)+1. And the f_i are computable functions, so f_k(k) is a well defined number, which I can subtract on the left and the right side of f_k(k) = f_k(k)+1, giving 0 = 1. Contradiction. So the set of computable functions from N to N is not enumerable. What is wrong? We know that the set of computable function has to be enumerable, because computable means we can describe how to compute the function in a finite expression in some language, and the set of all finite expressions has been shown enumerable. So what happens? If you tried to compute g(k) and g was in the list, i.e. some f_k, then when you searched a for g, when you came to f_k it would start with the prescription ...just search in the enumeration... and you would be in a infinite loop. This is a bit fuzzy, but then the exercise was a bit fuzzy too, so I can considered this as correct. More below. Barry Brent wrote: Brent, I don't think this is enough. There may be a different algorithm for f_k that escapes your infinite loop. If this alternative algoritm doesn't exist, I think you need to show that it doesn't exist. I suspect that the error in Bruno's erroneous proof has to do with formal languages. Say a function f is computable with regard to a formal language L when there exists an algorithm written in L to compute f. The f_n are computable with regard to some particular formal language. Functions computable with regard to one language may or may not be computable with regard to another language. (If this is false, Bruno needs to prove it's false.) Thus when Bruno argues that the set of computable functions is enumerable, he must mean for any fixed language L, the functions computable with regard to L is enumerable. Now the procedure Bruno described for computing g is not written in a formal language--it's written in English. The fact that this English language description is finite doesn't prove that g is computable with regard to L, ie, doesn't prove that g is one of the f_n. I'm an amateur at this--this solution is really just a question for Bruno... Barry (Barry Brent, not Brent Meeker!) Now, if this comment was correct, it would mean that universal languages or universal machines would not exist! Actually, I can also take this remark as a correct conclusion, but only by considering a restricted notion of universal machines or language. Barry, are you actually denying Church Thesis (which says that an universal language exists, indeed LAMBDA-CALCULUS is one!) ? Barry Brent, Brent Meeker, you are both correct, individually, but you cannot be both correct simultaneously, so what? I let you and others think a bit more, for the fun of it, for the importance of being 100% clear on this before proceeding, and because I have not the time to say more today. Don't worry, even the biggest one like Godel, Kleene, Church ... all have been wrong on this at some moment. It *is* a bit subtle. But all the possibility of my work, or more generally, the very consistency of comp relies on that subtlety. Only after a good understanding on this, will I be able to come back on less technical explanation. If I explain things non technically to soon I will have the feeling to take you in a boat (we say in French), meaning roughly to be dishonest. It is worth to take the time, and to play a bit with the idea, right? Bruno PS I know also, for having explained this years ago in the list that some in the list does understand what happen here, but I encourage them to go through the reasoning again, because I am not sure they did understand the *impact* of this It is one thing to understand a proposition, and another thing to get the importance, relatively to the TOE search of what is really going on here ... In particular, when the ASSA people invoke Kolmogorov complexity notions, they do rely on Church Thesis The key post is a key for everybody, I mean for both ASSA and RSSA type of TOE researchers.
Re: Cantor's Diagonal
Bruno-- Ahh, my amateur status is nakedly exposed. I'm going to expose my confusion even further now. Never heard of a universal language. I thought I was familiar with Church's thesis, but apparently no. I thought it was the claim that two or three or four concepts (including recursive function and computable function) were extensionally equivalent. I have heard of the lambda calculus, but I don't know what it is, or what its connection is with Church's thesis. I have a rough guess, based on what you're saying. I'm surprised. I imagine that the claim of existence of a universal language must be made in the context of a theory of languages? Never heard of that theory. Well, if I imagine such a theory, it must involve both syntax and semantics, yes? Semantics connects a language to a world, right? (The experts are cringing, I'm sure) Can one language encompass all possible worlds? Can't we imagine worlds, the structures of which are so dissonant, that their languages could never be consistently subsumed under some single larger (universal) language? (More cringing, no doubt) Or, is it that when we restrict the worlds in question to some suitable realm--say, numbers-- all these things work out? (Cringes redoubled!) I can imagine other ways out. Maybe we're concerned with just one world, suitably described. Maybe structural inconsistencies of possible worlds are no more an impediment to being expressible in one language than logical inconsistencies? (But how do we know?) What about cardinality? From your remarks, I imagine that the number of elementary symbols in any language, including the universal language, is supposed to be finite, so that the set of algorithms is countable? If there are lots of worlds and languages, I wonder how people make that work. Is such a language going to be adequate for expressing propositions about all possible worlds? How do we know? My poor excuse is, I've only been on this list a little while, and I made my (sketchy) acquaintance with these ideas a very long time ago. Sorry if I'm way off topic. Tell me to go look it up somewhere, or stop wasting time, if you want to... Barry Brent On Dec 18, 2007, at 8:49 AM, Bruno Marchal wrote: Le 17-déc.-07, à 19:04, meekerdb (Brent Meeker) wrote: Bruno wrote: Exercise: What is wrong with the following argument. (I recall that by definition a function from N to N is defined on all natural numbers). (false) theorem: the set of computable functions from N to N is not enumerable. (erroneous) proof: let us suppose (by absurdum) that the set of computable functions from N to N is enumerable. Thus there exist an enumeration f_1, f_2, f_3, ... f_i, of the computable functions from N to N. But then I can define the following computable function g, from N to N, by: g(n) = f_n(n) + 1 g is computable: to compute it just search in the enumeration the function f_n, which is computable, and then apply it on n, and then add 1. But then g has to be in that enumeration f_i of the computable function. Thus there is a k such that g = f_k. In particular g(k) = f_k(k). But g(k) = f_k(k) + 1, by definition of g. Thus f_k(k) = f_k(k)+1. And the f_i are computable functions, so f_k(k) is a well defined number, which I can subtract on the left and the right side of f_k(k) = f_k(k)+1, giving 0 = 1. Contradiction. So the set of computable functions from N to N is not enumerable. What is wrong? We know that the set of computable function has to be enumerable, because computable means we can describe how to compute the function in a finite expression in some language, and the set of all finite expressions has been shown enumerable. So what happens? If you tried to compute g(k) and g was in the list, i.e. some f_k, then when you searched a for g, when you came to f_k it would start with the prescription ...just search in the enumeration... and you would be in a infinite loop. This is a bit fuzzy, but then the exercise was a bit fuzzy too, so I can considered this as correct. More below. Barry Brent wrote: Brent, I don't think this is enough. There may be a different algorithm for f_k that escapes your infinite loop. If this alternative algoritm doesn't exist, I think you need to show that it doesn't exist. I suspect that the error in Bruno's erroneous proof has to do with formal languages. Say a function f is computable with regard to a formal language L when there exists an algorithm written in L to compute f. The f_n are computable with regard to some particular formal language. Functions computable with regard to one language may or may not be computable with regard to another language. (If this is false, Bruno needs to prove it's false.) Thus when Bruno argues that the set of computable functions is enumerable, he must mean for any fixed language L, the functions
Re: Cantor's Diagonal
Hi Daniel,
I agree with Barry, but apaprently you have still a problem, so I
comment your posts.
Le 16-déc.-07, à 10:49, Daniel Grubbs a écrit :
Hi Folks,
I joined this list a while ago but I haven't really kept up. Anyway,
I saw the reference to Cantor's Diagonal and thought perhaps someone
could help me.
Consider the set of positive integers: {1,2,3,...}, but rather than
write them in this standard notation we'll use what I'll call 'prime
notation'.
OK. That is often used to compare the purely additive and the purely
multiplicative structures of the natural numbers. Of course the number
0 is banished in the multiplicative structure (so you have to handle 0
manualy, but that does not change the enumeration question, ok).
Here, the number m may be written as
m = n1,n2,n3,n4,...
1 = 0,0,0,0,0,...
2 = 1,0,0,0,0,...
3 = 0,1,0,0,0,...
4 = 2,0,0,0,0,...
5 = 0,0,1,0,0,...
...
28 = 2,0,0,1,0,0,0,...
...
D = 1,1,1,1,1,...
I can see that one may complain that D is clearly infinite and
therefore should not be in the set, ...
Yes. D does not describe a natural number.
... but consider the following...
Let's take the original set and reorder it by exchanging the places
of the i'th prime number with that of the number in the i'th
position. (i.e. First switch the number 2 with the number 1 to move
it to the first position. Then switch 3 with the number -- now 1 -- in
the 2nd position. Then 5 with the 1 which is now in the 3rd position.
Etc...) Because we are just trading the positions of the numbers, all
the same numbers will be in the set afterwards.
The set is now:
2 = 1,0,0,0,0,...
3 = 0,1,0,0,0,...
5 = 0,0,1,0,0,...
7 = 0,0,0,1,0,...
11= 0,0,0,0,1,...
...
What does ... mean here? It seems to me you are just enumerating the
prime numbers. At which step will you put the numbers 1, 4, 6, etc.
If you do have a way to add, in the limit, those numbers in the set,
then you are just constructing an order type (ordinal) bigger than
omega on the set of positive integers. But such constructive) ordinal
are all enumerable.
You could have said directly: let us consider the following order: it
is the usual order except that we decide that all even numbers are
bigger than the odd numbers, so we have the order:
1, 3, 5, 7, 9, 2, 4, 6, 8, 10,
This is an example of order type OMEGA+OMEGA
So what? We can easily enumerate it by zigzagging between the even and
odd numbers.
D = 0,0,0,0,...
I would suggest that the diagonal method does not find a number which
is different from all the members of a set, but rather finds a number
which is infinitely far out in the ordered set.
Like I say. Your construction put a bigger, but still enumerable, order
on N. Actually we have already used diagonalization for building
constructive ordinal, or order type on the set of computable growing
functions. But those produce enumerable sets.
If anyone can find where I've gone wrong, please let me know.
Cantor showed that ALL tentative enumeration of some set S fails. This
is what makes that set S non enumerable. You are just showing that the
diagonal method can also work on some precise enumeration on N. This
does not make N non enumerable, it makes only your precise enumeration
incomplete (or extendible in the constructive ordinal, but that does
not change anything).
A set is non enumerable if ALL attempts to enumerate it fail, not if
some particular attempt fails. That is why we do a proof by a reductio
ad absurdo.
In you next post you say (to Barry):
Let me see if I am clear about Cantor's method. Given a set S, and
some enumeration of that set
Well S is fixed. It is the set we want to show being NOT enumerable.
Then you take not some enumeration, but ANY enumeration.
(i.e., a no one-one onto map from Z^+ to S) we can use the
diagonalization method to find an D which is a valid element of S but
is different from any particular indexed element in the enumeration.
... is different from any particular indexed element, for any arbitrary
enumeration. You have to be sure that the diagonal will work whatever
enumeration is proposed.
Cantor's argument then goes on to say (and here is where I disagree
with it) that therefore D is not included in the enumeration and the
enumeration is incomplete.
I, on the other hand, would posit that the enumeration may include
elements whose index is not well defined.
H In Cantor's proof of the non enumerability of 2^N (the set of
infinite binary sequences), the indexes are all perfectly well defined
even if it is in Platonia or in the mind of God, so your remark does
not apply.
But now, curiously enough, a remark similar to your's can be done about
the proof that the (total) computable functions from N to N are not
*computably* enumerable.
In that case, if we assume Church thesis, and thus the existence of a
universal
Re: Cantor's Diagonal
Hi.
Bruno could do this better, but I like the practice.
I guess you're trying to demonstrate that the form of Cantor's
argument is invalid, by displaying an example in which it produces an
absurd result.
Start with a set S you want to show is not enumerable. (ie, there is
no one-one onto map from Z^+ to S). The form of the diagonalization
argument is as follows: give me any, repeat, any, particular
candidate for an enumeration of S. This should be a map from Z^+
into S. (If it isn't such a map, it isn't an enumeration.) I will
show you an element D of S that your candidate enumeration omits.
(That is, I will show you that your candidate is not onto.) Hence, S
is not denumerable.
In your first attempt, your D is not an element of your S (= Z^+).
So your first attempt doesn't fit the form of the diagonalization
argument on this account. More fundamentally, it also fails to fit
the form of Cantor's argument because you haven't tried to debunk
*any* candidate enumeration, but a particular one.
In your second attempt, if I understand you, you start with a map
from the primes (all of them!) and then (your work suggests, but I
think you'd need more details--what's the image of 4, for example?)
from the rest of Z^+, into S = Z^+ again. This example doesn't
invalidate Cantor's argument either. Again, you debunk a particular
candidate enumeration, not any and all candidate enumerations. So
you don't arrive at the absurdity you seem to be after, even if you
fill in the details I mentioned.
Barry
On Dec 16, 2007, at 3:49 AM, Daniel Grubbs wrote:
Hi Folks,
I joined this list a while ago but I haven't really kept up.
Anyway, I saw the reference to Cantor's Diagonal and thought
perhaps someone could help me.
Consider the set of positive integers: {1,2,3,...}, but rather than
write them in this standard notation we'll use what I'll call
'prime notation'. Here, the number m may be written as
m = n1,n2,n3,n4,...
where ni is the number of times the i'th prime number is a factor
of m. Thus:
1 = 0,0,0,0,0,...
2 = 1,0,0,0,0,...
3 = 0,1,0,0,0,...
4 = 2,0,0,0,0,...
5 = 0,0,1,0,0,...
...
28 = 2,0,0,1,0,0,0,...
...
If we now apply the diagonal method to this ordered set, we get the
number:
D = 1,1,1,1,1,...
Has this just shown that the set of positive integers is not
denumerable?
I can see that one may complain that D is clearly infinite and
therefore should not be in the set, but consider the following...
Let's take the original set and reorder it by exchanging the places
of the i'th prime number with that of the number in the i'th
position. (i.e. First switch the number 2 with the number 1 to
move it to the first position. Then switch 3 with the number -- now
1 -- in the 2nd position. Then 5 with the 1 which is now in the 3rd
position. Etc...) Because we are just trading the positions of the
numbers, all the same numbers will be in the set afterwards.
The set is now:
2 = 1,0,0,0,0,...
3 = 0,1,0,0,0,...
5 = 0,0,1,0,0,...
7 = 0,0,0,1,0,...
11= 0,0,0,0,1,...
...
Now instead of adding 1 to each 'digit' of the diagonal, subtract
1. This will ensure that the diagonal number is different from
each of the numbers in the set. Thus,
D = 0,0,0,0,...
But this is the number 1 which we know was in the set to begin
with. What happened to it?
I would suggest that the diagonal method does not find a number
which is different from all the members of a set, but rather finds
a number which is infinitely far out in the ordered set.
If anyone can find where I've gone wrong, please let me know.
Dan Grubbs
Dr. Barry Brent
[EMAIL PROTECTED]
http://home.earthlink.net/~barryb0/
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Everything List group.
To post to this group, send email to [EMAIL PROTECTED]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups.google.com/group/everything-list?hl=en
-~--~~~~--~~--~--~---
Re: Cantor's Diagonal
On Sun, Dec 16, 2007 at 04:49:34AM -0500, Daniel Grubbs wrote: Cantor's argument only works by finding a number that satisfies the criteria for inclusion in the list, yet is nowhere to be found in the list. In your first case, the number (1,1,1,1...) is not a natural number, since it is infinite. In the second case, (0,0,0,...) is a natural number, but is also on the list (at infinity). Therefore Cantor's argument doesn't work in these cases. Cheers -- A/Prof Russell Standish Phone 0425 253119 (mobile) Mathematics UNSW SYDNEY 2052 [EMAIL PROTECTED] Australiahttp://www.hpcoders.com.au --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to [EMAIL PROTECTED] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: Cantor's Diagonal
Hi Barry,
Let me see if I am clear about Cantor's method. Given a set S, and
some enumeration of that set (i.e., a no one-one onto map from Z^+ to
S) we can use the diagonalization method to find an D which is a valid
element of S but is different from any particular indexed element in
the enumeration.
Cantor's argument then goes on to say (and here is where I disagree
with it) that therefore D is not included in the enumeration and the
enumeration is incomplete.
I, on the other hand, would posit that the enumeration may include
elements whose index is not well defined. For example, 1 or 4 in my
second example. They were in the enumeration prior to its being
shuffled, and always had a definite position during the process. They
must still be in there, with definite positions, despite the fact that
their indices are now infinite and ill-defined.
If the diagonalization process does not produce the proffered result in
this case (i,e., it does not prove that the element D is not included
in the enumeration) then it does not prove it in any case. The number
D found with this method may actually be in the enumeration, but with
an ill-defined index.
Dan
Barry Brent wrote:
Hi.
Bruno could do this better, but I like the practice.
I guess you're trying to demonstrate that the form of Cantor's
argument is invalid, by displaying an example in which it produces an
absurd result.
Start with a set S you want to show is not enumerable. (ie, there is
no one-one onto map from Z^+ to S). The form of the diagonalization
argument is as follows: give me any, repeat, any, particular
candidate for an enumeration of S. This should be a map from Z^+
into S. (If it isn't such a map, it isn't an enumeration.) I will
show you an element D of S that your candidate enumeration omits.
(That is, I will show you that your candidate is not onto.) Hence, S
is not denumerable.
In your first attempt, your D is not an element of your S (= Z^+).
So your first attempt doesn't fit the form of the diagonalization
argument on this account. More fundamentally, it also fails to fit
the form of Cantor's argument because you haven't tried to debunk
*any* candidate enumeration, but a particular one.
In your second attempt, if I understand you, you start with a map
from the primes (all of them!) and then (your work suggests, but I
think you'd need more details--what's the image of 4, for example?)
from the rest of Z^+, into S = Z^+ again. This example doesn't
invalidate Cantor's argument either. Again, you debunk a particular
candidate enumeration, not any and all candidate enumerations. So
you don't arrive at the absurdity you seem to be after, even if you
fill in the details I mentioned.
Barry
On Dec 16, 2007, at 3:49 AM, Daniel Grubbs wrote:
Hi Folks,
I joined this list a while ago but I haven't really kept up.
Anyway, I saw the reference to Cantor's Diagonal and thought
perhaps someone could help me.
Consider the set of positive integers: {1,2,3,...}, but rather than
write them in this standard notation we'll use what I'll call
'prime notation'. Here, the number m may be written as
m = n1,n2,n3,n4,...
where ni is the number of times the i'th prime number is a factor
of m. Thus:
1 = 0,0,0,0,0,...
2 = 1,0,0,0,0,...
3 = 0,1,0,0,0,...
4 = 2,0,0,0,0,...
5 = 0,0,1,0,0,...
...
28 = 2,0,0,1,0,0,0,...
...
If we now apply the diagonal method to this ordered set, we get the
number:
D = 1,1,1,1,1,...
Has this just shown that the set of positive integers is not
denumerable?
I can see that one may complain that D is clearly infinite and
therefore should not be in the set, but consider the following...
Let's take the original set and reorder it by exchanging the places
of the i'th prime number with that of the number in the i'th
position. (i.e. First switch the number 2 with the number 1 to
move it to the first position. Then switch 3 with the number -- now
1 -- in the 2nd position. Then 5 with the 1 which is now in the 3rd
position. Etc...) Because we are just trading the positions of the
numbers, all the same numbers will be in the set afterwards.
The set is now:
2 = 1,0,0,0,0,...
3 = 0,1,0,0,0,...
5 = 0,0,1,0,0,...
7 = 0,0,0,1,0,...
11= 0,0,0,0,1,...
...
Now instead of adding 1 to each 'digit' of the diagonal, subtract
1. This will ensure that the diagonal number is different from
each of the numbers in the set. Thus,
D = 0,0,0,0,...
But this is the number 1 which we know was in the set to begin
with. What happened to it?
I would suggest that the diagonal method does not find a number
which is different from all the members of a set, but rather finds
a number which is infinitely far out in the ordered set.
If anyone can find where I've gone wrong, please let me know.
Dan Grubbs
Dr. Barry Brent
[EMAIL PROTECTED]
http://home.earthlink.net/~barryb0/
--~--~-~--~~~---~--~~
Re: Cantor's Diagonal
Hi Dan, Let me take your statements a few at a time. Let me see if I am clear about Cantor's method. Given a set S, and some enumeration of that set (i.e., a no one-one onto map from Z^+ to S) we can use the diagonalization method to find an D which is a valid element of S but is different from any particular indexed element in the enumeration. Not given a set S and *some* enumeration... but given a set S and *any candidate for an enumeration*... The idea is to show that no candidate for an enumeration succeeds, hence the set S has no enumeration, hence the set S is not enumerable. we can use the diagonalization method to find an D which is a valid element of S but is different from any particular indexed element in the enumeration. Yes. Cantor's argument then goes on to say (and here is where I disagree with it) that therefore D is not included in the enumeration and the enumeration is incomplete. Yes, except for your disagreement with it One step of Cantor's argument is to show, for a given candidate enumeration of S, that some D in S is different from every single enumerated member of S. If you can't show this for some particular candidate enumeration, you haven't done a Cantor diagonalization argument that encompasses the candidate enumeration. To do a successful Cantor diagonalization argument, you must show that some D in S is different from every single enumerated member of S, for each candidate enumeration of S. The value of D will typically depend on the candidate. I, on the other hand, would posit that the enumeration may include elements whose index is not well defined. For example, 1 or 4 in my second example. They were in the enumeration prior to its being shuffled, and always had a definite position during the process. They must still be in there, with definite positions, despite the fact that their indices are now infinite and ill-defined. I don't need to parse this shuffling enumeration to say that what you're doing is not an instance of Cantor's argument. Any instance of Cantor's argument will debunk, not just one candidate shuffling enumeration, to take your example, but each and every candidate enumeration. And you haven't even debunked the shuffling enumeration. In fact you're arguing that it's valid (it seems to me.) If the diagonalization process does not produce the proffered result in this case (i,e., it does not prove that the element D is not included in the enumeration) then it does not prove it in any case. The number D found with this method may actually be in the enumeration, but with an ill-defined index. A defender of the validity of the form of Cantor's argument doesn't *want* to use it to prove that Z^+ has no enumeration. To do so would be to fall into the paradox you're trying to construct. So it's perfectly fine if the diagonalization process does not produce the proffered result in this case. Barry On Dec 16, 2007, at 9:09 PM, Daniel Grubbs wrote: Hi Barry, Let me see if I am clear about Cantor's method. Given a set S, and some enumeration of that set (i.e., a no one-one onto map from Z^+ to S) we can use the diagonalization method to find an D which is a valid element of S but is different from any particular indexed element in the enumeration. Cantor's argument then goes on to say (and here is where I disagree with it) that therefore D is not included in the enumeration and the enumeration is incomplete. I, on the other hand, would posit that the enumeration may include elements whose index is not well defined. For example, 1 or 4 in my second example. They were in the enumeration prior to its being shuffled, and always had a definite position during the process. They must still be in there, with definite positions, despite the fact that their indices are now infinite and ill-defined. If the diagonalization process does not produce the proffered result in this case (i,e., it does not prove that the element D is not included in the enumeration) then it does not prove it in any case. The number D found with this method may actually be in the enumeration, but with an ill-defined index. Dan Dr. Barry Brent [EMAIL PROTECTED] http://home.earthlink.net/~barryb0/ --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to [EMAIL PROTECTED] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: Cantor's Diagonal
Le 03-déc.-07, à 16:56, David Nyman a écrit :
On Nov 20, 4:40 pm, Bruno Marchal [EMAIL PROTECTED] wrote:
Conclusion: 2^N, the set of infinite binary sequences, is not
enumerable.
All right?
OK. I have to try to catch up now, because I've had to be away longer
than I expected, but I'm clear on this diagonal argument.
OK. I hope you have done the exercise below, which consists to show
that N^N is also not enumerable. It is the same reasoning, of course.
(Of course it is also a consequence of the non enumerability of 2^N,
because 2^N is included in N^N, but in the exercise I was asking for a
direct diagonal argument).
You can look at the solution:
http://www.mail-archive.com/everything-list@eskimo.com/msg14063.html
I will send the key post asap. It is written, but I am currently
hesitating to add more explanations, but sometimes when I do that, I
introduce just more confusion. I guess I will send some part so that
you have something to think about (of 'course I don't doubt you have
many things to think about ...).
Bruno
===
Hi,
David, are you still there? This is a key post, with respect to the
Church Thesis thread.
So let us see that indeed there is no bijection between N and 2^N =
2X2X2X2X2X2X... = {0,1}X{0,1}X{0,1}X{0,1}X... = the set of infinite
binary sequences.
Suppose that there is a bijection between N and the set of infinite
binary sequences. Well, it will look like that, where again
represents the ropes:
0 -- (1, 0, 0, 1, 1, 1, 0 ...
1 -- (0, 0, 0, 1, 1, 0, 1 ...
2 --- (0, 1, 0, 1, 0, 1, 1, ...
3 --- (1, 1, 1, 1, 1, 1, 1, ...
4 --- (0, 0, 1, 0, 0, 1, 1, ...
5 (0, 0, 0, 1, 1, 0, 1, ...
...
My sheep are the natural numbers, and my neighbor's sheep are the
infinite binary sequences (the function from N to 2, the elements of
the infinite cartesian product 2X2X2X2X2X2X... ).
My flock of sheep is the *set* of natural numbers, and my neighbor's
flock of sheep is the *set* of all infinite binary sequences.
Now, if this:
0 -- (1, 0, 0, 1, 1, 1, 0 ...
1 -- (0, 0, 0, 1, 1, 0, 1 ...
2 --- (0, 1, 0, 1, 0, 1, 1, ...
3 --- (1, 1, 1, 1, 1, 1, 1, ...
4 --- (0, 0, 1, 0, 0, 1, 1, ...
5 (0, 0, 0, 1, 1, 0, 1, ...
...
is really a bijection, it means that all the numbers 1 and 0 appearing
on the right are well determined (perhaps in Platonia, or in God's
mind, ...).
But then the diagonal sequence, going from the left up to right down,
and build from the list of binary sequences above:
1 0 0 1 0 0 ...
is also completely well determined (in Platonia or in the mind of a
God).
But then the complementary sequence (with the 0 and 1 permuted) is
also
well defined, in Platonia or in the mind of God(s)
0 1 1 0 1 1 ...
But this infinite sequence cannot be in the list, above. The God in
question has to ackonwledge that.
The complementary sequence is clearly different
-from the 0th sequence (1, 0, 0, 1, 1, 1, 0 ..., because it differs at
the first (better the 0th) entry.
-from the 1th sequence (0, 0, 0, 1, 1, 0, 1 ... because it differs at
the second (better the 1th) entry.
-from the 2th sequence (0, 0, 0, 1, 1, 0, 1 ... because it differs at
the third (better the 2th) entry.
and so one.
So, we see that as far as we consider the bijection above well
determined (by God, for example), then we can say to that God that the
bijection misses one of the neighbor sheep, indeed the sheep
constituted by the infinite binary sequence complementary to the
diagonal sequence cannot be in the list, and that sequence is also
well
determined (given that the whole table is).
But this means that this bijection fails. Now the reasoning did not
depend at all on the choice of any particular bijection-candidate.
Any
conceivable bijection will lead to a well determined infinite table of
binary numbers. And this will determine the diagonal sequence and then
the complementary diagonal sequence, and this one cannot be in the
list, because it contradicts all sequences in the list when they cross
the diagonal (do the drawing on paper).
Conclusion: 2^N, the set of infinite binary sequences, is not
enumerable.
All right?
Next I will do again that proof, but with notations instead of
drawing, and I will show more explicitly how the contradiction arise.
Exercice-training: show similarly that N^N, the set of functions from
N
to N, is not enumerable.
Bruno
http://iridia.ulb.ac.be/~marchal/
http://iridia.ulb.ac.be/~marchal/
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Everything List group.
To post to this group, send email to [EMAIL PROTECTED]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options,
Re: Cantor's Diagonal
On Nov 20, 4:40 pm, Bruno Marchal [EMAIL PROTECTED] wrote:
Conclusion: 2^N, the set of infinite binary sequences, is not
enumerable.
All right?
OK. I have to try to catch up now, because I've had to be away longer
than I expected, but I'm clear on this diagonal argument.
David
Hi,
David, are you still there? This is a key post, with respect to the
Church Thesis thread.
So let us see that indeed there is no bijection between N and 2^N =
2X2X2X2X2X2X... = {0,1}X{0,1}X{0,1}X{0,1}X... = the set of infinite
binary sequences.
Suppose that there is a bijection between N and the set of infinite
binary sequences. Well, it will look like that, where again
represents the ropes:
0 -- (1, 0, 0, 1, 1, 1, 0 ...
1 -- (0, 0, 0, 1, 1, 0, 1 ...
2 --- (0, 1, 0, 1, 0, 1, 1, ...
3 --- (1, 1, 1, 1, 1, 1, 1, ...
4 --- (0, 0, 1, 0, 0, 1, 1, ...
5 (0, 0, 0, 1, 1, 0, 1, ...
...
My sheep are the natural numbers, and my neighbor's sheep are the
infinite binary sequences (the function from N to 2, the elements of
the infinite cartesian product 2X2X2X2X2X2X... ).
My flock of sheep is the *set* of natural numbers, and my neighbor's
flock of sheep is the *set* of all infinite binary sequences.
Now, if this:
0 -- (1, 0, 0, 1, 1, 1, 0 ...
1 -- (0, 0, 0, 1, 1, 0, 1 ...
2 --- (0, 1, 0, 1, 0, 1, 1, ...
3 --- (1, 1, 1, 1, 1, 1, 1, ...
4 --- (0, 0, 1, 0, 0, 1, 1, ...
5 (0, 0, 0, 1, 1, 0, 1, ...
...
is really a bijection, it means that all the numbers 1 and 0 appearing
on the right are well determined (perhaps in Platonia, or in God's
mind, ...).
But then the diagonal sequence, going from the left up to right down,
and build from the list of binary sequences above:
1 0 0 1 0 0 ...
is also completely well determined (in Platonia or in the mind of a
God).
But then the complementary sequence (with the 0 and 1 permuted) is also
well defined, in Platonia or in the mind of God(s)
0 1 1 0 1 1 ...
But this infinite sequence cannot be in the list, above. The God in
question has to ackonwledge that.
The complementary sequence is clearly different
-from the 0th sequence (1, 0, 0, 1, 1, 1, 0 ..., because it differs at
the first (better the 0th) entry.
-from the 1th sequence (0, 0, 0, 1, 1, 0, 1 ... because it differs at
the second (better the 1th) entry.
-from the 2th sequence (0, 0, 0, 1, 1, 0, 1 ... because it differs at
the third (better the 2th) entry.
and so one.
So, we see that as far as we consider the bijection above well
determined (by God, for example), then we can say to that God that the
bijection misses one of the neighbor sheep, indeed the sheep
constituted by the infinite binary sequence complementary to the
diagonal sequence cannot be in the list, and that sequence is also well
determined (given that the whole table is).
But this means that this bijection fails. Now the reasoning did not
depend at all on the choice of any particular bijection-candidate. Any
conceivable bijection will lead to a well determined infinite table of
binary numbers. And this will determine the diagonal sequence and then
the complementary diagonal sequence, and this one cannot be in the
list, because it contradicts all sequences in the list when they cross
the diagonal (do the drawing on paper).
Conclusion: 2^N, the set of infinite binary sequences, is not
enumerable.
All right?
Next I will do again that proof, but with notations instead of
drawing, and I will show more explicitly how the contradiction arise.
Exercice-training: show similarly that N^N, the set of functions from N
to N, is not enumerable.
Bruno
http://iridia.ulb.ac.be/~marchal/
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Everything List group.
To post to this group, send email to [EMAIL PROTECTED]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups.google.com/group/everything-list?hl=en
-~--~~~~--~~--~--~---
Re: elaboration Re: Cantor's Diagonal
Le 22-nov.-07, à 07:19, Barry Brent a écrit :
The reason it isn't a bijection (of a denumerable set with the set of
binary sequences): the pre-image (the left side of your map) isn't
a set--you've imposed an ordering. Sets, qua sets, don't have
orderings. Orderings are extra. (I'm not a specialist on this stuff
but I think Bruno, for example, will back me up.) It must be the
case that you won't let us identify the left side, for example, with
{omega, 0, 1, 2, ... }, will you? For if you did, it would fall under
Cantor's argument.
I agree.
Presently, I prefer not talking too much on the ordinals, because it
could be confusing for many. More later ...
Bruno
http://iridia.ulb.ac.be/~marchal/
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Everything List group.
To post to this group, send email to [EMAIL PROTECTED]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups.google.com/group/everything-list?hl=en
-~--~~~~--~~--~--~---
Re: Cantor's Diagonal
Le 21-nov.-07, à 17:33, Torgny Tholerus a écrit :
What do you think of this proof?:
Let us have the bijection:
0 {0,0,0,0,0,0,0,...}
1 {1,0,0,0,0,0,0,...}
2 {0,1,0,0,0,0,0,...}
3 {1,1,0,0,0,0,0,...}
4 {0,0,1,0,0,0,0,...}
5 {1,0,1,0,0,0,0,...}
6 {0,1,1,0,0,0,0,...}
7 {1,1,1,0,0,0,0,...}
8 {0,0,0,1,0,0,0,...}
...
omega --- {1,1,1,1,1,1,1,...}
What do we get if we apply Cantor's Diagonal to this?
Note also that in general, we start from what we want to prove, and
then do the math. Your idea of transfinite (ordinal) diagonalisation is
cute though, but I have currently no idea where this could lead. BTW,
it is also funny that such a transfinite idea is proposed by an
ultrafinistist!
I guess you have seen that {(0,0,0,0,0,0,0,...), (1,0,0,0,0,0,0,...),
... does clearly not enumerate the infinite sequences (you don't have
to use the diagonal for showing that. It is also better to use
parentheses instead of accolades, given that the binary sequences are
ordered (notation detail).
Bruno
http://iridia.ulb.ac.be/~marchal/
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Everything List group.
To post to this group, send email to [EMAIL PROTECTED]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups.google.com/group/everything-list?hl=en
-~--~~~~--~~--~--~---
Re: Cantor's Diagonal
Le 20-nov.-07, à 17:47, David Nyman a écrit :
On 20/11/2007, Bruno Marchal [EMAIL PROTECTED] wrote:
David, are you still there? This is a key post, with respect to the
Church Thesis thread.
Sorry Bruno, do forgive me - we seem destined to be out of synch at
the moment. I'm afraid I'm too distracted this week to respond
adequately - back on-line next week at the latest.
Take it easy. It is the main advantage of electronical conversation,
unlike the phone, we can answer at the best moment. But I appreciate
you tell me.
See you next week.
Bruno
PS I'm afraid I have not the time to comment the last posts today,
except for elementary question perhaps, but I will have more time soon
(probably or hopefully tomorrow).
David
Hi,
David, are you still there? This is a key post, with respect to the
Church Thesis thread.
So let us see that indeed there is no bijection between N and 2^N =
2X2X2X2X2X2X... = {0,1}X{0,1}X{0,1}X{0,1}X... = the set of infinite
binary sequences.
Suppose that there is a bijection between N and the set of infinite
binary sequences. Well, it will look like that, where again
represents the ropes:
0 -- (1, 0, 0, 1, 1, 1, 0 ...
1 -- (0, 0, 0, 1, 1, 0, 1 ...
2 --- (0, 1, 0, 1, 0, 1, 1, ...
3 --- (1, 1, 1, 1, 1, 1, 1, ...
4 --- (0, 0, 1, 0, 0, 1, 1, ...
5 (0, 0, 0, 1, 1, 0, 1, ...
...
My sheep are the natural numbers, and my neighbor's sheep are the
infinite binary sequences (the function from N to 2, the elements of
the infinite cartesian product 2X2X2X2X2X2X... ).
My flock of sheep is the *set* of natural numbers, and my neighbor's
flock of sheep is the *set* of all infinite binary sequences.
Now, if this:
0 -- (1, 0, 0, 1, 1, 1, 0 ...
1 -- (0, 0, 0, 1, 1, 0, 1 ...
2 --- (0, 1, 0, 1, 0, 1, 1, ...
3 --- (1, 1, 1, 1, 1, 1, 1, ...
4 --- (0, 0, 1, 0, 0, 1, 1, ...
5 (0, 0, 0, 1, 1, 0, 1, ...
...
is really a bijection, it means that all the numbers 1 and 0 appearing
on the right are well determined (perhaps in Platonia, or in God's
mind, ...).
But then the diagonal sequence, going from the left up to right down,
and build from the list of binary sequences above:
1 0 0 1 0 0 ...
is also completely well determined (in Platonia or in the mind of a
God).
But then the complementary sequence (with the 0 and 1 permuted) is
also
well defined, in Platonia or in the mind of God(s)
0 1 1 0 1 1 ...
But this infinite sequence cannot be in the list, above. The God in
question has to ackonwledge that.
The complementary sequence is clearly different
-from the 0th sequence (1, 0, 0, 1, 1, 1, 0 ..., because it differs at
the first (better the 0th) entry.
-from the 1th sequence (0, 0, 0, 1, 1, 0, 1 ... because it differs at
the second (better the 1th) entry.
-from the 2th sequence (0, 0, 0, 1, 1, 0, 1 ... because it differs at
the third (better the 2th) entry.
and so one.
So, we see that as far as we consider the bijection above well
determined (by God, for example), then we can say to that God that the
bijection misses one of the neighbor sheep, indeed the sheep
constituted by the infinite binary sequence complementary to the
diagonal sequence cannot be in the list, and that sequence is also
well
determined (given that the whole table is).
But this means that this bijection fails. Now the reasoning did not
depend at all on the choice of any particular bijection-candidate.
Any
conceivable bijection will lead to a well determined infinite table of
binary numbers. And this will determine the diagonal sequence and then
the complementary diagonal sequence, and this one cannot be in the
list, because it contradicts all sequences in the list when they cross
the diagonal (do the drawing on paper).
Conclusion: 2^N, the set of infinite binary sequences, is not
enumerable.
All right?
Next I will do again that proof, but with notations instead of
drawing, and I will show more explicitly how the contradiction arise.
Exercice-training: show similarly that N^N, the set of functions from
N
to N, is not enumerable.
Bruno
http://iridia.ulb.ac.be/~marchal/
http://iridia.ulb.ac.be/~marchal/
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Everything List group.
To post to this group, send email to [EMAIL PROTECTED]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups.google.com/group/everything-list?hl=en
-~--~~~~--~~--~--~---
Re: Cantor's Diagonal
Le 20-nov.-07, à 23:39, Barry Brent wrote : You're saying that, just because you can *write down* the missing sequence (at the beginning, middle or anywhere else in the list), it follows that there *is* no missing sequence. Looks pretty wrong to me. Cantor's proof disqualifies any candidate enumeration. You respond by saying, well, here's another candidate! But Cantor's procedure disqualified *any*, repeat *any* candidate enumeration. Barry Brent Torgny, I do agree with Barry. Any bijection leads to a contradiction, even in some effective way, and that is enough (for a classical logician). But look what you write: On Nov 20, 2007, at 11:42 AM, Torgny Tholerus wrote: An ultrafinitist comment to this: == You can add this complementary sequence to the end of the list. That will make you have a list with this complementary sequence included. But then you can make a new complementary sequence, that is not inluded. But you can then add this new sequence to the end of the extended list, and then you have a bijection with this new sequence also. And if you try to make another new sequence, I will add that sequence too, and this I will do an infinite number of times. How could an ultrafinitist refute an argument by saying ... and this I will do an infinite number of times. ? So you will not be able to prove that there is no bijection... Actually no. If you do what you described omega times, you will just end up with a set which can still be put in 1-1 correspondence with N (as shown in preceding posts on bijections) To refute Cantor, here, you should do what you described a very big infinity of times, indeed an non enumerable infinity of times. But then you have to assume the existence of a non enumerable set at the start. OK? Bruno http://iridia.ulb.ac.be/~marchal/ == What is wrong with this conclusion? -- Torgny Dr. Barry Brent [EMAIL PROTECTED] http://home.earthlink.net/~barryb0/ --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to [EMAIL PROTECTED] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: Cantor's Diagonal
Le 21-nov.-07, à 08:49, Torgny Tholerus a écrit :
meekerdb skrev:Torgny Tholerus wrote:
An ultrafinitist comment to this:
==
You can add this complementary sequence to the end of the list. That
will make you have a list with this complementary sequence included.
But then you can make a new complementary sequence, that is not
inluded. But you can then add this new sequence to the end of the
extended list, and then you have a bijection with this new sequence
also. And if you try to make another new sequence, I will add that
sequence too, and this I will do an infinite number of times. So you
will not be able to prove that there is no bijection...
==
What is wrong with this conclusion?
You'd have to insert the new sequence in the beginning, as there is no
end of the list.
Why can't you add something to the end of the list? In an earlier
message Bruno wrote:
Now omega+1 is the set of all ordinal strictly lesser than omega+1,
with the convention above. This gives {0, 1, 2, 3, ... omega} = {0, 1,
2, 3, 4, {0, 1, 2, 3, 4, }}.
In this sentence he added omega to the end of the list of natural
numbers...
Adding something to the end or to the middle or to the beginning of an
infinite list, does not change the cardinality of that list. And in
Cantor proof, we are interested only in the cardinality notion.
Adding something to the beginning or to the end of a infinite ORDERED
list, well, it does not change the cardinal of the set involved, but it
obviosuly produce different order on those sets, and this can give
different ordinal, which denote type of order (isomorphic order).
The ordered set {0, 1, 2, 3, ...} has the same cardinality that the
ordered set {1, 2, 3, 4, ... 0} (where by definition 0 is bigger than
all natural numbers). But they both denote different ordinal, omega,
and omega+1 respectively. Note that {1, 0, 2, 3, 4, ...} is a different
order than {0, 1, 2, 3, ...}, but both order here are isomorphic, and
correspond to the same ordinal (omega).
That is why 1+omega = omega, and omega+1 is different from omega.
Adding one object in front of a list does not change the type of the
order. Adding an element at the end of an infinite list does change the
type of the order. {0, 1, 2, 3, ...} has no bigger element, but {1, 2,
3, ... 0} has a bigger element. So, you cannot by simple relabelling of
the elements get the same type of order (and thus they correspond to
different ordinals).
OK? (this stuff will not be used for Church Thesis, unless we go very
far ...later).
Bruno
http://iridia.ulb.ac.be/~marchal/
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Everything List group.
To post to this group, send email to [EMAIL PROTECTED]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups.google.com/group/everything-list?hl=en
-~--~~~~--~~--~--~---
Re: Cantor's Diagonal
Bruno Marchal skrev:
Le 20-nov.-07, 23:39, Barry Brent wrote :
You're saying that, just because you can *write down* the missing
sequence (at the beginning, middle or anywhere else in the list), it
follows that there *is* no missing sequence. Looks pretty wrong to me.
Cantor's proof disqualifies any candidate enumeration. You respond
by saying, "well, here's another candidate!" But Cantor's procedure
disqualified *any*, repeat *any* candidate enumeration.
Barry Brent
Torgny, I do agree with Barry. Any bijection leads to a contradiction,
even in some effective way, and that is enough (for a classical
logician).
What do you think of this "proof"?:
Let us have the bijection:
0 {0,0,0,0,0,0,0,...}
1 {1,0,0,0,0,0,0,...}
2 {0,1,0,0,0,0,0,...}
3 {1,1,0,0,0,0,0,...}
4 {0,0,1,0,0,0,0,...}
5 {1,0,1,0,0,0,0,...}
6 {0,1,1,0,0,0,0,...}
7 {1,1,1,0,0,0,0,...}
8 {0,0,0,1,0,0,0,...}
...
omega --- {1,1,1,1,1,1,1,...}
What do we get if we apply Cantor's Diagonal to this?
--
Torgny
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to [EMAIL PROTECTED] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
elaboration Re: Cantor's Diagonal
The reason it isn't a bijection (of a denumerable set with the set of
binary sequences): the pre-image (the left side of your map) isn't
a set--you've imposed an ordering. Sets, qua sets, don't have
orderings. Orderings are extra. (I'm not a specialist on this stuff
but I think Bruno, for example, will back me up.) It must be the
case that you won't let us identify the left side, for example, with
{omega, 0, 1, 2, ... }, will you? For if you did, it would fall under
Cantor's argument.
Barry
On Nov 21, 2007, at 10:33 AM, Torgny Tholerus wrote:
Bruno Marchal skrev:
Le 20-nov.-07, à 23:39, Barry Brent wrote :
You're saying that, just because you can *write down* the missing
sequence (at the beginning, middle or anywhere else in the list),
it follows that there *is* no missing sequence. Looks pretty
wrong to me. Cantor's proof disqualifies any candidate
enumeration. You respond by saying, well, here's another
candidate! But Cantor's procedure disqualified *any*, repeat
*any* candidate enumeration. Barry Brent
Torgny, I do agree with Barry. Any bijection leads to a
contradiction, even in some effective way, and that is enough (for
a classical logician).
What do you think of this proof?:
Let us have the bijection:
0 {0,0,0,0,0,0,0,...}
1 {1,0,0,0,0,0,0,...}
2 {0,1,0,0,0,0,0,...}
3 {1,1,0,0,0,0,0,...}
4 {0,0,1,0,0,0,0,...}
5 {1,0,1,0,0,0,0,...}
6 {0,1,1,0,0,0,0,...}
7 {1,1,1,0,0,0,0,...}
8 {0,0,0,1,0,0,0,...}
...
omega --- {1,1,1,1,1,1,1,...}
What do we get if we apply Cantor's Diagonal to this?
--
Torgny
Dr. Barry Brent
[EMAIL PROTECTED]
http://home.earthlink.net/~barryb0/
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Everything List group.
To post to this group, send email to [EMAIL PROTECTED]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups.google.com/group/everything-list?hl=en
-~--~~~~--~~--~--~---
Re: Cantor's Diagonal
On 20/11/2007, Bruno Marchal [EMAIL PROTECTED] wrote:
David, are you still there? This is a key post, with respect to the
Church Thesis thread.
Sorry Bruno, do forgive me - we seem destined to be out of synch at
the moment. I'm afraid I'm too distracted this week to respond
adequately - back on-line next week at the latest.
David
Hi,
David, are you still there? This is a key post, with respect to the
Church Thesis thread.
So let us see that indeed there is no bijection between N and 2^N =
2X2X2X2X2X2X... = {0,1}X{0,1}X{0,1}X{0,1}X... = the set of infinite
binary sequences.
Suppose that there is a bijection between N and the set of infinite
binary sequences. Well, it will look like that, where again
represents the ropes:
0 -- (1, 0, 0, 1, 1, 1, 0 ...
1 -- (0, 0, 0, 1, 1, 0, 1 ...
2 --- (0, 1, 0, 1, 0, 1, 1, ...
3 --- (1, 1, 1, 1, 1, 1, 1, ...
4 --- (0, 0, 1, 0, 0, 1, 1, ...
5 (0, 0, 0, 1, 1, 0, 1, ...
...
My sheep are the natural numbers, and my neighbor's sheep are the
infinite binary sequences (the function from N to 2, the elements of
the infinite cartesian product 2X2X2X2X2X2X... ).
My flock of sheep is the *set* of natural numbers, and my neighbor's
flock of sheep is the *set* of all infinite binary sequences.
Now, if this:
0 -- (1, 0, 0, 1, 1, 1, 0 ...
1 -- (0, 0, 0, 1, 1, 0, 1 ...
2 --- (0, 1, 0, 1, 0, 1, 1, ...
3 --- (1, 1, 1, 1, 1, 1, 1, ...
4 --- (0, 0, 1, 0, 0, 1, 1, ...
5 (0, 0, 0, 1, 1, 0, 1, ...
...
is really a bijection, it means that all the numbers 1 and 0 appearing
on the right are well determined (perhaps in Platonia, or in God's
mind, ...).
But then the diagonal sequence, going from the left up to right down,
and build from the list of binary sequences above:
1 0 0 1 0 0 ...
is also completely well determined (in Platonia or in the mind of a
God).
But then the complementary sequence (with the 0 and 1 permuted) is also
well defined, in Platonia or in the mind of God(s)
0 1 1 0 1 1 ...
But this infinite sequence cannot be in the list, above. The God in
question has to ackonwledge that.
The complementary sequence is clearly different
-from the 0th sequence (1, 0, 0, 1, 1, 1, 0 ..., because it differs at
the first (better the 0th) entry.
-from the 1th sequence (0, 0, 0, 1, 1, 0, 1 ... because it differs at
the second (better the 1th) entry.
-from the 2th sequence (0, 0, 0, 1, 1, 0, 1 ... because it differs at
the third (better the 2th) entry.
and so one.
So, we see that as far as we consider the bijection above well
determined (by God, for example), then we can say to that God that the
bijection misses one of the neighbor sheep, indeed the sheep
constituted by the infinite binary sequence complementary to the
diagonal sequence cannot be in the list, and that sequence is also well
determined (given that the whole table is).
But this means that this bijection fails. Now the reasoning did not
depend at all on the choice of any particular bijection-candidate. Any
conceivable bijection will lead to a well determined infinite table of
binary numbers. And this will determine the diagonal sequence and then
the complementary diagonal sequence, and this one cannot be in the
list, because it contradicts all sequences in the list when they cross
the diagonal (do the drawing on paper).
Conclusion: 2^N, the set of infinite binary sequences, is not
enumerable.
All right?
Next I will do again that proof, but with notations instead of
drawing, and I will show more explicitly how the contradiction arise.
Exercice-training: show similarly that N^N, the set of functions from N
to N, is not enumerable.
Bruno
http://iridia.ulb.ac.be/~marchal/
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Everything List group.
To post to this group, send email to [EMAIL PROTECTED]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups.google.com/group/everything-list?hl=en
-~--~~~~--~~--~--~---
Re: Cantor's Diagonal
Bruno Marchal skrev: But then the complementary sequence (with the 0 and 1 permuted) is also well defined, in Platonia or in the mind of God(s) 0 1 1 0 1 1 ... But this infinite sequence cannot be in the list, above. The "God" in question has to ackonwledge that. The complementary sequence is clearly different -from the 0th sequence (1, 0, 0, 1, 1, 1, 0 ..., because it differs at the first (better the 0th) entry. -from the 1th sequence (0, 0, 0, 1, 1, 0, 1 ... because it differs at the second (better the 1th) entry. -from the 2th sequence (0, 0, 0, 1, 1, 0, 1 ... because it differs at the third (better the 2th) entry. and so one. So, we see that as far as we consider the bijection above well determined (by God, for example), then we can say to that God that the bijection misses one of the neighbor sheep, indeed the "sheep" constituted by the infinite binary sequence complementary to the diagonal sequence cannot be in the list, and that sequence is also well determined (given that the whole table is). But this means that this bijection fails. Now the reasoning did not depend at all on the choice of any particular bijection-candidate. Any conceivable bijection will lead to a well determined infinite table of binary numbers. And this will determine the diagonal sequence and then the complementary diagonal sequence, and this one cannot be in the list, because it contradicts all sequences in the list when they cross the diagonal (do the drawing on paper). Conclusion: 2^N, the set of infinite binary sequences, is not enumerable. All right? An ultrafinitist comment to this: == You can add this complementary sequence to the end of the list. That will make you have a list with this complementary sequence included. But then you can make a new complementary sequence, that is not inluded. But you can then add this new sequence to the end of the extended list, and then you have a bijection with this new sequence also. And if you try to make another new sequence, I will add that sequence too, and this I will do an infinite number of times. So you will not be able to prove that there is no bijection... == What is wrong with this conclusion? -- Torgny --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to [EMAIL PROTECTED] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: Cantor's Diagonal
Torgny Tholerus wrote: Bruno Marchal skrev: But then the complementary sequence (with the 0 and 1 permuted) is also well defined, in Platonia or in the mind of God(s) *0* *1* *1* *0* *1* *1* ... But *this* infinite sequence cannot be in the list, above. The God in question has to ackonwledge that. The complementary sequence is clearly different -from the 0th sequence (*_1_*, 0, 0, 1, 1, 1, 0 ..., because it differs at the first (better the 0th) entry. -from the 1th sequence (0, *_0_*, 0, 1, 1, 0, 1 ... because it differs at the second (better the 1th) entry. -from the 2th sequence (0, 0, *_0_*, 1, 1, 0, 1 ... because it differs at the third (better the 2th) entry. and so one. So, we see that as far as we consider the bijection above well determined (by God, for example), then we can say to that God that the bijection misses one of the neighbor sheep, indeed the sheep constituted by the infinite binary sequence complementary to the diagonal sequence cannot be in the list, and that sequence is also well determined (given that the whole table is). But this means that this bijection fails. Now the reasoning did not depend at all on the choice of any particular bijection-candidate. Any conceivable bijection will lead to a well determined infinite table of binary numbers. And this will determine the diagonal sequence and then the complementary diagonal sequence, and this one cannot be in the list, because it contradicts all sequences in the list when they cross the diagonal (do the drawing on paper). Conclusion: 2^N, the set of infinite binary sequences, is not enumerable. All right? An ultrafinitist comment to this: == You can add this complementary sequence to the end of the list. That will make you have a list with this complementary sequence included. But then you can make a new complementary sequence, that is not inluded. But you can then add this new sequence to the end of the extended list, and then you have a bijection with this new sequence also. And if you try to make another new sequence, I will add that sequence too, and this I will do an infinite number of times. So you will not be able to prove that there is no bijection... == What is wrong with this conclusion? You'd have to insert the new sequence in the beginning, as there is no end of the list. Brent Meeker -- Torgny --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to [EMAIL PROTECTED] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
Re: Cantor's Diagonal
meekerdb skrev:
Torgny Tholerus wrote:
An ultrafinitist comment to this:
==
You can add this complementary sequence to the end of the list. That
will make you have a list with this complementary sequence included.
But then you can make a new complementary sequence, that is not
inluded. But you can then add this new sequence to the end of the
extended list, and then you have a bijection with this new sequence
also. And if you try to make another new sequence, I will add that
sequence too, and this I will do an infinite number of times. So you
will not be able to prove that there is no bijection...
==
What is wrong with this conclusion?
You'd have to insert the new sequence in the beginning, as there is no
"end of the list".
Why can't you add something to the end of the list? In an earlier
message Bruno wrote:
"Now omega+1 is the set of all ordinal strictly lesser than omega+1,
with the convention above. This gives {0, 1, 2, 3, ... omega} = {0, 1,
2, 3, 4, {0, 1, 2, 3, 4, }}."
In this sentence he added omega to the end of the list of natural
numbers...
--
Torgny
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups Everything List group. To post to this group, send email to [EMAIL PROTECTED] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~--~~~~--~~--~--~---
