Infinities

[Jake]

How is it possible that some infinities can be bigger than others? Seems like it contradicts the concept of infinity! Or something.

[friedo]

If it helps, try not to think of infinity as meaning "everything." What it really means is "if you tried to count it, it would take forever."

So, take the set of even positive integers, E: { 2, 4, 6, 8 ... } Obviously, it's infinite. If we tried to count them, it would take forever. It's also a subset of the set of all positive integers, P, and there are positive integers which aren't even. Therefore, P must have more items in it than E, even though we already know that E is infinitely big. Wacky.

For the purposes of basic algebra and calculus, this doesn't matter. Infinity can be treated as just a really big limit. It starts to matter when you study set theory and other topics, and learn about aleph numbers and such. That stuff is beyond me, though.

[Anne Neville]

First, realize that your common sense notions of one thing being "bigger" than another don't really apply to infinities. Your common sense is based on your experiences with finite sets, so you're going to have rules and concepts that don't really apply when you talk about infinite sets.

It's kind of like how your common sense ideas of physics don't always apply in circumstances you don't have experience with, like a vacuum. It makes perfect sense to say that a heavier object will fall faster than a lighter one in air, because that's generally what does happen in your everyday experiences (all of which include air, at least for most people). That doesn't mean that that's what will happen in a different set of circumstances (like in a vacuum).

Originally Posted by friedo

So, take the set of even positive integers, E: { 2, 4, 6, 8 ... } Obviously, it's infinite. If we tried to count them, it would take forever. It's also a subset of the set of all positive integers, P, and there are positive integers which aren't even. Therefore, P must have more items in it than E, even though we already know that E is infinitely big. Wacky.

Except P doesn't have more items in it than E.

When you're comparing infinite sets, the question to ask isn't "are all the items in E also in P, and are there also items in P that are not in E?" The right question to ask is "can you come up with a one-to-one function that maps all members of E onto members of P?"

What you're trying to do is find some way to match each member of E to each member of P. It's just like matching socks after doing laundry, really (assuming each pair of socks that you have is different from every other pair)- each left sock matches to only one right sock, and each right sock matches to only one left sock.

We do this by trying to come up with an equation that says how to match items from E to items from P. With the sets E (even integers) and P (all integers), the equation y = 2x will work, where x is a member of P and y is a member of E. For every x in P, that equation gives you exactly one y which is a member of E. For every y in E, that equation matches it to exactly one x which is a member of P. Every even integer is 2 times some integer, in other words. You could make a list that shows how they match up:

1. 2
2. 4
3. 6
4. 8

and so on. Every member of P will have a corresponding member of E, and every member of E will appear somewhere in this list.

From the sock example, though, that must mean that the sets are the same size- if you can match one right sock to every left sock, that means you must have the same number of left and right socks. So E and P are the same size, even though there are items in P that aren't in E. Yes, it's freaky, but that's infinite sets for you.

Using a different equation, you can also match up the set of all positive integers plus zero (all non-negative integers) to the set of all positive integers (the equation here is y = x + 1). (Yes, a set that your common sense tells you has one more member than another set is the same size.) You can also match up the set of all positive and negative integers to the set of all positive integers. Any set that you can match up to the set of positive integers this way is said to have a size of aleph-null.

There are infinite sets that don't have a size of aleph-null. The set of all real numbers is one of them. There's a rather clever proof of that that Georg Cantor came up with:

Suppose you did have a one-to-one equation that connected the integers and the real numbers. For simplicity's sake, let's say you had a one-to-one equation that mapped the integers to the real numbers between 0 and 10 (that has to be the same size as the set of all real numbers or smaller). If you did, you could make a list of the real numbers. It might look something like this:

1. 0.00000...
2. 3.14159...
3. 2.71725...
4. 0.77777...
5. 1.29975...

and so on. But I can prove that there is at least one real number that isn't anywhere in your list. For each number in your list, this number is 1 bigger than the number in your list in the decimal place corresponding to its place in the list. For the list I've got there, the number would be 1.2288... The first digit is one different from the zero in the first position of real number #1, the second is one different from the one in the first decimal place of #2, the third is one different from the one in the second decimal place of #3, and so on.

If you try to say, "But that number is in the list, it's #137 in the list", I can say, "No, it isn't- it's one different from #137 in the list in the 136th decimal place." That proves that you can't match the set of all real numbers to the set of integers the way you could match the set of integers to the set of even integers. You've got at least one right sock (real number) that doesn't match up with any left sock (integer), so you must have more right socks than left socks. There are more real numbers than there are integers.

There's a name for the size of the set of all real numbers- it's called aleph-one. It's also sometimes called the continuum. The question of whether there is any "aleph-one-half", or is there any infinite set that is bigger than the set of integers and smaller than the set of real numbers, is an unsolved problem in modern mathematics. Nobody knows, in other words. Cantor suspected that there isn't, but he couldn't prove it, and nobody since him (he died in 1918) has been able to prove or disprove it.

