AlienRenders said:
Sorry to dig this up, but what happens if my list is not square?
With infinite lists, "square" does not have the same meaning that it does with finite ones. If it has any meaning at all. Try this:
- Imagine an infinite table, call it T1, where the rows and columns are labeled with the set of natural numbers. I don't care what you put in the table, just the labels. Since it has the same set labeling each dimension, it's "square," right?
- Make a second table, call it T2, by simply doubling the labels for the columns in T1. You didn't change anything about the size of the table, so T2 is just as "square" as T1.
- Make a third table, call it T3, by taking the odd-numbered columns out of T1. It seems like T3 cannot be square since you removed columns, but not rows, from a table that was already "square." But if you compare T3 to T2, you will see that they use the same sets as labels, so they are exactly the same size.
If the rows of your table are countably infinite, that means you can pair them up in a way you called one-to-one (which means something else in set theory) with the natural numbers
|N. That is, there is a function R(n) that returns the nth real number in your table for every n in
|N, and for the whole table. If R(n) is a real number, that means that it has a decimal representation where there is a digit associated with each power (1/10)^n. If you apply Diagonalization to this function R(n), it defines a new decimal representation that is different from every one that R(n) returns.
Now, you seem to think you have a table that is countably infinite in two dimensions, but not square. That just meand you are using a different function R(n) that you should. So just count the row labels, and replace each label ROW(n) with n. Viola! Your table is square by your standards.
This is one of the unusual properties of infinite sets that Cantor was trying to understand. Probably 90% of the arguments ever presented against Diagonalization, including yours, are based on misunderstanding these properties.
The digits and rows are not one to one.
"One-to-one," by which I think you mean "one-to-one and onto" or "bijective," is not a property of a pair of sets. It is a property of a function that maps one set to the other.
A function maps every member of the first set to one of the second. A function is "one-to-one" if every member of the first set is mapped to a different one of the second. It is "onto" if every one of the second is mapped this way. A function that has both properties is called a bijective function, or a bijection. That is the property I think you mean.
With finite sets, the distinction between whether the description applies to the pair of sets, or the function, is irrelevant. If a bijective function exists, any function that is one-to-one is also onto, and any function that is onto is also one-to-one. That's why you have gotten away with ignoring it with finite sets. The same is not true with infinite sets. Even if a bijective function exists, you can find other functions that are one-to-one but not onto, or that are onto but not one-to-one. That's what makes the existence of a bijective function from
|N the only requirement to apply Diagonalization.
1. For each digit column (assuming a grid of columns and rows), there will be a corresponding row in my list identical to a row from the identity matrix with a 1 in the same column. Basically, the strings 1000..., 0100..., 0010... etc will all be in my list somewhere.
Why? Even if you assume the table is complete, you can construct it so there is always a 0 in column n of R(n).
The problem stems from the fact that the infinite identity matrix is also N, but does not represent all binary strings N.
This is, in fact, related to the reason why the reals cannot be counted. In fact you can translate your statement
directly into "
|N cannot represent every binary string." Which is what Cantor proved with diagonalization.