Why Some Infinities Are Bigger Than Others
scientificamerican.com
scientificamerican.com
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.
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?
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. :-)
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.
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 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.
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.
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.
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.
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.
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.
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.
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.
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!
The probability distribution that we all want to define on the real numbers does not exist. And this has non-trivial consequences.
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.
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.
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?
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.
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".
'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.
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.
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.
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"?
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.
It has to do with the fact that we can construct an open set of arbitrarily small size that includes every rational.
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.)
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.
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.
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.
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.)
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 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.
> 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.
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.
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.
And if you want every infinite set to have size continuum, then N (and so Z and Q) break horribly
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.
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 don't use infinitesimals, and analysis using infinitesimals is explicitly separate from traditional analysis
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.
The approach via infinitesimals is even called "nonstandard analysis".
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 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 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.
Biologist: They must have reproduced
Engineer: It must have been a measurement error
Mathematician: If one person enters the building, it will become empty
-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
Even this notation assumes base ten for the number written inside the parenthesis. Otherwise it works for any base.
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.
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"?
Haven't you only demonstrated a countable list of all possible things that might possibly represent a computable number, or some similar concept?
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.)
"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 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.
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
The field of numerical analysis depends on formal treatments of calculus. Formal treatments of calculus don't work in sets smaller than the reals.
Is there something I'm missing, something that the formal treatment of calculus depends on them for?
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 a hack. Mathematicians can come up with hacks too.
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.
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.
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.
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 said, with Google's paper "towards an api for the real numbers", you get close enough for many practical purposes
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.
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'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.
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.
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.
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?"
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?
“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.
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".
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 acceptance of multiple infinities and some concepts around continuum (Dedekind cuts etc) are questionable due to this assumption.
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.
This is the magic that makes calculus work (from a formal standpoint).
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.
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.
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.
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.
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
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
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?)
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?
if this were true it would be trivial for you to give devastating examples