Why Some Infinities Are Bigger Than Others(scientificamerican.com)
scientificamerican.com
Why Some Infinities Are Bigger Than Others
https://www.scientificamerican.com/article/a-deep-math-dive-into-why-some-infinities-are-bigger-than-others/
7 comments
There is however a bijection between the natural/countable numbers and every number that mathematicians, physicists, and any other scientist have every used in all of human history (or will ever use). Start with the computable numbers, and then generalize to anything that has been written down in symbolic text.
It's very hard to point to a real number which is not in the set of computable numbers, and for the few examples (Chaitin's constant(s) etc...), there are countably many of them.
From this point of view, I'm curious whether the computable numbers are sufficient to do integral and differential calculus etc... (basically all "normal" math that engineers or applied scientists might use) Maybe it requires a different definition of limits, I dunno. What number are we interested in that can't be done with computable numbers?
At what point do we need Real numbers and their mind-blowingly weird properties?
It's very hard to point to a real number which is not in the set of computable numbers, and for the few examples (Chaitin's constant(s) etc...), there are countably many of them.
From this point of view, I'm curious whether the computable numbers are sufficient to do integral and differential calculus etc... (basically all "normal" math that engineers or applied scientists might use) Maybe it requires a different definition of limits, I dunno. What number are we interested in that can't be done with computable numbers?
At what point do we need Real numbers and their mind-blowingly weird properties?
I am certainly not an expert on this, but my guess is that there will be be challenges to doing calculus since you won't have the standard foundational properties of the reals (like the least upper bound property). That being said, it looks like mathematicians have investigated this.[0]
0. https://en.wikipedia.org/wiki/Computable_analysis
0. https://en.wikipedia.org/wiki/Computable_analysis
It's not individual numbers that matter, but the properties of sets of them and functions over them. You can define a Reimann integral over computable numbers without changing much, but not the more general Lebesgue integral. This means you won't get e.g. the nice properties of L2 spaces which are used heavily in quantum mechanics.
I'm not sure if you'll see this reply since it's been several days, but I appreciate the answer. I majored in math, but I never stumbled on the Lebesgue integral, and I don't know enough quantum to understand the subtlety there either. I'll have to take your word for it that L2 spaces don't work with just computable numbers, but I can't see why yet. All of that to say, I'm just admitting my ignorance and not arguing at all.
Still, I think it's interesting that if Reals are truly needed to model the universe (physics), then there must be some case where computables are insufficient. And if the universe isn't computable, that says something amusing and deep about determinism and whether we can ever succeed in modelling it. :-)
Still, I think it's interesting that if Reals are truly needed to model the universe (physics), then there must be some case where computables are insufficient. And if the universe isn't computable, that says something amusing and deep about determinism and whether we can ever succeed in modelling it. :-)
One of the major pillars of measure theory is countable subadditivity, which serves to allow one to work with countably infinite series in a nice way. This is pretty much unworkable in a countable space like the computables. That isn't to say we really "need" the reals, merely that math hasn't come up with a fully-featured alternative framework that physics can use. I know there are people working on "computable measure theory" in recent years, and there's no reason why the universe should use a mathematical framework that is easy for we humans to construct.
A fun wrinkle is that there are (infinitely many) models of set theory which are pointwise definable. Thus in the right model of zfc, every mathematical object is uniquely addressable by a certain finite formula.
(see https://arxiv.org/pdf/1105.4597.pdf )
I think it's mostly a distinction between abstract and practical concepts. You might say that the infinite set of real numbers between 0 and 1 is as big as the infinite set of positive integers, but that's just true in an abstract sense. In the practical sense, for example, there are not infinite frequencies between 0 and 1 Hertz because they're subject to physical limits.
> You might say that the infinite set of real numbers between 0 and 1 is ad big as [N]
No, I would say that it is much bigger, since [0, 1] is uncountable.
> there are not infinite frequencies between 0 and 1.
Personally I think time is continuous. It sounds like you believe it is discrete. But such a debate is entirely irrelevant to the set theory.
No, I would say that it is much bigger, since [0, 1] is uncountable.
> there are not infinite frequencies between 0 and 1.
Personally I think time is continuous. It sounds like you believe it is discrete. But such a debate is entirely irrelevant to the set theory.
And that is another example of the abstract vs pragmatic visions: it hasn't been proved that time is (or isn't) quantized, so we're left with out own opinions.
Seeing that time needs things happening, and things are made of matter, which is quantized, I'm inclined to think time is quantized too.
Seeing that time needs things happening, and things are made of matter, which is quantized, I'm inclined to think time is quantized too.
The idea of "differently sized infinities" has always felt like a mathematical game to me.
The work of Cantor and beyond regarding infinite sets is generally taught as mathematical "fact", as fundamental as 2+2=4, but unlike 2+2=4 is there any practical constraints or applications around it? It seems more like an almost arbitrary puzzle than "fact".
I don't disagree with any of the proofs or reasoning... it just kinda bugs me that the way the formal cardinality of infinite sets is communicated is as the commonsense notion of "size".
When we make statements such as the size of the set of all natural numbers 1, 2, 3... is the same as the size of the set of all natural even numbers 2, 4, 6..., despite the former containing the latter but not vice-versa... it seems the word "size" -- and associated terminology "larger than", "smaller than", etc. -- is a particularly unhelpful set of words to have chosen for this.
The reason I think this is important is because if you go to e.g. the Wikipedia page for "irrational number", it states in the introduction [1]:
> "As a consequence of Cantor's proof that the real numbers are uncountable and the rationals countable, it follows that almost all real numbers are irrational."
But it seems like an unwarranted leap to go from this formal comparison of cardinality of infinite sets, to the intuitive English-sentence idea that "almost all" real numbers are irrational, as if it had any analogy whatsover to a statement such as e.g. "almost all" values of 1/x are defined.
Am I missing anything here? I've never heard of any natural practical application of this concept, in a way that suggests it's "true" in the same way algebra and calculus are considered to be.
[1] https://en.wikipedia.org/wiki/Irrational_number
The work of Cantor and beyond regarding infinite sets is generally taught as mathematical "fact", as fundamental as 2+2=4, but unlike 2+2=4 is there any practical constraints or applications around it? It seems more like an almost arbitrary puzzle than "fact".
I don't disagree with any of the proofs or reasoning... it just kinda bugs me that the way the formal cardinality of infinite sets is communicated is as the commonsense notion of "size".
When we make statements such as the size of the set of all natural numbers 1, 2, 3... is the same as the size of the set of all natural even numbers 2, 4, 6..., despite the former containing the latter but not vice-versa... it seems the word "size" -- and associated terminology "larger than", "smaller than", etc. -- is a particularly unhelpful set of words to have chosen for this.
The reason I think this is important is because if you go to e.g. the Wikipedia page for "irrational number", it states in the introduction [1]:
> "As a consequence of Cantor's proof that the real numbers are uncountable and the rationals countable, it follows that almost all real numbers are irrational."
But it seems like an unwarranted leap to go from this formal comparison of cardinality of infinite sets, to the intuitive English-sentence idea that "almost all" real numbers are irrational, as if it had any analogy whatsover to a statement such as e.g. "almost all" values of 1/x are defined.
Am I missing anything here? I've never heard of any natural practical application of this concept, in a way that suggests it's "true" in the same way algebra and calculus are considered to be.
[1] https://en.wikipedia.org/wiki/Irrational_number
"The idea of "differently sized infinities" has always felt like a mathematical game to me."
How do you feel about negative numbers?
There is absolutely no way you can have -3 oranges. There are metaphors, and we're all taught what you can do with a negative number, and there are all those lovely proofs of the properties of negative numbers, but you will never see -3 oranges sitting on someone's dining table.
(And I'm not even going to go into the reals---they're just ridiculous.)
The commonsense notion of "size" is one of those metaphors, but it's a good one: for non-infinite sets, the idea of a bijection and the idea that two sets have the same size match exactly. Consider three blocks, one labelled "1", another "2", and a third "3", and three oranges. Block "1" goes with that big, fat orange. Block "2" goes with the smaller orange. And Block "3" goes with the orange that's kind of pear-shaped.
Now, the extension of "size" to infinite sets is a little weird, mostly because infinite sets are very weird. As is the phrase "almost all"; it's not immediately obvious that, because there are more Rs than Ns, that there are a lot more Rs than Ns.
But it's true (in the sense that it's how math works), and you just have to get used to it the same way you got used to -3.
How do you feel about negative numbers?
There is absolutely no way you can have -3 oranges. There are metaphors, and we're all taught what you can do with a negative number, and there are all those lovely proofs of the properties of negative numbers, but you will never see -3 oranges sitting on someone's dining table.
(And I'm not even going to go into the reals---they're just ridiculous.)
The commonsense notion of "size" is one of those metaphors, but it's a good one: for non-infinite sets, the idea of a bijection and the idea that two sets have the same size match exactly. Consider three blocks, one labelled "1", another "2", and a third "3", and three oranges. Block "1" goes with that big, fat orange. Block "2" goes with the smaller orange. And Block "3" goes with the orange that's kind of pear-shaped.
Now, the extension of "size" to infinite sets is a little weird, mostly because infinite sets are very weird. As is the phrase "almost all"; it's not immediately obvious that, because there are more Rs than Ns, that there are a lot more Rs than Ns.
But it's true (in the sense that it's how math works), and you just have to get used to it the same way you got used to -3.
Reminds me of a joke:
A biologist, an engineer and a mathematician see two people enter a seemingly empty building, and a moment later, three people leave.
Biologist: They must have reproduced
Engineer: It must have been a measurement error
Mathematician: If one person enters the building, it will become empty
Biologist: They must have reproduced
Engineer: It must have been a measurement error
Mathematician: If one person enters the building, it will become empty
Negative numbers work just fine for directions. -3 feet west makes plenty of sense, even if -3 oranges doesn't.
Negative numbers work fine for bookkeeping too. You owe someone 3 oranges.
On the other hand double entry was invented so bookkeepers didn't need to deal with negative numbers.
it seems there's a little issue in math, in that the concept and notation often assume enough intuition and imagination from the reader
-3 looks odd if you interpret it as material existence
but as you say, read in bookkeeping context, it's totally natural (npi).
it's a bit like numbers 10 is actually 10 (base 10) but we elude it
-3 looks odd if you interpret it as material existence
but as you say, read in bookkeeping context, it's totally natural (npi).
it's a bit like numbers 10 is actually 10 (base 10) but we elude it
That's one of those metaphors plus what you have been taught about how negative numbers work. It's a product of Cartesian geometry (which had to be invented).
The difference is that negative numbers are 1) practically useful, and 2) extremely interrelated with other useful mathematical concepts. We build up an entire system of real (and even complex) algebra.
While with differently-sized infinite sets, the point is that they aren't (to the best of my knowledge) either 1) directly useful or 2) particularly interrelated with anything else. E.g. they're in addition to the set theory used for real and complex analysis -- not a foundation for it.
And so it seems more apt to put the notion of measuring different "sizes" for infinite sets in the same category of, say, quaternions and sedenions. I don't think too many people would say sedenions are "true", just that they're a construction with certain properties. They're not derived from anything, in the way that negative numbers are derived from inverting addition. Yet math textbooks and courses indeed attempt to present the "sizes" of infinite sets as "true" -- as real as negative numbers -- when I still fail to see how they're anything but a relatively arbitrary curiosity like sedenions.
While with differently-sized infinite sets, the point is that they aren't (to the best of my knowledge) either 1) directly useful or 2) particularly interrelated with anything else. E.g. they're in addition to the set theory used for real and complex analysis -- not a foundation for it.
And so it seems more apt to put the notion of measuring different "sizes" for infinite sets in the same category of, say, quaternions and sedenions. I don't think too many people would say sedenions are "true", just that they're a construction with certain properties. They're not derived from anything, in the way that negative numbers are derived from inverting addition. Yet math textbooks and courses indeed attempt to present the "sizes" of infinite sets as "true" -- as real as negative numbers -- when I still fail to see how they're anything but a relatively arbitrary curiosity like sedenions.
"practically useful"
The Mathematician blinks several times, looking at you as if you'd just grown a third elbow. :-O :-)
The problem is that there's nothing arbitrary about Cantor's work. Now, you could (along with Aristotle, IIRC) just declare "there are no actual infinities, only potential infinities" and thus that the whole investigation is verboten. But that's not very mathy.
Another alternative would be to redefine the fundamentals to outlaw actual infinite sets, but if you do that then you have redo everything, because some of the things that you might consider useful and related to other things go out the window. (Offhand, I think the result would be constructive mathematics. Putting on my computer scientist hat, I'm perfectly happy with constructive math. But most mathematicians aren't really.)
But if you allow infinite sets, then the properties of them, including infinite sets of different sizes, are derived directly from basic set theory. They are as "true" as anything else in math. (I'm a formalist---we're just playing a game that has a specific set of rules. :-))
"Sedenion neural networks provide a means of efficient and compact expression in machine learning applications and were used in solving multiple time series forecasting problems." "Metacognitive Sedenion-Valued Neural Network and its Learning Algorithm" (https://ieeexplore.ieee.org/document/9160921/).
The Mathematician blinks several times, looking at you as if you'd just grown a third elbow. :-O :-)
The problem is that there's nothing arbitrary about Cantor's work. Now, you could (along with Aristotle, IIRC) just declare "there are no actual infinities, only potential infinities" and thus that the whole investigation is verboten. But that's not very mathy.
Another alternative would be to redefine the fundamentals to outlaw actual infinite sets, but if you do that then you have redo everything, because some of the things that you might consider useful and related to other things go out the window. (Offhand, I think the result would be constructive mathematics. Putting on my computer scientist hat, I'm perfectly happy with constructive math. But most mathematicians aren't really.)
But if you allow infinite sets, then the properties of them, including infinite sets of different sizes, are derived directly from basic set theory. They are as "true" as anything else in math. (I'm a formalist---we're just playing a game that has a specific set of rules. :-))
"Sedenion neural networks provide a means of efficient and compact expression in machine learning applications and were used in solving multiple time series forecasting problems." "Metacognitive Sedenion-Valued Neural Network and its Learning Algorithm" (https://ieeexplore.ieee.org/document/9160921/).
> While with differently-sized infinite sets, the point is that they aren't (to the best of my knowledge) either 1) directly useful or 2) particularly interrelated with anything else.
The distinction between countable and uncountable is very practically useful. You can always encode the elements of a countable set such that every element is represented in the computer by a finite-length bit string, but you can never design an encoding that does this for every member of an uncountable set. No exceptions.
In addition, this notion of distinguishing countability from uncountability can be applied to show that the set of Turing machines is countable (up to isomorphism). This immediately informs one of the limits of computation, and why, e.g. trying to design a computer or program that performs exact arithmetic operations on real numbers in general, or say finding the limit of a series in real numbers in general, is as achievable as squaring the circle.
And make no mistake, computational modeling that today already permeates every aspect of society would look very different if exact operations on real numbers were computable and efficient. (and for the general programmer, no need to worry about the imprecision of floats and especially with financial stuff)
The distinction between countable and uncountable is very practically useful. You can always encode the elements of a countable set such that every element is represented in the computer by a finite-length bit string, but you can never design an encoding that does this for every member of an uncountable set. No exceptions.
In addition, this notion of distinguishing countability from uncountability can be applied to show that the set of Turing machines is countable (up to isomorphism). This immediately informs one of the limits of computation, and why, e.g. trying to design a computer or program that performs exact arithmetic operations on real numbers in general, or say finding the limit of a series in real numbers in general, is as achievable as squaring the circle.
And make no mistake, computational modeling that today already permeates every aspect of society would look very different if exact operations on real numbers were computable and efficient. (and for the general programmer, no need to worry about the imprecision of floats and especially with financial stuff)
> While with infinite sets, the point is that they aren't (to the best of my knowledge) either 1) directly useful or 2) particularly interrelated with anything else.
Formal treatments of calculus are based around infinitesimals. Infinitesimals are the same set of ideas about infinite sets, but applied to the spaces between arbitrarily close points.
Specifically formal treatments of calculus work because between any two points there are an infinite number of points and the size of that infinity is the same size as the entire set of real numbers.
At least this is my undergrad level of comprehension. I'm certain there are more exotic treatments, but this is the one that you have to do all the proofs for.
Formal treatments of calculus are based around infinitesimals. Infinitesimals are the same set of ideas about infinite sets, but applied to the spaces between arbitrarily close points.
Specifically formal treatments of calculus work because between any two points there are an infinite number of points and the size of that infinity is the same size as the entire set of real numbers.
At least this is my undergrad level of comprehension. I'm certain there are more exotic treatments, but this is the one that you have to do all the proofs for.
> Formal treatments of calculus are based around infinitesimals
formal treatments of calculus don't use infinitesimals, and analysis using infinitesimals is explicitly separate from traditional analysis
formal treatments of calculus don't use infinitesimals, and analysis using infinitesimals is explicitly separate from traditional analysis
You're absolutely right. I don't know what I was thinking when I wrote this last night.
I meant to say that formal treatments are based around being able to find arbitrarily small neighborhoods around a point, and that this only works when you have something the size of the reals, for which you can find a real-sized space between any two points.
It's this infinite self-similarity at any arbitrarily small scale that is at the heart of calculus.
I meant to say that formal treatments are based around being able to find arbitrarily small neighborhoods around a point, and that this only works when you have something the size of the reals, for which you can find a real-sized space between any two points.
It's this infinite self-similarity at any arbitrarily small scale that is at the heart of calculus.
This is not true. The usual calculus that people learn (and usually learn with rigor in a real analysis course) does not touch infinitesimals.
The approach via infinitesimals is even called "nonstandard analysis".
https://en.wikipedia.org/wiki/Nonstandard_analysis
The approach via infinitesimals is even called "nonstandard analysis".
https://en.wikipedia.org/wiki/Nonstandard_analysis
You're absolutely right. I was going for a different concept. See explanation above. I should stop writing after 02:00.
The problem here is that you're basing your conception of what is "good," "interesting," and "useful" based off of what you might discuss in an undergraduate class in Real or Complex Analysis.
The notion of cardinality and how we can have different "sizes of infinity" is an enormously important and interesting idea that comes up all the time in mathematics.
The notion of cardinality and how we can have different "sizes of infinity" is an enormously important and interesting idea that comes up all the time in mathematics.
How can you say that infinities of different sizes are not useful? All of analysis is built on the fact that R is the unique complete ordered field, and therefore uncountable.
And if you want every infinite set to have size continuum, then N (and so Z and Q) break horribly
And if you want every infinite set to have size continuum, then N (and so Z and Q) break horribly
The field of constructive analysis would beg to differ with you.
An amazing amount of real analysis can be done with absolutely no reference to the excluded middle, completeness axiom, or accepting the existence of uncountable sets.
An amazing amount of real analysis can be done with absolutely no reference to the excluded middle, completeness axiom, or accepting the existence of uncountable sets.
Note: although the phrase “almost all” sounds like an intuitive English-sentence idea, it actually has a very precise mathematical meaning: it means the complement has Lebesgue measure zero.
It sounds like maybe you take issue with this phrase. I kind of think about it probabilistically: if you start uniformly sampling decimal digits 0-9 at random d1,d2,d3,… then the corresponding number
0.d1d2d3…
(with the digits going on forever) will be irrational with probability 1.
It sounds like maybe you take issue with this phrase. I kind of think about it probabilistically: if you start uniformly sampling decimal digits 0-9 at random d1,d2,d3,… then the corresponding number
0.d1d2d3…
(with the digits going on forever) will be irrational with probability 1.
> The work of Cantor and beyond regarding infinite sets is generally taught as mathematical "fact", as fundamental as 2+2=4, but unlike 2+2=4 is there any practical constraints or applications around it?
Yes. There exist libraries that allow us to do arithmetic with arbitrarily large integers with exact precision in a computer, but none that allow us to do arithmetic with arbitrary real numbers. This is because you cannot ever find an encoding that assigns each element of an uncountable set a finite-length string, but you always can find one such for countable sets, no exceptions.
So in practical day-to-day, the programmer (and computational modeller) has to settle for all the quirks of imprecision when dealing with floats, and this imprecision makes a lot of algorithms more complex and limited than the mathematical computation they are trying to model.
Yes. There exist libraries that allow us to do arithmetic with arbitrarily large integers with exact precision in a computer, but none that allow us to do arithmetic with arbitrary real numbers. This is because you cannot ever find an encoding that assigns each element of an uncountable set a finite-length string, but you always can find one such for countable sets, no exceptions.
So in practical day-to-day, the programmer (and computational modeller) has to settle for all the quirks of imprecision when dealing with floats, and this imprecision makes a lot of algorithms more complex and limited than the mathematical computation they are trying to model.
> that allow us to do arithmetic with arbitrary real numbers
Of course there are. You can symbolically encode and manipulate real numbers with exact precision. Sure it might become unwieldy and is fundamentaly constrained by the physical limits of your computer but the same is true with large integers computation.
People don't do it usually because it's useless not because it's impossible. Bounded precision is fine most of the time.
Of course there are. You can symbolically encode and manipulate real numbers with exact precision. Sure it might become unwieldy and is fundamentaly constrained by the physical limits of your computer but the same is true with large integers computation.
People don't do it usually because it's useless not because it's impossible. Bounded precision is fine most of the time.
That doesn’t let you work with arbitrary real numbers because the vast majority of real numbers cannot by symbolicly encoded, even on a turing machine with infinite memory
If they cannot be symbolically encoded why would you ever _need_ to encode them?
Not being able to do something has never stopped people from needing to do it :P
That said, with Google's paper "towards an api for the real numbers", you get close enough for many practical purposes
That said, with Google's paper "towards an api for the real numbers", you get close enough for many practical purposes
> is there any practical constraints or applications around it?
To speak to this question: Suppose you were going to build a calculator program on your computer. You might start with integers and have addition multiplication and subtraction. All perfectly fine. Even if the numbers are very big you can still represent them by using multiple memory slots.
The you add division, and since you don’t want rounding errors in your calculator, you add rational numbers. Can rational numbers still be represented by a computer? Yes, because they are a countable infinity, you can represent them just as easily as you can represent integers.
You would like your calculator to be as complete as possible so you keep adding functions like roots, exp, log, sin, et cetera. But no matter how many functions you add, you’ll never be able to represent every real number. This is useful to know so that nobody ever tries to build a computer that does this.
To speak to this question: Suppose you were going to build a calculator program on your computer. You might start with integers and have addition multiplication and subtraction. All perfectly fine. Even if the numbers are very big you can still represent them by using multiple memory slots.
The you add division, and since you don’t want rounding errors in your calculator, you add rational numbers. Can rational numbers still be represented by a computer? Yes, because they are a countable infinity, you can represent them just as easily as you can represent integers.
You would like your calculator to be as complete as possible so you keep adding functions like roots, exp, log, sin, et cetera. But no matter how many functions you add, you’ll never be able to represent every real number. This is useful to know so that nobody ever tries to build a computer that does this.
> just kinda bugs me that the way the formal cardinality of infinite sets is communicated is as the commonsense notion of "size".
It's not in any place doing maths sensibly.
It's just that both the USA and the UK have a terribly unrigorous way of teaching maths even at university level.
If you take a look at the French Wikipedia article on cardinality, you will see that the world size is never used and the closest thing you will find to it is that cardinality can intuitively be seen as the "number" of elements in a set with actual quotes around. The article then compare multiple very rigorous definitions. I expect a translation of it would be unreadable by most American however. The average French reader will have been exposed to significantly more formal mathematics.
Using the world "size" when talking about infinities is just sloppy.
It's not in any place doing maths sensibly.
It's just that both the USA and the UK have a terribly unrigorous way of teaching maths even at university level.
If you take a look at the French Wikipedia article on cardinality, you will see that the world size is never used and the closest thing you will find to it is that cardinality can intuitively be seen as the "number" of elements in a set with actual quotes around. The article then compare multiple very rigorous definitions. I expect a translation of it would be unreadable by most American however. The average French reader will have been exposed to significantly more formal mathematics.
Using the world "size" when talking about infinities is just sloppy.
Actually the proofs depend on philosophical assumptions that both can and have been questioned. The conclusions likewise.
If you go down that path, then "uncountable" can mean something closer to, "a self-referential tangle is involved" than it does to "more". For example you can't enumerate the reals. But there is a countable list that DOES include every possible real - you just can't always figure out whether things on that list are reals!
See https://news.ycombinator.com/item?id=27847353 for previous discussion on this.
If you go down that path, then "uncountable" can mean something closer to, "a self-referential tangle is involved" than it does to "more". For example you can't enumerate the reals. But there is a countable list that DOES include every possible real - you just can't always figure out whether things on that list are reals!
See https://news.ycombinator.com/item?id=27847353 for previous discussion on this.
> But there is a countable list that DOES include every possible real - you just can't always figure out whether things on that list are reals!
A (hopefully) helpful way to look at it: Cantor's diagonalization argument doesn't work if every function from natural numbers to reals, that includes all reals, is partial. Which, per the halting problem[0], is exactly the behaviour you get if your correspondance function involves doing arbitrary computations decoded from the input natural.
0: The class of propositions "Turing machine #N halts.", in addition to true and false propositions, also contains infinitely many propositions that are neither true nor false[1], so compacting out the non-halting naturals doesn't help.
1: aka infinitely many counterexamples to the axiom of excluded middle
A (hopefully) helpful way to look at it: Cantor's diagonalization argument doesn't work if every function from natural numbers to reals, that includes all reals, is partial. Which, per the halting problem[0], is exactly the behaviour you get if your correspondance function involves doing arbitrary computations decoded from the input natural.
0: The class of propositions "Turing machine #N halts.", in addition to true and false propositions, also contains infinitely many propositions that are neither true nor false[1], so compacting out the non-halting naturals doesn't help.
1: aka infinitely many counterexamples to the axiom of excluded middle
Does that imply that the reals are a subset of a countable list?
Well, not necessarily.
One of the standard constructions of the reals is via sequences of rationals. A sequence of rationals that looks like it should be converging is called a Cauchy sequence. (I'm avoiding the technical definitions, but they are easy to find.) Two Cauchy sequences that look like they are converging to the same thing, are equivalent. And reals are defined as equivalence classes of Cauchy sequences.
This translates pretty well to a constructive approach. For example we can build our mathematics out of things expressible in a programming language. We can define a Cauchy sequence as a function that can be proven by our favorite axiom system to produce a sequence of rationals converging at a specified rate. Again, two functions are equivalent if they can be proven to produce sequences converging to the same thing. We can certainly enumerate all possible programs. But we cannot, thanks to the Halting problem, write a program that is able to select out which possible programs represent reals. Nor can we reliably identify which pairs of programs are equivalent.
So in this construction there is really no actual set of reals that can be identified. Nor can we tell whether a real has been listed already. But there is a countable list that has all possible things that might possibly represent a real. Which will include each real many times.
Does that clarify what I meant by "self-referential tangle"?
One of the standard constructions of the reals is via sequences of rationals. A sequence of rationals that looks like it should be converging is called a Cauchy sequence. (I'm avoiding the technical definitions, but they are easy to find.) Two Cauchy sequences that look like they are converging to the same thing, are equivalent. And reals are defined as equivalence classes of Cauchy sequences.
This translates pretty well to a constructive approach. For example we can build our mathematics out of things expressible in a programming language. We can define a Cauchy sequence as a function that can be proven by our favorite axiom system to produce a sequence of rationals converging at a specified rate. Again, two functions are equivalent if they can be proven to produce sequences converging to the same thing. We can certainly enumerate all possible programs. But we cannot, thanks to the Halting problem, write a program that is able to select out which possible programs represent reals. Nor can we reliably identify which pairs of programs are equivalent.
So in this construction there is really no actual set of reals that can be identified. Nor can we tell whether a real has been listed already. But there is a countable list that has all possible things that might possibly represent a real. Which will include each real many times.
Does that clarify what I meant by "self-referential tangle"?
> But there is a countable list that has all possible things that might possibly represent a real.
Haven't you only demonstrated a countable list of all possible things that might possibly represent a computable number, or some similar concept?
Haven't you only demonstrated a countable list of all possible things that might possibly represent a computable number, or some similar concept?
No, but you may have to put aside some preconceptions to get the point.
https://en.wikipedia.org/wiki/Brouwer%E2%80%93Hilbert_contro... is a good starting point on the historic debate over the philosophy of math.
From within Formalism, which for all intents and purposes won, your characterization is correct. We have the standard reals. And we've constructed a proper subset of the reals.
From within Constructivism, the "standard reals" is a piece of sophistry. It is ridiculous to claim the existence inconceivable infinite swarms of non-existent things whose only claim to "existence" is the sheer multitude of numbers that can never be named or constructed. And therefore the "reals" that I described are a sensible thing to call reals, all of whom have an existence that can be established on reasonable grounds.
From within either philosophy, the other doesn't make much sense. But, in fact, both philosophies are internally consistent, and no logical argument can ever establish one over the other. (In fact, Formalism won because it is more convenient. And for no other reason.)
https://en.wikipedia.org/wiki/Brouwer%E2%80%93Hilbert_contro... is a good starting point on the historic debate over the philosophy of math.
From within Formalism, which for all intents and purposes won, your characterization is correct. We have the standard reals. And we've constructed a proper subset of the reals.
From within Constructivism, the "standard reals" is a piece of sophistry. It is ridiculous to claim the existence inconceivable infinite swarms of non-existent things whose only claim to "existence" is the sheer multitude of numbers that can never be named or constructed. And therefore the "reals" that I described are a sensible thing to call reals, all of whom have an existence that can be established on reasonable grounds.
From within either philosophy, the other doesn't make much sense. But, in fact, both philosophies are internally consistent, and no logical argument can ever establish one over the other. (In fact, Formalism won because it is more convenient. And for no other reason.)
> you may have to put aside some preconceptions to get the point.
"Preconceptions" is a rather unhelpful way to describe the actual situation here, which is you using a different definition for real numbers, that is not even remotely equivalent, without making that clear from the outset.
You said:
> But there is a countable list that DOES include every possible real - you just can't always figure out whether things on that list are reals!
Which is pretty clearly incorrect using the usual definition of real numbers.
The fact that you don't like how real numbers is usually defined is not sufficient justification for you to start confusing a discussion by mixing in your alternative definition without making an explicit distinction.
You've defined a set that can certainly be the subject of interesting investigation, even in a context where the usual definitions about real numbers and uncountable infinities are still accepted. Choosing to inject a naming conflict is counterproductive and suggests you're more concerned with making smug claims about being able to do things mainstream mathematicians consider impossible, rather than having a productive discussion about how to construct most of familiar mathematics without allowing uncountable infinities.
"Preconceptions" is a rather unhelpful way to describe the actual situation here, which is you using a different definition for real numbers, that is not even remotely equivalent, without making that clear from the outset.
You said:
> But there is a countable list that DOES include every possible real - you just can't always figure out whether things on that list are reals!
Which is pretty clearly incorrect using the usual definition of real numbers.
The fact that you don't like how real numbers is usually defined is not sufficient justification for you to start confusing a discussion by mixing in your alternative definition without making an explicit distinction.
You've defined a set that can certainly be the subject of interesting investigation, even in a context where the usual definitions about real numbers and uncountable infinities are still accepted. Choosing to inject a naming conflict is counterproductive and suggests you're more concerned with making smug claims about being able to do things mainstream mathematicians consider impossible, rather than having a productive discussion about how to construct most of familiar mathematics without allowing uncountable infinities.
The name "real numbers" predates the first formal definitions.
The philosophical debate that I pointed to predates the general acceptance of the standardization of the modern definition of the reals.
Now standard definitions literally makes no sense within constructivism. You talk about constructing familiar mathematics, but are using non-constructions that depend on questionable and questioned notions of absolute truth.
What I described is as close to standard mathematics as you can come within a constructivist framework. The tradition of calling such constructions "the real numbers" may be new to you, but is actually over a century old.
The philosophical debate that I pointed to predates the general acceptance of the standardization of the modern definition of the reals.
Now standard definitions literally makes no sense within constructivism. You talk about constructing familiar mathematics, but are using non-constructions that depend on questionable and questioned notions of absolute truth.
What I described is as close to standard mathematics as you can come within a constructivist framework. The tradition of calling such constructions "the real numbers" may be new to you, but is actually over a century old.
I am sure you repeat the same argument with practical application when you go and tell a caveman that the earth is not flat.
> The work of Cantor and beyond regarding infinite sets is generally taught as mathematical "fact", as fundamental as 2+2=4, but unlike 2+2=4 is there any practical constraints or applications around it? It seems more like an almost arbitrary puzzle than "fact".
The field of numerical analysis depends on formal treatments of calculus. Formal treatments of calculus don't work in sets smaller than the reals.
The field of numerical analysis depends on formal treatments of calculus. Formal treatments of calculus don't work in sets smaller than the reals.
When I studied real analysis, I don't recall anything regarding real numbers that seemed to depend on assigning different sizes to infinite sets.
Is there something I'm missing, something that the formal treatment of calculus depends on them for?
Is there something I'm missing, something that the formal treatment of calculus depends on them for?
Dedekind cuts (which are necessary for epsilon-delta proofs) or alternatively Bolzano Weierstrass theorem (if you use sequential convergence definition) imply multiple sizes of infinity, so the logical arrow is in the other direction, roughly: "real analysis implies assigning different sizes to sets", not "assigning different sizes to sets implies real analysis".
It's been a while but iirc there are other constructions (such as p-adic numbers) which create multiple sizes of infinities out of the rationals which aren't real analysis.
It's been a while but iirc there are other constructions (such as p-adic numbers) which create multiple sizes of infinities out of the rationals which aren't real analysis.
The Surreal Numbers are a particularly intuitive sort that create different sizes of infinities. All the ordinals, really. They're isomorphic (in NBG) to a maximal-class hyperreal field of nonstandard analysis.
The following frames Cantor's argument in a more computational way, maybe it is of use:
https://bartoszmilewski.com/2019/11/06/fixed-points-and-diag...
Some of the references found in the above make for interesting reading as well.
https://bartoszmilewski.com/2019/11/06/fixed-points-and-diag...
Some of the references found in the above make for interesting reading as well.
It should be noted that “almost all” is a probability term, meaning that (under a uniform probability measure on the 0-1 interval), the probability that a randomly chosen number is rational is 0. The probability that that a randomly chosen number is irrational is 1.
> The idea of "differently sized infinities" has always felt like a mathematical game to me.
It's a hack. Mathematicians can come up with hacks too.
It's a hack. Mathematicians can come up with hacks too.
> cardinals are mathematical games
Totally agreed, as with 2+2=4. It's an interesting topic in philosophy that we often gloss over because the naturals are exceptionally predictive of so many things in the real world.
> cardinals aren't necessarily commonsense
Maybe. The two notions being applied are (1) that if you just rename everything in your set you haven't changed it's size, and (2) that if all renaming attempts necessarily leave some elements out then the set containing those elements must be bigger. Any "size" capturing those two ideas is equivalent to a renaming of the cardinals.
> naturals vs even naturals
Any topological sort of the infinite subsets of the naturals preserving the set inclusion partial order is going to have some weird oddities. In particular, you'll have a lot of incomparable sets (like the evens and odds, or like all the vertex-deleted N-{x} sets) which are artificially bigger/smaller than each other or artificially the same size, despite the order superficially looking like one based on set inclusion.
> other more commonsense alternatives to cardinals
Even just looking at infinite subsets of the naturals, any ordering you choose must necessarily have the property that there exist infinitely many sizes which each either do not have a next bigger element or do not have a next smaller element. That's a decidedly weird property that doesn't manifest for finite sizes, and it's entirely unavoidable. I'm potentially okay with "size" not being used as the name, but as a counterpoint the motivation is to extend the notion of "size" for finite sets as best as possible.
> cardinals aren't useful
They're often used to prove things that you do use directly. Sometimes those proofs can get convoluted, but a surprisingly effective technique in many domains is just arguing that two sets have different sizes so they can't be the same (or can't map to each other in the desired way or whatever). Cardinalities agree with our intuition about size on finite sets well enough to directly extend to those sorts of proofs. As one example, the math leading up to the fixed point theorems proving the optimal solution to a GAN yields the desired probability distribution is usually done (and originally done iirc) via infinite counting arguments.
I'll be the first to admit that my day-to-day as a programmer doesn't often do much with infinite cardinalities, but given that the mathematical world we've constructed for ourselves happens to often line up nicely with the real world, "mathematical games" that leverage existing intuition to expand our knowledge of that mathematical world still seem valuable.
Totally agreed, as with 2+2=4. It's an interesting topic in philosophy that we often gloss over because the naturals are exceptionally predictive of so many things in the real world.
> cardinals aren't necessarily commonsense
Maybe. The two notions being applied are (1) that if you just rename everything in your set you haven't changed it's size, and (2) that if all renaming attempts necessarily leave some elements out then the set containing those elements must be bigger. Any "size" capturing those two ideas is equivalent to a renaming of the cardinals.
> naturals vs even naturals
Any topological sort of the infinite subsets of the naturals preserving the set inclusion partial order is going to have some weird oddities. In particular, you'll have a lot of incomparable sets (like the evens and odds, or like all the vertex-deleted N-{x} sets) which are artificially bigger/smaller than each other or artificially the same size, despite the order superficially looking like one based on set inclusion.
> other more commonsense alternatives to cardinals
Even just looking at infinite subsets of the naturals, any ordering you choose must necessarily have the property that there exist infinitely many sizes which each either do not have a next bigger element or do not have a next smaller element. That's a decidedly weird property that doesn't manifest for finite sizes, and it's entirely unavoidable. I'm potentially okay with "size" not being used as the name, but as a counterpoint the motivation is to extend the notion of "size" for finite sets as best as possible.
> cardinals aren't useful
They're often used to prove things that you do use directly. Sometimes those proofs can get convoluted, but a surprisingly effective technique in many domains is just arguing that two sets have different sizes so they can't be the same (or can't map to each other in the desired way or whatever). Cardinalities agree with our intuition about size on finite sets well enough to directly extend to those sorts of proofs. As one example, the math leading up to the fixed point theorems proving the optimal solution to a GAN yields the desired probability distribution is usually done (and originally done iirc) via infinite counting arguments.
I'll be the first to admit that my day-to-day as a programmer doesn't often do much with infinite cardinalities, but given that the mathematical world we've constructed for ourselves happens to often line up nicely with the real world, "mathematical games" that leverage existing intuition to expand our knowledge of that mathematical world still seem valuable.
Goodstein's theorem comes with a function on the natural numbers. Whether we can prove that the function works correctly, and indeed whether we can implement the function, depends on how big we allow infinities to be. https://en.wikipedia.org/wiki/Goodstein%27s_theorem#Sequence...
Sorry, that isn't what that link says.
We can implement the function on a Turing machine. Whether we can prove that the function winds up being well-defined depends on which axioms we use. But if you allow transfinite induction up to ε0 (see https://en.wikipedia.org/wiki/Epsilon_numbers_(mathematics)) we can prove that the function works correctly. And this statement can be made without any reference to the size of any uncountable infinities. (Indeed the argument can even be made constructively, within mathematical systems where everything is countable.)
We can implement the function on a Turing machine. Whether we can prove that the function winds up being well-defined depends on which axioms we use. But if you allow transfinite induction up to ε0 (see https://en.wikipedia.org/wiki/Epsilon_numbers_(mathematics)) we can prove that the function works correctly. And this statement can be made without any reference to the size of any uncountable infinities. (Indeed the argument can even be made constructively, within mathematical systems where everything is countable.)
Proof-theoretic ordinal ε₀ isn't sufficient to prove Goodstein's theorem; the entire point is that PA has ε₀ as proof-theoretic ordinal and yet is not able to prove it.
The better point to make in the context of the parent comment is that ω is the first of many transfinite numbers; our ability to talk about multiple numbers "above infinity" is intimately related to the set theory which underlies Cantor's theorems. Infinities aren't just about some sort of mathematical game, but directly influence what we can define and describe.
The better point to make in the context of the parent comment is that ω is the first of many transfinite numbers; our ability to talk about multiple numbers "above infinity" is intimately related to the set theory which underlies Cantor's theorems. Infinities aren't just about some sort of mathematical game, but directly influence what we can define and describe.
The link I gave begs to differ:
The smallest epsilon number ε0 appears in many induction proofs, because for many purposes, transfinite induction is only required up to ε0 (as in Gentzen's consistency proof and the proof of Goodstein's theorem).
If you trace through the sketch of the proof of Goodstein's theorem at https://en.wikipedia.org/wiki/Goodstein%27s_theorem#Proof_of... you can see for yourself that transfinite induction up to ε₀ is indeed sufficient.
As for the rest of your comment, I'm able to talk classical mathematics but my sympathies are firmly Constructivist. So yes, I really do see most discussion of infinities as part of an explicitly meaningless mathematical game known as Formalism.
The smallest epsilon number ε0 appears in many induction proofs, because for many purposes, transfinite induction is only required up to ε0 (as in Gentzen's consistency proof and the proof of Goodstein's theorem).
If you trace through the sketch of the proof of Goodstein's theorem at https://en.wikipedia.org/wiki/Goodstein%27s_theorem#Proof_of... you can see for yourself that transfinite induction up to ε₀ is indeed sufficient.
As for the rest of your comment, I'm able to talk classical mathematics but my sympathies are firmly Constructivist. So yes, I really do see most discussion of infinities as part of an explicitly meaningless mathematical game known as Formalism.
You really don't want to try a Wikipedia slap-fight with me. From my original link, at the very top of the page, in the first paragraph:
> In mathematical logic, Goodstein's theorem is a statement about the natural numbers, proved by Reuben Goodstein in 1944, which states that every Goodstein sequence eventually terminates at 0. Kirby and Paris[1] showed that it is unprovable in Peano arithmetic (but it can be proven in stronger systems, such as second-order arithmetic).
Despite PA having such a big proof-theoretic ordinal, PA cannot prove Goodstein's theorem. We need SOL.
Also, as one constructivist to another: Nobody cares la~ Hopefully you know the difference between PA, which describes NNOs, and HOL, which is ambient in each topos. Just because some topoi have NNO (just because HOL can host PA) and topoi recognize Goodstein's theorem (because Goodstein's provable in HOL) doesn't imply that all NNOs can witness Goodstein.
Indeed, double-check your understanding with the following quirk: In the topos Diff for synthetic differential geometry, the natural numbers are decideable and countable, but the real numbers are not decidable (and in fact prove LEM false!) and uncountable. Due to smoothness requirements, the real numbers are fundamentally different from the natural numbers in Diff. These are two different objects, two different infinities, with two different topologies.
> In mathematical logic, Goodstein's theorem is a statement about the natural numbers, proved by Reuben Goodstein in 1944, which states that every Goodstein sequence eventually terminates at 0. Kirby and Paris[1] showed that it is unprovable in Peano arithmetic (but it can be proven in stronger systems, such as second-order arithmetic).
Despite PA having such a big proof-theoretic ordinal, PA cannot prove Goodstein's theorem. We need SOL.
Also, as one constructivist to another: Nobody cares la~ Hopefully you know the difference between PA, which describes NNOs, and HOL, which is ambient in each topos. Just because some topoi have NNO (just because HOL can host PA) and topoi recognize Goodstein's theorem (because Goodstein's provable in HOL) doesn't imply that all NNOs can witness Goodstein.
Indeed, double-check your understanding with the following quirk: In the topos Diff for synthetic differential geometry, the natural numbers are decideable and countable, but the real numbers are not decidable (and in fact prove LEM false!) and uncountable. Due to smoothness requirements, the real numbers are fundamentally different from the natural numbers in Diff. These are two different objects, two different infinities, with two different topologies.
This seems like just an observation about the less formal nature of colloquial language. We also say things like "70% of people do X", when in actuality the underlying study "extrapolates" from a smaller population via statistical analysis.
All these statements are attempting to do is summarize a more complex/nuanced statement in terms that a lay person can relate to. It could also be that people are deliberately overloading the meaning of the words "size" etc, which is one well known mechanism that cause mutations in languages over time.
All these statements are attempting to do is summarize a more complex/nuanced statement in terms that a lay person can relate to. It could also be that people are deliberately overloading the meaning of the words "size" etc, which is one well known mechanism that cause mutations in languages over time.
>We also say things like "70% of people do X", when in actuality the underlying study "extrapolates" from a smaller population via statistical analysis.
Isn't that approximation because we will never really know how many people exactly do X.
>All these statements are attempting to do is summarize a more complex/nuanced statement in terms that a lay person can relate to. It could also be that people are deliberately overloading the meaning of the words "size" etc, which is one well known mechanism that cause mutations in languages over time.
Are they overloading the meaning of "size" or offloading it? Because again nobody really knows what real size or cardinality of anything is so they offload it to some other future term or meaning just like you said "which is one well known mechanism that cause mutations in languages over time."
I'm not a mathematician but I heard from them say that it is better to use word unbounded than infinite because infinities are tricky.
Isn't that approximation because we will never really know how many people exactly do X.
>All these statements are attempting to do is summarize a more complex/nuanced statement in terms that a lay person can relate to. It could also be that people are deliberately overloading the meaning of the words "size" etc, which is one well known mechanism that cause mutations in languages over time.
Are they overloading the meaning of "size" or offloading it? Because again nobody really knows what real size or cardinality of anything is so they offload it to some other future term or meaning just like you said "which is one well known mechanism that cause mutations in languages over time."
I'm not a mathematician but I heard from them say that it is better to use word unbounded than infinite because infinities are tricky.
Here, terms like "almost all" come to us from measure theory (and its application to probability theory), which tries to define a general notion of the size or volume of sets.
I think the problem is that infinity doesn't exist in real life. We don't have access to unbounded quantities, so any discussion of them is necessarily going to be more abstract than the notions we're used to dealing with.
The results may be unintuitive, but they follow from very intuitive ways of doing counting. Two piles of rocks are the same size if you can line them up so each rock from one pile matches with a rock from the other pile. But once you combine that with mathematical induction, you start getting into the realm of objects that don't exist in real life and it starts looking weird.
I think there's an easy way to draw an analogy between the statements that "almost all" real numbers are irrational and "almost all" values of 1/x are defined. If you were to pick a random real number from the domain of 1/x, the chances of picking one for which 1/x is undefined approaches zero. Similarly, if you pick a random real number, the chances of picking a rational one approaches zero.
The results may be unintuitive, but they follow from very intuitive ways of doing counting. Two piles of rocks are the same size if you can line them up so each rock from one pile matches with a rock from the other pile. But once you combine that with mathematical induction, you start getting into the realm of objects that don't exist in real life and it starts looking weird.
I think there's an easy way to draw an analogy between the statements that "almost all" real numbers are irrational and "almost all" values of 1/x are defined. If you were to pick a random real number from the domain of 1/x, the chances of picking one for which 1/x is undefined approaches zero. Similarly, if you pick a random real number, the chances of picking a rational one approaches zero.
> We don't have access to unbounded quantities, so any discussion of them is necessarily going to be more abstract than the notions we're used to dealing with.
I've always thought of infinite as very concrete unbounded processes, rather than quantities (but then, I'm a computer scientist, not a mathematician).
You cannot count the size of an infinite set because you can never stop counting; the process goes on and on. So the way to compare infinities is to map things between them.
If you can map all elements from the first infinite to the second, but not the other way around, the second is larger than the first. It makes sense as to define this process as the way to compare sizes, since actually counting all their items is ruled out.
"Almost all" elements of an infinite set could be defined similarly, if for each item without a particular property you can create a limitless variety of different items with it.
I've always thought of infinite as very concrete unbounded processes, rather than quantities (but then, I'm a computer scientist, not a mathematician).
You cannot count the size of an infinite set because you can never stop counting; the process goes on and on. So the way to compare infinities is to map things between them.
If you can map all elements from the first infinite to the second, but not the other way around, the second is larger than the first. It makes sense as to define this process as the way to compare sizes, since actually counting all their items is ruled out.
"Almost all" elements of an infinite set could be defined similarly, if for each item without a particular property you can create a limitless variety of different items with it.
> If you can map all elements from the first infinite to the second, but not the other way around, the second is larger than the first.
This seems simple enough but it's still very much counter intuitive when comparing say all the natural numbers with only the even numbers. An intuitive mapping would lead you to think there are more naturals than evens, but math says these two infinites are of the same size.
This seems simple enough but it's still very much counter intuitive when comparing say all the natural numbers with only the even numbers. An intuitive mapping would lead you to think there are more naturals than evens, but math says these two infinites are of the same size.
> When we make statements such as the size of the set of all natural numbers 1, 2, 3... is the same as the size of the set of all natural even numbers 2, 4, 6..., despite the former containing the latter but not vice-versa... it seems the word "size" -- and associated terminology "larger than", "smaller than", etc. -- is a particularly unhelpful set of words to have chosen for this.
It seems to me, when you're counting things, you wouldn't care what are the things you're counting specifically; while in your example it does matter for determining the subset relation. Whatever way of counting where it matters would be kind of weird.
> it seems like an unwarranted leap to go from this formal comparison of cardinality of infinite sets, to the intuitive English-sentence idea that "almost all" real numbers are irrational
But the article uses "almost all" in the formal sense? Which, by the way, also has pretty intuitive meaning, in my opinion.
It seems to me, when you're counting things, you wouldn't care what are the things you're counting specifically; while in your example it does matter for determining the subset relation. Whatever way of counting where it matters would be kind of weird.
> it seems like an unwarranted leap to go from this formal comparison of cardinality of infinite sets, to the intuitive English-sentence idea that "almost all" real numbers are irrational
But the article uses "almost all" in the formal sense? Which, by the way, also has pretty intuitive meaning, in my opinion.
> But the article uses "almost all" in the formal sense? Which, by the way, also has pretty intuitive meaning, in my opinion.
By formal sense, do you mean everywhere but a finite-measure set? Zero-measure?
I'll use finite-measure because it allows for intuitive constructions like "almost all real numbers are outside the closed unit interval 0 <= x <= 1".
But, there are still some constructions that a layperson might expect to hold, like: "almost all real numbers have fractional part < 1e-100", or "almost all positive numbers are of the form x.y with 0.y < 1/x" (thanks, harmonic series).
I think that without formal training, we're especially bad at reasoning about dense sets such as the set of rational numbers, compared to, say, the reals.
By formal sense, do you mean everywhere but a finite-measure set? Zero-measure?
I'll use finite-measure because it allows for intuitive constructions like "almost all real numbers are outside the closed unit interval 0 <= x <= 1".
But, there are still some constructions that a layperson might expect to hold, like: "almost all real numbers have fractional part < 1e-100", or "almost all positive numbers are of the form x.y with 0.y < 1/x" (thanks, harmonic series).
I think that without formal training, we're especially bad at reasoning about dense sets such as the set of rational numbers, compared to, say, the reals.
> ... intuitive constructions like "almost all real numbers are outside the closed unit interval 0 <= x <= 1".
But that would be wrong wouldn't it? I can produce all real numbers by pairing a finite number of (in this case 3) real numbers outside the set with each real number inside the set.
For each real x, in 0 <= x <= 1, we also have:
1/x (covers all real x, 1 <= x <= +infinity
-x (covers all real x, -1 <= x <= 0
-1/x (covers all real x, -infinity <= x <= -1)
The cardinality of all those reals outside of 0 <= x <= 1 is therefore 3x the cardinality of those inside 0 <= x <= 1, in this construction. But for infinite cardinalities the 3 can be discarded.
So there are exactly as many real numbers in 0 <= x <= -1 as outside it.
But that would be wrong wouldn't it? I can produce all real numbers by pairing a finite number of (in this case 3) real numbers outside the set with each real number inside the set.
For each real x, in 0 <= x <= 1, we also have:
1/x (covers all real x, 1 <= x <= +infinity
-x (covers all real x, -1 <= x <= 0
-1/x (covers all real x, -infinity <= x <= -1)
The cardinality of all those reals outside of 0 <= x <= 1 is therefore 3x the cardinality of those inside 0 <= x <= 1, in this construction. But for infinite cardinalities the 3 can be discarded.
So there are exactly as many real numbers in 0 <= x <= -1 as outside it.
I don't disagree that these sets are the same cardinality. But cardinality isn't the only way to describe the "size" of a set.
I suppose the typical measure-theoretic definition of "almost all" / "almost everywhere" insists on "everywhere but a zero-measure set", and you can't define a measure that satisfies sigma-additivity that treats intervals of finite Lebesgue measure as such, while ascribing nonzero measure to sets of infinite measure.
But even so, the Lebesgue measure of R is infinite, while the same measure of the unit interval is 1.
I suppose the typical measure-theoretic definition of "almost all" / "almost everywhere" insists on "everywhere but a zero-measure set", and you can't define a measure that satisfies sigma-additivity that treats intervals of finite Lebesgue measure as such, while ascribing nonzero measure to sets of infinite measure.
But even so, the Lebesgue measure of R is infinite, while the same measure of the unit interval is 1.
I think so?
If I do it the "normal" way (repeating the [0, 1] interval infinitely many times), there are infinite times as many reals outside the [0, 1] interval as there are in it.
But that "infinite times" is a countable infinity - the number of integers. How does "the number of reals in [0, 1] times the number of integers" compare to "the number of reals in [0, 1]"? Are they the "same" infinity?
What if we use rationals instead of reals? We can do the same x 3 thing, right? But the number of rationals is countably infinite, and "3 times countably infinite" is the same as "countably infinite times countably infinite", isn't it?
If I do it the "normal" way (repeating the [0, 1] interval infinitely many times), there are infinite times as many reals outside the [0, 1] interval as there are in it.
But that "infinite times" is a countable infinity - the number of integers. How does "the number of reals in [0, 1] times the number of integers" compare to "the number of reals in [0, 1]"? Are they the "same" infinity?
What if we use rationals instead of reals? We can do the same x 3 thing, right? But the number of rationals is countably infinite, and "3 times countably infinite" is the same as "countably infinite times countably infinite", isn't it?
Maybe not the most formal of meanings, but my favorite is a probabilistic one: given a random element, how likely it is that it satisfies a predicate? If some elements don't, but it's still satisfied with probability 1, that's pretty clearly almost always.
EDIT: yeah you guys are right, I wouldn't worry too much about the prior not being a proper distribution, but still - this doesn't seem related to the cardinality of sets in a simple way after all!
EDIT: yeah you guys are right, I wouldn't worry too much about the prior not being a proper distribution, but still - this doesn't seem related to the cardinality of sets in a simple way after all!
I think for infinitely sized sets this isn't so simple.
For instance, what is the random distribution you are using to select from a set of infinite numbers?
The cardinality of any two intervals of real numbers is the same, regardless of the lengths of the intervals.
For instance, what is the random distribution you are using to select from a set of infinite numbers?
The cardinality of any two intervals of real numbers is the same, regardless of the lengths of the intervals.
Random according to what distribution?
The probability distribution that we all want to define on the real numbers does not exist. And this has non-trivial consequences.
The probability distribution that we all want to define on the real numbers does not exist. And this has non-trivial consequences.
[deleted]
If you are referring to a measure then 'almost all' pretty much exclusively means every except for a zero-measure set. I've never encountered another definition when dealing with measures.
I agree!
But consider a different, entirely valid context of "almost all":
"Almost all natural numbers are greater than 10."
"Almost all prime numbers are odd."
If we wanted to extend this intuitively, we might want to support the statement that "almost all positive reals are greater than 10". One option of doing that is by using the nonstandard definition of "everywhere but on a finite-measure set".
But consider a different, entirely valid context of "almost all":
"Almost all natural numbers are greater than 10."
"Almost all prime numbers are odd."
If we wanted to extend this intuitively, we might want to support the statement that "almost all positive reals are greater than 10". One option of doing that is by using the nonstandard definition of "everywhere but on a finite-measure set".
Is the meaning unintuitive, or is it in fact simply that the world doesn't match your intuitions?
'cos I mean, I'm not a betting man, but "I bet mathematical facts are correct despite being unintuitive" makes my (winning, profitable) bet in December 2020 that Trump lost look like a true gamble by comparison.
'cos I mean, I'm not a betting man, but "I bet mathematical facts are correct despite being unintuitive" makes my (winning, profitable) bet in December 2020 that Trump lost look like a true gamble by comparison.
> But it seems like an unwarranted leap to go from this formal comparison of cardinality of infinite sets, to the intuitive English-sentence idea that "almost all" real numbers are irrational, as if it had any analogy whatsover to a statement such as e.g. "almost all" values of 1/x are defined.
What's the objection? Almost all values of 1/x are defined. The analogy is... it's the same usage with the same meaning. That's not even an analogy.
What's the objection? Almost all values of 1/x are defined. The analogy is... it's the same usage with the same meaning. That's not even an analogy.
Almost none of the numbers of the form 1/x have definitions. Definitions have finite length, so there is only a countable number of numbers with definitions. But there are uncountable number of numbers of the form 1/x.
Please note, the statement "almost all reals are not rational" has nothing to do with cardinality.
It has to do with the fact that we can construct an open set of arbitrarily small size that includes every rational.
It has to do with the fact that we can construct an open set of arbitrarily small size that includes every rational.
"Arbitrarily small size" and "nothing to do with cardinality" are confusing me.
For "nothing to do with cardinality", the Cantor set has the same cardinality as the reals, and yet has measure zero.
For arbitrarily small size, let's start with an enumeration of the rationals. Now pick ε > 0. Let's put an open interval of size ε/2 around the first rational, ε/4 around the second, ε/8 around the third and so on. The union of those intervals is an open set of length bounded above by ε/2 + ε/4 + ε/8 + ... = ε. (Note, it is actually smaller than this because some of the intervals overlap...)
That constructs an open set, which includes every rational, of size as small as we like.
So "cardinality" and "the measure of a set" have no particular relationship, other than that the measure of a countable set is always 0.
For arbitrarily small size, let's start with an enumeration of the rationals. Now pick ε > 0. Let's put an open interval of size ε/2 around the first rational, ε/4 around the second, ε/8 around the third and so on. The union of those intervals is an open set of length bounded above by ε/2 + ε/4 + ε/8 + ... = ε. (Note, it is actually smaller than this because some of the intervals overlap...)
That constructs an open set, which includes every rational, of size as small as we like.
So "cardinality" and "the measure of a set" have no particular relationship, other than that the measure of a countable set is always 0.
A statement is true of 'almost all' x in the set X if, when sampling from X, the probability that the statement will be true of the value you sample is exactly 1.
If you think there's a conflict between "arbitrarily small size" and "nothing to do with cardinality", there isn't; this is a different kind of size.
(OK, there is a relationship to cardinality, but two sets of the same cardinality can be different sizes by this metric, and two sets of the same size can have different cardinalities.)
If you think there's a conflict between "arbitrarily small size" and "nothing to do with cardinality", there isn't; this is a different kind of size.
(OK, there is a relationship to cardinality, but two sets of the same cardinality can be different sizes by this metric, and two sets of the same size can have different cardinalities.)
No, it's an entirely different meaning.
Because yes, almost all values of 1/x are defined -- for every real value of x except for one, the number zero.
While saying "almost all" real numbers are irrational... is saying that real values are all irrational, except for... the entire infinitely large set of rational numbers.
The idea of "almost all" and "except for an infinite number of items" is not even close to the same commonsense meaning, not even remotely.
That's my whole point -- that meanings are being mixed up, that this way of classifying infinite sets shouldn't be conceptualized as "size" at all because the analogies break down, well, instantly.
Because yes, almost all values of 1/x are defined -- for every real value of x except for one, the number zero.
While saying "almost all" real numbers are irrational... is saying that real values are all irrational, except for... the entire infinitely large set of rational numbers.
The idea of "almost all" and "except for an infinite number of items" is not even close to the same commonsense meaning, not even remotely.
That's my whole point -- that meanings are being mixed up, that this way of classifying infinite sets shouldn't be conceptualized as "size" at all because the analogies break down, well, instantly.
> While saying "almost all" real numbers are irrational... is saying that real values are all irrational, except for... the entire infinitely large set of rational numbers.
You're claiming that the precise mathematical definitions of these terms are ridiculous, and then just repeating those mathematical definitions of the terms to support your claim.
> That's my whole point -- that meanings are being mixed up, that this way of classifying infinite sets shouldn't be conceptualized as "size" at all because the analogies break down, well, instantly.
The whole point is that when you're comparing infinite sets, common sense terms like "size," "almost all," etc. don't make any sense at all, so mathematicians create precise definitions for the terms that are then used among all mathematicians and do make sense. These terms are common among mathematicians and they do make sense.
The fact that these definitions don't precisely match the definitions used by non-mathematicians is precisely the goal, because those definitions make no sense whatsoever when referring to infinite sets. It's okay to complain about using jargon in discussions not related to mathematics, although that's not what is happening here (and it's difficult to imagine a conversation about infinite sets that is not also about mathematics). This complaint is comparable to complaining that the definitions of "sharp" and "flat" in music theory don't at all match the definitions of "sharp" and "flat" used in conversations not about music.
I suppose another way to approach this is to ask what you would propose the term "almost all" to mean when referring to an infinite set? For that matter, what do you propose that the term "almost all" means to a layperson referring to small finite sets? What percentage do you need in order to use "almost all"?
You're claiming that the precise mathematical definitions of these terms are ridiculous, and then just repeating those mathematical definitions of the terms to support your claim.
> That's my whole point -- that meanings are being mixed up, that this way of classifying infinite sets shouldn't be conceptualized as "size" at all because the analogies break down, well, instantly.
The whole point is that when you're comparing infinite sets, common sense terms like "size," "almost all," etc. don't make any sense at all, so mathematicians create precise definitions for the terms that are then used among all mathematicians and do make sense. These terms are common among mathematicians and they do make sense.
The fact that these definitions don't precisely match the definitions used by non-mathematicians is precisely the goal, because those definitions make no sense whatsoever when referring to infinite sets. It's okay to complain about using jargon in discussions not related to mathematics, although that's not what is happening here (and it's difficult to imagine a conversation about infinite sets that is not also about mathematics). This complaint is comparable to complaining that the definitions of "sharp" and "flat" in music theory don't at all match the definitions of "sharp" and "flat" used in conversations not about music.
I suppose another way to approach this is to ask what you would propose the term "almost all" to mean when referring to an infinite set? For that matter, what do you propose that the term "almost all" means to a layperson referring to small finite sets? What percentage do you need in order to use "almost all"?
Mathematics is a language unto itself, and some concepts are more difficult to map to natural language than others. Even if you had a much broader English vocabulary, with unique words assigned to every currently known mathematical abstraction, the intuitive sense in which we speak and read and understand will clash with the behavior and features of mathematical symbols.
Natural language maps onto an embodied experience designed by evolution. Math transcends what our brains are built to expect and predict. Infinities, exponentials, quantum entanglement, and an infinite array of other very real things simply exist outside what we are capable of understanding intuitively, without some special conjunction of neural wiring, training, or happenstance.
The nature of infinities might seem like navel gazing, but it helps us understand the features of different types of numbers, and those are the building blocks of proofs. Knowing to which infinity class a number belongs might help inform the optimization of real world engineering of chips or data storage, or drug design algorithms, and so on. It could eventually be part of figuring out practical quantum computers, solving p vs np, or maybe just a piece of a better factorization algorithm that improves cryptography.
Natural language maps onto an embodied experience designed by evolution. Math transcends what our brains are built to expect and predict. Infinities, exponentials, quantum entanglement, and an infinite array of other very real things simply exist outside what we are capable of understanding intuitively, without some special conjunction of neural wiring, training, or happenstance.
The nature of infinities might seem like navel gazing, but it helps us understand the features of different types of numbers, and those are the building blocks of proofs. Knowing to which infinity class a number belongs might help inform the optimization of real world engineering of chips or data storage, or drug design algorithms, and so on. It could eventually be part of figuring out practical quantum computers, solving p vs np, or maybe just a piece of a better factorization algorithm that improves cryptography.
I could also mathematically say that "almost all" integers are not powers of 58279. I think that would fit the commonsense meaning, even though there are infinite counterexamples.
It's because they kinda follow the same rules as finitely sized sets. Say you have two sets: A and B. A has five elements and B has seven. That means that for each element in A there is a unique corresponding element in B, but the reverse is not true: B has elements that do not map to elements in A. OK, now say A is the set of integers, and B is the set of points on the x-axis. Same deal applies, you can map every integer to a point on the x-axis and still have points on the x-axis that do not map to integers. So we've formalized infinite sets in a way that preserves our intuitive notion of what it means to have more or less of something, without having to count or measure the sets which would be bloody impossible! Yes, it's a game but so is all of math!
As for "almost all", in statistics we have this notion of "almost surely", which is formally defined as "with probability 1". It turns out that a probability of 1 doesn't guarantee that something will happen, because 1 less an infinitesimal is still 1! So roll a spherical die that yields a real number between 0 and 1; if you roll a 0, you lose. The probability that you will win is still 1, but you might still roll that goose egg! So we say that you will "almost surely" win at this game.
If you think of rational and real numbers in terms of our two sets with different cardinalities, not only is there a real number for every rational number (because the rationals are a subset of the reals), but you can map an infinite number of real numbers to each rational number! Take your pencil and put a dot on a random point on the x-axis; you might hit a point whose coordinate is a rational number, but your chances of doing so are infinitesimal! Therefore, in a formal probabilistic sense, you will "almost surely" choose a point with an irrational coordinate. Therefore, we say that "almost all" the real numbers are irrational.
As for "almost all", in statistics we have this notion of "almost surely", which is formally defined as "with probability 1". It turns out that a probability of 1 doesn't guarantee that something will happen, because 1 less an infinitesimal is still 1! So roll a spherical die that yields a real number between 0 and 1; if you roll a 0, you lose. The probability that you will win is still 1, but you might still roll that goose egg! So we say that you will "almost surely" win at this game.
If you think of rational and real numbers in terms of our two sets with different cardinalities, not only is there a real number for every rational number (because the rationals are a subset of the reals), but you can map an infinite number of real numbers to each rational number! Take your pencil and put a dot on a random point on the x-axis; you might hit a point whose coordinate is a rational number, but your chances of doing so are infinitesimal! Therefore, in a formal probabilistic sense, you will "almost surely" choose a point with an irrational coordinate. Therefore, we say that "almost all" the real numbers are irrational.
> Take your pencil and put a dot on a random point on the x-axis; you might hit a point whose coordinate is a rational number, but your chances of doing so are infinitesimal!
But see, that's precisely the kind of intution I'm arguing against -- the kind of "analogy" that seems indefensible to me.
After all, I can select any pixel from an infinitely zoomable number line on my computer and it will always be rational, every time. Or any measurement you take of a pencil on paper will always be bounded by two rational numbers measured by counting off ticks on a ruler, and unknown within that. One could argue it's impossible to even define what it means to point with a pencil to an irrational number on a straight line. What does it even mean to select a value randomly from multiple infinite sets? And if you define that in some particular way, how do you justify that a pencil could ever do that on paper?
I understand perfectly everything you describe about mapping -- I'm familiar with the math. It just seems misguided and potentially dangerous to me to draw any practical comparisons to it, such as your pencil-and-paper one, because they seem to break down instantly.
But see, that's precisely the kind of intution I'm arguing against -- the kind of "analogy" that seems indefensible to me.
After all, I can select any pixel from an infinitely zoomable number line on my computer and it will always be rational, every time. Or any measurement you take of a pencil on paper will always be bounded by two rational numbers measured by counting off ticks on a ruler, and unknown within that. One could argue it's impossible to even define what it means to point with a pencil to an irrational number on a straight line. What does it even mean to select a value randomly from multiple infinite sets? And if you define that in some particular way, how do you justify that a pencil could ever do that on paper?
I understand perfectly everything you describe about mapping -- I'm familiar with the math. It just seems misguided and potentially dangerous to me to draw any practical comparisons to it, such as your pencil-and-paper one, because they seem to break down instantly.
"Bigger" is poor wording when discussing cardinality.
I can see other comments here are struggling with this. Cardinality should not be thought of as "size." Cardinality is purely a functional property. If you can define a bijective function between two sets, then they have the same cardinality. If you can't, then you take the set which has all of its elements paired, place it before the set that has unpaired elements, and there you go, you've defined a partial order over all possible sets, including infinite sets.
But it doesn't really match what we usually mean by "size." The size of a set is more properly associated with measure. This is why we rely on measure to coherently formalize continuous probability. The sets (0, 0.1) and (0, 0.9) have exactly the same cardinality, but the latter has greater measure, which is why we can say an event space defined by the latter is more probable than one defined by the former. Both event spaces are infinite, but one is "bigger" than the other, in this case in a way that captures intuition about size much better than cardinality does.
I can see other comments here are struggling with this. Cardinality should not be thought of as "size." Cardinality is purely a functional property. If you can define a bijective function between two sets, then they have the same cardinality. If you can't, then you take the set which has all of its elements paired, place it before the set that has unpaired elements, and there you go, you've defined a partial order over all possible sets, including infinite sets.
But it doesn't really match what we usually mean by "size." The size of a set is more properly associated with measure. This is why we rely on measure to coherently formalize continuous probability. The sets (0, 0.1) and (0, 0.9) have exactly the same cardinality, but the latter has greater measure, which is why we can say an event space defined by the latter is more probable than one defined by the former. Both event spaces are infinite, but one is "bigger" than the other, in this case in a way that captures intuition about size much better than cardinality does.
One can define an order relation using cardinality. Cardinality does capture a notion of size of sets that corresponds to intuition for finite sets and captures the idea of one infinite set being “smaller” or the same size as another.
In general sets don’t have a measure on them in the sense of measure theory. Indeed, assuming the Axiom of Choice there are non measurable sets of the real numbers. But every set has a cardinality. And there is a well defined linear order of the hierarchy of cardinal numbers. I’m assuming the axiom of choice.
In general sets don’t have a measure on them in the sense of measure theory. Indeed, assuming the Axiom of Choice there are non measurable sets of the real numbers. But every set has a cardinality. And there is a well defined linear order of the hierarchy of cardinal numbers. I’m assuming the axiom of choice.
> Cardinality is purely a functional property.
Is something like "granularity" an appropriate intuition? Both sets are of infinite size, but one has more points with which to take measurements against than the other. It isn't "bigger" so much as it is "finer?"
Is something like "granularity" an appropriate intuition? Both sets are of infinite size, but one has more points with which to take measurements against than the other. It isn't "bigger" so much as it is "finer?"
But this breaks when you compare say, the set of integers vs the set of prime numbers or the set of powers of 2. The intuition say naturals are more granular and the others more sparse, but they are infinites of the same size...
If you were hoping to make size more intuitive by using measures then immeasurable sets kind of pose a problem. With Banach-Tarski as the ultimate example.
"a subset of the x-y plane with a large cardinality need be neither measurable nor of large measure. For example, the entire plane with its 2^ℵ0 elements has an infinite measure."
This should be ℵ0^2, since we are talking about plane defined by two axes, x * y, each with measure ℵ0, so the measure becomes ℵ0 * ℵ0 = ℵ0^2, which is the same as ℵ0, right?
Edit: maybe they don't mean elements as points in plane, but subsets of the plane, in which case the statement would apply?
This should be ℵ0^2, since we are talking about plane defined by two axes, x * y, each with measure ℵ0, so the measure becomes ℵ0 * ℵ0 = ℵ0^2, which is the same as ℵ0, right?
Edit: maybe they don't mean elements as points in plane, but subsets of the plane, in which case the statement would apply?
No, they really did mean 2^ℵ0. Note the earlier sentence
“The set ℝ of real numbers (also called the real line) is as large as the power set of ℕ, and this cardinality is denoted 2^ℵ0, or “continuum.””
So the x-y plane has cardinality 2^ℵ0 * 2^ℵ0 = 2^ℵ0.
“The set ℝ of real numbers (also called the real line) is as large as the power set of ℕ, and this cardinality is denoted 2^ℵ0, or “continuum.””
So the x-y plane has cardinality 2^ℵ0 * 2^ℵ0 = 2^ℵ0.
Ah, indeed. Thanks for the correction. I read there, for some reason, an implication that a plane would have a larger cardinality than a line, which isn't true. But indeed, both are 2^ℵ0.
Ah, sweet memories of discrete math.
This feels really arbitrary to me, I am more found to think that exist two additional disjoint categories just unbounded and bounded, and we can have unbounded countable sets and bounded countable sets, and an order relation between the cardinalities of unbounded countable sets just don't exist, it doesn't make any logical sense. In which point you stop walking both sets to compare their size?
You don't actually walk the sets to compare their sizes. You establish a 1-1 relationship between their elements.
Take the natural numbers 0,1,2,3... (call that N) and the even counting numbers 0,2,4,6... (call that E).
Here's a function between N -> E: f(n) = n * 2. You can prove that f maps every element of N to an element of E, and that every element of E is mappable from an element of N. f is 1-1. And therefore, N and E are the same "size".
Take the natural numbers 0,1,2,3... (call that N) and the even counting numbers 0,2,4,6... (call that E).
Here's a function between N -> E: f(n) = n * 2. You can prove that f maps every element of N to an element of E, and that every element of E is mappable from an element of N. f is 1-1. And therefore, N and E are the same "size".
An integral can be used to find the area under a curve by summing infinitesimally small areas.
The point isn't to walk to the end of the infinity. It's to use it as a tool to calculate something in a different or previously impossible way.
All tools are arbitrary without an application. But sometimes you have to figure out what's possible before you can try to find an application.
The point isn't to walk to the end of the infinity. It's to use it as a tool to calculate something in a different or previously impossible way.
All tools are arbitrary without an application. But sometimes you have to figure out what's possible before you can try to find an application.
That's one interpretation but it's kind of shaky without a theory of infinitesimals, and when you do work with a theory of infinitesimals it turns out not to be all that much better than working with the more traditional delta/epsilon approach, which is really quite rigorous and can be explained without the use of any infinities.
The fallacy of Cantor (and his supporters such as Hilbert) lies in mixing the mathematical logic which is meaningful only for finite numbers, with the infinity as if it were a number that obeys comparison operations such as bigger, smaller etc. Almost anything can be proved/disproved or debated when one assumes such validity of the logical concepts to infinity.
The acceptance of multiple infinities and some concepts around continuum (Dedekind cuts etc) are questionable due to this assumption.
The acceptance of multiple infinities and some concepts around continuum (Dedekind cuts etc) are questionable due to this assumption.
I don't think there's any confusion of the finite and infinite numbers in Cantor's diagonalization argument. Here's the most generic form of Cantor's argument: there is no surjective function from a set A to its power set P(A).
We prove this by contradiction. Consider any function f: A -> P(A) , i.e. it takes elements of A and outputs subsets of A. Suppose this function is surjective: i.e. for all y in P(A) there is some x in A such that f(x) = y. But let q = { a in A | a is not in f(a) }. Clearly this is a valid set. And if f is surjective, there must be some x in A such that f(x) = q. Is x in q? If x were in q, then x would be in f(x), so that's a contradiction. If x were not in q, then by the definition of q x would be in q, which is also a contradiction. Thus we have a contradiction, so f cannot be surjective.
As you can see, nowhere do we make any logical jumps that would only make sense in the case of finite sets. This proof is as straightforward as the proof that there is no set of all sets. We don't use the axiom of choice, the argument is even valid in constructive mathematics (though you have to make some adjustments).
Now, we define one set X as being "less than" another set Y if and only if there is no surjective function from X to Y. You'll see that this definition corresponds exactly to the usual notions of size for finite sets, and makes intuitive sense (if for every y we have an x, there must be at least as many xs as ys). Now, just plug in the set of natural numbers into Cantor's theorem and you get: the power set of natural numbers is larger than the set of natural numbers.
We prove this by contradiction. Consider any function f: A -> P(A) , i.e. it takes elements of A and outputs subsets of A. Suppose this function is surjective: i.e. for all y in P(A) there is some x in A such that f(x) = y. But let q = { a in A | a is not in f(a) }. Clearly this is a valid set. And if f is surjective, there must be some x in A such that f(x) = q. Is x in q? If x were in q, then x would be in f(x), so that's a contradiction. If x were not in q, then by the definition of q x would be in q, which is also a contradiction. Thus we have a contradiction, so f cannot be surjective.
As you can see, nowhere do we make any logical jumps that would only make sense in the case of finite sets. This proof is as straightforward as the proof that there is no set of all sets. We don't use the axiom of choice, the argument is even valid in constructive mathematics (though you have to make some adjustments).
Now, we define one set X as being "less than" another set Y if and only if there is no surjective function from X to Y. You'll see that this definition corresponds exactly to the usual notions of size for finite sets, and makes intuitive sense (if for every y we have an x, there must be at least as many xs as ys). Now, just plug in the set of natural numbers into Cantor's theorem and you get: the power set of natural numbers is larger than the set of natural numbers.
If you are counting a set, you necessarily are creating a map between the item of the set you are counting and the natural numbers, this is basics, how come that you can say such statement about the sizes of power set of natural number and natural number?, from where the notion of the cardinality comes if not from counting, and counting implies a map to a natural number, so the set of natural number is bigger than its selves?
Cardinality doesn't have to do with "counting" necessarily. Two sets X and Y are said to have the same cardinality if there is a function f : X -> Y where f is a bijection. By bijection we mean it has two properties: that for all a,b in X, if f(a) = f(b), then a = b (this is also called the injective property), and for all c in Y, there is some d in X such that f(d) = c (this is called the surjective property). Set X has cardinality less than Y if there is no such bijective function, but there is a function f: X -> Y that is injective. Conversely, X has cardinality larger than Y if there is no such bijective function, but there is a function f: X -> Y that is surjective. All you have to do to compare the size of two sets is to look at the functions mapping one to the other. No "counting" involved.
This make much more sense, so most time the cardinality which people refer is with respect to the set of natural numbers, but according to you, we can have this relation between any two sets. The problem is not make those things clear in the wording. Why not just called it "the cardinality order relation", and try it always like a binary relation, instead of a property that each set has in insolation.
Well you can use this relationship to establish the cardinal numbers. You can use "there exists a bijective function between sets X and Y" as an equivalence relation between sets. And with a equivalence relation you can talk about partitioning things into their equivalence classes. But because we are talking about a relationship between all sets it gets tricky to formally construct things (because there is no set of all sets for you to use to define things, so you can't just say "take the sets under the equivalence relations"). There are multiple ways to explicitly construct them, but they tend to be pretty complicated compared to just talking about bijections. The constructions I know about either require the axiom of choice or the axiom of regularity (every non-empty set A contains an element that is disjoint from A). But you don't need any of that to establish a lot of the properties of cardinalities
It is possible to make a set that contains all the set except itself, operationally this pretty simple, I am working on creating a language programming based on set theory, so this will be an easy way to define some notion of universal set.
fn contain(u0:(universal, set), u1:(universal, set)){ return false }
fn contain(u:(universal, set), s:set){ return true }
but don't how much logical sense it will make
fn contain(u0:(universal, set), u1:(universal, set)){ return false }
fn contain(u:(universal, set), s:set){ return true }
but don't how much logical sense it will make
Unfortunately the set that contains all sets except itself doesn't exist either. If such a set X existed, then you could easily build X unioned with {X}, which would be the set of all sets, which doesn't exist. You can't really avoid Russel's paradox, it prevents you from being able to make a set that is basically all sets, minus some exceptions.
But there is a way to get around Russel's paradox, the standard way is to define a new kind of object called a class. See https://en.wikipedia.org/wiki/Class_(set_theory) . Basically a class is like a set, a set can be a member of a class, and you can do most operations with sets on classes as well (union, intersection, etc). And you can create a class which is all sets satisfying some property. From this you can't have a set of all sets, but you can have a class of all sets. Russel's paradox doesn't go away, you still can't have the set of all sets (and you can't have the class of all classes), but this still gives you enough to talk about properties of all sets. See https://en.wikipedia.org/wiki/Von_Neumann%E2%80%93Bernays%E2... for an example of how to define classes. That particular example is a conservative extension of ZFC: any statement about sets that can be proved using NBG can also be proved using ZFC and vice versa (assuming ZFC is consistent). Your statement can't involve classes, because there is no definition of classes in ZFC so it wouldn't translate, but your proof in the NBG system can make use of it
But there is a way to get around Russel's paradox, the standard way is to define a new kind of object called a class. See https://en.wikipedia.org/wiki/Class_(set_theory) . Basically a class is like a set, a set can be a member of a class, and you can do most operations with sets on classes as well (union, intersection, etc). And you can create a class which is all sets satisfying some property. From this you can't have a set of all sets, but you can have a class of all sets. Russel's paradox doesn't go away, you still can't have the set of all sets (and you can't have the class of all classes), but this still gives you enough to talk about properties of all sets. See https://en.wikipedia.org/wiki/Von_Neumann%E2%80%93Bernays%E2... for an example of how to define classes. That particular example is a conservative extension of ZFC: any statement about sets that can be proved using NBG can also be proved using ZFC and vice versa (assuming ZFC is consistent). Your statement can't involve classes, because there is no definition of classes in ZFC so it wouldn't translate, but your proof in the NBG system can make use of it
If you aren’t aware of it already, you might be interested to read about Russell’s paradox [1] which shows a problem with allowing sets to be defined into existence without restriction (making Frege’s life’s work the Grundgesetze stillborn). It involves using the “set” of all things that are not a member of themselves.
[1] https://en.m.wikipedia.org/wiki/Russell's_paradox
[1] https://en.m.wikipedia.org/wiki/Russell's_paradox
Typically, unless you specify the other set, it's assumed to be N, the natural numbers. And when you have a bijection between some other set and (some subset of) the natural numbers, you're doing something equivalent to counting.
> You'll see that this definition corresponds exactly to the usual notions of size for finite sets, and makes intuitive sense.
This has always been my problem with the idea of some infinities being "bigger" than others. This definition does not correspond to the usual notion of size for finite sets, because finite sets actually have size. So rather than making "intuitive sense", it makes no sense (to me).
Having no surjective function from one set to another makes sense, but defining one set necessarily as "less than" the other does not, as the word "less" cannot, in such a context, mean what its definition implies.
> (if for every y we have an x, there must be at least as many xs as ys)
The lack of a surjective function does not mean that we cannot have an X for every Y, it just means we can't map an X for every Y with a surjective function. It doesn't mean a pairing cannot exist (at least not abstractly, which is how all infinite sets exist anyway). The pairing can simply be random and undefinable. There, now a pairing exists and both sets are the same "size". (It's not a surjective function, but if the point is simply to compare "sizes", then what does it matter?)
This has always been my problem with the idea of some infinities being "bigger" than others. This definition does not correspond to the usual notion of size for finite sets, because finite sets actually have size. So rather than making "intuitive sense", it makes no sense (to me).
Having no surjective function from one set to another makes sense, but defining one set necessarily as "less than" the other does not, as the word "less" cannot, in such a context, mean what its definition implies.
> (if for every y we have an x, there must be at least as many xs as ys)
The lack of a surjective function does not mean that we cannot have an X for every Y, it just means we can't map an X for every Y with a surjective function. It doesn't mean a pairing cannot exist (at least not abstractly, which is how all infinite sets exist anyway). The pairing can simply be random and undefinable. There, now a pairing exists and both sets are the same "size". (It's not a surjective function, but if the point is simply to compare "sizes", then what does it matter?)
Cardinalities of sets do have sensible operations like less than and greater than though - |A| <= |B| if there exists an injective function from A to B. One has to check that this inequality behaves in the ways that you expect, but it is a well-defined concept.
It is defined in the abstract, but I think there are a lot of implicit assumptions that get lost when dealing with cardinalities which may turn out to be important. Just because a bijective/injective/surjective function exists doesn't mean that such a transform is possible when you apply it to a specific situation.
If sizes were sensible then for a set A composed of "every other integer" would be smaller than the a set B composed of "2 times every integer". If we were using calculus to take the limit of the ratio of sizes of the generating functions for A and B as the source set size goes to infinity then we find that A is in fact half the size of B. If we try to simply apply cardinality to A and B we find that the sets are exactly equal, since cardinality doesn't care about source sets or limits!
This can a big deal if say, you're calculating probabilities across an infinite number of possible events/event configurations. There is a big difference between a 50% chance, a 0.000001% chance and a 100% chance.
I'm not saying there's no use for cardinality and infinity classes, but they can easily be misapplied to allow you to be wrong, with confidence.
If sizes were sensible then for a set A composed of "every other integer" would be smaller than the a set B composed of "2 times every integer". If we were using calculus to take the limit of the ratio of sizes of the generating functions for A and B as the source set size goes to infinity then we find that A is in fact half the size of B. If we try to simply apply cardinality to A and B we find that the sets are exactly equal, since cardinality doesn't care about source sets or limits!
This can a big deal if say, you're calculating probabilities across an infinite number of possible events/event configurations. There is a big difference between a 50% chance, a 0.000001% chance and a 100% chance.
I'm not saying there's no use for cardinality and infinity classes, but they can easily be misapplied to allow you to be wrong, with confidence.
> If sizes were sensible then…
Sorry, but they simply don’t meet your (non-standard) definition of sensible. Both of the sets you mentioned can be interpreted as the set of even integers. This set is in bijection with itself (trivially), and thus is not considered to be strictly smaller than itself.
Sorry, but they simply don’t meet your (non-standard) definition of sensible. Both of the sets you mentioned can be interpreted as the set of even integers. This set is in bijection with itself (trivially), and thus is not considered to be strictly smaller than itself.
> Almost anything can be proved/disproved or debated when one assumes such validity of the logical concepts to infinity.
if this were true it would be trivial for you to give devastating examples
if this were true it would be trivial for you to give devastating examples
"Almost anything can be proved/disproved or debated when one assumes such validity of the logical concepts to infinity."
I strongly believe that statement to be false.
Can you provide a contradiction that is provable using Cantor's definition of the cardinality of sets?
I strongly believe that statement to be false.
Can you provide a contradiction that is provable using Cantor's definition of the cardinality of sets?
Many logical concepts which we take for granted, might not be meaningful in the realm of infinite. For example, something being equal to itself, some statement being true or false (no third state), things having unique identity or location, the concept or possibility of multiple things (and distinguishability), being able to compare one thing with another etc. All these make sense only in finite contexts but not in infinite or infinitesimal contexts.
If we accept infinity as a participant in the mathematical logic, the infinitesimal also deserves a role as a counter-party.
If we accept infinity as a participant in the mathematical logic, the infinitesimal also deserves a role as a counter-party.
> If we accept infinity as a participant in the mathematical logic, the infinitesimal also deserves a role as a counter-party.
Infinitesimals have a much bigger role in widely-known mathematics than infinities do; they are the basis for calculus.
Infinitesimals have a much bigger role in widely-known mathematics than infinities do; they are the basis for calculus.
Series play a big role in all of math...
Infinitesimals are just a different aspect of mathematical infinity.
This is the magic that makes calculus work (from a formal standpoint).
This is the magic that makes calculus work (from a formal standpoint).
While you can build a calculus using infinitesimals, the usual construction does not use them.
https://en.wikipedia.org/wiki/Nonstandard_analysis
https://en.wikipedia.org/wiki/Nonstandard_analysis
The original construction did though, if you look at the writings of Newton/Leibniz. But their work was totally hand-wavey. Cauchy discovered limits in the 1800s, and it wasn’t until the 20th century that the original idea of infinitesimals was formalized. In some sense we have come full circle.
I do think that infinitesimals are a much more intuitive way to understand calculus. It’s a shame it took so long to find positive numbers less than any real.
I do think that infinitesimals are a much more intuitive way to understand calculus. It’s a shame it took so long to find positive numbers less than any real.
It’s a fundamental mathematical fact that there does not exist a bijection between the naturals and the reals. This is what provides genuine distinction between the discrete and the continuous, the countable and the uncountable. It certainly is a mind-blowing fact. But many facts blow the human mind, and it isn’t Cantor’s fault that he was brilliant enough to discover one such.