[Yllaria]

It may or may not help if you think of a lace doily that's two inches wide, but whose length is infinite. Put the doily on top of a 2x4 with infinite length, and you can see 2x4 through the gaps in the doily, even though both go on forever. However if you put the 2x4 on top, you can't see the doily at all. Therefore the 2x4 represents a larger infinity.

Now imagine a 2 x infinity plane. Put the doily and the 2x4 on top of it. You can see plane sticking out from under both the doily and the 2x4. But if the plane was on top, you couldn't see either. The plane is therefore a larger infinity than either the 2x4 or the doily.

I see the doily as representing sequences and the plank and plane as representing continua, but that may be because of a weakness in my math. Feel free to slam, debunk, or correct the doily/plank explanation in any way it needs to be slammed, debunked, or corrected.

[minor7flat5]

But the presence of gaps doesn't correlate to one infinity being greater than the other. Anne Neville showed this: she matched one sparse set if integers with the full set of integers. Even though the doily (the even integers) allows the full set of integers to peek through, they can be matched one to one since the set never ends.

I have heard of a similar trick used to match points on a line with points on a plane: you can express the point in the plane as an X,Y pair of real numbers. Then all you need to do is make a new single real number by using the digits of X for the odd digits and the digits of Y for the even digits.

1.234
5.678

maps to

15.263748

Now that's where my memory of this ends. I vaguely recall that the integers and the real numbers are different forms of infinity, as Anne pointed out, but that points on a line (the real numbers) vs. points on a plane are the same, using the trick above.

I recall a mention that the number of different curves in a plane is a higher kind of infinity than the real numbers, but I can't quite get my head around that statement, so I never went any further.

[DrCube]

I read your question a little differently than Anne Neville (whose post was quite informative):

Basically, math only incidentally has any kind of relationship to "reality". You make up some definitions, some assumptions, some rules of inference and then you play the game and see where it all gets you -- that's math. Of course it would be a complete waste of time if it wasn't useful, so mathemeticians try to start out with definitions and assumptions that correspond in some ways to what we know is true already.

Long story short: "Bigger" in this instance means "can't be put into one-to-one correspondence with"; that's all it means. It is useful because in real life one-to-one correspondence is often how we tell which member of a set is bigger. When I'm at the roulette table for instance, I have one stack of twenty chips that I measure all my other stacks of chips against in just this way.

I kind of disagree with the notion that our "common sense" just can't handle infinities; it's that the definitions involved mean different things than they do in the context of finite numbers simply because that's the only way they'll make any sense at all.

[Anne Neville]

Originally Posted by DrCube

I kind of disagree with the notion that our "common sense" just can't handle infinities; it's that the definitions involved mean different things than they do in the context of finite numbers simply because that's the only way they'll make any sense at all.

You have to make some adjustments to your common sense ideas to deal with a situation (like infinite sets) that you don't have experience with. Common sense says that, if you can match sets A and B in a one-to-one correspondence, that means that A can't contain everything in B plus some additional things- you'd match up the members of A and B that are the same, and have the additional members of A left over, and there'd be no way to match them all up one-to-one. That common-sense logic works for finite sets, but not for infinite ones. You could call it a change in the definition of "bigger" for infinite sets, or that infinite sets don't work the way that common sense tells you sets work. It's two ways of looking at the same thing.

[Rysto]

Originally Posted by Anne Neville

There's a name for the size of the set of all real numbers- it's called aleph-one. It's also sometimes called the continuum. The question of whether there is any "aleph-one-half", or is there any infinite set that is bigger than the set of integers and smaller than the set of real numbers, is an unsolved problem in modern mathematics. Nobody knows, in other words. Cantor suspected that there isn't, but he couldn't prove it, and nobody since him (he died in 1918) has been able to prove or disprove it.

You have your notation wrong. Aleph-One is the cardinality of the set of all countable ordinal numbers. Cantor's Continuum Hypothesis says that the cardinality of the set of all real numbers(let's call it c) is equal to Aleph-One(well, it does with the Axiom of Choice), but that has not been proven.

[Yllaria]

Originally Posted by minor7flat5

But the presence of gaps doesn't correlate to one infinity being greater than the other. Anne Neville showed this: she matched one sparse set if integers with the full set of integers.

Both the integers and the even integers would be doilies. You can manipulate any one doily to cover any other doily. To be a 2x4, a continuum is required.

[Bytegeist]

Originally Posted by Rysto

You have your notation wrong. Aleph-One is the cardinality of the set of all countable ordinal numbers.

I think you meant Aleph-Null there.

[ultrafilter]

Originally Posted by Anne Neville

