By Listing Them Randomly, Could we Count the Irrationals?

middleCmusic

So, I was thinking a lot about different ways to order the irrationals. Most of them had to do with infinite-dimensional row/columns, but nothing was really working (obviously - as if I'm going to prove Cantor wrong LOL). However, despite the clear history against me, I'm wondering if it's possible to order the irrationals randomly.

It would work like this: You have a random number generator, which also contains a decimal point, which acts like another number, but can only be used once (i.e. 11 "numbers" in this machine: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ".") You'd start the number generator, and when it spits out the second non-decimal, you use that as the first of a new number, and start a second number generator. You then repeat the process and have more and more number generators working (eventually an infinite number.) If the second number spit out is a ".", you use the third number spit out. It's not exactly an "ordering", but there is there any real reason why this ordering couldn't be random? EDIT: The ordering would be that the number associated with the first number generator is 1st, the second is 2nd, and so on.

The reason I started thinking about this at all was because, in my opinion, I found Cantor's proof that the irrationals can't be ordered flawed. I'm sure the vast majority of the mathematical community disagrees, but I'll bet more than a handful find his proof a bit hand-wavy, at least the popular version. I haven't read the original. Cantor's proof depends on the list having an infinite # of entries with which to construct his new number which isn't on the list. But if you must construct this number from an infinity of numbers in your list, how can you ever know whether this new number isn't already on the list? In other words, if you can never get to the end of the list, can you really ever know if that "new" number you're constructing isn't there? And if one says that you can use the order of the list to rule that possibility out, that would seem to contradict his proof right there because Cantor's proof is supposedly saying that there ISN'T such an ordering.

I know that was probably hard to follow, and sounds like crazy jibber-jabber, but I'm very interested in this stuff, and his proof doesn't ring true to me (for the reasons above).

So... thoughts? On the random number generator idea and my critique of Cantor's proof? I'd love to hear what all of you think, especially the sages around here.

- Chris

Number Nine

I hesitate to even respond to this, since the overwhelming majority of people who make posts like yours are cranks (I've had bad experiences), but I'm crossing my fingers...

The contradiction is the point; Cantor's diagonalization argument is a proof by contradiction. Cantor assumes that such an ordering exists (which it must if the reals are countable, by definition), and then uses the order to show that there is some real number not on the list. Therefore, there is no such order. The proof is is as rigorous as they come. If an order exists, then you've missed a real number (contradiction). If no order exists, then there is no bijection with the natural numbers by definition, since any such bijection establishes an ordering.

Beyond that, you haven't really explained how your method supposedly counts the reals. Where is the purported bijection?

pwsnafu

Cantor's argument demonstrates that every order fails. It is independent of the method used to generate the order.

Number Nine

This is, strangely, an often overlooked point. People construct the most creative and elaborate supposed bijections with the natural numbers and never even bother addressing Cantor's actual argument or trying to apply it to their mapping.

dcpo

A few people have a problem with the infinite list idea, I'm not entirely sure why, but it can be thought of as an illustration. The Cantor argument doesn't need it, nor does it need to be a contradiction. In essence the diagonal argument says that any function from the natural numbers to the interval (0,1) of reals must fail to be onto. This proves by definition that (0,1) must be uncountable.

As an aside, there is a separate and very simple proof that there can be no onto function from a set to its powerset (given function [itex]f\colon X\to \wp(X)[/itex] the set [itex]\{x\in X:x\notin f(x)\}[/itex] cannot be in the range of [itex]f[/itex]). This shows that uncountable sets must exist, and it can be shown that the reals are in bijection with the powerset of the naturals and thus are uncountable

middleCmusic

I'm actually a math major in my third year and I'm quite aware that Cantor's proof is a proof by contradiction, thank you very much. :P I'm not a "crank" I assure you. Not that I am a genius or anything, and not that my argument might not be total BS, but I was inducted into Pi Mu Epsilon last year, if that means anything towards credibility. It probably wasn't very clear in my explanation, but I was making a little proof by contradiction here saying that I believe his theorem contradicts itself as a whole. The bijection is just from a random real number to an integer, in the order that the random number generators come "online". I can try to elaborate on my argument as to why it seems to me that his proof is flawed, but if there are other proofs using power sets as dcpo says below, then obviously my method cannot work regardless.

I'll try to tell you though. I'm saying that when we take new digits across the diagonal of the list, and use these new digits to create a number which is different from all the other numbers in every place, we need to continue this process forever in order to create a number which truly is an irrational. For if the process stopped at some point, we wouldn't have an irrational. So then, if we must continue this forever to get a new number, how can we ever be sure that the number we're creating isn't part of the list, just beyond the numbers we've already considered? That is what I'm saying seems to be a general contradiction in the proof for me. It just seems sort of wishy-washy. I tried but failed to think of ways to apply his method of reasoning to other more mundane examples that would produce more obviously false results. Again, if there are other proofs which convince me, certainly it would not be worthwhile to try to think of exotic ways to count the irrationals.

I get that that is what is supposedly does, but I'm saying that I think his proof is flawed.

I would really love to see this proof, as I don't have time at the moment to try to construct it on my own. Do you know of any books/links that contain it?

dcpo

The powerset proof proceeds by, given f, showing that there can be no x with f(x) equal to the set I defined in my previous post (similar to Russell's paradox, x will be in f(x) iff it is not). A discussion of bijections between the reals and the powerset of the natural numbers can be found e.g. here.

micromass

Terms like "continuing forever" are inherently unmathematical. A third year math major should be able to see this and should be able to rigorize the proof. It is true that the proof is informal, but the thing is that every textbook proof is informal. If you want to see a perfectly formal proof of Cantor's theorem then you should look at: http://us.metamath.org/mpegif/ruc.html (an informal discussion can be found at http://us.metamath.org/mpegif/mmcomp...ml#uncountable ). This should convince you that Cantor's proof is perfectly fine.

Again, don't fool yourself by using buzzwords such as "continuing forever", but try to make Cantor's proof rigorous yourself. In doing the proof, you don't need "continuing forever".

pwsnafu

Firstly, it isn't a process. The choice for every digit is done together, at the same time. You are not constructing the number one-digit-at-a-time. You don't do that when you multiply two irrational together, and you don't do it here.

Secondly, even if you did, Cantor's still right. Look at the first number on the list, and choose the first digit to be different. The remaining digits are zero. Call this x₁. Now continue this for the second digit. Call this x₂ (note that its different to the first two numbers on the list). Continue to generate a sequence. Then you have a monotonicly increasing sequence bounded above by 1. The least upper bound of the sequence cannot be on the list.

Think about what equality of two real number actually is in terms of positioning notation.

ppnl

Look at the diagonal number that Cantor's argument can produce from this list of numbers. Which random number generator generates it? It can't be the first generator because the first digit is wrong. It can't be the second generator because the second digit is wrong. It can't be the third generator because...

Cantor's argument works with any ordering. Randomness does not change that. If the process of producing the list of numbers is well defined then the process of producing the diagonal number is well defined. Then asking where the diagonal number falls in the list is a well defined question. And the answer is "Not at any finite distance down the list."

SteveL27

middleCmusic, you just earned 10 points on John Baez's famous Crackpot Index.

http://math.ucr.edu/home/baez/crackpot.html

10 points for pointing out that you have gone to school, as if this were evidence of sanity.

Nothing personal, I just thought I'd mention this amusing article in case anyone's not already familiar with Professor Baez's famous list, or his wonderful and highly accessible online work in general.

Also, although your argument's wrong, you can at least tighten it up by ignoring the complication of the "one-time-only" decimal point. It's sufficient to show that one either can or can't enumerate the reals between 0 and 1; since if those are denumerable, so are all the rest, since there are countably many intervals endpointed by consecutive pairs of integers.

Thirdly, you should be using the word "list" rather than "order." To list a set means to establish a bijection between the set and the natural numbers (or an initial segment thereof). If all you want to do is well-order the reals you can assume the Axiom of Choice, which guarantees a well-order of any set whatsoever. And if all you want is a linear order, the usual order on the reals will suffice.

middleCmusic

Thanks, I'll definitely check it out.

Thanks for the links! And yes, I know my discussion wasn't a rigorous proof. It wasn't even meant to be a proof of course, just criticism of Cantor's proof.

I realized from looking at ppnl's response that my mistake was not considering the list as already completed. Considering an infinite list as ever being "complete" is a little hard to wrap the head around when you're first thinking about it, so that's what tripped me up.

Thanks - that cleared things up for me.

Well, at least it was only ten points, I guess. :P I don't mean to be crackpot-y or snooty by mentioning that - it's just that I posed a discussion and was immediately being accused of basically trolling, so I thought I should give some evidence that I wasn't a 12-year-old hooked on Wikipedia. Baez's list is great btw.


Thanks everyone for all the input! No one person fixed my brain, but between all of your responses, I think I get where I was screwing up with Cantor's proof now. I realize that writing a post about the non-denumerability of the irrationals, the Goldbach conjecture, the Riemann Zeta function, etc., immediately raises eyebrows, but I'd rather get my head straightened out now than pursue a meaningless idea for years and years, which is how real crackpots are made.