(My problem is NOT with the diagonal argument itself per se, but rather with one of its underlying assumptions)
How does one prove that the statement: "diagonalization is only applicable to lists of any finite size "
is false.?
It obviously IS true that FINITE lists of reals can be diagonalized, that's obvious. But although "plausible", it is by no means clear (to me) that the property of diagonalizability EXISTS when the list is not finite.
For consider by analogy, the function: D = (-1) to the power of (1/2n), associated with each list of finite size n,
for all natural numbers n, no mater how large, D is a complex number with the property of having a non-zero imaginary part. No matter HOW large n gets, the exponent never becomes 0, D is always complex and the list always has the property of being diagonalizable.
If the exponent is just suddenly stated to be zero however, D does NOT have a non-zero imaginary part. D = (-1)^0 =1.
It seems to me not impossible that likewise, a list, which is just suddenly stated to be, the list of "ALL" reals simply "suddenly" (and this is what I can't prove to be false) DOESN'T HAVE the property of diagonizability.
In neither case is there any suggestion of "counting up" to "0" or "up to" the "list of all reals"; both are just suddenly stated as a "let there be".
In other words, there is a discontinuity in the way the diagonal argument is presented in textbooks, And, as in the case of D above, the fact that something has a property for every value of n, doesn't mean that that property is necessarily present in every case.
There is a discontinuity, because one does not "gradually" grow a finite list into an infinite one; nobody is suggesting that.
"The list of all reals " is just SUDDENLY STATED. Entering without precedent into the argument as it were. To say nothing of the "reification of infinity" error that such a phrase implies, such an entity as "the list of all reals" might bear only an apparent similarity "in speech" to the finite lists of reals and not share their property of diagonalizability at all.
If diagonalization is applied to "the infinite list of all reals" we obtain a contradiction. That is a fact.
This fact implies either (a) or (b)
(a)= "the list of all reals cannot exist"
(b)= "diagonalization cannot be applied to the infinite list of all reals"
but how am I supposed to know for certain which of these two is the real McCoy? (no pun intended)
If (a) were true then (b) would be vacuously so. but if (b) were non- vacuously true then (a) would not be implied since no contradictory real could be diagonally constructed.
(I have no idea how this could be the case, but neither can I prove that it would not)
so how DOES one prove, independently that (b) is false and that therefore it is (a) which is implied by the diagonal argument?
your answer in "logical baby-step -by- logical baby-step" please
unless (b) is PROVABLY false, the diagonal argument itself is inconclusive. and any "understanding" of the diagonal argument is an illusion.
As I say, I don't know how (b) could in fact be true (it's certainly not true for any FINITE list of reals) but EQUALLY I cannot see how I can legitimately confer diagonalizability on "the list of all reals" by a mere discontinuous analogy with "all finite lists of reals" (as in function D above)
I believe that saying:
"for all elements in X" (where X is an infinite set),
is meaningful only if, by it, one means
"for each element in X" otherwise it is a reification error.
> But although "plausible", it is by no means clear (to > me) that the property of diagonalizability EXISTS when the list is not > finite.
> For consider by analogy, the function: > D = (-1) to the power of (1/2n), > associated with each list of finite size n,
> for all natural numbers n, no mater how large, D is a complex number > with the property of having a non-zero imaginary part. No matter HOW > large n gets, the exponent never becomes 0, D is always complex and > the list always has the property of being diagonalizable.
> If the exponent is just suddenly stated to be zero however, D does NOT > have a non-zero imaginary part. D = (-1)^0 =1.
> It seems to me not impossible that likewise, a list, which is just > suddenly stated to be, the list of "ALL" reals simply "suddenly" (and > this is what I can't prove to be false) DOESN'T HAVE the property of > diagonizability.
> In neither case is there any suggestion of "counting up" to "0" or "up > to" the "list of all reals"; both are just suddenly stated as a "let > there be".
> In other words, there is a discontinuity in the way the diagonal > argument is presented in textbooks, And, as in the case of D above, > the fact that something has a property for every value of n, doesn't > mean that that property is necessarily present in every case.
> There is a discontinuity, because one does not "gradually" grow a > finite list into an infinite one; nobody is suggesting that.
> "The list of all reals " is just SUDDENLY STATED. Entering without > precedent into the argument as it were. To say nothing of the > "reification of infinity" error that such a phrase implies, such an > entity as "the list of all reals" might bear only an apparent > similarity "in speech" to the finite lists of reals and not share > their property of diagonalizability at all.
> If diagonalization is applied to "the infinite list of all reals" we > obtain a contradiction. > That is a fact.
> This fact implies either (a) or (b)
> (a)= "the list of all reals cannot exist"
> (b)= "diagonalization cannot be applied to the infinite list of all > reals"
> but how am I supposed to know for certain which of these two is the > real McCoy? (no pun intended)
> If (a) were true then (b) would be vacuously so. but if (b) were non- > vacuously true then (a) would not be implied since no contradictory > real could be diagonally constructed.
> (I have no idea how this could be the case, but neither can I prove > that it would not)
> so how DOES one prove, independently that (b) is false and that > therefore it is (a) which is implied by the diagonal argument?
> your answer in "logical baby-step -by- logical baby-step" please
> unless (b) is PROVABLY false, the diagonal argument itself is > inconclusive. and any "understanding" of the diagonal argument is an > illusion.
> As I say, I don't know how (b) could in fact be true (it's certainly > not true for any FINITE list of reals) but EQUALLY I cannot see how I > can legitimately confer diagonalizability on "the list of all reals" > by a mere discontinuous analogy with "all finite lists of reals" (as > in function D above)
> I believe that saying:
> "for all elements in X" (where X is an infinite set),
> is meaningful only if, by it, one means
> "for each element in X" otherwise it is a reification error.
On Aug 26, 5:47 am, slartibartfast <tomokane2...@yahoo.ie> wrote:
> with regard to lists of real numbers:
> (My problem is NOT with the diagonal argument itself per se, but > rather with one of its underlying assumptions)
> How does one prove that the statement: > "diagonalization is only applicable to lists of any finite size "
> is false.?
By showing explicitly how it's done. In the case at hand one unambiguously defines a real not in the proposed list by saying that it's nth decimal, b_n, should be 4 if a_{n,n} is not 4 and 7 if a_{n,n} is 4.
> It obviously IS true that FINITE lists of reals can be diagonalized, > that's obvious. But although "plausible", it is by no means clear (to > me) that the property of diagonalizability EXISTS when the list is not > finite.
> For consider by analogy, the function: > D = (-1) to the power of (1/2n), > associated with each list of finite size n,
Unfortunately this is not a well-defined function (at n it has 2n possible values ...) but I get your drift
> for all natural numbers n, no mater how large, D is a complex number > with the property of having a non-zero imaginary part. No matter HOW > large n gets, the exponent never becomes 0, D is always complex and > the list always has the property of being diagonalizable.
> If the exponent is just suddenly stated to be zero however, D does NOT > have a non-zero imaginary part. D = (-1)^0 =1.
Yes, but failure of continuity here says nothing about the completely different situation that is the diagonal argument.
>(My problem is NOT with the diagonal argument itself per se, but >rather with one of its underlying assumptions) >[...]
>If diagonalization is applied to "the infinite list of all reals" we >obtain a contradiction. >That is a fact.
>This fact implies either (a) or (b)
>(a)= "the list of all reals cannot exist"
>(b)= "diagonalization cannot be applied to the infinite list of all >reals"
>but how am I supposed to know for certain which of these two is the >real McCoy? (no pun intended)
You're supposed to realize that "diagonalization can be applied" by observing that "diagonalization" _is_ "applied" in the proof! Something that we do is something that can be done.
You seem to think that "diagonalization can be applied" is some sort of assumption here. It's not. Look at the actual proof - exactly what step do you fear may be invalid?
>If (a) were true then (b) would be vacuously so. but if (b) were non- >vacuously true then (a) would not be implied since no contradictory >real could be diagonally constructed.
>(I have no idea how this could be the case, but neither can I prove >that it would not)
>so how DOES one prove, independently that (b) is false and that >therefore it is (a) which is implied by the diagonal argument?
>your answer in "logical baby-step -by- logical baby-step" please
You've seen the proof. The one-step-at-a-time answer to your question consists of first a careful exposition of the proof, which I'm not going to repeat right now, followed by the observation that if we've done something it must be possible.
>unless (b) is PROVABLY false, the diagonal argument itself is >inconclusive. and any "understanding" of the diagonal argument is an >illusion.
>As I say, I don't know how (b) could in fact be true (it's certainly >not true for any FINITE list of reals) but EQUALLY I cannot see how I >can legitimately confer diagonalizability on "the list of all reals" >by a mere discontinuous analogy with "all finite lists of reals" (as >in function D above)
It's exactly right to say that reasoning about infinite sets by analogy with finite sets can cause big problems. But that's irrelevant here - there is no such reasoning by analogy involved in the proof.
>I believe that saying:
> "for all elements in X" (where X is an infinite set),
> is meaningful only if, by it, one means
>"for each element in X" otherwise it is a reification error.
So?
David C. Ullrich
"Understanding Godel isn't about following his formal proof. That would make a mockery of everything Godel was up to." (John Jones, "My talk about Godel to the post-grads." in sci.logic.)
> On Aug 26, 5:47 am, slartibartfast <tomokane2...@yahoo.ie> wrote:
> > with regard to lists of real numbers:
> > (My problem is NOT with the diagonal argument itself per se, but > > rather with one of its underlying assumptions)
> > How does one prove that the statement: > > "diagonalization is only applicable to lists of any finite size "
> > is false.?
> By showing explicitly how it's done. In the case at hand one > unambiguously > defines a real not in the proposed list by saying that it's nth > decimal, b_n, should > be 4 if a_{n,n} is not 4 and 7 if a_{n,n} is 4.
But this is precisely my difficulty: I can understand what it means when on says the expression: "it's nth decimal, b_n, should be 4 if a_{n,n} is not 4 and 7 if a_{n,n} is 4." But I don't know what that means when n is not a finite natural. sense 1: If the list is said to be an "infinite list", then n is not a number at all: you can't have the infinitieth member in a list nor the infinity-1-th member. sense 2: On the other hand IF by "infinite list" it is meant simpy that there is no upper bound on the length n of the list to which the diagonalization is to be performed, then that's ok but in THIS case n is always finite (albeit unboundedly so) and what is being listed is only some of the reals (n of them) and not all of them. and so there is no contradiction in constructing the diagonal.
It seems to me that the only way to produce a contradiction is if "infinite list" is meant as in sense 1 which seems to me to be a reification error and also I do not see how diagonalizability for such an "entity" is entailed by the fact that finite lists of reals can be diagonalized.
"showing explicitly how it's done" can only be done by using a letter of the alphabet "n", say. And such explicit showing is and remains only an explict showing for finite n's because n is never "infinity". i.e. such an explicit showing, no matter how clear and lucid, is always expressed in terms of "n". And is perfectly valid for all n and n is never = "infinity".
So we go round in circles back to the initial question: How does one show firstly what an "infinite list" actually "is" or means, and secondly that diagonalization is defined for it. (as opposed to merely being defined for all n as in sense 2 which wouldn't then produce a contradiction)
> > It obviously IS true that FINITE lists of reals can be diagonalized, > > that's obvious. But although "plausible", it is by no means clear (to > > me) that the property of diagonalizability EXISTS when the list is not > > finite.
> > For consider by analogy, the function: > > D = (-1) to the power of (1/2n), > > associated with each list of finite size n,
> Unfortunately this is not a well-defined function (at n it has 2n > possible values ...) > but I get your drift
> > for all natural numbers n, no mater how large, D is a complex number > > with the property of having a non-zero imaginary part. No matter HOW > > large n gets, the exponent never becomes 0, D is always complex and > > the list always has the property of being diagonalizable.
> > If the exponent is just suddenly stated to be zero however, D does NOT > > have a non-zero imaginary part. D = (-1)^0 =1.
> Yes, but failure of continuity here says nothing about the completely > different > situation that is the diagonal argument.
> KP
I know ... I wasn't suggesting there was any "relationship" between the two cases. ...I was only using it as an example that sometimes a thing can have a certain propertie over a whole finite range of values and yet NOT have that property when "infinities" are involved... just that it does sometimes happen ... thats all .
On Aug 26, 10:48 am, slartibartfast <tomokane2...@yahoo.ie> wrote:
> I can understand what it means > when on says the expression: "it's nth decimal, b_n, should be 4 if > a_{n,n} is not 4 and 7 if a_{n,n} is 4." > But I don't know what that means when n is not a finite natural.
We only need to define for all natural numbers n.
The anti-diagonal (call it 'd') is a function. The domain of d is the set of natural numbers. And for each natural number n, we have d(n)=4 if a(n n) not= 4 and d(n)=7 if a(n n)= 4.
That's all there is to it: A function whose domain is the set of natural numbers.
There is no concern for what it "means" when n is not a natural number, i.e., for when n is not in the domain of d.
> sense 1: > If the list is said to be an "infinite list", then n is not a number > at all: you can't have the infinitieth member in a list nor the > infinity-1-th member. > sense 2: > On the other hand IF by "infinite list" it is meant simpy that there > is no upper bound on the length n of the list to which the > diagonalization is to be performed, then that's ok but in THIS case n > is always finite (albeit unboundedly so) and what is being listed is > only some of the reals (n of them) and not all of them. and so there > is no contradiction in constructing the diagonal.
> It seems to me that the only way to produce a contradiction is if > "infinite list" is meant as in sense 1 which seems to me to be a > reification error and also I do not see how diagonalizability for such > an "entity" is entailed by the fact that finite lists of reals can be > diagonalized.
> "showing explicitly how it's done" can only be done by using a letter > of the alphabet "n", say. And such explicit showing is and remains > only an explict showing for finite n's because n is never "infinity". > i.e. such an explicit showing, no matter how clear and lucid, is > always expressed in terms of "n". And is perfectly valid for all n and > n is never = "infinity".
> So we go round in circles back to the initial question: How does one > show firstly what an "infinite list" actually "is" or means, and > secondly that diagonalization is defined for it. (as opposed to merely > being defined for all n as in sense 2 which wouldn't then produce a > contradiction)
> > > It obviously IS true that FINITE lists of reals can be diagonalized, > > > that's obvious. But although "plausible", it is by no means clear (to > > > me) that the property of diagonalizability EXISTS when the list is not > > > finite.
> > > For consider by analogy, the function: > > > D = (-1) to the power of (1/2n), > > > associated with each list of finite size n,
> > Unfortunately this is not a well-defined function (at n it has 2n > > possible values ...) > > but I get your drift
> > > for all natural numbers n, no mater how large, D is a complex number > > > with the property of having a non-zero imaginary part. No matter HOW > > > large n gets, the exponent never becomes 0, D is always complex and > > > the list always has the property of being diagonalizable.
> > > If the exponent is just suddenly stated to be zero however, D does NOT > > > have a non-zero imaginary part. D = (-1)^0 =1.
> > Yes, but failure of continuity here says nothing about the completely > > different > > situation that is the diagonal argument.
> > KP
> I know ... I wasn't suggesting there was any "relationship" between > the two cases. > ...I was only using it as an example that sometimes a thing can have > a certain propertie over a whole finite range of values and yet NOT > have that property when "infinities" are involved... just that it does > sometimes happen ... thats all .
> >(My problem is NOT with the diagonal argument itself per se, but > >rather with one of its underlying assumptions) > >[...]
> >If diagonalization is applied to "the infinite list of all reals" we > >obtain a contradiction. > >That is a fact.
> >This fact implies either (a) or (b)
> >(a)= "the list of all reals cannot exist"
> >(b)= "diagonalization cannot be applied to the infinite list of all > >reals"
> >but how am I supposed to know for certain which of these two is the > >real McCoy? (no pun intended)
> You're supposed to realize that "diagonalization can be applied" > by observing that "diagonalization" _is_ "applied" in the proof! > Something that we do is something that can be done.
If someone were to show you a proof containing an application of a division by 0, are you supposed to just accept that such can be applied just because its in the proof? To do so would negate the whole purpose for giving logical proofs in the first place. If you deny yourself the right to question then you are just a parrot substituting verbatim regurgitation with understanding and do not understand that you do not understand, or you are a God who understands things first time and doesn't need to question anything.
> You seem to think that "diagonalization can be applied" is > some sort of assumption here. It's not. Look at the > actual proof - exactly what step do you fear may be invalid?
I don't SEEM to think it; I DO think it! There IS NO explicit step in the proof that I fear might be invalid, what I question the validity of is the implicit ASSUMPTION that those explicit steps, which are in themselves very easy to understand, can be applied to an "infinite list" because when I look at to proof, I see only a proof that is valid for all lengths of lists. However I am also mindful of the fact that "infinity" is not a length. and that's precisely the issue.
So whatever is meant by "infinite list", the diagonalization is never defined for that kind of "entity" when the proof is explicitly described for lists of all finite lengths n; as in "...take the nth digit of the nth real..." and so on, n never can be increased "to" infinity because infinity isn't a number
So the property of diagonalizability, which finite lists of reals obviously DO have, is nowhere IN THE ARGUMENT shown to be a property that an "infinite list " of reals would have and therefore it is VERY MUCH an ASSUMPTION to claim that such an entity would be diagonalizable since finite lists do not "grow" into an "infinite" one. And there is therefore nothing to suggest that such a property would be shared by such an "infinite list". To assume otherwise is also an "assumption" and one which, if accepted purely on the grounds that "it is used/applied in the proof", is not only unwarranted but circular to boot!
> >If (a) were true then (b) would be vacuously so. but if (b) were non- > >vacuously true then (a) would not be implied since no contradictory > >real could be diagonally constructed.
> >(I have no idea how this could be the case, but neither can I prove > >that it would not)
> >so how DOES one prove, independently that (b) is false and that > >therefore it is (a) which is implied by the diagonal argument?
> >your answer in "logical baby-step -by- logical baby-step" please
> You've seen the proof. The one-step-at-a-time answer > to your question consists of first a careful exposition of the > proof, which I'm not going to repeat right now, followed > by the observation that if we've done something it must > be possible.
> >unless (b) is PROVABLY false, the diagonal argument itself is > >inconclusive. and any "understanding" of the diagonal argument is an > >illusion.
> >As I say, I don't know how (b) could in fact be true (it's certainly > >not true for any FINITE list of reals) but EQUALLY I cannot see how I > >can legitimately confer diagonalizability on "the list of all reals" > >by a mere discontinuous analogy with "all finite lists of reals" (as > >in function D above)
> It's exactly right to say that reasoning about infinite sets by > analogy with finite sets can cause big problems. But that's > irrelevant here - there is no such reasoning by analogy > involved in the proof.
> >I believe that saying:
> > "for all elements in X" (where X is an infinite set),
> > is meaningful only if, by it, one means
> >"for each element in X" otherwise it is a reification error.
> So?
> David C. Ullrich
> "Understanding Godel isn't about following his formal proof. > That would make a mockery of everything Godel was up to." > (John Jones, "My talk about Godel to the post-grads." > in sci.logic.)- Hide quoted text -
> On Aug 26, 10:48 am, slartibartfast <tomokane2...@yahoo.ie> wrote:
> > I can understand what it means > > when on says the expression: "it's nth decimal, b_n, should be 4 if > > a_{n,n} is not 4 and 7 if a_{n,n} is 4." > > But I don't know what that means when n is not a finite natural.
> We only need to define for all natural numbers n.
> The anti-diagonal (call it 'd') is a function. The domain of d is the > set of natural numbers. And for each natural number n, we have d(n)=4 > if a(n n) not= 4 and d(n)=7 if a(n n)= 4.
> That's all there is to it: A function whose domain is the set of > natural numbers.
> There is no concern for what it "means" when n is not a natural > number, i.e., for when n is not in the domain of d.
yes you're right BUT....since the domain of d is the natural numbers, then every value of d is a function of some FINITE natural number n,
"That's all there is to it" = "thats all there is to the definition of d" correct the definition of d is not in question.
"There is no concern " ="There is no concern with regard to the definition of d" That is correct taking the definition of d on its own. that's perfectly correct.
but a concern ARISES when we THEN say "let's consider the infinite list (of reals)" for such a list would require n that is NOT in the domain of d, since every n in the domain of d, is necessarily finite.
since the domain of d is the natural numbers, then every value of d is a function of some FINITE natural number n, and this fact is incompatible with a comparison with an "infinite" list of anything.
Because it doesn't make sense to compare an infinite list "all of a piece" with anything, the countability of the infiinite set of the natural numbers is defined as being a 1-to-1 correspondence for any n in the set. So in establishing this countability one never has to reify an infinite list. its quite sleek! However in determining whether the reals are countably or uncountably infinite, one cannot pair them with the naturals one at a time like this. The Diagonal argument considers the "entire infinite list of all reals" all in one chunk and this cannot be done even for the naturals, because it is a reification.
So although d IS perfectly well defined, the listing -- that precedes the d operation -- is not.
> > sense 1: > > If the list is said to be an "infinite list", then n is not a number > > at all: you can't have the infinitieth member in a list nor the > > infinity-1-th member. > > sense 2: > > On the other hand IF by "infinite list" it is meant simpy that there > > is no upper bound on the length n of the list to which the > > diagonalization is to be performed, then that's ok but in THIS case n > > is always finite (albeit unboundedly so) and what is being listed is > > only some of the reals (n of them) and not all of them. and so there > > is no contradiction in constructing the diagonal.
> > It seems to me that the only way to produce a contradiction is if > > "infinite list" is meant as in sense 1 which seems to me to be a > > reification error and also I do not see how diagonalizability for such > > an "entity" is entailed by the fact that finite lists of reals can be > > diagonalized.
> > "showing explicitly how it's done" can only be done by using a letter > > of the alphabet "n", say. And such explicit showing is and remains > > only an explict showing for finite n's because n is never "infinity". > > i.e. such an explicit showing, no matter how clear and lucid, is > > always expressed in terms of "n". And is perfectly valid for all n and > > n is never = "infinity".
> > So we go round in circles back to the initial question: How does one > > show firstly what an "infinite list" actually "is" or means, and > > secondly that diagonalization is defined for it. (as opposed to merely > > being defined for all n as in sense 2 which wouldn't then produce a > > contradiction)
> > > > It obviously IS true that FINITE lists of reals can be diagonalized, > > > > that's obvious. But although "plausible", it is by no means clear (to > > > > me) that the property of diagonalizability EXISTS when the list is not > > > > finite.
> > > > For consider by analogy, the function: > > > > D = (-1) to the power of (1/2n), > > > > associated with each list of finite size n,
> > > Unfortunately this is not a well-defined function (at n it has 2n > > > possible values ...) > > > but I get your drift
> > > > for all natural numbers n, no mater how large, D is a complex number > > > > with the property of having a non-zero imaginary part. No matter HOW > > > > large n gets, the exponent never becomes 0, D is always complex and > > > > the list always has the property of being diagonalizable.
> > > > If the exponent is just suddenly stated to be zero however, D does NOT > > > > have a non-zero imaginary part. D = (-1)^0 =1.
> > > Yes, but failure of continuity here says nothing about the completely > > > different > > > situation that is the diagonal argument.
> > > KP
> > I know ... I wasn't suggesting there was any "relationship" between > > the two cases. > > ...I was only using it as an example that sometimes a thing can have > > a certain propertie over a whole finite range of values and yet NOT > > have that property when "infinities" are involved... just that it does > > sometimes happen ... thats all .- Hide quoted text -