There's a name for the size of the set of all real numbers- it's called aleph-one. It's also sometimes called the continuum. The question of whether there is any "aleph-one-half", or is there any infinite set that is bigger than the set of integers and smaller than the set of real numbers, is an unsolved problem in modern mathematics. Nobody knows, in other words. Cantor suspected that there isn't, but he couldn't prove it, and nobody since him (he died in 1918) has been able to prove or disprove it.

Good post, but there are a couple errors in this paragraph. As mentioned, the cardinality of the naturals is aleph₀. The cardinality of the reals is 2^aleph₀. The equality of 2^aleph₀ and aleph₁ is independent of the standard axiomatization of mathematics. Wikipedia has a pretty good article discussing this and its generalization.

[Rysto]

Originally Posted by Bytegeist

I think you meant Aleph-Null there.

No. Aleph Null is the cardinality of the set of integers.

[Jake]

Thanks All. You've given me plenty to think about. Please keep up the discussion.

[Chronos]

The question of whether there is any "aleph-one-half", or is there any infinite set that is bigger than the set of integers and smaller than the set of real numbers, is an unsolved problem in modern mathematics. Nobody knows, in other words. Cantor suspected that there isn't, but he couldn't prove it, and nobody since him (he died in 1918) has been able to prove or disprove it.

It's a bit misleading to say that this is an unsolved problem. The question has been completely resolved: We know for an absolute fact that it cannot be answered. For the continuum hypothesis to be false is exactly as consistent as for it to be true.

[ianzin]

Originally Posted by Anne Neville

For simplicity's sake, let's say you had a one-to-one equation that mapped the integers to the real numbers between 0 and 10 (that has to be the same size as the set of all real numbers or smaller). If you did, you could make a list of the real numbers. It might look something like this:

1. 0.00000...
2. 3.14159...
3. 2.71725...
4. 0.77777...
5. 1.29975...

and so on. But I can prove that there is at least one real number that isn't anywhere in your list. For each number in your list, this number is 1 bigger than the number in your list in the decimal place corresponding to its place in the list. For the list I've got there, the number would be 1.2288... The first digit is one different from the zero in the first position of real number #1, the second is one different from the one in the first decimal place of #2, the third is one different from the one in the second decimal place of #3, and so on.

If you try to say, "But that number is in the list, it's #137 in the list", I can say, "No, it isn't- it's one different from #137 in the list in the 136th decimal place." That proves that you can't match the set of all real numbers to the set of integers the way you could match the set of integers to the set of even integers.

This is Cantor's famous 'diagonal shift' proof of infinities distinct from aleph null. However, it's flawed.

(1) It is based on being able to create, construct or write a list of the real numbers. However, if we accept the concept of infinity, you can't do this. There is no way to create such a list. Note that you have done what Cantor and every other writer has done. You have given a few lines of this supposed list and then added 'and so on'. You have also used an ellipsis at the right-hand end of every line to indicate 'and so on'. However, 'and so on' is only meaningful if the omitted sections could be constructed, written or depicted, but are omitted for reasons of simplicity or saving time. This is not the case here. There is no way to create this list. You can define what items would be on the list, but that's not the same as actually listing them. The former is possible, the latter is not. It's a subtle distinction, but an important one.

Writing a few lines of this supposed list and then adding 'and so on' is a kind of mathematical three card trick. It gets past the critical thinking gate for most readers, but it is flawed. This list could never be written, constructed or depicted. If you doubt me, then I challenge you to do a simple thing that can be done with any list: reverse the order of its constituent elements. Tell me what number is now at the top. You can't. This should give us a clue that to refer to this 'list' is actually meaningless.

(2) You cannot draw a diagonal line through the numbers in this list. Not only is it impossible for anyone to create this list, you cannot produce, draw or define a 'diagonal' line which passes through the nth digit of the nth member of the list (as Cantor suggested). If you don't appreciate this, ask yourself where the other end of the diagonal line is. We know it starts at what would be graph co-ordinates 0,0. But where is the other end? Give me the co-ordinates, and I will accept it can be drawn. But it can't. So the idea of a 'diagonal shift' is also flawed.

'Diagonal' as a concept is only meaningful if we can define end points. It is easy to define the 'diagonal' of a square or a chess board. But the 'list of numbers' you have presented cannot have a 'diagonal' because there is no way to define what this 'diagonal' would be or consist of. It only has one co-ordinate. If you feel tempted to reply that the other end lies at a co-ordinate defined by infinity along the x axis and infinity along the y axis, then tell me its co-ordinates when rotated 90 degrees. You can do this (define the result when the diagonal is rotated 90 degress) for a square or a chess board, because 'diagonal' is meaningful in these cases. You cannot do this for the list of numbers, which should provide a clue to the fact that 'diagonal' in meaningless in this context.

