Talk:Cantor's diagonal argument/Archive 1
![]() | This is an archive of past discussions. Do not edit the contents of this page. If you wish to start a new discussion or revive an old one, please do so on the current talk page. |
Archive 1 | Archive 2 | Archive 3 |
I'm glad there is an article on this in Wikipedia. Cantor's Diagonal argument is my favourite piece of Mathematics - Andre Engels
OK, the two "notes" on the page as it currently stands is annoying. We can prove this property of the *reals*, and not just their decimal expansions if we use the following rule: The digit x is increased by 1, unless it is 8 or 9, and then the digit becomes 1. This will gaurantee the number is different from every other number on the list and would not create a different representation of any of those numbers. The discussion of 0.99999... = 1 should most certainly be put on its own page to lay to rest the assumption that decimal expansions are unique. But please, let's not get sloppy on the page cluttering it with "notes."
quote
Its result can be used to show that the notion of the [set of all sets]? is an inconsistent notion; if S would be the set of all sets then P(S) would at the same time be bigger than S and a subset of S.
end quote
Can the diagonal argument really do this? If we accept the existence of uncountable infinities (and i guess you do if you accept the diagonal argument) then it is pretty clear that the set of all sets must be of uncountable size if it exists. How do you define an ordered list of elements of an uncountable set? If you can't define an ordered list, how do you apply the diagonal argument? (Maybe you can, but it's not immediately obvious how. I think a bit more needs to be written about this if the above quote is to remain.)
If you look at the second proof you can see that it makes no assumptions about S being ordered. That is in fact the main difference between the actual diagonalization argument and its generalization that is used in the second proof. I will add a remark that the second proof is not equal to the actual diagonal argument but a generalization of it. -- Jan Hidders
That sounds good to me. Thanks.
OTOH, the line:
- But since there are expansions such as 0.01999... and 0.02000... that represent the same real number,
seems like pure and utter bunk. 0.01999... and 0.02000... are only the same number to computers, who can't see off into infinity. In the mathematical world, they're completely different.
Or has it been too long since my math degree?
- Yes, it has been too long. You are mistaken. --AV
Could you be slightly more terse? :-) Seriously, please expand. Wikipedia demands proof!
- Consider the following simple explanation. If a and b are two real numbers, a<b, then there is another real number strictly between them - for example, (a+b)/2. If 0.019999... and 0.20000... were distinct, then the first would be smaller than the second, and therefore their average would be strictly between them; but a quick consideration of its decimal expansion will convince you that there can be no decimal expansion strictly between 0.01999.... and 0.200..... . Therefore, the numbers represented by these two expansions are actually equal.
- This is a rather roundabout way to demonstrate the obvious, but it might be more convincing to you. --AV
- If I understand it correctly, the property of being able to represent a rational number by two infinite decimals is a logical consequence of how the real numbers are constructed. Without this property, Bad Things would happen. Comments appreciated, I am off to contemplate real numbers for a while.
- It is a consequence, but I don't see the Bad Things you mean. Some rational numbers, for instance 1/3, can only be represented by one infinite decimal. --AxelBoldt
- Right, didn't mean to claim some couldn't be represented by 1 infinite decimal, only that some require being able to be represented by 2 infinite decimals, e.g., 0.999... = 1.000.... Some Bad Thing would *surely* happen if one decided that 0.999... != 1.000..., but I have not yet taken the time to work out the consequence. Maybe after dinner...
- Actually, I'm not sure that Bad Things do happen at all; Bad Things do not occur with the hyper-reals, and I'm pretty sure that 0.999... != 1.000... will just end up being another model, but there will be some magic with spaces homeomorphic to the continuum sitting between 0.999... and 1.000... . Needs a bit of thought.
Here's another argument: look at the formula for geometric series, and then calculate 0.999999... = 9/10 + 9/100+ 9/1000 + 9/10000 + .... = 9 ( 1/10 + (1/10)2 + (1/10)3 + ... ) = 9 ( 1 / (1 - 1/10) - 1) = 1. --AxelBoldt
Or
1/3 0.333... + 2/3 + 0.666... ----- ---------- 3/3 = 0.999... = 1
Excellent arguments, all -- thanks! I sit corrected. -- NK
I once ran across a generalization of Cantor's argument applied to functions on the unit interval. Anyone know how it went?
I, Juuitchan, have something I find cool in a weird way.
You know how, in mathematics, there are an infinite number of real numbers, but most of these you cannot access? The reason, of course, is that it would require an infinite string of symbols to specify the number. So let's limit ourselves to numbers you CAN specify. We need a standard library of symbols, such as digits, operations, logical symbols, undefined "dummy" symbols that we can specify a definition for within the specification for a number, etc. Of course, there are only aleph-null of these. But as soon as you try to list them systematically, you find that there are more than aleph-null of them (using the diagonal argument)! AAARGH! Is this related to Gödel's incompleteness theorem?
- You could be talking about either the constructible numbers or the computable numbers. In either case there are only aleph null of them, because they are limited to finite length descriptions; each can be coded as an integer, although the resulting number may be a real such as pi.
- It's not out of the question to consider infinitely long "programs" which describe numbers - in fact this is basically what we mean by the decimal representation of a real number. The number 0.a1a2a3... is the input to a simple program which is "return ∑i = 1 to ∞ai". But if we restrict ourselves to finite length descriptions (finite algorithms, finite inputs to algorithms) it is natural that we cannot obtain the set of all infinite length descriptions.
- The incompleteness theorem is (to me) more vexing than this, because it restricts itself to finite length descriptions. The fact that, given the usual set theory, there are theorems of finite length which cannot be proven is a related but, to me, not identical idea. Still, trippy stuff indeed. Chas zzz brown 11:50 Dec 30, 2002 (UTC)
Juuitchan, I think I see where you are going. You are talking about definable numbers, and indeed there are only countably many of them. You want to list the definable numbers in proper order (maybe lexicographically ordered by their defining strings), and then you want to define a new number that runs down the diagonal, with digits flipped, like Cantor does. So you have a new definable number which is not in your original list, even though the original list was supposed to be complete. What gives?
The problem is that it is not possible to nicely order the definable numbers by their defining string. Whether a string defines a number or not is a non-trivial question. You would have to come up with some order of your defining strings that is "definable", in other words you would need a logical formula F(n,x) which is true if and only if x is the real number defined by the n-th definition in your list. Such a formula doesn't exist, as indeed your diagonal argument shows. AxelBoldt 20:58 Jan 4, 2003 (UTC)
Cantor's Error
I think Cantor's argument as you describe it is fundamentally flawed.
Let's look at statement (5) in the 'proof' which says:
"This set is therefore not an enumeration of all the reals in the interval (0,1)."
This statement seems to be exactly right. The set Cantor has constructed is NOT an enumeration of all the reals. But there is no contradiction with (2)which says "We may then enumerate the numbers in this interval as a sequence, { r1, r2, r3, ... }" Cantor has simply failed to find a way to construct them all. In fact, this is the only thing his argument proves; that the diagonal method must of necessity fail.
Wherever Cantor stops on his way to infinity (namely at n ), he will always find that he has failed to list the numbers he hasn't yet reached. Why should this surprise anyone?
- You misunderstand utterly completely. The diagonal method is not an attempt to enumerate the real numbers! It is an attempt to show why any sequence whatsoever must always fail to enumerate them. There is no failure of any particular method to point to, since no particular method is proposed. Michael Hardy 19:22, 24 Oct 2003 (UTC)
Thanks Mike but...
Mike:
I think you have missed the whole point here when you say "There is no failure of any particular method to point to, since no particular method is proposed". It is Cantor himself who proposes the method, and it is he who finds that it fails!
When you say "The diagonal method is not an attempt to enumerate the real numbers" you again miss the point. That is the whole idea behind Cantor's argument! "Cantor's diagonal argument (was devised) to demonstrate that the real numbers are not countably infinite." He does this by assuming the opposite (that they can be enumerated) and then looks for a contradiction.
The numbers on the left (r) are intended to be from a countably infinite set like the natural numbers. Cantor then tries to enumerate the reals in a chosen interval on the right, and place them in one-to-one correspondence with (r) on the left. If he succeeds, the reals are countably infinite.
Now this is where Cantor goes wrong. Because his list fails to include some real number x on the right, he assumes that x can not be paired with any natural number (r) on the left. He thinks he has found a contradiction where there is none. For ANY new number x Cantor creates on the right, there is also a new natural number (r) on the left with which it can be paired. He somehow thinks that his "diagonal" can be completed before he constructs his new number x. It can not be. There is no such thing as a completed infinite set.
- You're wrong. Cantor does not try to enumerate the reals; rather, he assumes it's already been done, and goes from there to a contradiction. He was not proposing any particular enumeration of the reals. Obviously, if he proposed some particular enumeration, and found that it fails to enumerate the reals, that would not prove that the reals are uncountable; it would only prove that one particular enumeration fails. You have entirely misunderstood his argument. Michael Hardy 17:34, 31 Oct 2003 (UTC)
Mike. If Cantor was not proposing "a particular enumeration of the reals", why does he pair them with the naturals using his r sub n notation? Is that not a particular enumeration? I think it is. Also, do you claim that Cantor's diagonal arrangement of the reals is not a "particular arrangement"?
But let's try it your way. As you say, Cantor assumes for the sake of his argument that the reals in the chosen interval "have already been enumerated", (ie, placed in one-to-one correspondence with the naturals) and that they can be arranged according to his diagonal scheme. (Surely you agree so far). Now he looks for his contradiction.
To find it, he takes us to the theoretical "end" of his "diagonal" and shows us a real number x in the interval which is not on this diagonal. This, of course, is nonsense since he can never reach the "end" of his diagonal in the first place; in theory or otherwise. By his own definition, there is no end to it! He can never do more than stop somewhere along its path to find his "contradiction". Now he can't have it both ways- either his "diagonal" is infinite or it is not. If it is infinite he can never apply his argument at all!! I'm surprised at how many people fail to see this.
Counterproof(?) for Diagonal method on [0,1]
This is a question that I've had for some time, I've never seen anyone come across anything that really states that [0,1] is countable, but I kinda think that I have a counterproof. The proof is a proof by contradiction, I assume that the diagonal proof is true.
For simplicity, I'm doing this in binary (base 2), but the same result can be achieved in any base. I have an ordering for the reals that maps it to the natural numbers. The ordering has a simple algorithm, take the binary number for the natural number (minus 1), and reverse the digits, and place a decimal point in front of it.
The numbers may look like this
0.0 0.1 0.01 0.11 0.001 0.101 0.011 0.111 0.0001 ...
Then via the diagnoal "proof" I choose an algorithm. If the xth digit is 0 I replace it with a 1 and vice versa. I will have to zero pad the numbers
0.0000000000 0.1000000000 0.0100000000 0.1100000000 0.0010000000 0.1010000000 0.0110000000 0.1110000000 0.0001000000
...
A simple proof will show that all of the digits will be zero. So using my algorithm, the number that the diagnoal proof says isn't in my list, is .111111111111111... (an infinite set of ones). But isn't that number in this list? Yes, it will be the last number in the list, but it will be there right? If so, then this is a counter-proof for the diagnoal method
- Wrong: There is no last number in your list. Michael Hardy 21:26, 26 Aug 2004 (UTC)
- (William M. Connolley 10:16, 24 Nov 2004 (UTC)) Also (assuming I've understood your real/natural mapping) .11111... doesn't map to a valid natural number. So it can't be on the list. Which is related to MH's reason.
The whole thing is wrong. That "enumeration" does not include any irrational number nor any number that isn't an integer divided by a power of two. They have infinitely long binary expansions. Instead, the enumeration only gives finite expansion, that is numbers such as n/2m with both n and m integers. There are incountably infinitely many numbers that don't fit in it.--Army1987 17:09, 23 Nov 2004 (UTC)
- I would like to see more about this construction and issues arising on my shiny new talk page. --Flabdablet 05:17, 24 Nov 2004 (UTC)
I don't know if this helps other people, but I find it easy to think of this from the point of view of a computer program. If you consider the above enumeration of the reals, and consider an analogous enumeration of the natural numbers. Now consider a program to count through each of the enumerations. For the program counting through the naturals, it's clear that if I pick any natural number, no matter how big (say 2^500), the program will eventually get to it. Whereas for the program counting the reals, it's clear it will never reach 0.1111... It will never reach one third either, since this requires an infinite string too. There are infinitely many reals it will never reach.--Frank Guerin 16:44, 24 Feb 2005 (UTC)
someone should add a few lines
The argument shows nicely that (0,1) is not countable. Someone should (for the casual reader) relate this to "R is not countable". One way would be to refer to or prove that a subset of a countable set is finite or countable. Another way would be to give an explicit 1-1 and onto correspondence between (0,1) and R.
- I've written a little bit about this. Anyone have a nice bijection from [0,1] to R? 4pq1injbok 01:40, 2 Jul 2004 (UTC)
- try f(x)=tan(x*pi-pi/2).
That fails: it does not include the endpoints of the closed interval [0,1]. Certainly I can give a bijection, but whether it is "nice" may be a delicate question. Michael Hardy 2 July 2005 21:00 (UTC)
small flaw
The given argument actually shows [0,1) is not countable (since the constructed x could be 0).
- Someone might add: note that (0,1) countable implies [0,1) countable (and conversely).
- (a) If r1, r2, ... counts (0,1) let s1=0, s2=r1, s3=r2,... Then this counts [0,1).
(b) (converse--not needed here) Suppose that s1, s2,,... counts [0,1). Suppose that s(k)=0.
- Define r1=s1,...,r(k-1)=s(k-1), r(k)=s(k+1), r(k+1)=s(k+2),... and this counts (0,1).
(More generally the union of a countable set and a finite set is countable , the union of a finite number of countable sets is countable and, with the Axiom of Choice, the union of a countable number of countable sets is countable.)
- To relate (0,1) and R one way is to use f:(0,1) to (-1,1) and then
- g:(-1,1) to (-p/2,p/2), where p=Pi=3.14159..., and
- h:(-p/2,p/2) to (-infinity, infinity)=R.
- The functions are 1-1 and onto (actually bi-continuous--but that is not relevant here).
- f(x)=2x-1, g(x)=px/2, and h(x)=tan(x).
The constructivists’ counterargument to the immediately preceding “proof” of the “uncountability” of the set of all real numbers hinges on their firm belief that there is no greatest natural number — hence, there is no last term in the sequence {r1, r2, r3, . . .} assumed in step (2).
Even granting arguendo Georg Cantor's tenet of actual or completed infinity, his diagonalization argument is untenable because:
(1) its line of reasoning is not a valid proof by contradiction or reductio ad absurdum deduction --- the definition of material implication, P -> Q, to be true under the condition that P is false or Q is true incorporates with it the two paradoxical interpretations that "a false proposition implies any proposition" and that "a true proposition is implied by any proposition". In the case of Cantor's diagonalization argument:
- (a) it is always true that the modified-diagonal-terms sequence is "excluded" from the row-listed sequences whether they are countable (finite or infinite) or not --- in the list of the decimal expansions of "all" the real numbers between 0 and 1 in step (3), the diagonal digits d1, d2, d3, . . . (which are highlighted in bold font) actually imposes an inherent ordering of the row-listed decimal expansions [the assumption of countability in step (1) implies that the imposed order is prior to the listing]; that is, for all natural number n, the nth-row decimal expansion must have a dn for its nth digit;
- (b) the premise of "completed totality of an infinite set" is necessarily false;
- (c) the premise that "The real numbers can be countably listed" (as applied to the modified-diagonal-terms sequence) is a self-contradictory proposition;
(2) while its application to the truly countable row-arrangement of place value positional numeral system expansions (in any base number greater than 1) of the rational numbers between 0 and 1 merely confirms their countability since every modified-diagonal-number expansion that can be constructed represents an irrational number between 0 and 1, its application to the countable algebraic real numbers greater than 0 and less than 1 is not conclusive because any modified-diagonal-number expansion that can be constructed from a truly countable row-listing of the algebraic real number expansions represents an indeterminate algebraic or transcendental irrational number;
(3) using binary (base number = 2) place value positional numeral system expansions ---
- (a) solely the complement-or-inverse-of-the-diagonal-digits binary expansion is "excluded" from a countable row-listing of all the binary expansions of the real numbers between 0 and 1 --- in his personally developed "hierarchy of transfinite ordinal numbers", Georg Cantor himself considered the ordinal number w+1 = {x1,x2,x3,...,x0} to be countable --- therefore, no contradiction is reached if one presupposes the countable row-listing of all the binary expansions of the real numbers greater than 0 and less than 1 to be of the form {x1,x2,x3,...,x0} (where x0 is the complement-or-inverse-of-the-diagonal-digits binary expansion) rather than of the form {x1,x2,x3,...};
- (b) every real number between 0 and 1 can be represented in a binary expansion such that its "tail-end" digit dw at sufficiently large natural number, or at countable infinity, position is "1" --- therefore, dw = "0" for the complement-or-inverse-of-the-diagonal-digits binary expansion whose "exclusion" from a "complete countable list" just affirms the exhaustive row-listing of the presupposed countably infinite real numbers between 0 and 1 with all binary expansions having dw = 1"
(4) the imposition of a "diagonal" structure to a presumed countable list of sequences of digits unreasonably restricts the enumeration scheme that may be concocted --- it must be emphasized that the sets of all integer or all rational numbers in their standard order are not valid countable orderings or enumerations but listing them in groups of elements --- such as interlacing the positive and negative integers in the set of integer numbers or gathering together the rational numbers in reduced terms in increasing order of the sum of their respective numerators and denominators (discarding repetitions) --- results in valid enumerations of these countable sets of numbers; and
(5) as a general refutation, its application to the set of all permutations of {0,1} taken countably-infinite-at-a-time --- in particular, to the countable subset of this permutation set that comprise all the periodic infinite permutations of binary digits --- cogently establish the logical flaw in Georg Cantor's hasty claim that the exclusion of the complement-or-inverse-of-the-diagonal-permutation implies the "uncountability" of the row-listed permutations.
BenCawaling@Yahoo.com
possible patches for (0,1)
1)You might insert a line after step 2. "Somewhere among the numbers is .0100.... If it is r1 leave it alone, otherwise exchange it with r1 so now r1=.0100... and the new ri's count (0,1) if the old ones did." Now make the necessary changes in r1 and the example. Now the x will be .1something and is not 0 and is in (0,1) as required and produces the contradiction.
2)Another way would be to use the given argument for [0,1) and give an explicit 1-1, onto function relating [0,1) and (0,1). For example: Let S={0, 1/2, 1/3, 1/4,...} and T={1/2, 1/3, 1/4,...} so S is contained in [0,1) and T is contained in (0,1) and [0,1)-S is the same as (0,1)-T. Define f:S to T by f(0)=1/2, f(1/2)=1/3, f(1/3)=1/4, etc. So f is 1-1, onto. Define g:[0,1) to (0,1) by g(x)=x on [0,1)-S and g(x)=f(x) for x in S Then g is the desired 1-1 correspondence. Thus the main argument proved [0,1) not countable hence the above g shows (0,1) not countable.
One solution I have once seen to avoid the 0.09999... = 0.1 issue is to consider only the set S of numbers in [0, 1) that have only zeros and ones in their decimal representations. S is obviously a subset of [0, 1), and the diagonal argument works without exceptional cases.
- The entry itself should discuss the issue, as it's important to understanding variations of the proof. The goal is not to create the most asthetically pleasing presentation, but rather to instruct as best we can about the topic. MShonle 09:10, 30 Mar 2004 (UTC)
How About This?
(1) Assume that the natural numbers are countably infinite.
(2) We may then enumerate the natural numbers as a sequence, { n1, n2, n3, ... }
(3) We shall now construct a natural number x in N by considering the nth least significant digit.
Assume, for example, that the decimal expansions of the beginning of the sequence are as follows.
... 0 0 0 0 0 0 0 = n1 ... 0 0 0 0 0 0 1 = n2 ... 0 0 0 0 0 0 2 = n3 ... 0 0 0 0 0 0 3 = n4 ... 0 0 0 0 0 0 4 = n5 ... 0 0 0 0 0 0 5 = n6 ... 0 0 0 0 0 0 6 = n7 ...
The digits we will consider run along a diagonal from top right to bottom left. From these digits we define the digits of x as follows.
If the kth least significant digit of nk is 0 then the kth least significant digit of x is 1; if the kth least significant digit of nk is not 0 then the kth least significant digit of x is 0.
For the example above this will result in the following decimal expansion.
x = ... 1 1 1 1 1 1 1
The number x is clearly a natural number.
(4) However, it differs in the kth least significant digit from nk, so x is not in the set { n1, n2, n3, ... }.
(5) This set is therefore not an enumeration of all the natural numbers.
(6) This contradicts with (2), so the assumption (1) that the natural numbers are countably infinite must be false.
Frank Guerin 09:25, 6 Apr 2004 (UTC)
The problem is that natural numbers are finite, and your example x is clearly an infinite sequence of digits. In other words, the error in your proof is in step 3. MShonle 17:55, 6 Apr 2004 (UTC)
- The natural numbers are finite? Frank, PLEASE! You can't possibly mean that!!!
- Yes they are. Not that the set of naturals is finite, but in the sense that every natural number is finite, i.e. consists of a finite number of (nonzero) digits -- this is the difference between naturals and reals (a real consists of infinite number of digits, so the Cantor's argument is valid for them). You have constructed an infinite sequence of digits that, indeed, is not in the list. However, it is not a natural number, so that it should not be there. --Mormegil 08:47, 26 Aug 2004 (UTC)
- (Flabdablet 10:58, 23 Nov 2004 (UTC)) This strikes me as a red herring. Any of the real numbers in Cantor's original formulation that happen to have terminating decimal representations must be padded on the right with an infinite number of zeroes to make the modify-the-diagonal procedure applicable; what you end up with is a convention where every real number has an infinite-number-of-digits representation, whether it needs one or not. Similarly, every natural number can be represented as an infinite string of digits by padding on the left with an infinite number of zeroes. Applying the diagonal argument to a list constructed in this way purports to demonstrate that the natural numbers can't be put into correspondence with themselves; this contradiction undermines the diagonal argument as a method, surely?
- (William M. Connolley 11:55, 23 Nov 2004 (UTC)) You can pad an integer to the left with an infinite number of zeroes, of course: it makes no difference. But what you can't do is say that the number formed by changing all those zeroes into 1's (or any non-zero numeral) is a number. By contrast, you *can* do this for a decimal expansion. This is step (7) in the argument on the page.
- (Flabdablet 10:58, 23 Nov 2004 (UTC)) As for the contention that every natural number has a finite number of digits: says who? The number of digits in a natural number N is clearly O(log(N)), and the log function has no upper bound. If you're willing to take lists of infinite length seriously, why balk at numbers of infinite length?
- (William M. Connolley 11:55, 23 Nov 2004 (UTC)) Each natural number is of finite length, individualy. But (as you note) there is no upper bound to the number of digits in a natural number. But the two ideas are distinct.
- (Flabdablet 10:58, 23 Nov 2004 (UTC)) Can somebody with mathematical credentials please spend a few minutes looking over this section? I think Frank is onto something important.
- (William M. Connolley 11:55, 23 Nov 2004 (UTC)) Cantors diagonal argument has been well tested by mathematicians far cleverer than you or me for many years now. You have not the smallest chance of finding a flaw in it. That doesn't mean you shouldn't try: your failures may well be instructive for other people.
- (Flabdablet 00:47, 24 Nov 2004 (UTC)) That reply strikes me as verging on the theological; clever people can produce large amounts of beautiful work from questionable axioms, and axioms are what interest me most. I want to rub Cantor and Turing together and look for sparks. IANAM, obviously; but I do have a computing background and I believe I can think reasonably clearly. I'm sure I'm not the only one in this position, and I would very much like the process by which I come to an understanding of this stuff to be accessible to and useful for others. Wikipedia is an obvious place to start exploring, but the guidelines ask us not to use this page for "debating" Cantor. I've set up my own talk page as a place to do just that. If that's an inappropriate use of Wikipedia resources, and somebody knows of a better place to raise these issues and have them discussed by informed people, could you please post a link? Thanks.
Thanks for the comments. My problem was that I was not aware of the distinction between a string of digits which is finite but "as big as you like" and an infinite one. Hence I thought that natural numbers, being made of strings of digits "as big as you like" could match the infinite strings of reals. The answer is that strings with "no upper bound" can still be finite and distinct from infinite strings. I am not onto something! I was merely ignorant. I don't think the addition to the main page "Why this doesn't work on integers" is necessary/appropriate. I notice that the proof now has extra points which make things more clear. More importantly, anybody who thinks like I did has a basic misunderstanding of the mathematical ideas that the proof is built on, it is not feasible for every mathematical article to include something to address all the possible mathematical prerequisites which a reader may lack. Those who need this can go to the discussion. --Frank Guerin 00:49, 21 Feb 2005 (UTC)
NONSENSE, NONSENSE, NONSENSE !
Like phrenology and astrology, Cantor's mathematics will eventually be recognized for what it really is- utter nonsense. Every field has its charlatans, and mathematics is no exception.
The very concept of a "countably infinite set" is self contradictory. What can be counted can not possibly be infinite, and what is infinite can not be counted. Karl Freidrich Gauss pointed this out when he wrote "I protest against the use of infinite magnitude as something completed, which is never permissible in mathematics". The flaw in the 'diagonal argument' has precisely this defect.
- Argument by authority has no place in mathematics. Only rigorous proofs count. Carandol
- This not "argument by authority". This is known as crediting one's source, and it is customary in mathematics.
- It's customary, when citing proofs. What you are quoting is not a proof, and so has no standing, no matter who said it.
- Actually the reverse is true. Mathematicians rarely quote proofs, except when they are not widely known to their audience. The more common practice is to use the result, and refer the reader to a proof elsewhere. On the other hand, it would be rare indeed for a journal editor to permit a quotation to be used without credit.
- Even if Euclid, Archimededs, Newton, and Euler all agreed with Gauss, it would mean absolutely nothing, unless there was a proof.
- Gauss said it because he didn't know how to deal with infinite sets, but Gauss was not omniscient. There are mathematical methods and theorems he never knew of, maths having progressed since his day. Carandol
Cantor assumes that the reals have already been placed in one-to-one correspondance in a "completed" fashion with (say) the integers and goes on from there. When this assumption fails, he concludes that his absurd result is true! He has found a real number than hasn't been counted!
- That's how proof by contradition works: When an assumption "fails", i.e., leads to a contradition, one concludes that the assumption is not true. Michael Hardy 19:05, 25 May 2004 (UTC)
- That's right, Hardy, but Cantor has not done that. He makes two assumptions, but rejects only one of them. Assumption #1: The rationals are "countably infinite". Assumption #2: The reals are also "countably infinite". Logic requires that BOTH assumptions be rejected.
- You're wrong: the diagonal argument DOES NOT USE THE PROPOSITION THAT THE RATIONALS ARE COUNTABLE; it does not mention ration numbers at all!!
- HARDY: No, you're wrong. Do you know what 1 to 1 correspondence means? Please tell us what Cantor could possibly mean when he says "the reals are not countable". Compared to what exactly, if not to a set that is countable? Please re-read the Wikipedia article if you are in doubt on this point. This is elementary stuff. Look it up.
- I am a mathematician and I know this topic well. The answer to "Compared to what exactly, if not to a set that is countable?", if I understand your question correctly, is: compared to the set of natural numbers. That's the definition of "countable". Michael Hardy 15:46, 1 Jun 2004 (UTC)
- If you are a mathematician, you should know that the "naturals" are "rationals". If you know this topic well, you should know that the diagonal argument as described in Wikipedia does indeed use rationals (as a subscript to r). Contrary to what you say above, the countability of these rational numbers is assumed. Indeed, the argument begins with that assumption. It begins "Let f be any one-to-one function...".
- I just looked again, and that's not there. Countability of the natural numbers is used, since that's the definition of countability. The fact that naturals are rationals and the naturals are countable in no way implies that the rationals are countable. The concept of rational number is not mentioned at all; let alone any premise that the rationals are countable. But if it used the fact that the rationals are countable, there would be nothing wrong with that, since it's easy to prove the rationals are countable; it is easy to construct an explicit one-to-one correspondence between the naturals and the rationals. Michael Hardy 21:40, 2 Jun 2004 (UTC)
- Neither does Cantor's original proof of uncountability of the reals, which appeared three years earlier (in 1874) and does not mention decimals or any other numerals. Michael Hardy 18:22, 27 May 2004 (UTC)
- ...and you're wrong about basic logic: the contradiction does not require rejection of all assumptions; it implies only that at least one of the assumptions is wrong. This is really simple secondary-school stuff, and you should master it before getting into things like this that are over your head. Michael Hardy 18:26, 27 May 2004 (UTC)
- A contradiction requires the rejection of at least one assumption, yes. But until you know which, ALL assumptions are suspect and must be rejected. You apparently missed that class in your secondary school.
- No assumption that the rationals are countable is relied on in the argument. (Nor would anything be wrong with it if it were.) Michael Hardy 15:48, 1 Jun 2004 (UTC)
- No, logic requires that you reject the conjunction of all the assumptions. Besides, although many assumptions are made in the proof, e.g. set-theoretic axioms, your assumption #1 is not one of them. -- Jan Hidders 16:01, 26 May 2004 (UTC)
- I don't see that Cantor has rejected the "conjunction" as required, Jan. In any case, if you think assumption #1 "is not one of them", tell that to Gauss.
To speak of the "cardinality" of an infinite set is manifestly absurd, as Gauss pointed out. To claim that the number of elements in one infinite set is "larger" than that of another is simply adding one absurdity to another.
_________________________________________________________________
Cantor might just as well have done the following. We shall hypothesize that the even and odd integers can NOT be placed in 1 to 1 correspondence. To prove this, we shall assume the opposite; that they can be.
We shall consider the numbers to the right of the equal sign as a way of representing the even integers.
r1 = 0 . 2 0 0 0 0 0 0 ... r2 = 0 . 0 4 0 0 0 0 0 ... r3 = 0 . 0 0 6 0 0 0 0 ... r4 = 0 . 0 0 0 8 0 0 0 ... r5 = 0 . 0 0 0 0 10 0 0 ... r6 = 0 . 0 0 0 0 0 12 0 ... r7 = 0 . 0 0 0 0 0 0 14 ...
...
rn = 0 . 0 0 0 0 0 0 ... 2n
o Let n be any positive integer.
o Let the nth digit of x = 2n
o Let all other digits in x be zero.
o Clearly, all even integers in the interval r1 to rn are represented.
We shall now construct an even integer x not in the interval r1 to rn. Let x = 2n+2. This number is clearly an even integer but appears nowhere in the interval , as our diagonal clearly shows. Since rn can be any positive integer, it is clear that this will always happen. There will always be an even integer we have not "counted". Therefore, the assumption that the odd and even integers have the same cardinality is false!
________
To the anonymous poster above: please identify yourself or be considered a boor.
You are right that 2n + 2 is an even integer not in the set { r1, ..., rn }. Yes, for any n the will be an even integer not "counted" among the first n terms of the sequence. Nonetheless, each even integer does occur in the sequence. The diagonal argument does not say there is a real number not among the first n terms of the sequence, for any n. That is trivial, and is also correct. It says there is a real number that is nowhere in the sequence. No matter which sequence is used.
Although there may be legitimacy in a philosophical position that infinite sets do not exist, your own arguments are just childish math errors. Michael Hardy 20:40, 26 May 2004 (UTC)
- Hardy. Frankly, I think your understanding of the diagonal argument is a bit shallow, but you are beginning to see the point. Yes, the notion of "completed infinite sets" is suspect, and Cantor's work does rest on that rather shaky foundation. Substitute the "reals" for the "even integers" in the argument above, and you have Cantor's argument. You have even found his error yourself and without much difficulty, but you don't seem to realize it. By the way, argumentum ad hominem is a logical fallacy. It doesn't become you.
- There's nothing ad hominem about Michael's remark about your childish math errors. They are. -- Jan Hidders 10:00, 27 May 2004 (UTC)
Move proof of Cantor's theorem to Cantor's theorem?
Wouldn't the more concrete proof of Cantor's theorem be more appropriate on Cantor's theorem? -- Jan Hidders 11:50, 23 Jun 2004 (UTC)
- Jan: you are right, I moved the concrete method to cantor's theorem and just provided a link to it in the cantor's diagonal argument article.--Dissipate 17:01, 24 Jun 2004 (UTC)
- Great, thanks. -- Jan Hidders 17:46, 24 Jun 2004 (UTC)
Replacement digit choices
There's a slight problem with this digit replacement scheme:
* if the nth digit of rn is 0 then the nth digit of x is 1 * if the nth digit of rn is not 0 then the nth digit of x is 0
Precisely, this can run afoul of the 0.09999999... = 0.1 problem. Suppose our list of reals goes
r1 = 0 . 0 9 9 9 9 9 9 ... r2 = 0 . 4 9 3 2 0 4 3 ... r3 = 0 . 8 2 9 5 0 2 6 ... r4 = 0 . 2 3 3 9 1 2 6 ... r5 = 0 . 4 1 0 7 9 4 6 ... r6 = 0 . 9 9 3 7 8 9 8 ... r7 = 0 . 0 1 0 5 1 3 9 ...
(with 9s the rest of the way on the diagonal). Then x turns out to be 0.1000000..., which is equal to r1. So I've changed the 0 and 1 to 4 and 5, which should cause no problems. 4pq1injbok 00:31, 2 Jul 2004 (UTC)
Cantor's Diagonalization Argument is untenable
Georg Cantor actually made four salient premises in his diagonalization argument:
(1) that the row-listed numbers (say, infinite binary sequences or decimal|binary expansions of real numbers between 0 and 1) are countable;
(2) {r1,r2,r3,...} presents a "completed totality" (that is, the mental perception of the exhaustive existence at the same time of all the elements of an infinite set) of all the presumed countable row-listed numbers and rn = rn1rn2rn3... designates a "completed infinity" (that is, the actual equality of, say, a non-terminating, non-repeating decimal expansion to the irrational number that it represents) of each row-number's column terms;
(3) the presupposed countability of all the row-listed numbers can only be expressed in the standard enumeration form {r1,r2,r3,...} (or, Georg Cantor insisted on using only this countably infinite listing form); and
(4) a very delicate assumption associated with axiom-of-choice mathematical existence in the construction of the modified-diagonal-digits number x.
As dramatically expressed in step (6) of the "proof" presented, Georg Cantor (with his already fixed view of "actual infinity" pointed to premise (1) --- that is, the presumption of countability of the row-listed numbers --- as the culprit in what he deemed as a "contradiction" in his diagonalization argument. Georg Cantor unequivocally diffused what he construed as a "contradiction" by concluding that all the infinite binary sequences or fractional real number expansions cannot be countably listed.
On the other hand, premise (2) is at the heart of the constructivists' or intuitionists' objection to his diagonalization argument --- that is, based on their adherence to the Aristotelian doctrine of potential infinity only, they firmly contend that "there is really no greatest natural number"
- (William M. Connolley 08:18, 11 Sep 2004 (UTC)) "there is no geatest natural number" is uncontentious - why are you bothering to mention it?
(or more precisely, in Ludwig Wittgenstein's "grammar of infinity", "however many numbers we had counted, we could always count more")
- ditto
which means that there is no last element in the countably infinite sequence {r1,r2,r3,...}
- ditto
(this simply states that the row-listing does not constitute a "completed totality" of all the row numbers --- say,all the infinite binary sequences or decimal|binary expansions of the fractional real numbers)
- but suddenly you veer off into oddness. Canotrs proof is that you cannot list all the sequences this way.
--- as well as that there is actually no final or ending digit in each one of the row-number's column terms (this simply means, for example, that each real number rn is never actually equal to its decimal|binary expansion .rn1rn2rn3...).
- Each number is never equal to rn1rn2rn3...rnm for finite m; but it *is* equal to the infinite expansion
Therefore, it is undeniably true that some infinite binary sequences or fractional real number expansions are "excluded" from a given countably infinite listing of them in the standard enumeration form {r1,r2,r3,...}.
- Again, you seem to be assuming the results of the proof, but for unclear and invalid reasons.
For our part,
- are you a collective entity?
we respectfully agree with the constructivists and intuitionists resolute rejection --- following their Aristotelian interpretation of potential infinity
- Aristotle didn't understand infinity. If you are basing your ideas on him, this would explain your confusion. I'll stop here.
--- of the opposite Cantorian viewpoint of actual or completed infinity. However, most mathematicians and philosophers of mathematics worldwide presently believe that Cantor's theory of infinite sets has still not been aptly demonstrated to be internally inconsistent so they continue to adhere to its principles. Our elementary refutations of Cantor's diagonalization argument grant arguendo Georg Cantor's dogmas of "actual infinity" or "completed totality of an infinite set" and "completed infinity of an infinite binary sequence or place value positional numeral system expansion" as well as "hierarchies of transfinite ordinal and cardinal numbers" and "all-at-once view of all the elements of an infinite set" (we allow the time-independent existence of constructible infinite sets and do not make an issue such as "it would take forever to assemble or construct the entire elements of an infinite set") --- that is, we are directly establishing the inconsistency of Cantor's theory of infinite sets under his own terms and in his own turf.
(1) We simply point out that Cantor's diagonalization argument is an instance of a "begging the question" or petitio principii logical fallacy --- that is, the conclusion that the modified-diagonal-digits number is "excluded" from the countably row-listed numbers necessarily follows from the premise of using the standard enumeration form {r1,r2,r3,...}.
(2) Our simplest counterargument to Cantor's diagonalization proof merely rebuts the suitability of the standard enumeration form {r1,r2,r3,...} for every complete row-listing of a countable set --- that is, the use of an also-countable listing form, say, {r1,r2,r3,...,r0} or {r1,r2,r3,...,s1,s2,s3,...} dissipates Cantor's "contradiction" in his diagonal argument.
(3) We present very elementary counterarguments to the Cantorian doctrines of "completed totality of an infinite set" --- for example, the premise of completed totality of all the rational numbers (that is, the "division points" in a real number line) vanishes the "gaps" between the "division points" and, therefore, the irrational numbers (which are points, along with more rational number points, in the "gaps") --- and "completed infinity of an infinite sequence or series" --- for example, the decimal|binary fractional real number expansion digits cannot be actually properly aligned up to any sufficiently large natural number column position in order to absolutely distinguish the fractional real numbers from each other.
(4) Our simplest counterexample to Cantor's diagonalization method is just its inconclusive application to the complete row-listing of the truly countable algebraic real numbers --- in this case, the modified-diagonal-digits number x is an undecidable algebraic or transcendental irrational number; that is, unless there is an acceptable proof that x is always a transcendental irrational number for any countable row-listing arrangement of the truly countable algebraic real numbers, then Cantor's diagonalization argument remains dubious.
An argument wherein the truth of the conclusion is already assumed by the premise is a logical fallacy commonly known as "begging the question" or petitio principii. It is implicitly true that, from the row-listed numbers {rn} (where rn = rn1rn2rn3... and d = r11r22r33... is the diagonal-digits number), the modified-diagonal-digits number r0 = r01r02...r0n, with each digit r0n is not equal to rnn, for all natural number n, is "excluded" because the diagonal digits {rnn} are actually an explicit expression of the inherent imposition of order and list-inclusion condition on the row-listed numbers {rn} --- that is, for every natural number n, the nth-row number must have an rnn for its nth digit --- whether the latter are finite {r1,r2,r3,...,rz}, or countably infinite {r1,r2,r3,...}, or the initial countably infinite segment of a well-ordered set, say, {r1,r2,r3,...,s1,s2,s3,...,t1,t2,t3,...}, or a countably infinite subset of an "uncountable" set (if any exists) {r1,r2,r3,...} union{"uncountable elements"}.
(1) We emphasize here the direct dependent contrast (some kind of a "yin and yang" concurrent existence) between the imposition of countable row-listing order in the form {r1,r2,r3,...} and the inclusion of the modified-diagonal-digits number in the row-listing. If we implement the former (that is, we impose the row-listing in the form {r1,r2,r3,...}), then the latter is not possible (that is, the modified-diagonal-digits number is inevitably excluded from the row-listing). Conversely, if we enforce the latter (that is, we insist on the inclusion of the modified-diagonal-digits number in the row-listing) then the countable row-listing cannot be of the standard enumeration form {r1,r2,r3,...} [that is, an "all at once view" of the infinite array would simply reveal that the countable row-listing should be in some other countable listing form, say, {r1,r2,r3,...,s1,s2,s3,...} where only the initial countably infinite segment {r1,r2,r3,...} must satisfy the imposed row-ordering since the column digits are also of the form {c1,c2,c3,...} --- and, hence, the diagonal digits are also of the form {d1,d2,d3,...}].
It is clear that the folly of Cantor's diagonalization argument --- granting arguendo Georg Cantor's dogmas of actual infinity or completed totality of an infinite set as well as hierarchy of transfinite ordinal numbers --- actually lies in his premise (3).
(1) In Georg Cantor's hierarchy of transfinite ordinal numbers --- 0,1,2,3, . . ., w,w+1,w+2, . . ., w×2, . . ., w×3, . . ., w2, . . ., w3, . . ., ww, . . . (here, w is omega) --- the ordinal numbers which are "polynomial expressions" in w are countable. For example, listings of the form, say, {r1,r2,r3,...,r0} or {r1,r2,r3,...,s1,s2,s3,...} are also countable.
(2) Applying Cantor's diagonalization argument on infinite binary sequences or binary expansions of real numbers between 0 and 1, solely the inverse-or-complement-of-the-diagonal-digits binary sequence or expansion is really "excluded" from a presumed countable row-listing in the form {r1,r2,r3,...} of all these infinite binary sequences or expansions.
(3) By Georg Cantor's creed of completed totality of an infinite set, the diagonal binary digits of the row-listing {r1,r2,r3,...} --- hence, concurrently, also the "excluded" complement-or-inverse-of-the-diagonal-digits binary sequence or expansion, say, r0 --- are known from an "all at once view" of the infinite array formed by the row-listing.
(4) Therefore, if Georg Cantor presupposed the countable row-listing of all the infinite binary sequences or binary expansions of the real numbers between 0 and 1 exclusive to be of the also countably infinite form {r1,r2,r3,...,r0} rather than of the standard countably infinite form {r1,r2,r3,...}, then he could not have arrived at his "contradiction" and deny premise (1). It is emphasized that the column terms are countably infinite so the diagonal terms will only run through the row-listed infinite binary sequences or expansions {r1,r2,r3,...} and not reach r0.
(5) In the decimal system, because there are more than one possible choices for each modified-diagonal-digit, this means that infinitely many modified-diagonal-digits decimal expansions are excluded from the listing {r1,r2,r3,...}. However, this does not imply that the presupposition of countability was defective and must be denied but only that the use of the also-countable listing, say, {r1,r2,r3,...,s1,s2,s3,...,t1,t2,t3,...} was more appropriate --- that is, the modified-diagonal-digits decimal expansions that are "excluded" from the initial countably infinite segment {r1,r2,r3,...} are indeed included in the later segments {s1,s2,s3,...} or {t1,t2,t3,...}.
(6) The Cantorians' insistence on using the standard enumeration form {r1,r2,r3,...} --- and refusing the use of a non-standard countable listing form, say, {r1,r2,r3,...,r0} or {r1,r2,r3,...,s1,s2,s3,...,t1,t2,t3,...} --- for a presumed countable set to sustain their adherence to the validity of Cantor's diagonalization proof is a nonsensical argument akin to the unreasonable insistence of invoking, say, the standard order of the integers {...,-3,-2,-1,0,1,2,3,...} --- and refusing the use of the form {0, -1,1, -2,2, -3,3, ...} --- to illogically deny the countability of the set of all integer numbers.
We accept the Cantorian's "all at once view" of infinite sets so that we can designate, say, with N the set of all natural numbers, with Q the set of all rational numbers, and with R the set of all real numbers. However, we concur with the constructivists or intuitionists and resolutely deny the completed totalities of N, Q, and R as infinite sets for at least the following reasons:
(1) There is no greatest natural number or no "last element" of N --- that is, however many we had already counted, we can always count more (this is referred to as "infinity by addition") --- hence, N is an incomplete totality;
(2) Q and R contain N --- hence, Q and R are incomplete totalities, too; moreover, between any two rational or real numbers, r and s, there is always a third rational or real number, say their arithmetic mean (r+s)/2 (this is referred to as "infinity by division");
(3) In a real number line, the rational numbers are the "division points" while the irrational numbers are points (along with more rational numbers or "division points" in the "gaps" between the "division points". A premise of completed totality of Q vanishes the "gaps" between "division points" and, therefore, the irrational numbers. Thus, the irrational numbers exist concomitant with the incomplete totality of the rational numbers --- that is, the rational and the irrational numbers exist in some kind of "yin and yang" concurrent being just like the contrasting concept "good and bad". In other words, just as it is impossible for all things to be "good", or that some things are "good" because other things are "bad", it is impossible for all real numbers or points in the real number line to be all rational numbers or "division points" --- that is, however many rational number "division points" we marked on the real number line, we could always mark more rational number "division points" in the "gaps" between the existing markings and there are always irrational number points in these "gaps". This very fact justifies the limit concept of rational numbers approximation of irrational numbers.
Considering their perspective on "completed infinity" and "ordinal numbers sequence" (that is, the natural numbers are the finite ordinals and w is the first transfinite ordinal, followed by w+1, w+2, etc.), it is clear that the Cantorians view the place value positional numeral system expansion, with radix or base natural number b > 1, of a real number greater than 0 and less than 1 as represented in the format r = .d1d2d3...dw where w (read as omega) is the sufficiently large natural number or countable infinity position which theoretically ensures that all the column digits --- di in {0,1,2,3,...,b-1}, for all natural number i or for i = w, and dw is not equal to 0 --- of all the row-listed fractional expansions [for example, the decimal expansions in step (3) of the Cantor's diagonal argument presented] are properly aligned so that they can be absolutely distinguished from one another. In other words, the categorical requirement to be able to distinctly differentiate each fractional real number --- that is, to remove the ambiguity in the "equality" or "disparity" of the fractional real number(s) represented by, say, the decimal expansions .1234567890..., .12345678901..., .123456789012..., etc. --- it is necessary to posit the existence of a "tail-end" digit dw not equal to 0 for each fractional real number expansion. We contend here that the Cantorian hypothesis of completed infinity is not a very convincing idea for at least the following reasons:
(1) The rational numbers are represented in definite terminating or periodic (which are also terminating in divisible base numbers --- for example, 1/3 = .3 in base 10 while 1/3 = .1 in base 3) expansions. The equivalence of the following decimal expansion representations (here, the underlined digits form a periodic string) of the same rational number is easily proved:
- .1234567890 =.12345678906 = .123456789067 = .1234567890678 = .12345678906789
However, an "all at once view" of the completed infinities of these disparate periodic decimal expansion representations would reveal different "tail-end" digits dw --- "6", "7", "8", or "9" --- so they cannot be completely equal to each other. One might counter-argue that this objection does not hold in binary system where every fractional real number can be represented in a binary expansion with dw = "1". Still, it is impossible to finitely align all the periodic binary expansion digits of the fractional rational numbers --- that is, the common "tail-end" digit column position at some sufficiently large natural number does not exist --- because their repeating strings of digit(s) as well as initial non-repeating digit(s) do not have a "least common multiple" length (if they do, then one could construct a modified-diagonal-digits expansion that also represents a rational number from a countable row-listing of all the rational numbers and refute outright Cantor's diagonalization argument).
(2) For the irrational numbers, it is implicitly correct to write, say, lim (1 + 1/n)**n = e or e = 2.7182818284590... --- here, we have a tacit common understanding of the irrational number limit of an infinite sequence of rational numbers or the intended unwritten decimal digits of the decimal expansion of the irrational number e. On the other hand, it is strictly not proper to write 2.7182818284590... = e as a completed infinity simply because, however many finite number of digits in the decimal expansion of e we could specify in advance or write down, there is always the possibility that the particular decimal expansion representation specified in advance or written down could converge to infinitely many other real number limits. In other words, while .3 definitely represents 1/3 in decimal system even without adhering to the concept of completed infinity, one would not be able to deduce with certainty the real number limit of a non-periodic, non-terminating decimal expansion such as 2.7182818284590... --- even with familiarity of an arbitrarily large number of initial digits of the decimal expansion of the irrational number e --- without a mutual agreement on an anticipated irrational number limit which guarantees with certainty that the "unwritten" digits are what they are intended to be. If one stops writing down the digits of a decimal expansion at some position after the decimal point, then one only gets a rational number. If a pattern of repetition of digit(s) or rule of construction of the positional digits is specified for the decimal expansion digits, then one can simply write down and emphasize a finite number of them and it is not necessary to actualize its infinite completion --- the period or rule of construction of the positional digits somehow encapsulates the "finiteness" of a countably infinite decimal expansion.
From a related perspective, the decimal expansion "2.7182818284590..." actually represents the line segment [2.7182818284590,2.71828182845909] and not a particular real number point. Thus, we could generalize our observation here and assail the designations of "real number points" in the row-listed countable sequence {rn} presented in step (3) --- that is, the Cantorian premise (1) is really for "countable line segments" and not for "countable real number points".
The designation r1 = .5105110... as a single real number is extremely highly questionable because the decimal expansion .5105110... cannot actually represent a definite convergence to one particular real number point --- indeed, it merely specifies the line segment [.5105110...,.51051109].
In general, we ask the philosophical question whether, say, the completed infinite decimal expansion .d1d2d3..., without a definite rule for the sequence of decimal digits {dn}, truly represents a mathematically existing real number. This issue is indirectly related to the controversy with the axiom of choice --- simply stated, the latter presupposes that, given any collection of sets (the count of the collection and|or the cardinality of each given set may be finite or infinite), one can select one object from each set and form a new set. We believe that the argument with the axiom of choice is not limited only to set-level interpretation (that is, to creating a contentious new set that contains the selected objects from each given set) but that it equally applies to element-level perspective (that is, the selected objects from each given set form a doubtful element of an existing set).
(1) In the case of, say, decimal expansions, each digit dn, for all natural number n, involves an arbitrary choice from the set of ten decimal digits {0,1,2,3,4,5,6,7,8,9} --- for particular examples, we simply ask: do "715..." and ".715..." actually represent real numbers? We seem inclined to deny the former because it is unbounded (without a decimal point) but accept the latter because it is known (due to the decimal point) to lie between 0 and 1 notwithstanding the logical necessity that the determination of its being a real number must be established first before one can meaningfully talk about its being greater than 0 and less than 1. We firmly believe that even ".715..." does not represent a definite real number (this fact is manifest in the use of the 3-dot ellipsis) --- instead, it actually just specifies the "gap" or line segment exclusively between the rational number "division points" .715 and .716 in the real number line or the open interval (.715,.716) "set".
(2) In the construction of the modified-diagonal-digits "decimal expansion" x, in step (3) of the presented "proof", the Cantorians imagine an "all at once view" of the countably infinite row numbers by the countably infinite column digits "infinite square array" --- with all the row-listed countably infinite fractional real number decimal expansions, each with all its column-listed countably infinite decimal digits, being all there exhaustively simultaneously. Each digit of x is an "arbitrary choice" from the remaining nine decimal digits that are not equal to the diagonal decimal digit at each row. One might argue that a "definite choice" for the modified-diagonal-decimal-digit could actually be made --- such as formulated in step (3) of the presented "proof" or if binary expansions are considered instead of decimal expansions. However, there is, as a matter of fact, an actual "arbitrariness" in the specification of the completed infinite decimal or binary digits of x --- that is, there is no prescribe rule relating all the digits of x.
(3) An often misused example about axiom of choice is Bertrand Russel's quote: "To choose one sock from each of infinitely many pairs of socks requires the axiom of choice, but for shoes the axiom is not needed." Here, it is meant to differentiate "the fact" that a pair of shoes has two distinguishable elements --- a left and a right shoe --- while supposedly a pair of socks has two identical elements. If the latter be the case, then Russel's example is wrong because it is a fundamental property of the concept of "set" that it contains no duplicate elements --- that is, say, {1,1} = {1}. The same misconception about identical elements of a set appears to hold also in the Banach-Tarski-Hausdorff paradox.
(4) We also emphasize the contextual difference of a "variable" decimal expansion representation assignment, say, x = .d1d2d3... which assigns to x some arbitrary real number such as 1/3 = .333..., √2-1 = .414..., π-3 = .141..., or e-2 = .718... from our discussion here about axiom of choice selection of the positional digits of a decimal expansion.
While we deny the consistency of the Cantorian concept of completed infinity of place value positional numeral system expansion, we soundly reiterate here that, for examples, √2, π and e are mathematically existing irrational numbers with definite decimal expansion representations from, say, the definite rules of their limit-of-infinite-sequence or limit-of-infinite-series definitions or derivations and their continued fraction expressions:
- ► 1/1, 3/2, 7/5, 17/12, 41/29, (p+2q)/(p+q), . . . ---> √2 (limit of infinite sequence)
- ► e = sum over all natural numbers of (1/n!) = 1/0! + 1/1! + 1/2! + 1/3! + . . . (limit of infinite series)
- ► π = [3,7,15,1,292,...] (continued fraction expression)
The irrational number points exist --- they simply lie (along with more rational number points) in "gaps" or line segments between two different rational number "division points" of the real number line. It is just that the irrational numbers cannot be completely delineated by place value positional numeral system expansion representations because of the incomplete totality of the natural numbers. In plain words, Georg Cantor's inconsistent notion of "completed infinity" of, say, decimal expansions cannot be used to justify the existence of irrational numbers, or vice versa (that is, because irrational numbers exists, then the concept of "completed infinity" is necessary).
A natural first reaction to the Cantor's diagonalization "proof" of the "uncountability" of the real numbers concerns its application to the set of all rational numbers, which were shown by Georg Cantor himself to be countable. While the rational numbers are also real numbers, the fact about their being countable could not be used as a valid counterexample (with respect to their exhaustive row-listing) to the Cantor's diagonalization argument because a presupposed complete countable row-listing of all the decimal expansions of the rational numbers between 0 and 1 (it must be emphasized that rational numbers have terminating or periodic decimal expansions --- hence, these decimal expansions actually represent real number points and not "gaps" or line segments in the real number line), as in step (3) of the presented "proof", is indeed an exhaustive list of all these rational numbers since any modified-diagonal-digits decimal expansion that could be constructed from the list is guaranteed to represent a number that is not rational.
(1) Every rational number greater than 0 and less than 1 could be represented by a periodic expansion in some place value positional numeral system with a finite radix or base number greater than 1 --- that is, it will have a repeating string of digit(s) in its expansion or it will be in the form:
- .d1d2d3...dmr1r2r3…rn
where m, n are natural numbers, m >= 0, n >= 1;
- d1d2d3...dm represents the initial non-repeating digit(s);
- r1r2r3...rn represents the repeating digit(s) ["period"].
The repeating digit(s) or period starts after m digit(s) and is n digit(s) long --- this means that every group of n digit(s) after the first m digit(s) or every digit at the positions m + i and m + i + j x n, for all i in {1,2,3,...,n} and all natural number j are the same. While all the lengths of all these periods are finite, there is no upper bound on these lengths of periods --- that is, the lengths of periods are all finite, but there is no greatest length of period --- so their "least common multiple" is countable infinity w (omega). Hence, any modified-diagonal-number expansion that can be obtained from a complete countable listing of all the place value positional numeral system expansions of the fractional rational numbers must have a countably infinite length of period or that the modified-diagonal-digits expansion will not eventually fall into a pattern of some repeating finite string of digit(s) --- that is, it will indeed represent a fractional irrational number so its "exclusion" from the exhaustive row-list of fractional rational number expansions is understandable.
(2) The application of Cantor's diagonalization argument to the also truly countable row-listing of all the algebraic real number expansions is inconclusive because every modified-diagonal-digits expansion x that could be constructed represents an undecidable algebraic or transcendental irrational number --- if x represents an algebraic real number, then Cantor's diagonalization proof is either refuted outright or it simply confirms the incompleteness of the row-listing form {r1,r2,r3,...} or signifies the suitability to use other also-countable row-listing forms, such as {r1,r2,r3,...,r0} or {r1,r2,r3,...,s1,s2,s3,...,t1,t2,t3,...}, instead of the standard enumeration form {r1,r2,r3,...}.
BenCawaling@Yahoo.com
A more simple argument
Tonight I had an argument with my girlfriend about infinites being equal and the countablity of real numbers. She brought up Cantor's argument as proof of her position... After reading it, I am fairly confident that I found an obvious flaw.
Consider Cantor's proof but assume that due to the unspecified matching function the matched rn we're going after is n = ∞ by the proof we see that x and n would differ in the ∞th place. If we accept that .99999.... = 1.000... then we must accept that x = n and thus this proof fails to show that you can't map reals onto the natural numbers.
If we deny that .9999... = 1.0000... then we break a lot of math including all of calculus.
- (William M. Connolley 11:12, 6 Jan 2005 (UTC)) It *is* true that 0.999... = 1.0, but you have to interpret 0.999... correctly. 0.999... equals limit-as-n-tends-to-infinity of (sum-from-i=1-to-i=n of (9*10^-i) ). You can prove that this limit exists, and that it equals 1.
- Right, no argument there.
I don't pretend to have a proof that you can map the reals onto the natural numbers, but rather I believe I've shown why the proof here fails to prove that it isn't possible.Gmaxwell 04:08, 6 Jan 2005 (UTC)
response Gmaxwell
How could there be a infinitieth place? The sequence never terminates. Grick 05:10, Jan 6, 2005 (UTC)
- Because if given a function f(n) (the mapping function) we can solve for f(n) as the limit approaching infinity. A simple mapping function for x in the range [0,1] might be x = n * (1/∞).
- (William M. Connolley 17:24, 6 Jan 2005 (UTC)) Your formula is literally meaningless. It is not possible to write 1-over-infinity within the context of the real numbers. Infinity is not a member of the real numbers or the natural numbers (its possible to modify the complex numbers to make sense of one called inifinity but thats not what we're talking about).
It's trivial to calculate the ∞th place for this one, it would be 1.
- (William M. Connolley 17:24, 6 Jan 2005 (UTC)) *There is no "infinitieth" place*.
X = .5000... would be the n halfway between 0 and ∞. This works because any infinite set can be mapped onto any of it's subsets which is also infinite, and there are an infinite number of such subsets. The continuous reals map quite nicely onto this... You can also look at it this way, with a decimal expansion based mapping, you can't map a single real without using an n which has in infinite number of digits, but fortunately we have an infinite number of such ns (∞-1, ∞-2, etc).
- (William M. Connolley 17:24, 6 Jan 2005 (UTC)) Again, infinity-minus-one doesn't exist in the real numbers, and if you were using a modified system in which it did exist, it would be equal to infinity.
I think it's pretty clear why this must be forbidden by the rules of set theory (because the Ns for all useful values become infinite values), but there is no reason why we should be taking the rules of set theory as an 'ultimate truth'. In mathmatical systems based on the reals (rather than the natural numbers as set theory is),
- (William M. Connolley 17:24, 6 Jan 2005 (UTC)) That last comment doesn't make sense. Set theory *contructs* the natural numbers (if you want it to) but it isn't based on them.
there is no such problem.Gmaxwell 15:37, 6 Jan 2005 (UTC)
What if you take out the decimal
r1 = 0 . 0 9 9 9 9 9 9 ... r2 = 0 . 4 9 3 2 0 4 3 ... r3 = 0 . 8 2 9 5 0 2 6 ... r4 = 0 . 2 3 3 9 1 2 6 ... r5 = 0 . 4 1 0 7 9 4 6 ... r6 = 0 . 9 9 3 7 8 9 8 ... r7 = 0 . 0 1 0 5 1 3 9 ...
turns into
r1 = 0 9 9 9 9 9 9 ... r2 = 4 9 3 2 0 4 3 ... r3 = 8 2 9 5 0 2 6 ... r4 = 2 3 3 9 1 2 6 ... r5 = 4 1 0 7 9 4 6 ... r6 = 9 9 3 7 8 9 8 ... r7 = 0 1 0 5 1 3 9 ...
so by his logic wouldn't the integers be uncountably infinite
- No, because those are not integers. An integer is not represented by an infinite sequence of digits. Even if the rows eventually terminate, your diagonal is still an infinite sequence of digits, and therefore does not represent any integer. Michael Hardy 00:47, 7 Jan 2005 (UTC)
Counting All the Real Numbers
The Aristotelian potential infinity view binary expansion representation of a fractional real number is 0.b1b2b3...bn→ where, for all natural number i, bi is in {0,1}. In this representation, it is already clear that all the fractional real numbers are countable — there are only 2n of them since they all have the same finite natural number length n, although n could be made arbitrarily large as one pleases.
Georg Cantor balked at this incomplete expansion’s sufficiency to represent a fractional irrational number. He emphasized that the set N of all natural numbers is indeed not adequate (by the very definition of n→ as “n approaches, but is never equal to, infinity”) to completely index all the countably infinite sequence of, say, binary expansion digits of an irrational number. He designated by the lowercase last letter of the Greek alphabet the first transfinite ordinal number which measures the order of the terms in the countably infinite sequence of all the natural numbers — <0,1,2,3,...,n,...> — that is, all ordinal or indexing numbers less than or preceding ω are just the finite natural numbers. The following text is Endnote Number 13 in Akihiro Kanamori, “The Mathematical Development of Set Theory from Cantor to Cohen”, Bulletin of Symbolic Logic (Vol. 2, No. 1, March 1996): “After describing the similarity between and 2 as limits of sequences, Cantor [in Mitteilungen zur Lehre vom Transfiniten, Zeitschrift für Philosophie und Philosophische Kritik, vol. 91, pp. 81-215; 252-270] interestingly correlated the creation of the transfinite numbers to the creation of the irrational numbers, beyond merely breaking new ground in different number contexts: ‘The transfinite numbers are in a certain sense new irrationalities and, in my opinion, the best method of defining the finite irrational numbers [via Cantor’s fundamental sequences] is wholly similar to, and I might even say, in principle, the same as, my method of introducing transfinite numbers. One can say unconditionally: the transfinite numbers stand or fall with the finite irrational numbers — they are like each other in their innermost being [Wesen] — for the former, like the latter, are definite delimited forms or modifications of the actual infinite.’ ”
Thus, Georg Cantor’s notion of ‘actually completed infinite sequence’ representing a fractional irrational number is exemplified by <0.1, 0.14, 0.141, 0.1415, 0.14159, 0.141592, 0.1415926, . . ., π-3> in decimal system or <0.0, 0.00, 0.001, 0.0010, 0.00100, 0.001001, 0.0010010, 0.00100100, . . ., π-3> in binary system. That is: π – 3 0.0010010000111...bn→ (Aristotle’s potential infinity view) = 0.0010010000111...bn...bω (Cantor’s completed infinite sequence) <0,0,1,0,0,1,0,0,0,...,bn,...,bω> (expansion-sequence term isomorphism). In other words, to actually represent fractional irrational numbers, say π-3, Georg Cantor claimed that it is necessary to posit a “tail-end” digit bω for each of them. A quick reflection entails that bω = 1 for every fractional irrational number binary expansion since they all have -terminating expansions and a binary expansion with bω = 0 contradictorily means a terminating expansion. In Georg Cantor’s actually completed infinite binary expansion representation of fractional real numbers, 0.b1b2b3...bn...1ω, it is also clear that the fractional real numbers are countable — there are still 2n of them since, all of them having the same “tail-end” digit 1ω, they all only differ in at most a finite natural number n count of binary digits.
Untenability of Cantor’s Diagonal Argument
Suppose that a “complete” row-listing of all the decimal or binary expansions of the presumed countably infinite fractional real numbers is as follows:
P1 = 0.a1,1a1,2a1,3a1,4a1,5... P2 = 0.a2,1a2,2a2,3a2,4a2,5... P3 = 0.a3,1a3,2a3,3a3,4a3,5... P4 = 0.a4,1a4,2a4,3a4,4a4,5... P5 = 0.a5,1a5,2a5,3a5,4a5,5... . . .
where i,j N+, ai,j {0,1,2,3,4,5,6,7,8,9} in decimal or ai,j {0,1} in binary system. Georg Cantor claims a “contradiction” that one could always construct some anti-diagonal “fractional real number expansion” — X = 0.d1d2d3d4d5..., dn ≠ an,n, n N+ — which could not have been included in the presupposed “exhaustive” row-list.
First of all, we emphasize the fundamental invalidity of Cantor’s diagonal method due to its violation of the first philosophy principle of non-contradiction; that is, its principal assumption — in any standard enumeration of a complete row-listing of countably infinite expressions each having countably infinite column terms, any anti-diagonal expression formed was excluded from the row-listed expressions — is an intrinsic self-contradictory statement just like “This sentence is false” (which is both true and false at the same time).
In the typical argument cited in this article, it is implicitly true that X is indubitably “excluded” from the row-listing inasmuch as the countably infinite sequence of diagonal digits <an,n> actually explicitly expresses the inherent list-inclusion condition and imposition of order for the row-listing of all the fractional real number expansions {Pn} — that is, because of the built-in structural relation of a square array (that is, a row-listing of expressions having column terms with the same number as the count of rows) anent its diagonal elements, regardless of the context of the original specification for the arrangement of all the fractional real number expansions in the standard row-listing it, in fact, ultimately redounds to: n N+, the nth-row fractional real number expansion must have an an,n for its nth digit to the right of the fractional expansion point!
For educational purposes, we will still proceed to demonstrate the unsound applicability of Cantor’s diagonal argument. From our foregoing discussion of the Aristotelian potential infinity view and the Cantorian actually completed infinity view of binary expansion for a fractional irrational number, this alleged “proof” manifestly contains numerous misgivings.
- Following the Aristotelian potential infinity view of the binary expansion for a fractional irrational number —
- Each row-listed fractional binary expansion has the structure:
Pn = 0.bn,1bn,2bn,3bn,4bn,5...bn,z→ , n N+
Properly understanding the meaning ascribed to the notation z→, then z (although it approaches infinity; that is, can be made arbitrarily large as one pleases) is really a finite natural number at all times — hence, n N+, Pn is only a fractional rational number so all the fractional irrational numbers were actually not included in the specified row-list as Georg Cantor himself emphasized and that is why he conceived of .
- Georg Cantor’s bone-of-contention anti-diagonal image in the open interval (0,1) — X = 0.b1b2b3...bz→, bn ≠ bn,n, n N+ — is not completely constructed so there is no contradiction on its “exclusion” from the given row-list. Moreover, the sequence <bn> is not well-defined — there is no definite unambiguous global rule to substantiate the formation of its terms and only the prefixed expansion point “.” formalizes its being “a real number greater than 0 but less than 1”.
- An arbitrary row-listed fractional binary expansion in the form:
0.bn,1bn,2bn,3bn,4bn,5...bn,z→ , n N+
[say, 0.011010100000100...], unless it is mutually understood to be especially representing an irrational number [say, 2 - 1], truthfully communicates (as the only valid interpretation for the ending 3-dot ellipsis “...”) some open interval or a line segment [say, (0.011010100000100, 0.011010100000101)] and not a true fractional real number point. Therefore, Cantor’s diagonal argument’s row-listed expressions are, in fact, for “countable intervals” and not for “countable real number points”.
- We stress the implicit presumption brought into play with the given row-listing — that all the fractional real number binary expansions could be absolutely distinguished from each other so they could be row-listed uniquely. This categorical requisite necessitates that their column digits be properly aligned in order to remove the ambiguity in the “equality” or “disparity” of the fractional real number(s) represented by, say, the binary expansions 0.11010010..., 0.110100101..., 0.1101001011..., and so on (here, one should try to imagine binary expansions with arbitrarily long common initial digits).
- Every fractional rational number is represented in a periodic expansion of the form:
0.a1a2a3....amr1r2r3…rn ; m N, n N+
where a1a2a3...am represents the initial non-repeating digit(s);
r1r2r3…rn represents the repeating digit(s) [“period”].
Because neither all the initial non-repeating digit(s) nor all the repeating digit(s) have their respective “least common multiple” finite length, then the column digits of a complete countable row-list of all the fractional real number expansions are truly even theoretically impossible to align up to some arbitrarily large finite natural number z position — in other words, all the fractional real number expansions cannot be uniquely row-listed.
- Here, we are simply asking how one, without hypothesizing some form of actually completed infinity, would go about really row-listing exhaustively in the standard enumeration form all the fractional number binary expansions? For instance, row-listing all the fractional number binary expansions with even just the form 2-n, n N+ — that is, 0.1, 0.01, 0.001, 0.0001, . . . — would already constitute a countably infinite number of rows, so what about the inclusion in the row-list of all the other fractional number binary expansion forms like 2-n + 2-(n+1), n N+ — that is, 0.11, 0.011, 0.0011, 0.00011, . . .?
- These and many other indeterminateness and non-constructibility issues (which are not consequences of the assumption of countability of all the fractional real numbers) in its fundamental presuppositions truly make unsound the application of Cantor’s diagonal method to “prove” the “uncountability” of all the fractional real numbers based on the Aristotelian potential view of infinity.
- Following the Cantorian actually completed countable infinity view of the binary expansion for a fractional irrational number —
- Each row-listed fractional binary expansion has the structure:
Pn = 0.bn,1bn,2bn,3bn,4bn,5...bn,m...1n, ; n,m N+.
We stress that Georg Cantor posited the first transfinite ordinal number ω precisely to put across the actually completed infinite sequence of expansion digits for an irrational number.
- With all the row-listed fractional binary expansions having a “tail-end” digit of b = 1, the application of Cantor’s diagonal argument to them would yield an anti-diagonal fractional binary expansion with a “tail-end” digit of b = 0 — thus, its exclusion from the complete row-listing is verily understandable.
- Georg Cantor’s original diagonalization proof actually involved the countably infinite binary sequences (he used the two characters “w” and “m” instead of “0” and “1”) — or, equivalently, the set P({“0”,“1”}) of all permutations of {“0”,“1”} taken -at-a-time where each actually completed infinite binary permutation is in the form b1b2b3...bn...bω with bn {“0”,“1”}, n N+ and n = ω. He could have simply row-listed first all the countably infinite binary permutations with bω = “0” then, below all of them, all the permutations with bω = “1” — hence, his anti-diagonal infinite binary permutation constructed from the top countably infinite segment with bω = “0” will indeed have a bω = “1” so it is verily excluded there but it is truthfully included in the bottom list of binary permutations with bω = “1”.
- The insistence on a row-list of all binary permutations taken -at-a-time — P({“0”,“1”}) = P0({“0”,“1”}) P1({“0”,“1”}) where P0({“0”,“1”}) consists of all infinite binary permutations with bω = “0” and P1({“0”,“1”}) includes all those with bω = “1” — in the standard enumeration form P1,P2,P3,... indeed directly undercuts Cantor’s diagonal method. The structural nature of the standard countable listing form expressly implies that this row-listing must have alternating elements from P0({“0”,“1”}) and from P1({“0”,“1”}) at some point onwards so that it cannot be actually completed by just a single element since its “ending” in, say, a member of P0({“0”,“1”}) would contrarily entail that P1({“0”,“1”}) is a finite set, or vice versa. In plain words, the actually completed countably infinite row-listing of all permutations in P({“0”,“1”}) must, of necessity, be in some countable listing form that has a countably infinite initial segment of elements and at least two more members after them — for instance, in the countable listing form P1,P2,P3,P4,...,P,P+1 where P P0({“0”,“1”}) and P+1 P1({“0”,“1”}), or vice versa.
- In general, the application of Cantor’s diagonal method to a countably infinite sequence f:N→S whose range S has a finite cardinality s > 1 as well as proper infinite subsequences involving the s elements of S indubitably bars the standard enumeration form P1,P2,P3,P4,... and inevitably calls upon the actually completed countable row-listing form, say:
P1,P2,P3,P4,P5,P6,..., P,P+1,...,P+s-1 = +s
or, P11,P21,P31,..., P12,P22,P32,..., . . . , P1s,P2s,P3s,... = s or, P11,P12,P13,..., P21,P22,P23,..., . . . , Ps1,Ps2,Ps3,... = s.
- Therefore, the application of Cantor’s diagonal argument to “prove” the “uncountability” of all the real numbers based on the Cantorian actually completed infinity view of the binary expansion for a fractional irrational number is also without merit.
Enumerating All the Real Numbers
Georg Cantor himself proved the denumerability of all the rational numbers — in particular, all the rational numbers exclusive between 0 and 1. For our part, we will readily enumerate all the binary expansions of the irrational numbers greater than 0 but less than 1 by listing them in groups of binary expansions (discarding repetitions) with digit(s) that differ from an arbitrarily chosen initial fractional irrational number binary expansion in their first; then first and second; then first, second, and third; and so on, binary positions. We could then easily assert the countability of all the real numbers in the open interval (0,1) by its being the union set of the independently countable sets of fractional rational and irrational numbers and presenting a straightforward enumeration scheme with alternating elements from the two countable sets or we could just interlace the rational numbers concurrently with our enumeration of the irrational numbers — the latter enumeration scheme could be achieved by listing the rational numbers (these are the fractional real numbers represented by periodic binary expansions of the form 0.a1a2a3...akr1r2r3...1l) of finite initial non-repeating string plus period length k + l = n, k,l N+, together in the respective groups of the fractional irrational numbers with different digit(s) from the initial fractional irrational number in their 2-1, 2-2, 2-3 up to 2-n binary positions.
We emphasize here that every fractional rational number could be represented in some periodic [that is, non|-terminating with a finite number of repeating digit(s)] binary expansion and they have a “least common multiple” length of so they are actually included during the consideration of all those fractional real numbers with digit(s) that differ from our initial fractional irrational number binary expansion in the 2-1, 2-2, 2-3, ad infinitum, positions. To allay possible opposition on this regard, as well as to highly simplify the formulation of our indexing scheme and enhance the comprehension of it by others, one could simply view our enumeration scheme as a countable listing of all the fractional irrational number binary expansions.
In the application of Cantor’s diagonalization method to the row-listing of all the fractional real number binary expansions, the sole anti-diagonal “fractional real number binary expansion” (if it really defines one despite the questionable formulation of its digits as a rather rule-less or extremely ambiguous infinite sequence) represents an irrational number — so we could start our enumeration scheme with it followed by all the row-listed fractional real number binary expansions. The objection that this new enumeration entails a new application of the Cantor’s diagonal argument to get a new row-listing and a new anti-diagonal “fractional real number binary expansion” not included in the new row-listing is nothing but just redundant absurdity (since the new row-listing is merely some rearrangement of the previous countably infinite enumeration) or simply the judicious admission of the incomplete totality of an infinite set.
In order to sidestep the preceding concern, we begin our enumeration scheme with, say, the fractional irrational number expansion:
P0 = 0.1101000100000001...
with 1 at each 2n, n N, binary position and 0 elsewhere.
There is only 20 = 1 fractional real number binary expansion that differs from P0 in the 2-1 binary position digit:
P1 = 0.0101000100000001...
There are only 22 - 21 = 21 = 2 fractional real number binary expansions that differ from P0 and P1 in their 2-1 and 2-2 binary positions digits:
P2 = 0.0001000100000001... P3 = 0.1001000100000001...
There are only 23 – 22 = 22 = 4 fractional real number binary expansions that differ from P0, P1, P2 and P3 in their 2-1, 2-2 and 2-3 binary positions digits:
P4 = 0.0011000100000001... P5 = 0.0111000100000001... P6 = 0.1011000100000001... P7 = 0.1111000100000001...
There are only 24 – 23 = 23 = 8 fractional real number binary expansions that differ from P0, P1, P2, . . ., P7 in their 2-1, 2-2, 2-3 and 2-4 binary positions digits:
P8 = 0.0000000100000001... P9 = 0.0010000100000001... P10 = 0.0100000100000001... P11 = 0.0110000100000001... P12 = 0.1000000100000001... P13 = 0.1010000100000001... P14 = 0.1100000100000001... P15 = 0.1110000100000001...
In general, for any positive natural number n, there are only 2n – 2n-1 = 2n-1 fractional real number binary expansions that differ from P0, P1, P2, . . ., P2n-1-2 and P2n-1-1 in their 2-1, 2-2, 2-3, . . ., 2-n+1 and 2-n binary positions digits which we can enumerate as P2n-1, P2n-1+1, P2n-1+2, . . ., P2n-1 — that is, from P0 up to P2n-1, there are only countable 2n fractional real numbers.
If one merely follows the progress (from the binary position 2-1 up to 2-n) of the highlighted-in-bold-font binary digits in our enumeration scheme, one would observe without difficulty that it simply lists, from P0 up to P2n-1, all the 2n permutations of {0,1} taken n-at-a-time — say, from binary position 2-1 up to 2-4, it lists, from P0 up to P15, all the 24 = 16 permutations of {0,1} taken 4-at-a-time. As already noted earlier, if one wishes to enumerate the fractional rational binary expansions concomitantly with the fractional irrational binary expansions, then the terminating fractional binary expansions with finite length n (derived from all the permutations of {0,1} taken n-at-a-time and discarding those with repeated insignificant trailing 0s) could be listed with their respective groups of fractional irrational numbers having digit(s) that differ from those of P0 in their 2-1, 2-2, 2-3 up to 2-n positions — however, we caution that this countable listing scheme would preclude the use of a simple formula for the enumeration index numbers.
We now present an enumeration scheme for the entire set R(0,1) of all the real numbers in the open interval (0,1) that alternately includes elements from our fractional irrational number binary expansions enumeration P0,P1,P2,P3,... and from some fractional rational number binary expansions listing Q0,Q1,Q2,Q3,... formed, say, by distinctly listing in groups the periodic binary expansions with initial non-repeating string plus period total length n, n N+:
P0 = 0.1101000100000001... Q0 = 0.1 P1 = 0.0101000100000001... Q1 = 0.01 P2 = 0.0001000100000001... Q2 = 0.01 P3 = 0.1001000100000001... Q3 = 0.001 P4 = 0.0011000100000001... Q4 = 0.101 P5 = 0.0111000100000001... Q5 = 0.001 P6 = 0.1011000100000001... Q6 = 0.101 P7 = 0.1111000100000001... Q7 = 0.001 . . .
— that is, R(0,1) = {P0,Q0,P1,Q1,P2,Q2,P3,Q3,P4,Q4,P5,Q5, . . .}. The bijection or one-to-one correspondence between all the real number points in the open interval (0,1) and the entire real number line R is easily demonstrated by bending the former as an upward semi-circular arc and placing it on top of the latter or through a function f:(0,1)R defined, say, by f(x) = tan[π (x – ½)].
However one regards a fractional irrational number expansion (say, our initial fractional irrational number expansion P0 = 0.1101000100000001...) — either as an Aristotelian potential (P0 = 0.1101000100000001...bn) or as a Cantorian actually completed (P0 = 0.1101000100000001...bn...1) infinite sequence, all fractional real number expansions have less than or equal lengths as the length of a fractional irrational number expansion and either they all have at most a finite (even though potentially infinite) natural number n length or they all have at most countably infinite ω length but with the same “tail-end” digit 1 at the countably infinite ω position.
Conclusion
Considering the foregoing discussions, it is very clear that Georg Cantor’s positing of actually completed countable infinity “tail-end” digit dω for fractional real number expansions does not add new information that is not already known or readily ascertainable from a potential infinity view of fractional real number expansions with dn→ — therefore, it is verily justified to sustain the Aristotelian view of potential infinity only that was in vogue for over 2,300 years and made rigorous as in the calculus of the mid-19th century.
In general, in addition to the finite polynomial expressions whose roots are the algebraic real numbers, the potentially infinite polynomial expressions or convergent Taylor power series whose limit-roots are the transcendental (trigonometric, exponential, logarithmic, etc.) real numbers truly suffice to represent all the real numbers without having to appeal to the Cantorian actually completed infinity perspective.
Our enumeration scheme easily defines a well-ordering of the real numbers without using the axiom of choice (unlike the proof by Ernst Zermelo):
- ► If a given subset of real numbers consists of only rational numbers, then one simply applies the typical well-ordering scheme for rational numbers.
- ► If a given subset of real numbers has at least one irrational number element, then we arbitrarily choose one of them as the first element and follow our enumeration scheme delineated earlier.
The distinction ascribed to “countable” or “denumerable” and “uncountable” or “non-denumerable” sets in all fields of mathematics are mostly merely references to “set of natural or integer or rational numbers” as opposed to “set of irrational or real numbers”, respectively. By just discarding the “uncountable” adjective and shifting to the suitable usage of “irrational” or “real” numbers, almost all of present mathematics can be retained because they are not adversely affected by the invalidity of Cantor’s infinity theorems — only references to the Cantor’s transfinite numbers beyond the natural numbers have to be cast off. A redefinition of “countability” that is limited to finite natural numbers would be appropriate — thus, a set is countable if and only if its elements can be put in one-to-one correspondence with a finite subset of N; otherwise, it is uncountable (although it is still denumerable). This suggested redefinition agrees well with the Aristotelian potential-only viewpoint of mathematical infinity.
The fittingly demonstrated one-to-one correspondence between the natural numbers and the real numbers blurs the distinction concerning the concepts of “discreteness” or “point” and “continuity” or “interval” in mathematical theory — it harmonizes well with the well-established “particle-wave duality” in physical reality. As Werner Heisenberg aptly put it: “There is a fundamental error in separating the parts from the whole, the mistake of atomizing what should not be atomized. Unity and complementarity constitute reality.”
BenCawaling@Yahoo.com
Assessment comment
The comment(s) below were originally left at Talk:Cantor's diagonal argument/Comments, and are posted here for posterity. Following several discussions in past years, these subpages are now deprecated. The comments may be irrelevant or outdated; if so, please feel free to remove this section.
Needs secondary references. Geometry guy 21:14, 17 June 2007 (UTC) Needs an extensive section on the objections to Cantorian theory. The article gives the impression that Cantor's views are accepted by all which they certainly are not. —Preceding unsigned comment added by 66.67.96.142 (talk) 23:31, 23 May 2008 (UTC) |
Last edited at 23:32, 23 May 2008 (UTC). Substituted at 06:32, 7 May 2016 (UTC)