A Bad Trip to Infinity(billwadge.com)
billwadge.com
A Bad Trip to Infinity
https://billwadge.com/2023/03/25/a-bad-trip-to-infinity/
126 comments
This is a somewhat glib but forty orders of magnitude, being a finite number, has no more to do with infinity that any other finite number. The nature of infinity is that you can’t get meaningfully closer to it.
> The car shot forward straight into the circle of light, and suddenly
> Arthur had a fairly clear idea of what infinity looked like.
>
> It wasn't infinity in fact. Infinity itself looks flat and uninteresting.
> Looking up into the night sky is looking into infinity - distance is
> incomprehensible and therefore meaningless. The chamber into
> which the aircar emerged was anything but infinite, it was just very
> very big, so that it gave the impression of infinity far better than
> infinity itself.
> Arthur had a fairly clear idea of what infinity looked like.
>
> It wasn't infinity in fact. Infinity itself looks flat and uninteresting.
> Looking up into the night sky is looking into infinity - distance is
> incomprehensible and therefore meaningless. The chamber into
> which the aircar emerged was anything but infinite, it was just very
> very big, so that it gave the impression of infinity far better than
> infinity itself.
This is from one of the Hitchhiker's Guide to the Galaxy books. They're with Slartibartfast driving onto the factory floor for creating planets. Slartibartfast, as you recall, is a famous "world designer" who won an award for designing the Fjords of Norway.
Depends on how you measure, for example what about the stereographic projection of the plane into the sphere and then use the metric in R3? Distance from a point in the plane to infinity is then the distance from where it maps to in the sphere to the north pole.
"They show the equation ∞ + 1 = ∞, which is true if ∞ is an infinite cardinal,
then proceed to subtract ∞ from both sides, giving 0=1, a howling contradiction. And that’s where they leave it."
This reminds me of Terrance Howard's statement that 1 multiplied by 1 equals 2: https://twitter.com/terrencehoward/status/925754491881877507
This reminds me of Terrance Howard's statement that 1 multiplied by 1 equals 2: https://twitter.com/terrencehoward/status/925754491881877507
> Instead they’re speculating about an orange in a box … which supposedly disintegrates then reassembles itself.
Haven't watched it but that sounds like they were attempting to cover the Banach-Tarski Theorem?
Haven't watched it but that sounds like they were attempting to cover the Banach-Tarski Theorem?
I have watched it, and it was actually talking about this: https://en.wikipedia.org/wiki/Poincar%C3%A9_recurrence_theor...
Ironically Banach-Tarski would have been better suited for a movie about infinity. Poincare recurrence is relevant for amounts of time that are merely exponentially large, not infinite.
I agree with Wadge that the movie was not very good, but I'm not actually sure what his objection is to the bit with the orange in a box, it seems fairly reasonable based on our current understanding of physics.
Ironically Banach-Tarski would have been better suited for a movie about infinity. Poincare recurrence is relevant for amounts of time that are merely exponentially large, not infinite.
I agree with Wadge that the movie was not very good, but I'm not actually sure what his objection is to the bit with the orange in a box, it seems fairly reasonable based on our current understanding of physics.
It’s been a while since I took a theoretical math class, so I’m struggling to remember how some infinite sets can be larger than others. The “one-to-one correspondence” definition given in the article is throwing me off.
If you have two infinite sets, then isn’t it always possible to map an element from one to a new element in the other, because there’s an unlimited number of elements to pick from?
If you have two infinite sets, then isn’t it always possible to map an element from one to a new element in the other, because there’s an unlimited number of elements to pick from?
>If you have two infinite sets, then isn’t it always possible to map an element from one to a new element in the other, because there’s an unlimited number of elements to pick from?
No. Consider the set of integers vs the set of real numbers. Suppose I have a 1 to 1 mapping from integers to reals. Lets pick an example of such a mapping to demonstrate.
Therefore, after mapping all the integers to real numbers, there's still left over real numbers. Hence the reals are a larger infinity than the ints.
No. Consider the set of integers vs the set of real numbers. Suppose I have a 1 to 1 mapping from integers to reals. Lets pick an example of such a mapping to demonstrate.
1 - .152345...
2 - .897454...
3 - .908345...
...
Therefore, after mapping all the integers to real numbers, there's still left over real numbers. Hence the reals are a larger infinity than the ints.
Responding as a constructivist would.
Let's define real numbers in a concrete way where they certainly exist, such as by equivalence classes of Cauchy sequences. Where a Cauchy sequence is a computer program that takes in a natural number, and returns a rational, complete with a proof that the rationals that it spits out will converge at a calculable rate.
Your mapping can now be constructed from an enumeration of such programs. (A single real may appear many times because many programs are equivalent. That's just a detail.) For each program we can put in a large enough number that we get the decimal place down to one of two. (The old 0.9999.... = 0 problem is a small complication here.) And then we pop out a clearly different digit. Given the mapping, this program can be easily written. And so we can produce our number which starts off in your example as the sequence .6, .64, .643, ... .
So far, so good. But what goes wrong?
Well we have a program that we assert produces a real. It certainly seems to do so. But proving that it represents a real requires proving that the program will always give the next digit. That requires proving that it works as advertised. That requires proving that the logic we used to make all of our decisions is consistent. But by Gödel's Incompleteness Theorem, we can only prove that if our logic is INCONSISTENT. And therefore our nice program doesn't have a proof that when ask for the n'th rational that it will ever return anything. And therefore it doesn't represent a real number!
This is why Cantor's diagonalization argument fails in constructivism. The impossibility of making a one-to-one map between naturals and reals becomes a statement about the self-referential logic embedded in the definition of real numbers, and NOT a proof that there exist an uncountable number of real numbers that we can never write down any meaningful description of!
Even if you don't subscribe to constructivism, I think it is important to recognize that the confident statements we make about infinity in classical mathematics rest on unprovable philosophical assumptions of a potentially dubious nature.
Let's define real numbers in a concrete way where they certainly exist, such as by equivalence classes of Cauchy sequences. Where a Cauchy sequence is a computer program that takes in a natural number, and returns a rational, complete with a proof that the rationals that it spits out will converge at a calculable rate.
Your mapping can now be constructed from an enumeration of such programs. (A single real may appear many times because many programs are equivalent. That's just a detail.) For each program we can put in a large enough number that we get the decimal place down to one of two. (The old 0.9999.... = 0 problem is a small complication here.) And then we pop out a clearly different digit. Given the mapping, this program can be easily written. And so we can produce our number which starts off in your example as the sequence .6, .64, .643, ... .
So far, so good. But what goes wrong?
Well we have a program that we assert produces a real. It certainly seems to do so. But proving that it represents a real requires proving that the program will always give the next digit. That requires proving that it works as advertised. That requires proving that the logic we used to make all of our decisions is consistent. But by Gödel's Incompleteness Theorem, we can only prove that if our logic is INCONSISTENT. And therefore our nice program doesn't have a proof that when ask for the n'th rational that it will ever return anything. And therefore it doesn't represent a real number!
This is why Cantor's diagonalization argument fails in constructivism. The impossibility of making a one-to-one map between naturals and reals becomes a statement about the self-referential logic embedded in the definition of real numbers, and NOT a proof that there exist an uncountable number of real numbers that we can never write down any meaningful description of!
Even if you don't subscribe to constructivism, I think it is important to recognize that the confident statements we make about infinity in classical mathematics rest on unprovable philosophical assumptions of a potentially dubious nature.
I'll bite. You can make a program the maps from integers (expressed in binary) to the real interval between 0 to 1. No matter what bit string the program outputs, it is meant to be (and thus interpreted as) the binary digits of the number that come after the decimal point. Thus there is no need for a proof of convergence, by the very nature of the representation it is impossible for the machine to output something that isn't a number somewhere on the interval from 0-1. All that matters then is proving it won't halt. But I can easily make sure it never halts by having a program that sits on top waiting for it to halt, and then if it does, restarts the program. So I can check the mapping from the integers to the interval, and by extension from the integers to the real number line.
Yes, you can write your program. And yes, you can guarantee that it will not halt. And yes, you can guarantee that its output is different than any program it managed to emulate.
But what happens when it tries to emulate itself? Well, if it produced any output, it would immediately produce a different output. The way out of paradox is that it returns nothing at all.
The program that sits on top now has a choice. If it decides to let the program continue to grind away, it NEVER produces that next digit. If it has any kind of logic that will give up after long enough, it WILL give up and move on.
Either way your program will fail to produce an output that is different from its own output. And therefore diagonalization fails.
But what happens when it tries to emulate itself? Well, if it produced any output, it would immediately produce a different output. The way out of paradox is that it returns nothing at all.
The program that sits on top now has a choice. If it decides to let the program continue to grind away, it NEVER produces that next digit. If it has any kind of logic that will give up after long enough, it WILL give up and move on.
Either way your program will fail to produce an output that is different from its own output. And therefore diagonalization fails.
>But what happens when it tries to emulate itself? Well, if it produced any output, it would immediately produce a different output. The way out of paradox is that it returns nothing at all.
Why immediately. It only has to differ by one bit somewhere along the infinite chain right? Why waste that perfectly good output when it can just as well output some of the emulation before interrupting it?
Why immediately. It only has to differ by one bit somewhere along the infinite chain right? Why waste that perfectly good output when it can just as well output some of the emulation before interrupting it?
You can try many variations on the scheme.
All will fall prey to the fact that the program must produce the same output as its emulation of itself. It can never get around this fact. Therefore it either produces a finite amount of input and then stops waiting for its emulated self, or it never gets around to producing something different than itself.
Either way it fails to diagonalize itself. The exact cause will vary. The eventual result will not.
Classical mathematics gets around this by waving hands over constructions with impossible procedures based on undiscoverable truths. By assumption these procedures can never be the input to themselves. The result is an insane number of possible outputs about whose tenuous existence we can say little but our claim that they exist.
No argument of pure logic alone can demonstrate any form of existence for these impossibilities, you must make additional unprovable philosophical assumptions about the nature of truth and existence.
I know that these techniques and results seem natural to you. But that is a consequence of your indoctrination into a system of thought which glosses over these complications instead of exploring them.
All will fall prey to the fact that the program must produce the same output as its emulation of itself. It can never get around this fact. Therefore it either produces a finite amount of input and then stops waiting for its emulated self, or it never gets around to producing something different than itself.
Either way it fails to diagonalize itself. The exact cause will vary. The eventual result will not.
Classical mathematics gets around this by waving hands over constructions with impossible procedures based on undiscoverable truths. By assumption these procedures can never be the input to themselves. The result is an insane number of possible outputs about whose tenuous existence we can say little but our claim that they exist.
No argument of pure logic alone can demonstrate any form of existence for these impossibilities, you must make additional unprovable philosophical assumptions about the nature of truth and existence.
I know that these techniques and results seem natural to you. But that is a consequence of your indoctrination into a system of thought which glosses over these complications instead of exploring them.
I am just guessing here, but I think the problem is that even if you redefine a real number as "that which can be written by a program", you cannot write a program that enumerates all such numbers.
That's kinda because different real numbers require programs of different complexity (for any specific complexity, e.g. the number of bytes, there is only a finite number of programs with that complexity), so listing all the real numbers would require infinite complexity, i.e. not a (finite) program.
So there is a countable set of integer, and a set of reals (by the new definition) which is countable (by the usual definition) but cannot be enumerated, so it is technically "uncountable" (by the new definition).
The trick is that if you are changing definitions, you may accidentally also change the definition of "countable". Because it is defined as "that which can be mapped to integers", but the problem is, which mappings are considered legal and which are not. In the world of "only things written by programs exist", only mappings which can be generated by programs exist; which is not the same as all possible mappings, so a few previously countable things now become "uncountable".
That's kinda because different real numbers require programs of different complexity (for any specific complexity, e.g. the number of bytes, there is only a finite number of programs with that complexity), so listing all the real numbers would require infinite complexity, i.e. not a (finite) program.
So there is a countable set of integer, and a set of reals (by the new definition) which is countable (by the usual definition) but cannot be enumerated, so it is technically "uncountable" (by the new definition).
The trick is that if you are changing definitions, you may accidentally also change the definition of "countable". Because it is defined as "that which can be mapped to integers", but the problem is, which mappings are considered legal and which are not. In the world of "only things written by programs exist", only mappings which can be generated by programs exist; which is not the same as all possible mappings, so a few previously countable things now become "uncountable".
You can write a program that will always generate a real number, but you can't write a program that will generate all of the reals, or even any single real that's irrational (like pi). And the vast, vast majority of reals are irrational.
The best you can do is a program that generates a crude approximation to an irrational, because you'd need an infinite number of states to write the entire number and every physical computer has a finite number of states.
If your program that sits on top restarts the underlying program, then it will generate a repeating binary sequence. And that's a rational number.
The best you can do is a program that generates a crude approximation to an irrational, because you'd need an infinite number of states to write the entire number and every physical computer has a finite number of states.
If your program that sits on top restarts the underlying program, then it will generate a repeating binary sequence. And that's a rational number.
>The best you can do is a program that generates a crude approximation to an irrational, because you'd need an infinite number of states to write the entire number and every physical computer has a finite number of states.
I can provide you with the requested infinite amount of state, I merely require infinite amounts of time.
>If your program that sits on top restarts the underlying program, then it will generate a repeating binary sequence. And that's a rational number.
And that would be stupid and obviously wrong. I should have clarified that the program sitting on top interrupting stuff is obviously changing something before restarting. Could be anything. Maybe flips some stateful starting info, maybe swaps to a different program, maybe starts xoring the output with something. Could be anything
I can provide you with the requested infinite amount of state, I merely require infinite amounts of time.
>If your program that sits on top restarts the underlying program, then it will generate a repeating binary sequence. And that's a rational number.
And that would be stupid and obviously wrong. I should have clarified that the program sitting on top interrupting stuff is obviously changing something before restarting. Could be anything. Maybe flips some stateful starting info, maybe swaps to a different program, maybe starts xoring the output with something. Could be anything
Again, the same trap.
It doesn't matter what the program sitting on top changes, it does so in a deterministic way. And therefore the emulation of the program changes the same thing, in the same way. Which means that the emulation cannot figure out the next bit of its output faster than the actual program.
And therefore the program either never decides to output anything which would have diagonalized itself, or it gets stuck after a finite time by a liar's paradox attempting to figure out the next bit of it would put out so that it can put something different out instead. Either way diagonalization of itself cannot succeed.
The reasoning here is very similar to Turing's proof of the Halting Problem - no program exists that is able to take a program + input and reliably determine whether that program will halt. And the reason is that you set up a program which would have to set up a liar's paradox about itself fed input that translates to itself fed input about itself recursively. The only logically consistent result is that this program both cannot halt, and cannot figure out that it doesn't halt.
It doesn't matter what the program sitting on top changes, it does so in a deterministic way. And therefore the emulation of the program changes the same thing, in the same way. Which means that the emulation cannot figure out the next bit of its output faster than the actual program.
And therefore the program either never decides to output anything which would have diagonalized itself, or it gets stuck after a finite time by a liar's paradox attempting to figure out the next bit of it would put out so that it can put something different out instead. Either way diagonalization of itself cannot succeed.
The reasoning here is very similar to Turing's proof of the Halting Problem - no program exists that is able to take a program + input and reliably determine whether that program will halt. And the reason is that you set up a program which would have to set up a liar's paradox about itself fed input that translates to itself fed input about itself recursively. The only logically consistent result is that this program both cannot halt, and cannot figure out that it doesn't halt.
… in python?
Just picking digits from the diagonal might not work, you have to make sure the digits of the new number aren't equal to the ones on the diagonal, one way is to add 1 mod 10, in the case you showed it would result with 0.209...
I always explain this with binary digits. You can always construct a new one from the diagonal by flipping each bit. I think the smaller domain {0,1} instead of {0,1,2,3,4,5,6,7,8,9} keeps people from getting distracted and trying to find a loophole.
Binary is the only base where that proof does not work well easily, because 100000... = 011111...
in a metric system.
100000... is only equal to 011111... if your digits roll over, but if your digits roll over then you have a p-adic number system (specifically a 2-adic system), and the exact same argument would hold equally well for the 10-adic applied to 10000..... = 99999.....
You argument isn't dependent on being binary or not. Only that the numbers roll over.
You argument isn't dependent on being binary or not. Only that the numbers roll over.
In bases higher than 2, you can avoid the issue entirely by saying that some digits get +1 and other digits get -1.
If the generated number only has digits 1-8, then 0000... vs 9999... is obviously not a problem.
If the generated number only has digits 1-8, then 0000... vs 9999... is obviously not a problem.
[deleted]
Okay, I think that jogged my memory.
So, the idea is that no matter what mathematical mapping you create from Natural -> Real, it will always be possible to find a Real number that is not in that mapping. Therefore, |Real| > |Natural|.
Still, it feels wrong. If my "function" is an immortal monkey I've trained to grab one item from an unlimited Natural number bucket, and another from an unlimited Real number bucket, and put them together, that process could go on ad infinitum. It's hard to imagine one bucket as been larger than the other, when both are endless.
So, the idea is that no matter what mathematical mapping you create from Natural -> Real, it will always be possible to find a Real number that is not in that mapping. Therefore, |Real| > |Natural|.
Still, it feels wrong. If my "function" is an immortal monkey I've trained to grab one item from an unlimited Natural number bucket, and another from an unlimited Real number bucket, and put them together, that process could go on ad infinitum. It's hard to imagine one bucket as been larger than the other, when both are endless.
If you had a bucket with 10 million options in one and 100m in another, you'd take 10 million picks before you realized via a 1-1 picking that one was smaller than the other.
Infinities obviously dont collapse and "end", but seeing infinities "grow" faster than others makes a lot of sense to me.
Infinities obviously dont collapse and "end", but seeing infinities "grow" faster than others makes a lot of sense to me.
Infinity as a concept is not easy to reason about because it’s not something we ever encounter in our daily lives. It leads to interesting paradoxes such as Hilbert Hotel.
Coming to Natural and Real numbers, one way I’d like to think is that real numbers are more “dense” (or continuous) compare to integers which are discrete. A cup full of sugar and cup full of water could be of equal volume but you can count sugar grains and not water because water is not grainy and is “continuous”.
Coming to Natural and Real numbers, one way I’d like to think is that real numbers are more “dense” (or continuous) compare to integers which are discrete. A cup full of sugar and cup full of water could be of equal volume but you can count sugar grains and not water because water is not grainy and is “continuous”.
The "therefore" is not quite right.
You have shown that that the original assumption leads to a contradiction and so doesn't hold.
You have shown that that the original assumption leads to a contradiction and so doesn't hold.
You can construct a mapping where an infinite number in the one are mapped to an infinite number in the other.
You can't always construct a mapping where all of one maps to all of the other.
Classical mathematics concludes from this that one set truly has more things than the other does. These presentations always assume that classical mathematics is right. But it ACTUALLY depends on philosophical assumptions that are both unprovable, and questionable.
In particular, classical mathematics assumes that it makes sense to talk about whether a statement is absolutely true or false. And to build constructions that require a series of decisions based on the absolute truth value of the statement. This despite the fact that we do not know whether it is true, have no procedures to determine it, and in some cases the statement is independent of our axioms.
Attempts to create finite parallels to this type of reasoning inevitably run into self-referential paradoxes and contradictions. It appears that classical mathematics avoids such paradoxes from the simple fact that nobody can actually carry out these impossible procedures. If we could, then we would certainly find similar contradictions.
People have attempted to figure out what mathematics would look like if we limited ourselves to things we can prove true and false, instead of making statements about the truth value of things that we have (and may never have) any proof of. The results go by names such as "constructivism" and "intuitionism". In those systems some infinite sets have more self-referential structure, but none has "more" elements than any other.
There is no logical reason to choose classical mathematics over these alternatives. Only arguments about philosophy and convenience help us choose. I wish that this fact was more often acknowledged.
You can't always construct a mapping where all of one maps to all of the other.
Classical mathematics concludes from this that one set truly has more things than the other does. These presentations always assume that classical mathematics is right. But it ACTUALLY depends on philosophical assumptions that are both unprovable, and questionable.
In particular, classical mathematics assumes that it makes sense to talk about whether a statement is absolutely true or false. And to build constructions that require a series of decisions based on the absolute truth value of the statement. This despite the fact that we do not know whether it is true, have no procedures to determine it, and in some cases the statement is independent of our axioms.
Attempts to create finite parallels to this type of reasoning inevitably run into self-referential paradoxes and contradictions. It appears that classical mathematics avoids such paradoxes from the simple fact that nobody can actually carry out these impossible procedures. If we could, then we would certainly find similar contradictions.
People have attempted to figure out what mathematics would look like if we limited ourselves to things we can prove true and false, instead of making statements about the truth value of things that we have (and may never have) any proof of. The results go by names such as "constructivism" and "intuitionism". In those systems some infinite sets have more self-referential structure, but none has "more" elements than any other.
There is no logical reason to choose classical mathematics over these alternatives. Only arguments about philosophy and convenience help us choose. I wish that this fact was more often acknowledged.
You can always "take an element from each set" over and over, but for this mapping to be shown to be a 1:1, you need to be more specific.
Example: the set of all natural numbers (0, 1, ...) is the same "size" as the set of all even numbers, because you can map any number N to the number 2N. It's obvious that any natural number N is uniquely accounted for by this mapping, since you can double any natural number (with a unique even result), and it's obvious that any even number is uniquely accounted for, because any even number divided by 2 is a (unique) natural number.
But if your mapping is defined as "take an arbitrary rational number and arbitrary irrational number, over and over forever", then there's no guarantee that, given an arbitrary irrational number, your mapping has defined a unique associated rational number.
Example: the set of all natural numbers (0, 1, ...) is the same "size" as the set of all even numbers, because you can map any number N to the number 2N. It's obvious that any natural number N is uniquely accounted for by this mapping, since you can double any natural number (with a unique even result), and it's obvious that any even number is uniquely accounted for, because any even number divided by 2 is a (unique) natural number.
But if your mapping is defined as "take an arbitrary rational number and arbitrary irrational number, over and over forever", then there's no guarantee that, given an arbitrary irrational number, your mapping has defined a unique associated rational number.
It’s been a while for me but the main thing you need to consider is bijections. If you can find a mapping for each A -> B and conversely each B -> A then they’re the same size.
Consider the rational numbers. They can all be written as x/y. It’s clear that you can map from rational to natural as x/1 -> x. Now imagine a 2d grid of natural numbers on each axis. You can spiral out from (0,0), (0,1), (1,1), (1,0) etc in a loop. Now you have a way of mapping from the natural numbers to the rational numbers. So they must be the same size.
Consider the rational numbers. They can all be written as x/y. It’s clear that you can map from rational to natural as x/1 -> x. Now imagine a 2d grid of natural numbers on each axis. You can spiral out from (0,0), (0,1), (1,1), (1,0) etc in a loop. Now you have a way of mapping from the natural numbers to the rational numbers. So they must be the same size.
To clarify. There is no mapping from natural numbers to all the irrational numbers. And that’s why there are different sized infinities
Why not?
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.
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.
Think about counting as three operations:
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.
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.
/me not a mathematician!
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.
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...
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.
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 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.
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.
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.
That’s the problem.
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.
That’s the problem.
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.
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.
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.
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.
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.
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.
> Think about counting as three operations:
> 1. Produce a number 2. Add it to the set of numbers I’m counting 3. Sort the numbers
Missing in your definition is the operation has to produce all numbers that you are counting over.
If you are counting something, you don't leave out elements.
Missing in your definition is the operation has to produce all numbers that you are counting over.
If you are counting something, you don't leave out elements.
If you are counting a set that is larger than your count, you will always leave elements out.
The only way you won’t leave elements out for an infinite set is if you keep counting forever.
The only way you won’t leave elements out for an infinite set is if you keep counting forever.
"If you are counting a set that is larger than your count"
What does that mean?
What does that mean?
If you want to count 4 natural numbers, your count is going to be 4, but the set of natural numbers is infinite. The set is larger than the count.
You can count natural numbers. Elementary school children do it every day. Now, try to count the real numbers. What comes after 1?
> What comes after 1?
Whatever I want.
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.
Whatever I want.
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.
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.
Like when proving 1=2 by dividing by 0.
But then what’s the point?
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.
Like when proving 1=2 by dividing by 0.
But then what’s the point?
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.
> 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?
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.
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.
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.
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.
"Counting", for these purposes, doesn't mean determining how many there are; it means going through them, or a subset of them, in some defined order.
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 =><=
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).
> 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).
> 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.
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.
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.
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?
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.
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…
Please see this other comment: https://news.ycombinator.com/item?id=35311403
> 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…
Please see this other comment: https://news.ycombinator.com/item?id=35311403
We're talking about infinity, not practical considerations.
> (or insert them in order),
There is no order. You can't describe one, and it is proven that no order exists.
> you can count as many real numbers as you want
No, you can't count more than 0% of them, even in infinite steps.
> (or insert them in order),
There is no order. You can't describe one, and it is proven that no order exists.
> you can count as many real numbers as you want
No, you can't count more than 0% of them, even in infinite steps.
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.
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.
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.
Neither the reals nor the naturals “exist”. We produce them as we need them.
Reals and naturals both have the same number of symbols: unknowable (“infinity”).
> Feel free to give me a generator function and I will give you a finite number that it cannot reach in finite steps.
f(n)=n
If you give n to that formula, it will generate n in 1 step.
> On the other hand, try giving me a finite positive integer that I cannot reach in finite steps.
Can’t come up with one. As long as is finite you can always just output the number itself.
Anything finite is countable. Anything infinite is unknowable.
Reals and naturals both have the same number of symbols: unknowable (“infinity”).
> Feel free to give me a generator function and I will give you a finite number that it cannot reach in finite steps.
f(n)=n
If you give n to that formula, it will generate n in 1 step.
> On the other hand, try giving me a finite positive integer that I cannot reach in finite steps.
Can’t come up with one. As long as is finite you can always just output the number itself.
Anything finite is countable. Anything infinite is unknowable.
> 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.
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.
What you are saying is:
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.
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.
> 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.
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.
I'm no expert but I think the trick is to say "give me a function that for any element in Set A, returns a matching element in Set B".
For mapping integers to even numbers it's f(x)->x*2
But for mapping integers to real numbers - there is no possible mapping.
Cantor's Diagonal Argument is really easy to follow - watch a YouTube vid or two on the topic. Also Hilbert's Hotel is well covered.
For mapping integers to even numbers it's f(x)->x*2
But for mapping integers to real numbers - there is no possible mapping.
Cantor's Diagonal Argument is really easy to follow - watch a YouTube vid or two on the topic. Also Hilbert's Hotel is well covered.
Whether a set is finite or infinite, its power set is always bigger.
Let S be any set and assume f: S -> P(S) exhaustively enumerates the subsets of S using only elements of S.
Then define a new subset L of S: For each s in S, we decide whether to include s in L as follows: If f(s) contains s, then L shall NOT contain s, if f(s) does not contain s, then L DOES contain it.
No s in S can be a preimage of L under f, since L disagrees with f(s) about whether it contains s or not, by construction. So f must have missed L. So P(S) is strictly larger than S.
Nothing about infinities in there. You can't have a surjective mapping from any set to its power set, ever.
Let S be any set and assume f: S -> P(S) exhaustively enumerates the subsets of S using only elements of S.
Then define a new subset L of S: For each s in S, we decide whether to include s in L as follows: If f(s) contains s, then L shall NOT contain s, if f(s) does not contain s, then L DOES contain it.
No s in S can be a preimage of L under f, since L disagrees with f(s) about whether it contains s or not, by construction. So f must have missed L. So P(S) is strictly larger than S.
Nothing about infinities in there. You can't have a surjective mapping from any set to its power set, ever.
We can say a lot about infinity. But for people who don't study advanced math by choice, the first question is why are we talking about infinity, when we don't normally, in our physical world, encounter infinite amounts of anything.
The answer is pretty simple: it is easier to work with infinity than with a large finite number, and by working with infinity, you discover similarities among situations in which you encounter different "large finite numbers". So, for example, it is easier to study a circle than a polygon with a million sides. In statistical physics we say that the heat capacity "diverges" at a phase transition, but of course a real material must absorb a finite amount of heat at a phase transition; nonetheless, we treat "macroscopic" as "infinite" freely, knowing that any errors will be far below measurement limitations.
In the above cases, we are dealing with infinity as the limit of a particular process. But in order to make the ideas in calculus convenient, we want to consider all of the limits of all sequences which converge, because it allows us to use the concept of limit freely. This leads to the definition of the "real numbers" by Dedekind cuts (the topological closure of the rationals); it is how we define the "bigger infinity". When we say the real numbers are "bigger" than the integers, we can explain this in finite-sounding terms as: we cannot define a "sequence of all sequences".
The answer is pretty simple: it is easier to work with infinity than with a large finite number, and by working with infinity, you discover similarities among situations in which you encounter different "large finite numbers". So, for example, it is easier to study a circle than a polygon with a million sides. In statistical physics we say that the heat capacity "diverges" at a phase transition, but of course a real material must absorb a finite amount of heat at a phase transition; nonetheless, we treat "macroscopic" as "infinite" freely, knowing that any errors will be far below measurement limitations.
In the above cases, we are dealing with infinity as the limit of a particular process. But in order to make the ideas in calculus convenient, we want to consider all of the limits of all sequences which converge, because it allows us to use the concept of limit freely. This leads to the definition of the "real numbers" by Dedekind cuts (the topological closure of the rationals); it is how we define the "bigger infinity". When we say the real numbers are "bigger" than the integers, we can explain this in finite-sounding terms as: we cannot define a "sequence of all sequences".
> we don't normally, in our physical world, encounter infinite amounts of anything.
I may be missing your meaning, but we encounter distances (e.g. line-segments) all the time; the number of points on a line-sement is equal to the cardinality of the reals. The physical world is full of infinite sets, most of which are uncountable.
I may be missing your meaning, but we encounter distances (e.g. line-segments) all the time; the number of points on a line-sement is equal to the cardinality of the reals. The physical world is full of infinite sets, most of which are uncountable.
Thinking of actions leads you astray. Maps look like actions but they are not.
Is the set of all odd numbers smaller than the set of all even and odd numbers together? If not, then if you were to merge the set of all even numbers to the set of all odd numbers, did you really merge anything since the set didn't grow?
Intuition tends to breakdown when dealing with infinite sets. This is especially true for uncountable sets. Instead thinking about enlarging or merging sets think of indexing things. The odd numbers can index in a unique way just as many things as the set of all integers.
The real numbers (everything on the number line, including things like 1, 0, 4/237, and pi) and the integers have no such correspondence. The reals are an "uncountable" infinity.
Though it's weirder than that. If you can actually put a number on the number line, then you have a computable number. And those are countable.
Uncountable reals only exist as abstract thought experiments.
Uncountable reals only exist as abstract thought experiments.
> Uncountable reals only exist as abstract thought experiments.
Technically, sufficiently large natural numbers, such as 10^10^10 also exist only as thought experiments.
Technically, if we require the number to refer to some number of objects, there is such as thing as a largest natural number - it is the number of all particles that exist in the universe. If you add +1 to it, the result of that addition exists only as a thought experiment.
Technically, sufficiently large natural numbers, such as 10^10^10 also exist only as thought experiments.
Technically, if we require the number to refer to some number of objects, there is such as thing as a largest natural number - it is the number of all particles that exist in the universe. If you add +1 to it, the result of that addition exists only as a thought experiment.
As natural numbers get huge, they become gradually harder to use. Though no, I wouldn't require a number to represent some physical quantity, as long as the number itself fits in some kind of moderate physical boundary.
But real numbers are wonky right from the start. Picking a single random real out of a range is infeasible.
But real numbers are wonky right from the start. Picking a single random real out of a range is infeasible.
You are mixing up definitions. Pi is computable, meaning we can calculate one by one its digits, but is not rational. If you can compute a number in a finite time, you can put it om the number line, but the only numbers that can be finitely computed are the rationals which are countable
You can put pi on a number line just fine, though. You can pick any range of the number line to look at, and determine pi's place to arbitrary precision in finite time.
With "uniformly random real between 0 and 1" you can't do that.
More relevantly to infinities, the program that spits out the digits of pi is finite. We can easily count through all the computable numbers, including every number you can specifically name, albeit in a weird order and with duplicates.
It's not a bijection, but if you have a computable number you can derive a natural number that represents its program, and if you have a natural (or rational) number you can derive a program that computes it.
With "uniformly random real between 0 and 1" you can't do that.
More relevantly to infinities, the program that spits out the digits of pi is finite. We can easily count through all the computable numbers, including every number you can specifically name, albeit in a weird order and with duplicates.
It's not a bijection, but if you have a computable number you can derive a natural number that represents its program, and if you have a natural (or rational) number you can derive a program that computes it.
it isn’t always possible, and cantor’s proof demonstrates that neatly, by giving an algorithm to construct (an infinite number of) counter-examples of non-mappable elements of the larger set.
[deleted]
let's consider two potentially infinite sentences:
Buffalo buffalo buffalo buffalo -> infinite
and
Police Police Police Police -> infinite
certainly Buffalo and Police sentences can both be infinite but the Buffalo sentence is obviously larger than the Police sentence because Buffalo has 7 letters and Police only 6.
https://en.wikipedia.org/wiki/Buffalo_buffalo_Buffalo_buffal...
Buffalo buffalo buffalo buffalo -> infinite
and
Police Police Police Police -> infinite
certainly Buffalo and Police sentences can both be infinite but the Buffalo sentence is obviously larger than the Police sentence because Buffalo has 7 letters and Police only 6.
https://en.wikipedia.org/wiki/Buffalo_buffalo_Buffalo_buffal...
This is a bad example. In fact those sentences have the same cardinality, much like the set of even natural numbers has the same cardinality as the set of all natural numbers even though only half the natural numbers are even.
they may have the same cardinality, but one infinite sentence is obviously longer than the other infinite sentence.
on edit: noting depends on if we consider as elements the words, or the letters.
on edit: noting depends on if we consider as elements the words, or the letters.
Longer/larger according to what ?
If its according to cardinality then no, they have the same cardinality, same number of elements, presumably letters. If its according to a measure, then sure, one can be longer than the other -- the subset of [0,1] of the real line has the same cardinality, same number of 'points' as [0, 100] but the latter is longer when you compare according to the Lebesgue measure, i.e. 'length'.
If its according to cardinality then no, they have the same cardinality, same number of elements, presumably letters. If its according to a measure, then sure, one can be longer than the other -- the subset of [0,1] of the real line has the same cardinality, same number of 'points' as [0, 100] but the latter is longer when you compare according to the Lebesgue measure, i.e. 'length'.
Things that are "obviously" true are often false.
The only way to compare the lengths of the two infinite sentences is by comparing their cardinalities. There is no other meaningful definition of sentence length for an infinite sentence. They have the same cardinality, so they're the same "length."
The only way to compare the lengths of the two infinite sentences is by comparing their cardinalities. There is no other meaningful definition of sentence length for an infinite sentence. They have the same cardinality, so they're the same "length."
> Buffalo sentence is obviously larger than the Police sentence
It obviously isn't, since the infinite repetition of "Police " is
THE SAME as the infinite repetition of the longer "Police Police ".
It obviously isn't, since the infinite repetition of "Police " is
THE SAME as the infinite repetition of the longer "Police Police ".
there are some amusing other parts to this of course.
Since Buffalo -> is infinite and Police -> is infinite, but Buffalo is larger than Police how much larger is it?
It is obviously infinitely larger.
Since Buffalo -> is infinite and Police -> is infinite, but Buffalo is larger than Police how much larger is it?
It is obviously infinitely larger.
Those two infinite statements have the same cardinality.
they may have the same cardinality, but one infinite sentence is obviously longer than the other infinite sentence.
on edit: noting depends on if we consider as elements the words, or the letters.
on edit: noting depends on if we consider as elements the words, or the letters.
If one of them, presumably the buffalo sentence, indeed has more letters, then could you give us a invertible scheme that maps to each letter of the police sentence, a letter in the buffalo sentence, that covers all the letters in the police sentence, but has letters in the buffalo sentence still left over.
[deleted]
Infinity is a social construct in mathematics. Mathematics values terseness over case analysis, because humans have to manipulate the formulas. By introducing infinities, formulas have fewer cases to analyze.
You can have math without infinity and without undecidability, but there's much more case analysis and things get ugly. Look at how SAT solvers with rational arithmetic work.
You can have math without infinity and without undecidability, but there's much more case analysis and things get ugly. Look at how SAT solvers with rational arithmetic work.
> Infinity is a social construct in mathematics.
Out of curiosity, is the number "4" also a social construct?
Out of curiosity, is the number "4" also a social construct?
"Natural numbers were created by God, everything else is the work of men" — Kronecker
This documentary sounds pretty bad from the description, but I this article paints an incorrect picture of how mathematicans study the infinite.
Whether there is one infinity or multiple is entirely context dependent. Yes, there's far more than just one infinite cardinal. But it is a mistake to identify "infinities" with "infinite cardinals". In fact, mathematicians use a bunch of systems of infinite numbers; cardinals are only one of them. (Also, they may also use "infinity" in ways that can't reasonably be called numeric, or that are entirely informal; I'm not trying to cover every possibility here, just demonstrate how it's not just cardinals.)
For instance, in addition to cardinals, there are also the ordinals, another system of transfinite numbers which works quite differently. Or, if one wants infinitesimals as well, there are the surreal numbers (although these (sort of) include the ordinals).
But also, in many contexts, the right thing to do is not to use any of these, and to simply use the extended reals -- i.e., just take the real numbers and just stick a big flat undifferentiated "infinity" on the top of it (and possibly a minus infinity on the bottom depending on context). In the extended nonnegative reals, there really is only one infinity. And as much as I love cardinals and ordinals... they're not appropriate for most situations involving the infinite. The extended reals are useful far more often. You're going to be using a system with only one infinity far more often than a system with multiple infinities.
It's worth pointing out the more general point here -- numbers come in systems and cannot be used outside the context of some system! There is not, in fact, any single mathematical definition of a "number". You might imagine that in math there is some set of "the numbers". (Many people seem to specifically have the wrong idea that the complex numbers are "the numbers".) There isn't! There are different systems of numbers and each works differently.
Some of these systems of numbers fit together and are compatible with one another; e.g., the whole numbers include into the real numbers. And also, the whole numbers include into the cardinals; it's compatible with either. But some of these systems are not compatible with one another and do not fit together. You can't combine real numbers and cardinals! It's meaningless to ask, "What's 2pi + aleph_0?", even though both are "numbers" in some sense, because these systems are not compatible. (Well, unless you do the work to make them compatible, which can sometimes happen; although note that in many cases systems are quite definitely incompatible and can't be made to fit together.)
So it is incorrect to say that cardinals are the way to do infinities and that "infinities" mean "cardinals". There are other, incompatible, systems of infinities; and in many contexts, you want a system with just one infinity, not multiple. And in these contexts, which are numerous, you do just say "infinity" and leave it at that, and this is perfectly correct.
Whether there is one infinity or multiple is entirely context dependent. Yes, there's far more than just one infinite cardinal. But it is a mistake to identify "infinities" with "infinite cardinals". In fact, mathematicians use a bunch of systems of infinite numbers; cardinals are only one of them. (Also, they may also use "infinity" in ways that can't reasonably be called numeric, or that are entirely informal; I'm not trying to cover every possibility here, just demonstrate how it's not just cardinals.)
For instance, in addition to cardinals, there are also the ordinals, another system of transfinite numbers which works quite differently. Or, if one wants infinitesimals as well, there are the surreal numbers (although these (sort of) include the ordinals).
But also, in many contexts, the right thing to do is not to use any of these, and to simply use the extended reals -- i.e., just take the real numbers and just stick a big flat undifferentiated "infinity" on the top of it (and possibly a minus infinity on the bottom depending on context). In the extended nonnegative reals, there really is only one infinity. And as much as I love cardinals and ordinals... they're not appropriate for most situations involving the infinite. The extended reals are useful far more often. You're going to be using a system with only one infinity far more often than a system with multiple infinities.
It's worth pointing out the more general point here -- numbers come in systems and cannot be used outside the context of some system! There is not, in fact, any single mathematical definition of a "number". You might imagine that in math there is some set of "the numbers". (Many people seem to specifically have the wrong idea that the complex numbers are "the numbers".) There isn't! There are different systems of numbers and each works differently.
Some of these systems of numbers fit together and are compatible with one another; e.g., the whole numbers include into the real numbers. And also, the whole numbers include into the cardinals; it's compatible with either. But some of these systems are not compatible with one another and do not fit together. You can't combine real numbers and cardinals! It's meaningless to ask, "What's 2pi + aleph_0?", even though both are "numbers" in some sense, because these systems are not compatible. (Well, unless you do the work to make them compatible, which can sometimes happen; although note that in many cases systems are quite definitely incompatible and can't be made to fit together.)
So it is incorrect to say that cardinals are the way to do infinities and that "infinities" mean "cardinals". There are other, incompatible, systems of infinities; and in many contexts, you want a system with just one infinity, not multiple. And in these contexts, which are numerous, you do just say "infinity" and leave it at that, and this is perfectly correct.
> The average intelligent viewer will be left confused and intimidated
I’m not qualified to know if your post is better or worse than Netflix’s documentary, Bill, but this is an egregious example of a pot calling a kettle black.
I’m not qualified to know if your post is better or worse than Netflix’s documentary, Bill, but this is an egregious example of a pot calling a kettle black.
To be fair, it does a decent job of plowing through set theory in only a short rant about why the documentary is bad, forgetting to rant about the documentary because there's so much math to cover.
It only commits the cardinal sin of trimming it down so much that it makes sense if and only if the reader is already familiar with it, leaving other intelligent readers confused and intimidated.
It only commits the cardinal sin of trimming it down so much that it makes sense if and only if the reader is already familiar with it, leaving other intelligent readers confused and intimidated.
I am qualified to figure that out.
The post may be confusing, but it gets its math correct. And describes the documentary getting it wrong. So the post is probably better.
The post may be confusing, but it gets its math correct. And describes the documentary getting it wrong. So the post is probably better.
All people engage in mysticism, but when Materialists do it they expect a free pass, and due to being the dominant ideology (and also: cheating) they ~always win arguments, keeping everyone locked inside their artificial and invisible reality dome.
C'est la vie!!
C'est la vie!!
Yes, not all readers will follow everything but my post is true and studying it will clear things up. However the movie will resit any attempted clarification.
_le sigh_ ... still talking about infinities in semantic of quantity and size. For me, a better mental model is "relative density"
https://youtu.be/0fKBhvDjuy0
There's also an hour-long talk by Prof. Raymond Flood on Cantor's Infinities on YT that covers all the mathematical history.