[Chronos]

(1) It is based on being able to create, construct or write a list of the real numbers. However, if we accept the concept of infinity, you can't do this.

The whole crux of the proof is that you can't do it. That's how the proof works. However, the reason you can't do it isn't just that the list is infinite. You can construct a list of all of the integers.

The diagonal is likewise perfectly well-defined. We don't need to be able to specify the "other endpoint"; we just need to be able to specify every element of it, which we can do.

[ultrafilter]

Here's Cantor's argument in something closer to formal detail:

Assume that we have a function f which is a bijection between the positive natural numbers and decimal representations of real numbers in the interval [0, 1). Since f is a bijection, we know two things:

1. If f(m) = f(n), m = n.
2. For every decimal representation d, there is a natural number n_d such that f(n_d) = d.

Denote by d_i the ith digit to the right of the decimal point in the representation d. We construct a new representation k such that k_i = 1 if f(i)_i = 0 and 0 otherwise. By property 2 above, there is a positive natural n_k such that f(n_k) = k. But by our construction, k_nk is not equal to f(n_k)_k, and it follows that f(n_k) is not equal to k. This implies that there is no bijection f between the positive natural numbers and decimal representations of real numbers in the interval [0, 1).

To establish that the reals are larger than the naturals we have to show three additional facts:

1. [0, 1) has the same cardinality as the entire real line: Consider the function g defined by g(x) = (arctan(x) + 1)/2. This is a bijection between [0, 1) and the real line. I'll leave the details of the proof to the reader.
2. There is some subset of [0, 1) which has the same cardinality as the positive natural numbers: Let n be a positive natural number, and let d(n) be the least integer not less than log₁₀(n). The function h defined by h(n) = n/10^d(n) is a bijection between the positive naturals and some subset of [0, 1).
3. The positive naturals have the same cardinality as the naturals including zero: The bijection here is obvious.

