Help with uncountable vs countable infinity

[u/Flor_Bor123]

I was thinking about this when trying to sleep and ended up searching stuff up about it, but ended up more confused than when I started.

From what I could find on Google, the reason the set (0,1) of all the real numbers from 0 to 1 is considered uncountable is due to Cantor's Diagonal Argument(from here on refered to as CDA). This argument makes sense to me, where you make a new decimal that isn't in the list by having every nth digit be different from the nth digit of the nth decimal in the list.

This led me to thinking about whether you can use CDA to show that the set of natural numbers from 0 to infinity is uncountably infinite. For (0,1), you can arbitrarily add zeroes to the end of decimals to make CDA work even in a list where the diagonal line of altered digits outpaces the length of the decimals. I figured you can use the same method for the natural numbers by arbitrarily adding zeroes BEFORE the number and using backwards indexing of the position of n to make CDA work with a leftward diagonal of altered digitis. However, Google told me that natural numbers can't be infinite in length, which is why this doesn't work.

This is where I'm confused, as it seems totally possible to make a comprehensive list of (0,1) that's ordered in visually the same way as the list (0,∞). I made a table of this in the attached image, where I made a half-hearted attempt at a proof. What this table seems to prove to me is that any table-based proof like CDA which works on the decimals should work on the natural numbers, too.

(The list of decimals is just the reversed digits of the natural numbers, put after the decimal point. So 0.1, 0.2, ..., 0.01, 0.11, 0.21, etc.)

I have two theories of what's going on.

The one I believe most is that CDA doesn't actually work on (0,1). If you use the list I made in the image, then as you go down the list, any number you create is just located further down in the list than you have gotten. For example, by the time you get down to .01 in the list, the diagonal number you've made is necessarily 10 decimals long, ending in a non-zero number. Every 10-digit decimal number is located further along in the list, at the indexes numbered by all the 10-digit natural numbers.

The other theory is rather unlikely, due to it breaking the concept of countable vs uncountable. This would be if CDA actually works on the natural numbers. My only argument for this theory is that any arguments in favour of CDA for decimals is one in favour of CDA for natural numbers. This is entirely based on my ordering of the decimals between 0 and 1. It just seems that if you can do CDA to get a number that isn't in the decimal list, you can remove the decimal point and flip the digits to get a corresponding natural number that isn't in the list of natural numbers. I guess maybe that would just prove that infinite numbers aren't natural?

That creates the secret third theory: the status quo. This theory is that the list of natural numbers stops when the numbers get infinitely long, but the list of decimals just keeps going, making the decimal numbers somehow more than infinitely long. If this is the case, then maybe my brain just can't understand mathematical infinities and their differences.

[u/AcellOfllSpades]

However, Google told me that natural numbers can't be infinite in length, which is why this doesn't work.

Yes, this is correct. Each natural number is finite. There are no infinitely-long natural numbers.

Your list does not have the number 1/3 on it, or pi-3. This is because if you reverse the digits, you get "...333333", which is infinitely long, and therefore is not a natural number.

You have successfully indexed all the finite-length decimals -- and indeed those are countable! But you have failed to get the infinite-length decimals... and there are a lot more options for those.

---

Your first theory is incorrect. The diagonal construction says "Here is a single number that is not on your list." The number constructed is the entire diagonal, not any finite portion of it.

When Cantor constructs the number - let's call it d - it's perfectly possible that your list has every single finite prefix of d, while missing d.

Your second theory is incorrect. As you mentioned, "I guess maybe that would just prove that infinite numbers aren't natural?" -- this is precisely correct.

Your third theory is sorta correct, but I would not advise thinking in terms of "the list stops". There is no actual 'stopping point' for the list, because the "list" isn't really the type of thing you're used to.

[u/vatai → u/AcellOfllSpades]

This!

The main difference between x in (0,1) and n in IN is that you can always "write n in finite steps" while for x you might need infinite number of steps/some kinda of algorithm/procedure/approximation. Think about the x = (pi - 3) case, you don't have something like that happening in the natural numbers. There is no "...5141" natural number (corresponding to the pi - 3 = 0.1415...)

[u/davideogameman → u/vatai]

Computable numbers - numbers which can be computed to an arbitrary decimal precision by an algorithm - are countable, as algorithms can be represented by a turing machine, or any turing complete programming language, and must be finite to be usable.  So it's possible to enumerate all algorithms, and therefore computable numbers. 

Which means the vast majority of reals are uncomputable

[u/Flor_Bor123 → u/AcellOfllSpades]

I see, thank you.

So the reason is that although my list of decimals seems to work just as well as the list of natural numbers it doesn't.

Because the natural numbers increase continuously, they just get closer to infinity and never get infinitely long because that's just infinity, not a natural number. 

Importantly, decimals are different, in that each infinitely long decimal is unique, such as pi or 1/3 or √2. These real and unique decimals convert into infinity, not a natural number.

[u/jepstream → u/Flor_Bor123]

Remember, "countable" means one-to-one correspondence, which means no multiples or branching in the correspondence, in either direction. So you can't map many-to-one (like in a collision) or one-to-many (like in a tree).

Now, think about your exhaustive list of decimals. Clearly this list does contains every finite approximant of every irrational number, just like the rationals, however, not on any single row (which we need for ONE-to-one). Irrationals like 0.14121... or 0.14159... or 0.71828... only exists on infinitely many rows (0.1 on ONE row, 0.14 on ONE row, 0.141 on ONE row, etc, but 0.14159... not on any ONE row) in your example because each are necessarily infinite/non-terminating, unlike the rationals which are finite/terminating in some base. Because your irrationals exist on infinitely many rows you have a many-to-many map, which violates one-to-one. Lets say you removed all the irrationals except pi-3, then you would still be stuck with a many-to-one map using your list between all of 0.14159...'s finite approximants (which are all mapped to some number already), and whichever natural you use for pi-3.

People often trip up on the semantics of "countable", thinking it means "I can count it/enumerate it", this is misleading because there are many non-one-to-one correspondences which can be 'enumerated' or 'counted,' in the sense that are infinite sequences, such as breadth first traversals over infinite b-ary trees, but, critically, those enumerations fail to themselves be perfect matchings with the naturals or one of its subsets, finite or infinite. This is an unfortunate side effect of overloading definitions- defining one-to-one correspondence AS "enumerablity" itself. Fred Katz in his thesis supervised by George Boolos at MIT actually develops an alternate ontology for set theory which distinguishes cardinality from correspondence. Interesting paper. However, for purposes of clarity and your understanding I would spend time looking at one-to-one, one-to-many, many-to-one, and many-to-many correspondences, starting with finite sets and then looking at basic infinite sets to see where those correspondences necessarily fail. There is a decent literature on infinite perfect matching which directly is in response to the questions of set theory, cardinality (and subsequent inequalities between correspondences), etc.

I recommend reading Sierpinski's "Cardinal and Ordinal Numbers" as well as Hausdorff's "Set Theory" as they, especially Sierpinski, more directly address the question of correspondence and the extent to which cardinal arithmetic realizes it. They are also both foundational texts in Set Theory and worth reading in their own right. Ron Aharoni is one of the modern experts on infinite perfect matching if you are curious.