There’s no case in which you can have a complete map anyways.
If you say one infinity is larger/smaller than another, you’d be saying that the complete map for one is larger/smaller than for the other one.
But if they are both infinite, you will never stop counting, so you just can’t know.
I know the diagonalization argument. But reality is that you can’t even count natural numbers.
So if you have finite time to count any set, the set will be finite, and so it’s countable.
But if you have infinite amount of time, any set for which there’s a formula to produce an element of, will always produce infinite elements at whatever speed you are able to produce them.
If one formula is faster than another (eg n=(n-1)+1 vs n=(n-1)!), then you will count more of one than the other in the same amount of time, but that is processing power, not the size of the sets.
Countable (roughly) means that you can count from one element to any other in a finite amount of time, it doesn't mean you can count the whole set in a finite amount of time.
1. Produce a number
2. Add it to the set of numbers I’m counting
3. Sort the numbers
Usually when you produce a number, you produce it in order (eg. 1, 2, 3, 4). But you could also count like: 4, 1, 3, 2 and then sort the set.
As long as you have an algorithm/function to keep producing numbers for “each iteration”, you can always keep counting one at a time.
The case you say: “count from one element to any other” is equivalent to a finite operation, it has a very clear beginning and end. But an infinite set doesn’t, unless you stop counting.
I think you're mixing up math and natural language. A "countable set" in math, by definition, means what I said it means, (or more precisely means it is 1-to-1 with the natural numbers). You can argue that the word itself is misleading/unclear, but that's a semantic argument and you should make clear that that's your stance.
It seems to me that this definition of "countable" is obscure, and furthermore fails to show why the word "countable" is used. Is it wrong to say that a countable set is a set in which it is reasonable to ask which element is the "next" element? That's a natural-language definition, right?
You can do that with natural numbers (just add 1) and with rationals (so I understand, but I can't give a procedure). Both sets have the same cardinality: aleph-null. You can't do that with the reals; that set is not countable, and furthermore has grater cardinality than aleph-null.
It can also be shown that (a) there is no set with cardinality greater than aleph-null and smaller than the cardinality of the reals; and (b) no set with cardinality greater than aleph-null is countable.
I can't do these proofs, but I've read them (in their non-symbolic, natural-language forms), and I was convinced.
> You can... (define "next number") ...with rationals (so I understand, but I can't give a procedure).
1/1
1/2, 2/1
1/3, 2/2, 3/1
1/4, 2/3, 3/2, 4/1
1/5, 2/4, 3/3, 4/2, 5/1
...
The first rational number is 0. Next is 1/1, that is 1.
Next number to a positive rational number is its negative version, for example 1/1 is followed by -1/1.
Next number to a negative positive number can be found by taking its absolute value (i.e. the previous number), locating it in the pyramid, and choosing the next number... skipping those fractions which can be simplified. For example -1/1 is followed by 1/2.
So it goes like this: 0, 1/1, -1/1, 1/2, -1/2, 2/1, -2/1, 1/3, -1/3... now we skip 2/2 because that can be simplified to 1/1, and proceed with... 3/1, -3/1, 1/4, -1/4...
> Is it wrong to say that a countable set is a set in which it is reasonable to ask which element is the "next" element? That's a natural-language definition, right?
You can do that with real numbers as well.
F(x)=randomreal()
At any step you want a next element, you just produce a random real element.
You can’t pre-determine how that random element will relate to the previously generated elements, but you can still produce real numbers, one at a time, and count them as you go. And if you do it for infinity, then you will never finish, but at every single step you will have assigned a natural number to a real number.
The definitions used for the proof are fiction that you can ever fully finish counting something.
The illusion that will fall for is that we think that all natural numbers are somehow pre-computed.
If we are going to be generating infinite elements one by one, then you can count/number/order all of them, one at a time, no problem.
If you recall, your original comment said “ If you say one infinity is larger/smaller than another, you’d be saying that the complete map for one is larger/smaller than for the other one.
But if they are both infinite, you will never stop counting, so you just can’t know.”.
So, if I can map all of the positive integers onto the reals and provably have reals that cannot be generated, that should suffice, no?
Take the reals from 0 to 1. For each positive integer X, flip the digits and put it behind the decimal. So, 437 gets mapped to 0.734, 1000 gets mapped to .0001, etc.
None of the transcendental numbers between 0 and 1 will get mapped onto.
This is because all positive integers are a finite series of digits, whereas all transcendental numbers provably do not terminate. It is not possible to flip a finite sequence of digits and get a non terminating sequence of digits.
So, now you have a generator function that can go through the positive integers one by one and never generate any members of an entire class of real numbers.
FYI I find this quite useful in clarifying my own thinking so feel free to tell me why that isn’t convincing to you.
But you are imagining “all the numbers between 0 and 1”, those numbers don’t/won’t exist until you generate them.
You cannot perform the action of mapping.
You can give me a formula to start mapping. But I would never finish. So you are imagining the result.
There is no result, the mapping is a process, not a finite result that you can compare to another finite result.
As long as you keep counting (producing naturals one after another), I can keep producing random real numbers and sorting them. There’s no point at which either one of us cannot generate one additional number.
And if we keep going to infinity, then the random generator will have generated all possible real numbers.
Does pi/4 not exist? If I draw a circle of diameter 1 and erase all but one quadrant, I now have constructed a segment of length pi/4. This happens to be a transcendental number between 0 and 1.
Stop using your random number generator. It is making you miss the point. It has no special value. For some reason you are assigning it a special value the same way people might assign numerical greater than order a special value.
If you use the flipped positive integer generator instead, it is quite obvious that you will never generate pi/4 no matter how long you run that generator, yet that generator will run through all possible positive integers.
> Does pi/4 not exist? If I draw a circle of diameter 1 and erase all but one quadrant, I now have constructed a segment of length pi/4. This happens to be a transcendental number between 0 and 1.
Pi/4 the symbol exists. Pi/4 the calculated number output doesn’t exist. You can’t finish calculating it.
And if you calculated a finite approximation, then all you’d be doing is just connect one symbol (Pi/4) to another symbol (output of your calculation).
You keep thinking hat assigning symbols/labels to infinity somehow gives you an instant result of an infinite process/computation.
You don’t need to finish calculating pi/4 to know that it is a non-computable number, whereas all positive integers are computable, which is why the length of that segment will never show up in the generator.
My assertion is simply that the infinity of the positive integers is different from the infinity of the reals in the sense that the infinity of the positive integers can be computed to arbitrarily large measure given enough time.
Whereas for the reals, we’ll forever be stuck on pi/4 and never get to e. That given arbitrary time, we can only compute a non-measurable number of reals.
Which makes the infinity of the positive integers more “real” than the infinity of the reals, because we can use measurable things in algorithms, whereas non-measurable things require a leap of imaginative voodoo that I imagine you would rather not take.
If you prefer to take the infinity of the positive integers as literally the same as the infinity of the reals, then you’d have to believe that all finite sets of reals have positive measure within the reals. Sure, both infinities can be considered “unknowable” in that we cannot generate the entire thing so cannot generate/know all their properties, but we can generate the measure property. So they should both satisfy it.
Also, intuitively I think we should be able to prove the halting problem wrong, if all finite sets of reals are positively measurable, but don’t quote me on that! But I feel like taking such a property would imply that the spectral gap problem is computable, which then bunks the halting problem, and the concept of non-computable numbers altogether.
> My assertion is simply that the infinity of the positive integers is different from the infinity of the reals in the sense that the infinity of the positive integers can be computed to arbitrarily large measure given enough time.
Again the same issue. You are trying to make infinity finite by reducing it to “arbitrarily large measure”.
> Whereas for the reals, we’ll forever be stuck on pi/4 and never get to e. That given arbitrary time, we can only compute a non-measurable number of reals.
If you generate random reals at each step, you can generate a sequence as long as you want, without ever “getting stuck”.
I’m not trying to make infinity finite. I am just giving the infinity of the positive integers a computationally verifiable property.
> If you generate random reals at each step, you can generate a sequence as long as you want, without ever “getting stuck”.
You don’t understand your own argument. At no point did you ever generate an irrational number, nor can you. You can only generate approximations of them, all of which are rational. You are trying to make infinity finite by reducing it to “generate a random real”.
As it so happens, the infinity of the rationals is the same as the infinity of the positive integers, and demonstrably so. But the reals are not only the rationals. Or, you could say the reals do not exist. Only rational numbers do.
> At no point did you ever generate an irrational number, nor can you. You can only generate approximations of them, all of which are rational.
If you can’t generate an irrational number, then you can never have a set that contains it.
Again, you want to use a finite label “irrational”, to denote the idea of an infinite process (generating some irrational number one digit at a time without stopping).
You cannot count an infinite process. It doesn’t matter if it’s a rational number, the reals or the naturals.
The thing you are failing to understand is that your statement of “generate a random real” at each step is meaningless because each such step cannot be guaranteed to terminate.
Which means the generator function you have been espousing this entire time is in fact just as much symbolic fiction as the symbol of pi.
Consider the while loop,
while (1 === 1) {
print “Step {step++}”
}
Though clearly an infinite process, each step within the loop clearly terminates and has a loop index. That is, we will see “Step 100” printed, “Step 9999999”, etc given enough time. In a sense, countable, for a particular definition of countable.
On the other hand,
while (1 === 1) {
print “Step {step++}“
random_real()
}
This, your favored generator, is not guaranteed to ever print “Step 2”, because at step 1, it might try to print pi, which is a fiction that will never terminate and become real. Thus not countable.
I never guaranteed you that the process will finish. In fact I agree it will not, since it is infinite.
However, each subprocess within the process is finite and has a definite end. That is why the process is countable, albeit indefinite.
> No difference if you are trying to count the naturals, the reals or the digits of pi.
There is a difference. You can count the naturals. Each subprocess is finite: 1, 5, 2, 6, 3, 7, ....
You can count the digits of pi: 3, 1, 4, 1, 5, 9, ....
You cannot count the reals. randomreal() is not guaranteed to be finite a finite subprocess. I cannot guarantee you that any given invocation of randomreal() will terminate. In fact, it is trivial to construct a subprocess sequence where it fails to terminate:
randomreal(1) = 1
randomreal(2) = 3.14159.....
We will never reach randomreal(3).
In that sense, your issue is that your view is self-contradictory. For it to be consistent, you need to stop talking about the reals, because there is no such thing as the reals. Or, accept the notion of there being an infinite number of alephs.
You cannot both reference the reals and simultaneously claim there are not an infinite number of alephs without contradicting yourself. This is not a minor detail.
Which you path you choose, as far as I'm aware, is currently unknowable and a matter of personal philosophy rather than objectivity.
The definition of a countable set is that it has the same cardinality as the natural numbers set, “aleph-null”.
This is an ill defined concept for two reasons:
1) a set is supposed to be a “collection of items”, but the natural numbers is not a collection of numbers, it’s a method to generate an infinite number of numbers… which technically you could never count
2) it’s trying to use a symbol (aleph-null), to make infinity appear finite - the cardinality of an infinite set (like the natural numbers), cannot be a finite symbol.
So essentially there’s two contradictions in the definition of the cardinality of the set of natural numbers.
But that definition is taken as true, and then used as the basis for justifying other concepts, like comparing sizes of unknown infinities.
1) Who said a set is supposed to be a "collection of items" or any other kind of set in the CS definition? A set is a mathematical object which can be said to contain, or not contain, an element. The natural numbers fall into this definition of a set.
2) There's no such thing as a "finite symbol." What does that even mean? A symbol is a symbol, it symbolizes something. The symbols themselves are finite; they're just letters. But if that something that it symbolizes is an infinite quantity, why stop it?
You are living too close to reality and numbers and words. Even if sets were rigidly defined as finite objects, why not define some new thing, call it an "infinite collection," and let all the theorems like countability and aleph-null come out of that? It lets us do useful math, after all, so why let the words we use stop us? Clearly set theorists worldwide find nothing* wrong with the current definition.
> Clearly set theorists worldwide find nothing* wrong with the current definition.
Are you saying that popularity defines reality? If enough people agree on something that’s the truth and we shouldn’t question thing anymore?
About the two points:
1) the definition of what a set is vague, so math has determines that set is an atomic concept that through formality should conform to our expectations of what a set is. So instead of dormally defining what a set is, they formally define a description for a certain set (https://math.stackexchange.com/questions/1452425/what-is-the...)
2) not sure what you mean. All symbols are finite. Think of a symbol as a tag for something else. In the case of infinity, what’s happening here is that the label for infinity is being equated with actual infinity, and then used to determine other stuff.
Yes, I want this to mean something real. Because if we are just going to make stuff up, let’s just use a different language instead of co-opting concepts from natural language.
Cantors proof doesn’t prove that reals are uncountable, they prove that he couldn’t come up with a system to count them, if he had already counted the naturals and paired them up. But you cannot do that, it just doesn’t make sense.
Similarly, saying that the cardinality of the naturals is the label aleph-null, might be useful to perform operations. But whatever you conclude, will be based on the wrong assumption that you can finish counting infinity.
Why do you have to produce them in some predefined order?
You could generate random real numbers, one at a time, and sort them as you add them to your set.
When you stop, you will have a set of real numbers in order. If you want to know where a new one goes, you just generate it, add it to the set and sort it (or just add it in the proper position).
And you will have a finite set of real numbers.
If you never stop, you will keep forever generating real numbers, exactly the same as you would with natural numbers.
The only thing that matters is whether you stop counting or not.
If you stop counting, you get a finite set.
If you don’t stop counting, you get an infinite one (but you’d never finish generating it).
There is no way for a human to count for infinite time… so we can only speculate about that case.
The only case that will ever occur in reality for us, is the finite case.
The idea behind Cantor's diagonalization proof is that you can't find any way to assign "first", "second," "third", etc to the reals. The proof assumes that you can, and that you've already assigned every real number a unique natural number.
It then derives a contradiction by proving that there must be reals that aren't in that ordering, without making any assumptions about the ordering. So any ordering has this problem and none of them work.
The proof starts assuming you can count natural numbers, which you can’t.
It’s impossible to have a known cardinality of an “infinite set”.
The definition of set is “a collection of items”. You cannot “have” an infinite collection of items.
You can have a method/function/formula/algorithm that generates as many items as you can in a certain amount of time, but by definition of infinity, you can never “count” an infinite number of elements.
Hence, you can never know the cardinality of an infinite set (like the natural numbers).
Once you think you can reduce something unknowable, to a symbol, you can prove anything.
Sure, that way lies intuitionism, which is a perfectly respectable (if not particularly popular) school of mathematics.
> Once you think you can reduce something unknowable, to a symbol, you can prove anything.
That doesn't follow. If ZFC is trivially inconsistent then someone would probably have noticed by now and proved P && !P for some P and brought it crashing down. That hasn't happened though, so even if you have strong aesthetic preferences against infinite sets being actually real, it seems like you can treat them as if they are real and produce a productive and not-obviously-inconsistent mathematical system. Most mathematicians don't really care if the naturals are actually infinite or just can be productively treated as if they are.
> That doesn't follow. If ZFC is trivially inconsistent then someone would probably have noticed by now and proved P && !P for some P and brought it crashing down.
Ahh, the classic economic argument, “that’s not a $100 bill on the sidewalk, because if it was, someone else would have picked it up already”.
That’s a great way of accepting everything blindly to justify not questioning things.
It also means you are using popularity as a measure of truth.
It’s fine if mathematicians don’t care if naturals are “actually infinite”, but then what’s the point in reasoning about infinity through math if technically you are not really saying anything, but you’re going in circles around your own definitions instead?
You’re avoiding the difference. You can count (for example via generator function), the natural numbers, though you may never finish. Typically, people generate via numerical order, so 1, 2, 3, 4,…
Now try doing that with the real numbers. You explicitly said you can sort them after. So, tell me, what comes immediately after 1, so I can attempt to convince you that it does not.
In other words, that the real numbers only have local sorting, not global sorting, whereas the natural numbers have both.
It's not obvious how to order the rationals either, but there are of course loads of orderings that work, and it turns out that they can easily be put into correspondence with the naturals. Such orderings are not from lowest to highest, obviously, but they exist, and you might naturally assume there's one for the reals.
The thing with the reals is that no orderings work, that's what Cantor's diagonalization proof does.
As long as you have time and you keep counting, you can count anything.
But eventually you will have to stop.
Counting infinity is a contradiction, as you can never stop. Hence you can never get a final output.
It doesn’t make sense that the cardinality of the set of natural numbers is some finite symbol (aleph-null). We can never truly know the cardinality of that set, because we can’t count to infinity.
There’s an additional issue here. Which is: what does it mean to count?
Because counting natural numbers usually means generating them in a certain order.
The issue is that we cant come up with a way to produce reals in an orderly way one after the other.
But we can always generate a random real number, then add it to a set in a position between a smaller and a bigger number. That way the set will always be in order, even if the number wasn’t produced right after a smaller number and before a bigger number. The order is essentially ad-hoc and varies as you generate the set. And if you kept going “for infinity” you would generate all the real numbers.
But we can never count to infinity, not even for the natural numbers.
You can go through all the reals one by one, in order. As long as you can keep going for infinity.
Simple: at each step generate a random real number and assign it a natural number.
You will never run out of natural numbers.
And if you keep going to infinity, then the probability of generating all reals is 1. So you would be generating all reals and assigned all of them a natural number.
The issue is that the proofs for uncountability assume we can finish counting natural numbers and after finishing, generate a real that is not in the naturals.
But if we had finished counting, we could do the same for the naturals, just add 1 to the largest number and you’d have something not in the set. Of course you can only do that if you have a finite set, which is not the case for the naturals =><=
> You can go through all the reals one by one, in order. As long as you can keep going for infinity.
> Simple: at each step generate a random real number and assign it a natural number.
This is nonsense. You said you were going to go through the reals "in order". Then you give a procedure that involves generating reals randomly. Just think about what you said.
It's not possible to go through the reals "in order"; that would imply that for any real, there is a "next" real.
Let the starting real be A. Suppose there is a next real; let it be B (generate it using some random process, if that floats your boat). The interval between them, B-A, let us call that C. I can divide C by 2, and produce a new real D=A+(C/2), which is smaller than B and larger than A. Therefore B is not the next real.
This is true for any choice of A and B, so it follows that there cannot be a "next" real, and so it's impossible to go through the reals one by one, in order.
> As long as you can keep going for infinity.
That's irrelevant, even if you restrict yourself to the reals between 0.001 and 0.002, because whatever process you use to select the "next" real, I can find one that is a better candidate, by dividing the difference by two.
The number of reals between 0.001 and 0.002 is the same as the total number of reals, and it's bigger than the number of natural numbers. That's a mind-boggling conclusion; but note that Cantor died with his mind well and truly boggled (he went mad).
> Let the starting real be A. Suppose there is a next real; let it be B (generate it using some random process, if that floats your boat). The interval between them, B-A, let us call that C. I can divide C by 2, and produce a new real D=A+(C/2), which is smaller than B and larger than A. Therefore B is not the next real.
You need to decide whether you want to define counting as “there being a next element”, or “being able to produce those elements in a finite way with a predefined order”.
The issue here is that you are trying to make a finite/determinate assertion about an infinite process.
There are no reals in between 0.001 and 0.002, unless you generate them. And when you do, you can count them one by one until you finish generating them.
Just like you could never finish counting infinite real numbers, you could never finish counting infinite natural numbers.
So then what Cantors proof is saying is that if you could somehow count to infinity and get to a result, some infinities would have more elements than others. But that is a contradiction, because you can’t finish counting to infinity.
Hence, you cannot know infinity nor its cardinality. Not for the real numbers and not for the natural numbers either.
> There are no reals in between 0.001 and 0.002, unless you generate them.
You seem to be thinking of a real as a string of digits, or a block of bits, which is just the representation of a real. Like, a number doesn't exist until you think of it. That view doesn't help much in thinking about these matters.
> So then what Cantors proof is saying is that if you could somehow count to infinity and get to a result, some infinities would have more elements than others. But that is a contradiction, because you can’t finish counting to infinity.
So you're saying Cantor's "proof" embodies a contradiction. You must be a very great mathematician. I'm not a mathematician, so I'd better just bow out now. Anyway, I'm way too old to start thinking of numbers as some kind of generative process.
Why would someone need to be a mathematician to think and understand?
That’s just gate keeping through labels. And probably the reason why so many old ideas go completely unchecked and are taken as gospel for so long with no one questioning them.
You can clearly reason about this stuff, even if you are not a mathematician. But maybe it scares you to think that something that you thought was “true”, is just someone else’s opinion about what they thought it was true.
Unfortunately, a lot of results (proofs) about infinities are counter-intuitive, and they can't be disproven simply by showing how they go against (your) intuition. A proof is not "someone else's opinion"; it is formal reasoning that stands on its own, apart from whatever opinion may have been held by the creator of the proof.
In fact many proofs went against the opinion of the proof's creator.
So, I'm not "scared"; I'm prefectly prepared to take a stand against unproven orthodoxies. But I have enough humility to realize that if I think I've found a contradiction in a proof by a great mathematician such as Cantor, and nobody else has found it, then it must be me that's wrong.
> There is no way for a human to count for infinite time… so we can only speculate about that case.
We can talk about whether or not a countably infinite sequence S contains a given element x. We iterate through each element s of S one-by-one. If x is contained in S, then eventually we will find an element s such that s = x. But if x is not contained in S, then we will keep iterating for all eternity.
For all countably infinite sets, we can always produce such a sequence, where the iteration will eventually halt if and only if the element is contained in the set. But for the set of real numbers, no matter what sequence we choose, we will never ever find the diagonalized number in our sequence. That's why we call the set of real numbers uncountable.
You dispute that we can't physically count through all of the infinite elements in the real world. But math has no problem talking about what would hypothetically happen if we were to try. It lets us prove ahead of time that certain events will eventually happen if we iterate long enough, and other events will never ever happen.
> But for the set of real numbers, no matter what sequence we choose, we will never ever find the diagonalized number in our sequence.
So then it’s only proving that if you choose the ordering ahead of time, you won’t be able to do it, because real numbers don’t have a predefined order. You can only order them as you produce them.
If you re-sort after each iteration (or insert them in order), you can count as many real numbers as you want.
In any case, for practical applications, you could never count anything infinite, at some point you’d run out of physical storage to keep the count.
How many bits can be encoded in the universe? That will give the limit of what could ever be counted. And it’s not infinite.
> So then it’s only proving that if you choose the ordering ahead of time, you won’t be able to do it, because real numbers don’t have a predefined order. You can only order them as you produce them.
What's the problem? You just produce the diagonalized number at the same time as you produce your order. Every order you produce them in has its own corresponding diagonalized number that will never be produced.
> If you re-sort after each iteration (or insert them in order), you can count as many real numbers as you want.
You can count as many real numbers as you want, but none of them will ever be equal to the diagonalized number. (That is, in finite time, you will always be able to find a digit that differs between the two numbers.)
> How many bits can be encoded in the universe? That will give the limit of what could ever be counted. And it’s not infinite.
How do you know the universe isn't infinite?
Regardless, I don't see why we shouldn't consider formal systems in which infinite amounts of information can be manipulated. Even in our finite light cone, mathematical statements about infinite sets can help us separate the possible from the impossible. For instance, mathematics tells us that adding 1 to any integer will never produce the same integer. There are infinitely many integers, so we can't experimentally verify this in the real world. But if we accept that abstract statement, then we know what to expect when we do try to physically add one object to a group of objects.
If as you say, the infinity of the real numbers lacks the property of predefinable order, whereas the infinity of the natural numbers does have that property, does it not strike you that those infinities may be fundamentally different in some way relating to size, and therefore mapability?
It only strikes me that we are trying so hard to know the unknowable.
Infinite essentially mean unknown. How could you possible compare the size of two unknowns?
You just can’t, but we want to be able to reduce something infinite/unknowable, to a finite symbol that we can use in our limited language.
Edit: for sibling comment -> how would you know the cardinality of a set without counting it? And if you have two infinite sets, how would you ever finish counting them to determine their cardinality and compare them?
It doesn’t even make sense to talk about the cardinality of an infinite set, infinity is not a number.
We pretend that the infinity symbol can somehow magically summarize and quantize something that is essentially unknowable.
The infinity symbol doesn’t make something magically finite.
The cardinality of an infinite set is unknowable. It is not “infinity”.
> Infinite essentially mean unknown. How could you possible compare the size of two unknowns?
The point is, that's not really what infinite means. A set being infinite just means that we can start listing elements, and we'll always be able to find a new element that we haven't listed before.
To compare two infinite sets A and B, we can consider functions F that take any element from A and output some element from B.
If A and B have the same cardinality, then we can always describe a certain function F that can potentially output any element from B, if we know the right input from A.
But if B has a greater cardinality than A, then we cannot find any such function. No matter which function F we choose, there will always be certain values in B that can never be output by F given any input in A. Thus, we say that B has "more elements" than A in a certain sense.
In the case of Cantor's argument, A is the set of natural numbers, B is the set of real numbers, and F is the ordering we choose.
A variation of Cantor's argument can be expressed fully in terms of finite objects. Suppose we have a function F such that F(i) = f_i, where f_i is a function such that f_i(j) represents the jth digit of the ith real number in the sequence.
Then, we can write a new function g(j) = (F(j)(j) + 2) mod 10, or some variation. This function g(j) similarly represents a real number.
Now, we can take any i we want and start comparing f_i(1) vs. g(1), f_i(2) vs. g(2), etc. After a finite amount of time, we'll always reach a point where the two functions differ. This means that the two functions represent two different real numbers.
Therefore, the real number represented by g is not represented by any of the f_i, no matter which function F we start with.
Thank you, I really appreciate your thoughtful explanation.
> A set being infinite just means that we can start listing elements, and we'll always be able to find a new element that we haven't listed before.
You can do that for the real numbers, by keeping a set of all the unique real numbers you’ve produced before, then adding one random real number at a time, always checking that is not in the set already.
And if you could go forever, then the probability of generating every real number is 1.
However, infinity is unknowable. You can’t just say that the “infinite” cardinality of a set can just be reduced to a symbol, that is like saying you finished doing the calculation and that you know there’s a final result. But there isn’t a final result.
The arguments in your explanation only prove that you cannot predict or choose an ordering for the real numbers before counting them. But if you produce random real numbers at each step and re-order them, you don’t need a predefined order. In fact the order can just be the order in which the real number was generated, regardless of its value, then you don’t even need to reorder them.
Edit: replying to reply to this by LegionMammal978 as the nesting level doesn’t let me reply under it
Thank you for the engaging conversation.
You found the issue: Cantors argument assumes you can finish an infinite process and then add an extra step…
> However, infinity is unknowable. You can’t just say that the “infinite” cardinality of a set can just be reduced to a symbol, that is like saying you finished doing the calculation and that you know there’s a final result. But there isn’t a final result.
We put a symbol on cardinality because it lets us make statements about the properties of sets, like whether or not we're able to map them one-to-one with other sets. In turn, this often helps us with proving statements about finite objects. (Technically, they let us quantify over different scenarios: say what can't happen, or can happen, or might not happen, or must always happen.) To repeat my example, we say with symbols that x + 1 > x for all the infinitely many numbers x, even though we can't physically check all of them. But if you hand me some physical number X and I add 1 to it, I can apply the abstract statement to know that I'll get a bigger number in that scenario.
> The arguments in your explanation only prove that you cannot predict or choose an ordering for the real numbers before counting them. But if you produce random real numbers at each step and re-order them, you don’t need a predefined order. In fact the order can just be the order in which the real number was generated, regardless of its value, then you don’t even need to reorder them.
I don't understand what you're trying to say here. In more finite terms (given that random real numbers already contain infinite information), the diagonalization argument says, "You can keep generating individual real numbers as long as you want, by any process. But there'll always be at least one real number that you'll never ever count to, no matter how long you keep generating numbers." (You can't say the same thing about the natural numbers: some methods of counting them will, in fact, reach every number sooner or later. That's the crucial distinction.)
This does not require any kind of "predefined order". In fact, the diagonalization has to listen to all the numbers we generate just to provide an example of an unreachable number. So at any given point in the process, we can't know in full what the unreachable number is (without knowing the generation process); we only know its initial digits. But the limit of these partial answers is the full unreachable number, which had already been there in the first place.
(I hope you accept the idea of an arithmetic limit; without it, we'd have trouble with basic things like justifying that 0.999... = 1, or resolving Zeno's paradoxes of motion. It's an intrinsic part of what a real number is.)
The order is arbitrary. What is the order of natural numbers? If you say they are in ascending order, that’s just the order in which you count them.
The same way, I can just generate random real numbers, then define my set as in ascending order, and insert them in that order.
Which is what we essentially do with natural numbers as well. Except that the order is a sort of mainstream standard and has been drilled into our minds since babies.
Ascending order is just one of many arbitrary orders. An ordering is a first output of a generator function, a second output, a third output, etc, where for any arbitrarily chosen element X of the set (such as the positive integers or reals), we can show that the generator will reach X in N steps, for some finite N.
That is why ascending order is the norm for the positive integers. For any positive integer X, it is clear that we will reach it in X steps using that generator function. So, it’s not a matter of being mainstream, it’s just the simplest.
The difference between the infinity of the reals and the positive integers is that there is no such generator function for the reals. No matter what function you give me, I can write a finite number that you will not reach in a finite number of steps.
Feel free to give me a generator function and I will give you a finite number that it cannot reach in finite steps. On the other hand, try giving me a finite positive integer that I cannot reach in finite steps.
> The same way, I can just generate random real numbers, then define my set as in ascending order, and insert them in that order.
To perform the diagonalization, we can simply look at each real number that you randomly generate and add digits to the diagonalized number based on that order. It doesn't matter how much you shuffle them around afterward: the diagonalized number will still be different from all the generated numbers.
1) I will produce an infinite amount of numbers, then stop
2) I will look at the infinite amount of numbers and then produce a number which is not within the infinite numbers
3) Hey look, the number I produced in 2) is not within the infinite set, so there must be a larger infinite set
The issue is that you can never finish 1). That’s the error/illusion.
But if you get to cheat, then I can also add a step 4) As long as you add digits to my numbers to generate an additional number, I will reorder the set of generated real numbers and assign each of them a natural number.
Of course the order will change from iteration to iteration. But in this way the generated real numbers will always have a corresponding natural number.
Where did I imply 1)? We never finish producing the numbers, so unless our production order was fixed from the beginning, we never know the full value of the diagonalized number. But the partial diagonalized number (which we refine at each step by looking at the produced number) will gradually converge to a limit, which is a real number different from any number we will ever produce. At no point in the process do we know the limit exactly, but it is there nonetheless.
> Of course the order will change from iteration to iteration. But in this way the generated real numbers will always have a corresponding natural number.
The real numbers that you generate will always have a corresponding natural number. But the diagonalized number will never have a corresponding natural number, no matter how much you shuffle your generated values.
You are saying that when you stop counting, the diagonal number will be different.
That means that you stop. Which implies you are not going to infinity.
If you are going to infinity, there is no side that “wins” (real or naturals). You can always keep generating an additional one for either side.
The same way, we could continue this discussion forever if we just want to keep going back and forth (although HN does impose a limit of replies). And you could only make an assertion about the length of each side of the conversations, after the conversation ends. But if the conversation keeps going forever, you could never say to talked more than the other. Unless you specify a finite range for which you want to measure.
Naturals and Reals are both infinite. Saying that the cardinality of one is different than the cardinality of the other, is just comparing the ideas of cardinality about them that we have come with, but their actual cardinality can never be known.
> You are saying that when you stop counting, the diagonal number will be different.
Where, in all my comments, do I say that we must stop counting? You're putting words in my mouth here.
Since we don't stop counting, we never know the diagonal number's full value (unless our order is predefined). All we know is that the diagonal number exists, and it is different from all the real numbers we will ever count.
> If you are going to infinity, there is no side that “wins” (real or naturals). You can always keep generating an additional one for either side.
Of course. I am not disputing this. If we count through two different sets in the same way, then the subsets of values we count through will have the same cardinality (equal to the cardinality of the set of natural numbers).
But there's an important distinction. If we count through the natural numbers one-by-one without stopping, it's possible to exhaust the whole set of natural numbers, such that every single number will eventually get counted to.
Meanwhile, if we count through the real numbers one-by-one, it is impossible to reach all of them. There will always be a bunch of real numbers that we will never ever count to. That's why we say that there are more real numbers than can be counted: there are uncountably many.
We assign the label ℵ₀ to an infinite set when we want to express the property that any given element can eventually be reached in a finite time if we keep counting for long enough. That's what it means, no more and no less. I don't see what it has to do with "assigning a label to infinity" or "assuming you can finish counting them". We don't use cardinalities to magically make the infinite finite (well, I don't, but I'm sure some pop-math explanations do), we use them to compare and contrast the properties of infinite sets, and refusing to acknowledge these properties doesn't make them go away.
> We assign the label ℵ₀ to an infinite set when we want to express the property that any given element can eventually be reached in a finite time if we keep counting for long enough.
Look at your definition: “if we keep counting long enough”
You are reducing infinity to “long enough” and using that as a label for infinity.
You can’t know ahead of time that you will be able to finish without finishing.
You are saying you can know the unknown. But you won’t until you go and try to count the numbers.
You will never be able to count all the natural numbers. Regardless of what you think the formulas/symbols mean.
Math doesn’t happen by itself, it needs an interpreter to “execute the operations”. Without an operator, math is just a bunch of symbols.
The operator will never finish counting natural numbers. Or any other sequence/set/group of numbers that is infinite.
Perhaps I have not been as clear as I should be. The sequence of counted numbers is infinite, and we would never be able to finish counting all of it. But all we care about for defining ℵ₀ is whether or not the sequence contains some particular value. If it does contain the value, then we can confirm that in finite time, even though the sequence is infinite.
Let me try reframing it a bit. First, you think of some natural number N (e.g., 978) and keep it to yourself. Then, I start counting, "0, 1, 2, 3, 4, 5, ..." and never stop. You listen to me count until you hear N. Then, you can stop listening, even though I'll never stop counting. At that point, you already know that my sequence contains N, and you don't have to keep listening.
I hope you agree that no matter which N you choose, you'll hear me say it sooner or later, as long as I keep counting up by 1. If N is a smaller number, you'll hear me say it sooner; if N is a bigger number, you'll hear me say it later. But there's no N you can choose that forces you to listen to me forever. (And again, just because you stop listening doesn't keep me from talking forever.)
The same thing cannot be done with the real numbers. If you think of some real number R that I don't know, then there's no way for me to count through the real numbers to guarantee that you will eventually hear R and stop listening. Even if I do try to pick a certain sequence, there's a very good chance that you'll never hear R and you'll have to keep listening forever.
> Why do you have to produce them in some predefined order?
That’s not counting. You were asked to count. If we are just going to make stuff up, let’s just use a different language instead of co-opting concepts from natural language.
There’s no case in which you can have a complete map anyways.
If you say one infinity is larger/smaller than another, you’d be saying that the complete map for one is larger/smaller than for the other one.
But if they are both infinite, you will never stop counting, so you just can’t know.
I know the diagonalization argument. But reality is that you can’t even count natural numbers.
So if you have finite time to count any set, the set will be finite, and so it’s countable.
But if you have infinite amount of time, any set for which there’s a formula to produce an element of, will always produce infinite elements at whatever speed you are able to produce them.
If one formula is faster than another (eg n=(n-1)+1 vs n=(n-1)!), then you will count more of one than the other in the same amount of time, but that is processing power, not the size of the sets.