[Capt. Ridley's Shooting Party]

The diagrammatic nature of the proof is an aid to understanding and guide to intuition, not the crux of the proof. Not being able to physically draw an infinite line is neither here nor there.

Of course, Cantor's theorem and his diagonal argument aren't just idle intellectual curiosities. Diagonalisation is used all over theoretical computer science, for instance, and was instrumental in Turing's proof of the existence of undecideable numbers.

[ianzin]

Originally Posted by Chronos

You can construct a list of all of the integers.

Please demonstrate, or show me where someone has managed to do this. I wold be fascinated.

The diagonal is likewise perfectly well-defined. We don't need to be able to specify the "other endpoint"; we just need to be able to specify every element of it, which we can do.

Please do so, or show me where someone has managed to do this. Also, please respond to my earlier point and tell me where either end point of this diagonal may be found once you have rotated it through 90 degrees.

[Frylock]

Originally Posted by ianzin

Please demonstrate, or show me where someone has managed to do this. I wold be fascinated.

Here is what is meant by the claim that "you can construct a list of all the integers." What you are able to do is specify a way of writing out a sequence of integers such that, given any particular integer N, you are guaranteed eventually to write the number N in a finite amount of time. I give you the way of writing a sequence. You give me the number. And I will always (given enough time) be able to show you exactly where in my sequence your number ends up showing up.

What is meant, then, by the claim that you can't construct a list of the real numbers is the following. There is no way to specify any way of writing a sequence of real numbers such that, given any particular real number N, you are guaranteed eventually to write the number N in a finite amount of time. In other words, given any way of writing out a sequence of real numbers, there will always be at least one number N (*) which will not appear anywhere in that sequence in any amount of time, neither in any finite amount of time or in an infinite amount of time if there were such a thing.

That is what Cantor proved, paraphrased.

-FrL-

(*)Actually, for any way of sequencing real numbers, there are always an infinite number of such Ns. How big an infinity? The same size as the infinity of real numbers.

[Frylock]

Originally Posted by ianzin

(1) It is based on being able to create, construct or write a list of the real numbers.

This is a very strange criticism. Cantor's proof sets out to show that this is impossible to do. So he certainly doesn't base his proof on the idea that you can do so.

What he does do, though, is "assume" (in a loose sense) that you can do so, specifically for the purpose of showing that this assumption can't actually hold. It's a reductio argument. But "assuming" p for a reductio is by no means basing one's proof on an assertion that p is the case! Almost exactly the opposite!

-FrL-

[Frylock]

Originally Posted by ianzin

(2) ...
'Diagonal' as a concept is only meaningful if we can define end points.

Certainly not. A diagonal line can be specified by a point and a slope.

-FrL-

[ultrafilter]

Originally Posted by ianzin

Please demonstrate, or show me where someone has managed to do this.

I wold be fascinated. Please do so, or show me where someone has managed to do this. Also, please respond to my earlier point and tell me where either end point of this diagonal may be found once you have rotated it through 90 degrees.

You're getting caught up on the common meaning of words that are being used to signify some mathematical jargon. I've already explained Cantor's argument in detail, so please take a look at that.

With regards to the diagonal, what we're really talking about is the diagonal of a countably infinite matrix. This is a perfectly well-defined mathematical object.

[Frylock]

Originally Posted by ultrafilter

You're getting caught up on the common meaning of words that are being used to signify some mathematical jargon. I've already explained Cantor's argument in detail, so please take a look at that.

With regards to the diagonal, what we're really talking about is the diagonal of a countably infinite matrix. This is a perfectly well-defined mathematical object.

Not a good cite when discussing ianzin's particular objection, since the definition it gives refers explicitly to two endpoints.

-FrL-

[ultrafilter]

Originally Posted by Frylock

Not a good cite when discussing ianzin's particular objection, since the definition it gives refers explicitly to two endpoints.

-FrL-

Damn, I didn't even notice that. It's still a matrix diagonal, but you have to use a more formal definition of a matrix (which I guess I mentally substituted there).

[Thudlow Boink]

Originally Posted by ianzin

This is Cantor's famous 'diagonal shift' proof of infinities distinct from aleph null. However, it's flawed.

(1) It is based on being able to create, construct or write a list of the real numbers. However, if we accept the concept of infinity, you can't do this. There is no way to create such a list.

ianzin, are you a finitist, like Cantor's arch-enemy Leopold Kronecker?

The point of Cantor's proof is that, for any list of real numbers, there must be a real number that is not on the list. There's nothing in it about constructing a list: rather, given any such list, it's a way of constructing a number not on the list.

And by a "list" of elements, what is really meant is a one-to-one correspondence between those elements and the natural numbers.

I agree with ultrafilter that you look like you're getting caught up on common meanings of words, like "diagonal."

[Frylock]

Originally Posted by Thudlow BoinkThe point of Cantor's proof is that, for [b

any[/b] list of real numbers, there must be a real number that is not on the list. There's nothing in it about constructing a list: rather, given any such list, it's a way of constructing a number not on the list.

A finitist would not find this result suprising. "Any list" would include only finite lists, so of course there would be numbers not on the list.

I think the best way to put it when responding to a certain family of objections is as possible. The proof is that for any method for extending a list of real numbers indefinitely, there will always be a real number which will never show up on the extended list, no matter how far it has been extended. But importantly, this is not the case for the integers.

I think a finitist agrees that lists can be indefinitely extensible, even if never actually infinite.

-FrL-

[The Them]

If I'm reading this right, the diagonal technique is for rational numbers only (for which it works fine, just inefficiently). A transcendent number could be found too, with an infinite number of steps.
There was a class called "Comparative Infinities" that I didn't get to take because I had requireds filling that time slot. Consoled myself with "Non-Euclidean Geometry."
A cute thing that I guess the logic prof did to discourage us until we were higher level went like this:

Assume x=1+2+4+8+16+32+64+...
Then x=1+2(1+2+4+8+32+64+...)
Therefore
x=1+2x

The idea being that infinity is not entirely agreed upon yet. Heck, can anyone integrate 0/0?
And x=-1/2.

[Derleth]

Originally Posted by ianzin

If you doubt me, then I challenge you to do a simple thing that can be done with any list: reverse the order of its constituent elements. Tell me what number is now at the top.

As soon as you tell me the last number of e. (Decimal base representation only, please.)

[ianzin]

Originally Posted by Frylock

What he does do, though, is "assume" (in a loose sense) that you can do so, specifically for the purpose of showing that this assumption can't actually hold. It's a reductio argument. But "assuming" p for a reductio is by no means basing one's proof on an assertion that p is the case! Almost exactly the opposite!

First of all, I have no idea what your bracketed term " (in a loose sense) " means, and I would love you to elucidate.

Secondly, I am well aware of what constitutes a reductio ad absurdum argument, and my view is that Cantor's proof isn't one, or at least not a valid one. A reductio ad absurdum argument shows that a sequence of legitimate steps or deductions leads to a contradicton. What I am discussing is the fact that Cantor's famous proof involves an illegtimate step. Specifically, it asserts that, given an infinitely long list of numbers, one can construct a new number by taking the first digit of the first number, the second digit of the second number and so on. This sounds seductive and plausible, which is why is tends to pass without remark or objection. However, this procedure is only legitimate and meaningful for a finite list of numbers. If you are starting with a list of numbers that you assert has an infinite number of members, each of which can be expressed as an infinitely long decimal (hence the use of an ellipsis at the right-hand end of each number in Anne Neville's list), then the procedure described is meaningless.

