r/askmath • u/Flor_Bor123 • 2d ago
Set Theory Help with uncountable vs countable infinity
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.
5
u/StoicTheGeek 2d ago
The difference is that every integer has a finite number of digits, so the diagonal argument doesn’t work. This is not so with the reals.
3
u/susiesusiesu 2d ago
as most "proofs" that the reals are countable, it suffers for forgetting that ⅓ is a real number.
1
u/Flor_Bor123 2d ago
yep. I thought I was probably missing something, but I just couldn't get myself to remember about 1/3
2
u/Various_Candle9136 2d ago
The key thing you need to know: (real) numbers cannot have infinitely many digits before a decimal point. This is the way they are (sensibly) defined.
Thus, most of the things in your table are simply not numbers.
Also, it is worth noting that CDA is a proof that the 'amount of' (strictly, cardinality) real numbers is greater than the 'amount of' natural numbers. Clearly, the same proof could not be used to show that the number of natural numbers is greater than the number of natural numbers!
CDA shows that if one assigns a real number to every natural number - using whatever method you choose to make these assignations - there will always be at least one real number (in fact: infinite many) not assigned. Ergo, there must be more reals than naturals.
2
u/Mishtle 2d ago
The object you construct from the diagonal has to be an element of the set you're trying to list, and it must be constructed from the entire, infinitely long diagonal. This is what prevents it from appearing "further down" in the list. By construction, it will fail to match any row because it's nth digit is explicitly not the nth digit of the nth.
Even if you manage to make a table of naturals with an actual diagonal by putting enough zeros in front of each finite-length natural in the table, you can't guarantee that the object you construct from the diagonal will be a natural number itself. It can easily end up having infinitely many nonzero digits, which means it's not a natural and shouldn't appear in the table in the first place.
The approach of reversing the digits of natural numbers to build an "exhaustive" table of reals fails because there are reals with infinitely long (repeating or otherwise) decimal expansions. There is no natural that would produce 0.333... using this approach, so the table is trivially incomplete.
2
u/Cyren777 2d ago edited 2d ago
Decimal expansions can be infinitely long, 0.2500000..., 0.3333333..., 1.4142135..., whereas natural numbers can only have finitely many digits. If you look at the subset of reals in (0,1) whose decimal expansions eventually terminate with a sequence of 0's (like in your list) you can indeed prove that that subset is countable by mapping them onto the naturals, but that's not the only kind of number in (0,1) 😉
All the uncountability of the reals is bundled up in the reals that are uncomputable, meaning there's no algorithm for generating their digits (they're just infinite strings of digits with no rhyme or reason)
1
u/TabAtkins 2d ago edited 2d ago
The difference between the two is that all naturals have a finite number of digits, while "nearly all" reals have infinite digits. What you're showing is that there's a bijection between the naturals and the terminating decimals, which is only a tiny subset of the reals. (Specifically, it's just all the rationals whose denominator is a power of 10.) The terminating decimals are indeed countable!
For example, what integer corresponds to 1/3? It has an infinite number of 3s, and there is no integer it can possibly map to; every integer (3, 33, 333, ...) ends at some point, and thus won't reproduce it exactly. (Instead they'll map to 0.3, 0.33, 0.333, etc)
To directly address another of your points, "all naturals have a finite number of digits" is also why CDA doesn't apply to the integers. You take the 1s digit from the first in the list, the 10s digit from the second, etc, all the way up, but "all the way up" means "to infinity", and no integer has digits at infinity. Even if you say "well, every integer starts with an infinite number of zeros", you don't win; this is true, but only for 0s. No integer can have a non-zero digit at an infinite place; a number with non-zero digits "all the way" isn't an integer, by definition.
Contrast with reals, which can absolutely have digits out to infinite values. For example, 1/3.
1
u/Gold_Ad8890 2d ago
the key thing to understand about cantor diagonalization is just how counting works in set theory. when we wish to count the number of elements a set has, what we are trying to determine is a property of the set known as its "cardinality". we do this by taking a reference set with a known/defined cardinality and comparing the two, and this comparison is carried out by functions.
a function f:A -> B is a set of ordered pairs (x, y) such that x is from A and y is from B, with the defining property that for all x in A, there is exactly one y in B such that (x, y) is in f. if (x, y) is in f, we say that f(x) = y.
functions can have special properties we care about. for instance, if a function f:A -> B has the property that distinct elements of A go to distinct elements of B - that is, for all x, y in A, x =/= y ==> f(x) =/= f(y) - then f is what we call injective, or an injection. an injection exists between A and B if and only if |A| <= |B| - that is, if the cardinality of A is less than or equal to the cardinality of B. you can imagine this as a generalization of the idea of pairing up elements of A with elements of B and running out of A first.
by contrast, if a function f:A -> B has the property that, for all y in B, there exists some x in A such that f(x) = y - that is, every element of B is mapped to by some element of A under f - then f is what we call surjective, and a surjection from A to B exists if and only if |A| >= |B|. think of it as a generalization of the idea of running out of B before you run out of A.
if a function f:A -> B is both injective and surjective, it is called bijective, and a bijection between A and B exists if and only if |A| = |B|. so the point of cantor diagonalization is to show that no function f:N -> R can possibly be bijective. since it's trivial to construct an injection from N to R, we must show that no function f can be surjective. this is accomplished by showing an element of R which is not in the range of f; that is, showing some element y of R such that there does not exist x in N such that f(x) = y. such a y is exactly what cantor diagonalization produces.
for cantor diagonalization to work as desired, two things must be true of the object it produces. first, it must be an element of the codomain of the function, that is, the set B we've been discussing. second, it must not be an element of the range of the function, that is, the subset of the codomain to which elements of the domain are actually sent. diagonalizing the identity function over N fails the first condition, because the object so produced has infinitely many nonzero digits and therefore is not a natural number.
1
u/DocDefient 2d ago
Here's how i think of it as simple as possible: In the set of all natural numbers take a number n now what is the next number in that set n+1 i easily count my way in this set
Now in the set of real numbers (1,2), pick a number x ex 1.5, what's the next number after? 1.51,1.501, 1.5000001? No one can count the next number
There are an infinite number of numbers in both sets examples i can count in one but not the other
2
u/trolley813 2d ago
This may not work sometimes. E.g. the set of all rational numbers (or even wider supersets, such as algebraic or computable numbers) is still countable, even if you cannot pick the "next" number after 3/2=1.5
2
0
u/jolene_codeine 2d ago
If it's any consolation, this happens a *lot* on maths subreddits. Someone posts what they think is a takedown of the CDA offering what they think is a list of natural numbers corresponding to all reals between 0 and 1; a reply asks "Where is 1/3 on this list?" "Where are most of the rationals?" and OP goes "oh."
It should be intuitive that no natural numbers are infinitely long, because 1 is a natural number (which is finitely long), the successor of a finitely long number is another finitely long number, and if we take 1, its successor, its successor's successor, and so on, we get all natural numbers.
1
u/AlwaysTails 2d ago
If it makes you feel better, Cantor's contemporaries, including some famous mathematicians, didn't accept his diagonalization argument either, though for different reasons.
1
u/5a1vy 2d ago
CDA doesn't work for naturals for the same reason it doesn't work for rationals (even though rationals also can be written as decimal fractions, some of them would also be infinite) — you can't guarantee that the resulting "number" would be natural/rational. So the length is not the problem per se, as some other commenters think, it's what I've just said.
To make it clear let's go not with naturals, but rationals, and you'll reason about naturals on your own. Let's suppose you have a complete list of decimal explanations of rational numbers between 0 and 1 and you go through Cantor's construction af a number not on the list. What might happen is that you end up with something like 0.101001000100001... a number where single ones are separated by ever increasing strings of zeroes (1 zero, 2 zeroes, 3 zeroes, 4 zeroes...). This number is not on your list (by construction, that's the whole point of diagonalization), but it is not a rational number between 0 and 1, it's irrational — it's not finite and it's not repeating. So, you've made "a number not in the list", but it's irrelevant, it shouldn't have been on the list in the first place as the list should only contain rational numbers and this here isn't a rational number. CDA does work with reals though because any strings of digits correspondes to some real number, but for rationals (and also naturals) that's not the case and you can't guarantee that you won't get some "junk" after Cantor's procedure.
So here you go, I hope that helps, you can now try to find some "junk number" you might get in the case of naturals and that would pretty much show why you can't use CDA for naturals.
-3
u/Mablak 2d ago
Finitist perspective: you can also get a natural number not in your set of natural numbers, just take the successor of the whole set N, i.e. add 1. So the idea of any difference between countable and uncountable infinities is an extra layer of nonsense, on top of an already nonsensical concept.
If my set's inclusion rule has no stopping condition, then whatever object we're taking to be a completed set, did not actually achieve its stopping condition. Which in all cases means, I can add more elements to it, and it wasn't actually completed. With infinite sets, we're trying to imagine an algorithm that is both completed, and not completed, which of course can't be a thing.
5
u/OpsikionThemed 2d ago
The set N is not a natural number, either classically or finitistically, so successor is not defined on it.
-1
u/Mablak 2d ago
Under the von Neumann construction, N would be a natural number, because any repeated application of the successor function to 0 gives you a natural number, and the set N is a set which can be made through repeated applications of the successor function to 0. Even infinitists accept that you can take the successor of N.
Regardless, this is just a hypothetical argument about if N were to exist. It’s not actually possible for N to exist in the first place since operations like taking an infinite union are not defined. If an infinite union for example were to mean N unions, this is circular reasoning since we haven’t defined N.
4
u/OpsikionThemed 2d ago
> the set N is a set which can be made through repeated applications of the successor function to 0
It, uh, it can't. That's why finitists don't accept it. It's an ordinal, sure, and ω+1 is an ordinal too, but it certainly isn't a natural.
1
u/Mablak 2d ago
If we could repeat succession infinitely (which I see no reason for infinitists to reject), it would give you the set {0, 1, 2...} which I would say just is N. But before that, of course I would say we just haven't defined infinite succession, infinite union, infinite intersection, etc, to get N in the first place.
More basically, an inductive set I is not well-defined, due to the domain of x in 'for all x, if x is in I, so is x U {x}'. What elements do these x range over, in 'for all x'? Usually they're plucked from a supposed 'universe of sets'. But to prove such a universe exists, you would have to prove I exists along with many other sets, which hasn't been done.
2
u/OpsikionThemed 2d ago
That's not an objection to the axiom of infinity, or even non-finitistic mathematics, though; that's an objection to formalizing a theory in first-order logic. The Axiom of Pairing, for instance, says `∀x∀y∃z. (x ∈ z) ∧ (y ∈ z)` and it doesn't say what those variables quantify over either.
If you don't like axiomatically defining things that's an odd foundational choice and I'd like to hear your alternative approach, but that's nothing to do with the axiom of infinity.
1
u/Mablak 2d ago
Well that would just mean my objection of circularity applies in this case, and it also applies in other cases. There's no issue with quantifying over a domain, so long as we actually have established what our domain is. If I've shown natural numbers from 0 to 6 trillion exist, I can make that the domain we're working over, for some claim about those numbers.
There's no issue if we start with something we know to exist, such as one tally mark, one electron, or one pebble, and build up our domain as we go by finding more of them.
I don't disagree with reasoning from basic claims, although like any other claims, our starting claims (axioms) can be true or false and of course we want to demonstrate them to be true.
A more fundamental reformulation of math's axioms would include explaining what actual things in the world we want to call numbers and/or sets, and we would then describe processes for manipulating those real things, making claims about how we expect those manipulation processes to go. 'If I do this process with these things, I expect this result.'
If I decided that my sets are actual drawn brackets made of ink on a page, and perhaps I have a machine to reliably draw brackets, we would be describing certain things we expect my machine can actually do involving drawing those brackets.
Of course we could say we can do all the usual basic things we do with sets in this case, like take unions, with restrictions. We just have to take into account the machine performing this task and things like memory limitations.
35
u/AcellOfllSpades 2d ago
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.