Cantor's proof as it is traditionally presented uses an analogy in which the first part corresponds to easily understood, easily visualised everyday life, but the second part does not. This is where the illegitimate step creeps in, usually unnoticed. If you show me ten numbers written down as decimals, sure, I can note the first digit of the first number, the second digit of the second number, and so on for the complete list. This is something no-one has trouble either visualising or understanding. If one wants to, one can actually perform this task and, by altering each of the noted digits in some specific way (for example by adding 1), one can create an eleventh number that is distinct from each of the ten numbers originally on the list. Cantor's proof, as traditionally presented, and as presented earlier by Anne Neville, just assumes that one can perform the same operation on an infinitely long list of infinitely long decimal expressions, and uses this step within a reductio ad absurdem argument. What I am saying is open to qurstion is whether this assumption holds. I maintain that it does not.

One cannot perform this operation (taking the first digit of the first number... and so forth) on an infinitely long list. One way to realise this is to appreciate that one cannot count along to the 'infinity-th' digit of an 'infinitely' long number. Infinity is not a term that refers to a location, either on a long decimal expression or in any other sense. It is the term we use to denote 'non-finite'.

Another way to realise this is by reference to my earlier thought experiment about a diagonal line. On my list of ten numbers I can construct a diagonal line (passing through the nth digit of each of the countable numbers on the list), and if I want to I can rotate this diagonal line through 90 degress and tell you where the end points lie after this rotation. I cannot do this on Cantor's list. On Cantor's list, the 'diagonal line' cannot be created in the first place. If it were possible, Cantor would be able to rotate this line through 90 degrees and tell me where the end points or defining point now lie.

[ianzin]

Originally Posted by Frylock

Certainly not. A diagonal line can be specified by a point and a slope.

I believe I was referring to Cantor's proof as it is traditionally presented, for example in Godel, Escher, Bach which happens to be where I first read about it over 25 years ago, and in Anne Neville's earlier post. These presentations of the proof make no reference that I can find to 'a point and a slope'.

[ianzin]

Originally Posted by Frylock

Not a good cite when discussing ianzin's particular objection, since the definition it gives refers explicitly to two endpoints.

Thank you for bothering to point this out so that I don't have to.

[Capt. Ridley's Shooting Party]

Specifically, it asserts that, given an infinitely long list of numbers, one can construct a new number by taking the first digit of the first number, the second digit of the second number and so on. This sounds seductive and plausible, which is why is tends to pass without remark or objection.

Is addition of a number with an infinite decimal expansion meaningful? How?

[ianzin]

Originally Posted by Thudlow Boink

The point of Cantor's proof is that, for any list of real numbers, there must be a real number that is not on the list.

To be more precise, Cantor's proof refers to any complete list of real numbers. But if it is complete, one cannot then define a number that isn't on it. If one can define a number that isn't on it, then it isn't complete.

You will be familiar with argument about what happens when an irresistible force meets and immovable object. The answer is that in any defined world or system, if the word 'irresistible' is meaningful then no object can be immovable, and vice-versa. So the question as posed contradicts itself and at least one of the constituent terms must be rendered void or meaningless. It's the same with Cantor's proof as typically presented in prose terms. Either 'complete' means something, or it doesn't. If it means something, then one cannot use this term as part of a construction process that yields a number not on the list. If it does not mean something, then yielding a number that is not on the list is a trivial task that is of no importance (because the list was never said to be complete in the first place).

There's nothing in it about constructing a list: rather, given any such list, it's a way of constructing a number not on the list.

Your are aserting both that it is not about constructing a list and that it is about constructing a number not on the list. However, one can only define the latter (elements not on the list) if the list has previously been constructed.

[Capt. Ridley's Shooting Party]

To be more precise, Cantor's proof refers to any complete list of real numbers. But if it is complete, one cannot then define a number that isn't on it. If one can define a number that isn't on it, then it isn't complete.

What? No it doesn't. I thought you said you understood r.a.a? Cantor assumes, for the sake of reductio, that his list is complete. He then constructs a new real that isn't enumerated by the list, thus showing that his initial assumption, that the list is complete, is false.

[Frylock]

Originally Posted by Dominic Mulligan

What? No it doesn't. I thought you said you understood r.a.a? Cantor assumes, for the sake of reductio, that his list is complete. He then constructs a new real that isn't enumerated by the list, thus showing that his initial assumption, that the list is complete, is false.

This is true, and is exactly my point from above ianzin.

Originally Posted by ianzin

Secondly, I am well aware of what constitutes a reductio ad absurdum argument, and my view is that Cantor's proof isn't one, or at least not a valid one. A reductio ad absurdum argument shows that a sequence of legitimate steps or deductions leads to a contradicton. What I am discussing is the fact that Cantor's famous proof involves an illegtimate step. Specifically, it asserts that, given an infinitely long list of numbers, one can construct a new number by taking the first digit of the first number, the second digit of the second number and so on. This sounds seductive and plausible, which is why is tends to pass without remark or objection. However, this procedure is only legitimate and meaningful for a finite list of numbers. If you are starting with a list of numbers that you assert has an infinite number of members, each of which can be expressed as an infinitely long decimal (hence the use of an ellipsis at the right-hand end of each number in Anne Neville's list), then the procedure described is meaningless.

Let's not confuse your criticism of the possibility of diagonalization with your criticism from the impossibility of a list of the real numbers. Here you purport to be defending the latter criticism, but you are actually defending the former.

Your latter criticism trivially fails to apply to Cantor, because Cantor does not assume the possibility of a list of the real numbers, but rather constructs the proof to show that it is false.

Here is why your diagonalization criticism fails. Here is what it is possible to do. Note that a real number can be thought of as an indefinitely extensible list of digits (though for most reals we don't have a finite rule for extending that list). Now suppose we have specified a method for writing down a sequence of representations of real numbers. This is a method whose execution can never be actually completed, of course, but we can still give a method--one which makes it clear, given a coordinate, (here I'm thinking of the Cantor grid) what digit would be there. So then, given the existence of such a method, what is possible is to define a method for extending a particular list of digits indefinitely--namely the list of digits which are like this: for each slot in this list numbered m, the digit found there is identical to that found at coordinate [m, m], plus one. I can never finish writing this list, but you give me an m and I can tell you, in a finite amount of time, exactly what digit will be found at the mth place.

And since the digit at the mth place on this list (which is trivilly interpretable as a representation of a real number) at m will always differ from the digit on the grid at [m, m], it follows that the list is not the same as any row (or column) of the grid. Since the rows and the list represent real numbers, we can evaluate this conclusion as indicating that given any method for extending a list of real numbers indefinitely, it is always possible to define a real number (i.e. give a method for extending a list of single digits indefinitely) which would never appear on that list of real numbers no matter how long you went on writing it out. And importantly, what I just said is not true of lists of integers.

-FrL-

[Frylock]

ianzin, I'm interested in seeing a response to post 20 above (some of which I repeat in my last post). Do you agree that what I claim is possible and impossible there are in fact possible and impossible? Do you agree that the claim I make there is equivalent to the claim proved by Cantor?

(Mathematicians here, I'm also interested to hear your view on the questions, esp. the latter. Am I making a mistake to think Cantor's claim can be interpreted the way I've interpreted it?)

-FrL-

[Tyrrell McAllister]

ianzin, I think that you are putting too much stock in the popularized version of Cantor's proof that you read in Gödel, Escher, Bach. What GEB gives is perfectly fine, given that its constrained to use only concepts available to the lay reader. GEB takes certain formal concepts in mathematics, such as bijections, and "de-formalizes" them into more familiar concepts, such as lists. But these more familiar concepts are necessarily less precise. As they are given in popular accounts, they do not withstand the extremely rigorous scrutiny that you want to apply.

This means that, to subject the original argument to rigorous scrutiny, you are going to have to "re-formalize" the concept involved. My diagnosis of your doubt of the argument is that you are "re-formalizing" it in the wrong way. That is, you are not recovering the original formal argument as mathematicians understand it. Fortunately, ultrafilter already did the work of giving the true formal version of the argument in post #17. If you are going to accuse literally all professional mathematicians over the last century of being guilty of missing a simple mistake, you should level your criticisms at the actual argument, not at a less rigorous popularized version.

So I suggest that you pose your criticism in the context of the argument as ultrafilter gave it in post #17. If, for whatever reason, you can't do that, then you are not really addressing Cantor's proof.

[Scuba_Ben]

Originally Posted by Rysto

No. Aleph Null is the cardinality of the set of integers.

I was under the impression that aleph₀ was the cardinality of the set of rational numbers. Paging mathochist and other exotic-math experts....

[ultrafilter]

Originally Posted by Scuba_Ben

I was under the impression that aleph₀ was the cardinality of the set of rational numbers. Paging mathochist and other exotic-math experts....

The integers, naturals and rationals all have the same cardinality. By extension, any infinite set containing tuples of integers, naturals or rationals is countable as well.

[Giles]

Originally Posted by Scuba_Ben

I was under the impression that aleph₀ was the cardinality of the set of rational numbers. Paging mathochist and other exotic-math experts....

That's the same number, but it's more usual to define it as the cardinality of the natural numbers, i.e., the positive integers (including 0), since the natural numbers can be easily based on set theory. Every finite set has n elements, where n is a natural number.

[Thudlow Boink]

Originally Posted by ianzin

Specifically, it asserts that, given an infinitely long list of numbers, one can construct a new number by taking the first digit of the first number, the second digit of the second number and so on. This sounds seductive and plausible, which is why is tends to pass without remark or objection. However, this procedure is only legitimate and meaningful for a finite list of numbers. If you are starting with a list of numbers that you assert has an infinite number of members, each of which can be expressed as an infinitely long decimal (hence the use of an ellipsis at the right-hand end of each number in Anne Neville's list), then the procedure described is meaningless.

I think the problem is that such a procedure is dependent on the axiom of choice, and that you (ianzin) do not accept that axiom.

[ultrafilter]

Originally Posted by Thudlow Boink

I think the problem is that such a procedure is dependent on the axiom of choice, and that you (ianzin) do not accept that axiom.

I don't think it depends on the axiom of choice. If we can construct an explicit function to choose an element out of any given subset of a set, we don't have to invoke the AoC. It's only when you have to make arbitrary/undefineable choices that the axiom comes into play.

Somebody (I think Bertrand Russell) once noted that you don't need the axiom to choose one shoe from each of a countably infinite set of pair of shoes, but you do need it to do the same with socks. I think we're dealing with shoes rather than socks here.

[Giles]

Originally Posted by ultrafilter

Somebody (I think Bertrand Russell) once noted that you don't need the axiom to choose one shoe from each of a countably infinite set of pair of shoes, but you do need it to do the same with socks. I think we're dealing with shoes rather than socks here.

What if you're like me, and keep your socks in pairs? (Not that I have a countably infinite number of socks in my sock drawer).

[Frylock]

Originally Posted by The Them

Assume x=1+2+4+8+16+32+64+...
Then x=1+2(1+2+4+8+32+64+...)
Therefore
x=1+2x

The idea being that infinity is not entirely agreed upon yet. Heck, can anyone integrate 0/0?
And x=-1/2.

I think you meant that x = -1.

And also: You just blew. My mind.

I have never seen that one before.

-FrL-

[ultrafilter]

Originally Posted by Giles

What if you're like me, and keep your socks in pairs? (Not that I have a countably infinite number of socks in my sock drawer).

You still need the axiom. With shoes, you can come up with a rule to choose (e.g., always pick the left one). At least with a brand new pair of socks, there are no distinguishing features, so you can't have so succinct a rule.

[The Them]

This will be my last chance before someone who knows their stuff comes along and makes me look really bad.

The way I was taught to deal with infinity was not as a number, but as a limit. That is, there is no such thing as n/0, but there IS lim(x->0)n/x=infinity.

Apologies for being incompetent with the character map.

Infinity itself was on the border of "undefined." Though certainly useful. There's also bounded infinities, the easiest being the Koch Curve (we called it the Star of David Sequence), in which the boundary is infinity, but the area within is known.

Attempting to participate in this thread is gonna get me in a lot of trouble.

[Thudlow Boink]

Originally Posted by ultrafilter

I don't think it depends on the axiom of choice. If we can construct an explicit function to choose an element out of any given subset of a set, we don't have to invoke the AoC. It's only when you have to make arbitrary/undefineable choices that the axiom comes into play.

Yeah, I think you're right. (But I still think ianzin sounds like the kind of person who wouldn't accept the Axiom of Choice.)

[Giles]

Originally Posted by The Them

This will be my last chance before someone who knows their stuff comes along and makes me look really bad.

The way I was taught to deal with infinity was not as a number, but as a limit. That is, there is no such thing as n/0, but there IS lim(x->0)n/x=infinity.

Yes, thinking of infinity in terms of limits is right in analysis. However, when you talk about cardinal numbers, you are in set theory, where limits are not so important. (Though they are in the background: Cantor's proof involves decimal fractions, and those decimal fractions are really limits of an inifinte series).

[Tyrrell McAllister]

Originally Posted by Scuba_Ben

I was under the impression that aleph₀ was the cardinality of the set of rational numbers. Paging mathochist and other exotic-math experts....

You and Rysto are both right. The cardinality of the rationals is equal to the cardinality of the integers.

Here's a proof that the rational numbers in the open interval (0,1) are countable.

Recall that every nonzero rational number q in (0,1) can be written in a unique way as m_q / n_q with m_q and n_q coprime integers and 0 < m_q < n_q. Observe that for each positive integer N, there is a finite list of rational numbers q in (0,1) with n_q = N (ordered according to their position on the number line). Call this list L_N.

By concatenating these finite lists

L₁, L₂, L₃, . . .,

we get a countable list, which exhibits a bijection F between nonzero rational numbers and the positive integers.

More precisely, we define the bijection F as follows: Given a rational number q = m_q / n_q in (0,1), let k_q be the position of q in the list L_nq containing it. Let

F(q) = |L₁| + |L₂| + . . . + |L_{nq - 1}| + k_q.

(Here, |L_N| denotes the number of terms in the list L_N.) This defines our bijection in a way that hopefully even ianzin finds unobjectionable .