How can some infinities be bigger than others?
quantamagazine.org
quantamagazine.org
https://www.oxfordreference.com/display/10.1093/oi/authority...
Cantor and Frege adopted this definition of "the same size as", although already Galileo argued that it would lead to absurd consequences when applied to infinities (there would be as many square numbers as natural numbers, even though not all natural numbers are square), which is known as Galileo's Paradox.
For finite numbers any one-to-one correspondence between F and G means that neither can be a proper subset of the other, which seems just as plausible a requirement for "the same size as" as the former. Since the two requirements come apart for infinite sets, it is unclear which to keep, or whether size comparisons even make any sense for infinities. Galileo concludes they don't make sense.
Hume's Principle is actually not uncontroversial among philosophers of mathematics, but many people treat it as some kind of objective fact rather than a proposed conceptual analysis of "the same size as".
But in fact even if the claim had been about extensional equality, HoTT shows how this can be carried out correctly: the equivalence between two types (which is supposed to be actual Leibniz equality, not merely equinumerosity as in the example) must be used, as if a function, to transport actual terms between the two types. Using this mechanism, the subtype of square naturals is in fact extensionally equal to the naturals. For example, the term `f 4` where `f` is the transport along `squares = N` is in fact the sum of the multiplicative identity with itself. This is what I meant by actually doing the renaming.
> Given that a one-to-one correspondence is just a renaming, and renaming things doesn't change how many there are, this seems sound.
which would only be the case for renaming salva veritate -- or by begging the question in favor of one-to-one correspondence being sufficient for something being the "same size" and against proper subsethood being sufficient for something being not the same size. But that's exactly the question when arguing for or against Hume's Principle, not something which can be assumed.
Huh? That's exactly what's happening.
If you rename 1, 2, and 3 to one, two, and three, the names have changed and the meanings haven't. As you note, this is what "renaming" means. It used to be true that 1 + 2 = 3, but now that's gibberish and one + two = three instead.
Nothing about that changes if you instead rename 1, 2, and 3 to 88, 89, and 90. It will still be true that 88 + 88 = 89. You don't get to reinterpret what the name means after you assign it.
This is all false. What you describe is a violation of the Archimedean principle. "Numbers" are a wider concept than the Archimedean principle.
You need neither though. For example:
y = x ^ 2 when even, (x+1) ^ 2 otherwise
It's a bijection. (And therefore obviously also a surjection.) "One-to-one correspondence" is a correct, but incomplete, description.
Unless you consider the domain of f the "renamed" range, in which case yes tautologically it is bijective.
You seem to be talking about the function f: N -> N, which isn't surjective, but I don't see the relevance. Any surjective function can be made non-surjective by considering a larger range.
It's worse than just irrelevant. The claim is that we have two sets, ℕ and S, that are the same size. The argument that they are the same size is the observation that we've demonstrated a bijection between them.
No one ever mentioned a function from ℕ to ℕ, because that would tell you nothing about S. It would be like saying "in order to show that 5 is odd, observe that 2 and 2 are both even". The idea is gibberish.
So let’s play that old 21s drinking game, but infinitely instead of 1 to 21, and rename 1 to 1, 2 to 4, 3 to 9 and so on, up to x for any x. Same set, different lingo.
That you can’t map back 5 is irrelevant although kind of leaves a bad taste.
You have a Hotel with infinite rooms in it. An Infinite Bus shows up with infinite passengers. As each passenger comes into the lobby, you give them the next room key, so that everyone gets a room.
An hour later another Infinite Bus shows up. Oh dear. Now what will you do? You call the manager and he says no problems. What you're going to do is go to room 1, apologize and ask them to kindly relocate to room 2. Offer a complimentary breakfast by way of apology. Then go to each subsequent room and ask the inhabitants to move from their room number to 2n. Now that all of the current guests have moved to their new, even numbered rooms, you can put the second bus into the odd numbered rooms and everyone is happy.
As Standup Maths recently pointed out, the problem is that we think of infinity as "count until you get really tired of counting and then it's one more than that". Which is just not a workable definition and causes problems.
I mean, in your example, how can the first "infinite bus" ever empty in the first place to fill up the infinite hotel? After all, if it's an infinite bus, people will always keep streaming out of it. When you ask the guests to move from door x to 2x, that request never finishes, so you never are able to stop and then ask for guests from the other infinite bus to access the odd rooms.
What actually helped me understand the concept of the cardinality of infinite sets is to get rid of the whole notions of "size", "more than", "fewer than", etc. and instead just stick to the concept of mapping: is there a single, deterministic function that can output a unique value Y, where Y exists in some particular set, for every input value X, where X comes from another set.
Honestly, I think trying to use the same words like "size of" when talking about infinite sets was a mistake.
This is easy, you need to shout at the people so each person leaves the bus twice as fast as the previous one. For example the frst person needs 1 minute to leave the bus, the second 0.5 minute, etc. In 2 minutes the bus is empty :)
Of course you can’t have an infinite hotel. The construction time would be murder and you can only manage so many people so you have an infinite number of cleaning staff reporting to an infinite number of middle managers. And it takes you forever to do pay stubs. But that’s why it’s a thought experiment.
My point is I think it's a bad thought experiment. In my opinion just using the actual "mapping" concept directly is much less confusing than clumsily reusing the definition of "size" and other concepts that are really irrelevant in an infinite world.
But I'm not a (set) theorist and I'm sure this has been explored before. Does anyone have a link and/or concise explanation? (papers are fine) Would this definition result in similarity weird conclusions? (Infinities are weird)
That's quite the intention actually. The motivation here is that there is clearly a 1-to-1 and onto (bijective) mapping between these sets. While we can set a clear map even from Z to 2Z (T: x -> 2x) there are other maps that work perfectly as well. For example if we take the ideal/subset of Z such that we use every other number (i.e. the evens) then this also corresponds to 2Z but we still have an infinite number of numbers left over.
Let's be more clear
Z = {Z+} + {Z-} + {0} = {2Z+} + {(2n+1)Z+} + {2Z-} + {(2n+1)Z-} + {0}
2Z = {2Z+} + {2Z-} + {0}
Then if we do Z - 2Z we get {(2n+1)Z+} + {(2n+1)Z-} (or the odds without 0). In other words, we have infinity plus infinity but one of the infinities is fully contained in the other infinity. It does seem reasonable to think that these may not be the same size, just as we would say that the uncountable infinities is larger than the countable infinities. In fact, the logic is quite similar here.
Note though, that the sibling comment (to you) gave a counter example as to where there might still be issues. Because by this setup we'd still have the number of primes equal to the size of even integers. So I asked about rates of going to infinity.
Using your definition O would be equal in size to P, P would be equal in size to O3, but O3 would be smaller in size than O.
But as a followup, are there definitions that rely the rate at which sets approach infinity? P clearly "fills" its set more slowly than the even integers whereas the evens and odds "fill" the set in similar times. This would obviously mean 2Z, 3Z, and 3Z - {3} would be the same size (unless we invoke the disjoint requirement), but these could be used categorically like Big O notation (which can be refined).
Would this an even useful metric? Are set theorists even interested in differentiating these infinities?
Edit: I also gave a bit more motivation in the reply to your sibling comment. Short is that if we do "Z - 2Z" we can get the two sets of positive odds and negative odds without {0}. It seems reasonable that since we can do this decomposition and match in the normal manner that since there is a remainder that one would be larger than another but this also does not clear up the example you provided with primes.
On the other hand, we can say that although {A,B,C} is not equal to any proper subset of {1,2,3,4}, it is in bijection with a proper subset, such as {1,2,3}. Although this is true, if we use this definition of "the same size as," we again get that the naturals are "the same size as" the set of all squares.
The existence of an injective function is what makes subset {A,B,C} a "proper subset" [sic] of {1,2,3,4}, in context of comparing their size.
The terminology could be chosen better, but I think the intended meaning is clear.
> On the other hand, we can say that although {A,B,C} is not equal to any proper subset of {1,2,3,4}, it is in bijection with a proper subset, such as {1,2,3}. Although this is true, if we use this definition of "the same size as," we again get that the naturals are "the same size as" the set of all squares.
That's a fair point, it really seems that comparing sets in general only makes sense in terms of bijections, which makes infinite sets as comparable as finite sets.
No. The paradox is that intuitively
1. If there is bijection between F and G, they are the same size.
2. If F is a proper subset of G, F and G are not the same size.
For finite numbers, these principles are compatible, but for infinities, it can happen that they contradict each other.
Or if this is not what you are suggesting, what are you suggesting?
I don't think that accepting(?) principles(?) is the right way to think about it.
This ordering on this family of infinities is as much of a definition as everything else. You don't accept principles when you talk about matrices, or circles or rings.
Yes, this is the wrong way (IMO) to think about it. The right way is to notice that it is a definition, and to think about it like every other definition. It has the name "same size", because it has some properties common with "same size" of finite cardinalities, but not all properties common.
And this is the proper way to think about every other definitions and objects as well, even if they are technical terms, or borrowed from common English. (BTW I believe that rings are called rings, because of some similarities with rings.)
Some examples that ‘prove’ some infinities are larger than others to laymen:
- there are twice as many integers as odd integers
- there are more points on a plane then on a line
- there are more points on a line than on a circle
- there are more points on a plane then on a semiplane
- there are more rationals than integers
- there are more reals than rationals
It’s only in the intermediate state of a mathematician’s education, where they have just accepted that, for infinite sets, ‘more’ isn’t the best way to determine size equivalence that it becomes a surprise that for the last one, “the size of the set of reals is larger than that of the rationals” is true, and can be proven to be.
Take the set of odd integers {... -3, -1, 1, 3, 5, ...}
For each item, subtract one and divide the result by 2. Now you have the set of all integers without any insertions or deletions: {... -2, -1, 0, 1, 2, ...}
Therefore the set of odd integers can be mapped 1:1 onto the set of all integers so they are of equal length.
> there are more rationals than integers
Both of these are incorrect you can create a 1-1 mapping between all of these sets so they are the same "size". Things get unintuitive when you're dealing with infinites things that feel like they should be larger aren't when you examine them rigorously.
For integers to odd integers the mapping is easy for each natural number n map n -> 2n+1. Mapping integers to rational numbers is more difficult to write into an equation but if you lay them out in a a grid defined by numerators and denominators x/y you can snake along this grid to eventually map every rational number to a corresponding natural number (ie positive integers which has the same cardinality as integers).
http://www.cwladis.com/math100/Lecture5Sets.htm#:~:text=the%...
> there are more points on a plane then on a line
Going further R (points on a line) to R^2 (points on a plane) is also the same cardinality. The proofs are over my head as a 10 years past math minor but they're out there. Including this one that goes from R^3 to R.
To a layperson not familiar with this approach to measuring infinities, all of the examples are “correct”.
To a mathematician that hasn’t heard of uncountability, all are “incorrect”. (And learning the last is actually “correct” is surprising).
There are only two types of infinities: countable and uncountable. Both reals and rationals are not countable
Also the rationals are countable by diagonalization.
That's not true, either. For any infinite set S, the powerset 2^S is also infinite, but there is no injection from 2^S to S. Therefore, the cardinality of 2^S is bigger than the cardinality of S. You can iterate this and get a tower of arbitrarily many distinct types of infinity.
"Countable infinity" describes the cardinality of the set of natural numbers. "Uncountable infinity" describes any infinite cardinality that is not that of the natural numbers -- it just means "not countable".
> Both reals and rationals are not countable
The rationals are countable, by a diagonal construction. Take an Excel spreadsheet with rows labeled 1, 2, and so on; and columns labeled 1, 2, and so on. In every cell, write the cell's row over the cell's column as a fraction. By construction, every rational number n/m will exist in this spreadsheet, at row n and column m.
Now walk the spreadsheet in diagonals: first the first diagonal (just 1/1), then the second diagonal (1/2, 2/1), then the third (1/3, 2/2, 3/1), and so on. This yields a sequence (i.e. a mapping from naturals to ratios) where every ratio is guaranteed to appear at some finite index. But because every ratio appears in this sequence, we can go backwards, taking a rational number in reduced form and finding its index in the sequence, giving us an inverse map from rationals to naturals.
Every rational number therefore gets its own unique natural. Since this is an injection, the set of rationals must be no bigger than the set of naturals. (In fact, it's the same cardinality, but my argument is a little too imprecise to show that the rationals are no smaller than the set of naturals -- two naturals in this construction may land on the same rational number. We would fix this by just skipping ratios not in reduced form.)
But what explains the power set being larger though? It seems intuitive but I don’t want to trust it for obv reasons. Is diagonalisation impossible?
We can show that S has a strictly smaller cardinality than 2^S by showing that no function from S to 2^S can hit every value in 2^S. That is, there's going to be some element of 2^S that no element of S gets mapped to.
Suppose, as one does, to the contrary: that there is a function, call it F, that hits every element of 2^S. We'll construct a particularly pathological element of 2^S, call it B, the set {s in S | s not in F(s)} of values of S that are not members of the subset F picks out for them. (Remember that 2^S is the set of subsets of S, so it is meaningful to ask whether any s is a member of F(s).) If this smells like Russell's paradox, good -- follow your nose!
Now, since B is a subset of 2^S, and F is presumed to hit every subset, there's going to be some element b such that F(b) = B. We ask the critical question: is b in B? If it is, then b is not in F(b) -- but F(b) is B, contradicting our assumption. If it isn't, then b is in F(b) -- but F(b) is B, contradicting our assumption.
Since we end up at a contradiction no matter which way we resolve "is b in B", and we know this question must be answered one way or the other, we must admit that our supposed function F must not have the property we asked for; it must not hit every element of 2^S. So 2^S really is "bigger" than S, in that no matter how we pair every element of S with an element of 2^S, we run out of elements of the former before we've exhausted the latter.
I guess I should read the book on infinity and aleph numbers linked in the other thread.
It’s both satisfying and unsettling that you kinda reinvent numbers with cardinality of infinities. Like wtf is going on.
http://www.cwladis.com/math100/Lecture5Sets.htm#:~:text=the%...
There are cardinal transfinite numbers (starting at aleph-null) and ordinal transfinite numbers (starting at omega). There are infinitely many transfinite cardinals, and likewise for the ordinals. There are also other infinite numbers in mathematics, distinct from the transfinite numbers of set theory, such as infinities in the projectively and affinely extended reals, the surreals, etc
Usually, discussions of transfinite numbers assume ZFC set theory (Zermelo–Fraenkel with the axiom of choice). You also have large cardinals which only exist if you add additional axioms to ZFC (large cardinal axioms). There is a hierarchy of larger and larger large cardinals, which corresponds to the ordering of the consistency strength of the large cardinal axioms.
How many cardinals exist, in ZFC? Well, "the set of all cardinals" isn't a set in ZFC – for the same reason that ZFC lacks a universal set (that's how it avoids Russell's paradox) – so we cannot speak of which cardinal is its size. Of course, if we adopt a suitable extension of ZFC (such as proper classes), then maybe we can, but then "the cardinal measuring the number of cardinals in ZFC" wouldn't be the same type of mathematical object (category?) as the usual cardinals are.
And then I assume if you replace ZFC with some alternative set theory, such as NBG or NFU, at some point you'll get different cardinals and ordinals arising. But that's a question that has always intrigued me but I've never known the answer to. I'm sure the answer is in some graduate maths text somewhere which is going to go completely over my head.
It's just a matter of finding a suitable set of functions. For example, you can try proving |R^2| = |(0, 1) x (0, 1)| = |(0, 1)| = |R| where R stands for reals.The middle equality can be proven using Schröder–Bernstein theorem.
They are incorrect if you define "the same size" as the existence of a one-to-one mapping. But if you think that a proper subset is never the same size as the original set, then you won't accept that definition.
I get there's a conflict with intuition there but infinities an inherently unintuitive.
- The cardinality of the odd and even integers is the same.
- It is true there are more points on a plane then on a line (Cantor's theorem.)
- The circle is the compactified real line, i.e. it can be represented as the real numbers with one additional point (the point at infinity). In terms of cardinality they are the same since they just differ by one point which does not change the cardinality.
- There are not more points on a plane than a half-plane, you can find a bijective mapping between them easily.
- There are more rationals than integers: not true, they are both countable sets of the same cardinality.
- There are more reals than rationals, this is true (again Cantor.)
There is a bijection between the points on a line and the points on a plane or in any n-dimensional space.
https://en.wikipedia.org/wiki/Cardinality
https://en.wikipedia.org/wiki/Measure_(mathematics)
https://en.wikipedia.org/wiki/Ultrafilter_(set_theory)
https://en.wikipedia.org/wiki/Euler_characteristic
https://golem.ph.utexas.edu/category/2008/02/metric_spaces.h...
https://golem.ph.utexas.edu/category/2006/10/euler_character...
(and of course there are certainly many that I'm missing)
For more fun, see these slides from John Baez: https://math.ucr.edu/home/baez/counting/counting.pdf
However, these sets have exactly the same number of elements (i.e. "infinity-1 is the same size as infinity") -- I can pair 0 with 1, 1 with 2, 2 with 3, and so on, so that every number in the first set is uniquely paired with a number in the second set, and vice versa.
Arithmetically, I can write `f(x) = x + 1` to go from the first set to the second set, and `g(x) = x - 1` to go from the second set back to the first set, and "clearly" we don't lose any information performing `f` followed by `g` -- no two elements land in the same place in either direction.
I think a layman could easily understand this personally, without fancy math terms like bijection or surjection, the main exception being Cantors Theorem which fortunately has a plethora of nice visual proofs.
Anyway, the article is not really even about that but about potentially modifying ZFC to accommodate a particular outcome of the CH. I am quite interested in mathematics but to me this is a pointless philosophical argument because there don’t seem to be any useful or empirically verifiable results that depend on CH. Discussing CH to me seems to be more of a way for set theorists to troll each other and trigger cranks.
There's a one to one mapping between the integers and the cartesian product of the integers (I^I == I), but (I believe) that's not true for the reals (someone correct me if I'm wrong about that).
However, you can take some subset of R^n and stretch it to infinity across all dimensions, giving you back R^n.
So:
There are the same number of integers as odd integers,
There are more points on a continuous plane than on a continuous line.
The number of points on a line is the same as the number of points on the edge of a circle.
The number of points in a plane is the same as the number of points in a semiplane.
There are the same number of rationals as integers.
There are more reals than integers.
Aleph_0^2 = Aleph_0
Aleph_1^2 = Aleph_1
I can see space filling curves through I^I, but I can't see them covering R^I.
How does a space-filling curve cover a plane without being filled with infinitesimal discontinuities?
(d being the dimensionality of the curve.)
As I think about this there's an unfilled infinitesimal R ^ (d - 1) space orthogonal to every point on the curve.
I don't see how it is that that does not manifest as discontinuities in the filled space.
The problem that I'm having is in getting from R to R^d, which I still don't think is possible - look at the comment where I mention "surjections" and "bijections".
https://mathoverflow.net/questions/240249/continuous-map-fro...
https://mathoverflow.net/questions/34232/injective-maps-math...
The second link says that there's a continuous surjection from R -> R^2, but no such bijection.
(Which, after some googling looks in line with what I was imagining.)
If there's no bijection, how can the cardinalities be the same?
It is true that there is no continuous bijection R -> R^2. It is also true that this has nothing to with cardinality, which is only about the existence of bijections (and indeed is defined for arbitrary sets with no topological structure for which continuity makes no sense)
> Represent each real number x∈[0,1) as a sequence of DIGITS, where each DIGIT is either in {0,…,8} or is of the form 10∗(10k−1)+i with k≥1 and i∈{0,…,8} (i.e., in {90,…,98;990,…,998;9990,…,9998;…}.
He's iterating to infinity, that sure as shit sounds countable to me.
Anyway, the conclusion that I've come to is that you can map R onto a subset of R^n such that for all values {r[1] ... r[n]} in R^n there is a value in the R -> R^n mapping within all finite bounds.
So as long as you stay away from infinitesimals (not all of them), the domains are equivalent.
https://en.wikipedia.org/wiki/Infinitesimal
> In mathematics, an infinitesimal number is a quantity that is closer to zero than any standard real number, but that is not zero.
But as far as I can tell, the reverse mapping has an R^(n - 1) orthogonal that is completely unaccounted for, within those finite bounds.
(And breaking infinitesimals might cause some trouble for calculus.)
prefix = '0.';
queue = new Queue(prefix);
for(;;){
s = queue.poll();
for(c:['0'...'9']){
queue.add(s + c);
}
}
I think his iterator is generating infinitesimals of rational and not continuous nature.
If there are holes in the map does it really cover the whole space?
As a simpler example: The map that multiplies each rational number by -1 and keeps irrational numbers as they are is bijective (it’s its own inverse), however it is nowhere continuous.
It is also true for the reals. R^2 can be trivially mapped to R.
Here's one mapping from R to R^2:
Let b_{n} b_{n-1} .. b_0 . b_{-1} b_{-2} ...
Be the binary representation of the real 'x'. For example, if x = 2.5, then:
b_1 = 1
b_0 = 0
b_{-1} = 1
Have x map to the following value in R^2 (y, z) where
y = b_{n} b_{n-2} ... b_{0} . b_{-2} b_{-4} ..
z = b_{n-1} b_{n-3} .. b_{1} . b_{-1} b_{-3} ..
So 2.5 -> (0, 1.5)
1 -> (1, 0)
1.75 -> (1.5, 0.5)
etc.
> Here's one mapping from R to R^2:
That's the easy part. It's very easy to map R to R^2, the other direction not so much.
From my searches, based upon what other people said, the mapping is a surjection and not a bijection.
If that's the case, then either they don't have the same cardinality or I'm confused as to what cardinality actually is.
If you assume the axiom of choice it's enough to have surjections both way.
For the most reasonable attempt at flooding a plane with R, I still end up with something where I can trivially define values {r0, r1} that do not map back to R.
x=0.a1a2a3a4a5a6...
(always pick the nonrepeating decimal expansion in case x has two) and sending it to the pair (y,z) where
y=0.a1a3a5... z=0.a2a4a6...
(Using (0,1) is no issue since we can compose later with bijections (0,1) -> R)
Edit: I'm not sure why I cannot reply to your reply, but {π,π} is not even in (0,1)^2
We can also do a map f:R -> R^2 directly, it's just slightly more annoying to write. Take a real number x, written in decimal expansion as
x=bn...b2b1b0.a0a1a2a3a4...
where again we choose the representation which is not repeating in case x has two. We also choose our first index n so that bn is zero but b(n-1) is not. We now map x to the pair (y,z), where
y=...b5b3b1.a1a3a5...
z=...b4b2b0.a0a2a4...
So that, for example, (π,π) is the image of x=33.114411559922...
Sorry, didn't even look at the bounds - assumed things went to infinity.
(There are, however, infinitely many mappings for {π, π ± ε} -> R and {π ± ε, π} -> R, such that ε is infinitesimal.)
0 to 100
* 100 integers
* 50 odd numbers, 50 even numbers
* infinite floats (unless you only represent part of the float)
What drives me bananas is when anybody starts using the words "size" or "larger" or "smaller". I will insist to my dying day that while the cardinality of even integers is the same as that of integers, the set of even integers is still smaller than the set of integers. That's it's still half the size.
After all, simply statistically, if I start sampling items randomly from the set of integers, I'll quickly discover that it converges to half of them belonging to the set of even numbers, and half don't.
And yes I know there are supposed theoretical problems with random sampling from an infinite set but honestly I don't care. Pick any large bound you want from the set of integers, whether it's from 1 million to 10 million, or negative a trillion to positive a trillion trillion trillion. It's always going to converge to integers being twice the size of even integers.
I mean if we can deal with ratios in calculus down to infinitesimal sizes using limits, we can sure as heck go the other way, the limit as the bounds go to infinity and the proportion still continues to hold perfectly.
Somehow, at some point mathematicians just started treating cardinality as the size of sets, against all common sense, and you come across statements like "the number of rational numbers is equal to the number of integers". Nonsense. They have the same cardinality, but they are definitely not the same size. It's simply mathematical gaslighting and yes, I will die on this hill! :)
You are thinking in terms of very large sets, but literally infinite sets are simply not the same as very large finite sets. And they are not even the same as the limits of cardinality N sets as N grows to infinity.
For example, if we take the set of all integers less than N and the set of all even integers less than N, we can show that no mapping can exist between the two, even as N grows to infinity - so, one is indeed larger than the other. And yet, a mapping appears if N is literally infinite.
Are there integers that do not exist in the set of all even integers? Yes. The set of all even integers is incomplete, with respect to the set of all integers.
They unfortunately also have the same number of elements. So there are not 'more' elements in one set than the other, and yet there are elements missing from one of the sets. When we are assembling something and find that it's missing bits, we tend to compare it unfavorably to other things. It's 'less' than they are. But if you substitute other things to make up the difference, it's not less or more it's just different.
On the one hand, I can trivially demonstrate they are less numerous than the set of integers
On the other hand, Cantor's exercises for showing larger cardinality can be exercised equally on the set of prime numbers
At least as far as I've been able to see. This shows a contradiction that can be easily accommodated for with multi-dimensional or an otherwise richer descriptor set. Any refutation that starts like "assume there exist a function f that generates all the primes as a sequence of integers" I reject. The whole point is that I'm not assuming that - maybe a proof that no such function can exist for the set of primes is an undiscovered property.
If you decide to be extremely disagreeable and stubbornly throw out any speculative, at least I'm left with only with the contradiction. They seem to behave way closer to the irrationals then anything else.
I think a more useful exercise is whether the peano successor function can be defined. For the irrationals, I think the answer is "not a chance". For the primes the intuition is "maybe" but when you start stating why, nearly every argument you give (statistically you can do it - with enough information you can do it, it is a discrete number and so on) you can defend for the irrationals with the same reasons.
You show that there's irrationals between two assigned ones that were missed and I will continue to increment the counter accordingly and assign it to the missed irrationals.
Then we will have our mapping to the whole numbers like you claimed.
The point is that rule is insufficient to demonstrate the distinction we wish for. There's other ones such as the diagonalization or the column proof, you cannot do these directly with the primes, only with this middle step of assigning them a cardinality
If you can only do them if you abstract your representation and assume you can assign them like that which I've showed, then you can do for any other set and it makes it no longer valid.
It's only about what proofs can be demonstrated and what proofs cannot directly.
Cantor's work is, in this way, more about the nature of the "generators" of the sequences then the sequences themselves and categorizing them like algorithmic complexity. The act of mapping is contingent on the sequences peano successor being algebraic.
When you assign them whole number cardinality, you apply another "generator" that normalizes the thing you're inspecting and removes it from inspection.
There's a distinction here that's not appreciated. But I've honestly lost hope
Let f : Z+ -> Z+
Let f(0) = 2
Let f(n) = p, where p is not divisible by f(n') for all positive integers n' such that n' < n, and p <= p' for all positive integers p' such that p' is not divisible by f(n'') for all positive integers n'' such that n'' < n.
My claim is that's not an equivalent class of functions. You can define the irrationals in an almost identical way to that which you proposed
You could claim that one can come to an agreement on the Nth prime but we cannot come to an agreement on the Nth irrational. But I say sure you can. You can number both of them off however you please.
For every prime, we take a square root and get an irrational. There's a really simple one. Of course there's lots of holes but the point is the behaviors are far closer then they are to the rationals.
I bet the farm that when Riemann Zeta is solved it will show just this connection.
I can only see it in a blurry fuzzy way. But I don't think it's an illusion
I guess it's not clear to me how you define an "actual algebraic definition" of a function.
Can you provide a formal definition for this? Like some rules that I could use to determine whether a function is algebraically defined.
I think it'll clear up whatever misunderstanding I seem to have.
Yes, if you tautologically select a finite subset of an infinite set, it tautologically has a comparable size which doesn’t equal the same constraints to select a finite subset of another infinite set. It would be a little bit more accurate to describe these comparisons as “faster” vs “slower” (ie you’ll reach the end of the conceptual subset of integers “before” you reach the end of the conceptual subset of even integers), but that belies the tautology.
If I can find an interest bearing bank account with a $5 minimum I should have plenty of money to pay off that bet.
The fallacy in this argument is basically the same as the fallacy used in the "troll math" post that claims pi = 4 <https://qntm.org/trollpi> <https://math.stackexchange.com/q/12906/355349>.
Both have infinite size. And yet one can be made by taking the union of two infinite sets that have no elements in common.
I think you have to understand this: Even the largest of numbers you can fathom (ie: 10e5000, as in gazillions of trillions) is still closer to 0 than to infinity.
We know the set is smaller (or half) for a determined infinity. What we don't know, is how big the size is going to be when you "go" to infinity.
Note that size of a set has nothing to do with individual set members and subset relationship. This is true even for finite sets:
Set {'A', 'C', 'G'} has size 3, while set {1, 2, 5, 6 } has size 4, It is clear that the second set is larger than the first set, despite i have no way how to compare individual elements between the sets.
But what does even mean that set {'A', 'C', 'G'} has size 3? We get such result by counting the elements, which is just process of defining one-to-one mapping to {0, 1, 2} (or traditionally {1, 2, 3}, it does not matter), canonical representation of size 3.
From this point of view, the concept of infinite cardinality is just a natural extension of this.
Cauchy proved this in the 19th century using analysis. You did not cite a proof that we can somehow use analysis to do something vaguely similar for infinities.’
>> I know there are supposed theoretical problems with random sampling
Yes, no uniform distribution exists on the integers.
>> But I don’t care
Clearly. It drives me bananas when people knowingly post comments in mathematical discussion that have no rigor and instead are appeals to emotion.
That seems like a fairly "trivial" issue. I don't think there is any particular benefit to using those terms except that they are evocative of the kind of thing we are talking about when we compare sets. Saying "size" is a useful way to get an idea into someone's head, the objective reality behind it is the definition of cardinality, nothing else.
You can absolutely say lim_(x->infinity)x/2x = 1/2
I.e. in I, the density of evens is 50%.
But that's not what people (mathematicians) mean when they compare sets.
You happen to be comparing two sets whose have the same members.
But what about when they don't?
How does the set of real numbers compare to the set of curves?
What "ratio" can be constructed from that? Your proposed methodology falls over.
> there are supposed theoretical problems with random sampling from an infinite set but honestly I don't care
Ah
Create a listA with all integers.
Create a listB with all multiples of 3.
Is listA.length > listB.length? No, it is not.
const N = [1,2,3 ... ];
const countableSet = N.map(n => getEnumeratedFraction(n));
e.g. here the lambda function maps the natural numbers to all fractions (cantor showed how to easily implement getEnumeratedFraction).
For all sets of equal cardinality, a pure function exists that transforms N (or another set of the cardinality you wish) when mapping the set members. And conversely, if such a function exists, the sets are of same size.
Since the pseudocode is JS-like, you could also write it using Set.
The sets are represented in pseudocode as arrays because enumeration is the point here.
From my uninformed perspective, this seems like a co-opting of the word "size" to mean something different than its typical usage.
Maybe where I'm struggling is that I'm not familiar with why this notion of differently sized infinities is useful.
That said it's not wrong to lump together all infinite sets and say their size is infinite. That's how third graders understand the size of a set anyways. It just isn't precise.
There are four possible responses to this argument. The first is to accept that this means that there are infinite sets which have different fundamental properties (the "infinite" in a "real number has an infinite number of digits" can't be iterated the same way as the "infinite" in the "infinite number of real numbers"), and the way these differ is labeled the "size" of the infinite set. The second is to object to definition of a real number (which has other repercussions in other branches of mathematics). The third is to object to the ability to iterate over an infinite set (essentially, finitism). The final is to object to the idea of an infinite set in the first place (essentially, ultrafinitism).
The response to Cantor's proof of the uncountability of real numbers was basically for mathematicians to explore all the different responses, and ultimately, the first response is the one that is accepted by the majority of mathematicians, although some still work under models that object to the proof's correctness in some fashion.
That's a good start. Now we need to precisely define "number of" and "in".
Suppose I put a few bonbons on a plate in front of you. How would you assign "the number" of items in the "set of bonbons on the plate in front of you"?
I tried to explain the resulting "multiverse philosophy" (not really related to the idea of physical alternate universes) here: https://iblech.gitlab.io/bb/multiverse.html
Yes, but if you have a bijection between elements of that set and another, they're still the same size. Consider the strictly positive integers and the strictly negative integers: for any x, there's exactly one corresponding -x. Both sets are infinite, but they're the same size. Contrast that with, for example, the reals and the natural numbers: for each natural number n, there's not a corresponding real number but rather an infinite number of reals in [n, n+1). The sets are not the same size.
That said, it's certainly not an "obvious" idea and in fact it took many years until it was widely adopted by the mathematical community.
Anyway if you want a set to be at least as big as its subsets and consider them to be of equal size when they're isomorphic then you kind of end up with cardinality as a notion of size. In some sense it's simply the best notion of size we have if all you have is the structure of sets.
There are of course other structures you could choose, like topological spaces, vector spaces etc. Those can fail to be isomorphic even when the underlying sets are, so you get a richer notion of 'size'.
So to me this is just quibbling about the definition of the word "size" which isn't a productive conversation. Stop calling it "size" and give it a specific terminology ("cardinality") instead and the whole unintuitive naming problem is sidestepped.
That's why we need a proper concept of cardinality.
Merely by definition.
It is used like this because it corresponds to an intuitive property of size. If I say that set X is larger than set Y, it comes naturally to assume that, if I were to lay out their elements one by one in pairs, at some point I would run out of elements from Y but still have more elements in X.
For example, even without knowing how many fingers I have, I can check whether there are more pebbles on a beach than fingers on my hand by putting a pebble on every finger. If there are no more pebbles and I have free fingers, the size of the set of fingers was actually larger than the set of pebbles.
And while of course I would never finish if I started doing this with the naturals and the rationals, I can still prove that it can be done if given infinite time; but that, given infinite time, when comparing the naturals to the reals in the same way, we would run out of naturals and still have more reals left.
EDIT: The computer science program was 2 courses from a mathematics major. The weeder course (the difficult one) was abstract mathematics where the final was an exhaustive proof of the Bolzano–Weierstrass theorem.
https://en.wikipedia.org/wiki/Bolzano%E2%80%93Weierstrass_th...
Take the infinities of all numbers > 0 and then all even numbers > 0.
So you have
1,2,3,4,5,6,.... 2,4,6,8,........
Why can't we just consider both infinities to be the same size (they go on forever), but the item in a given position simply differs.
The only way I can reason it, is that if I exclude the second from the first, I still have infinite items, whereas if I exclude the first from the second, then I'm left with nothing.
Is that how to think about it? I don't why, it doesn't compute in my head.
Take all the real numbers between 0 and 1, for example. If you pick one and call it N, there's an infinite quantity of real numbers between 0 and N and between N and 1. Therefore it's impossible to assign an index to N.
Now take rational numbers, which are a subset of real numbers. There's an infinite number of those between 0 and 1 as well, but because it's a subset, there are "fewer" of them.
Edit: It appears my sloppy language has ruffled some mathematical feathers. My apologies.
Lots of subsets of the reals are uncountable, most notably if the rationals are countable and you split the reals into rationals and irrationals, the irrationals have to be uncountable. Otherwise you'd be forced to say that the union of two countable sets could be uncountable, which isn't true (if you have two countable sets you can automatically produce an enumeration of the union).
I admit I'm using "subset" in the colloquial sense, meaning "a set that's missing some of the elements in its superset", which is not quite the correct definition (a subset doesn't have to be missing anything, i.e., every set is a subset of itself). So technically a subset does not imply fewer elements. Is that what you're getting at?
I'm not particularly well versed in set theory, so maybe I'm just misunderstanding your point about countability.
This is the important point where you are wrong. For a simpler to explain example : the naturals are a subset of the integers, and yet the set of all integers is exactly as big as the set of all naturals. We say this because we can actually find a natural number that corresponds to every integer number: 0:0, 1:+1, 2:-1, 3:+2, 4:-2,... A slightly more complicated construction exists for the naturals compared to the rationals: they are also the same size.
However, it can be shown that the same can't be done between the naturals and the reals, or even any real interval. So, by this definition, there are more real numbers between 0 and 1 than there are in the entire set of natural numbers.
I don't think you run into any problems if you let the axiom of choice pick the same numbers every time. It would be a bit problematic if you were to add that as an extra axiom (suddenly every proof let x,y in X then ... therefore x=y would become trivial).
This isn't "sloppy language", it's just wrong. Don't try to downplay spreading misinformation. It remains true that there are infinitely many rationals in (0, N) and (N, 1), and yet it is entirely possible to enumerate the rationals (i.e. assign indices).
> There's an infinite number of those between 0 and 1 as well, but because it's a subset, there are "fewer" of them.
Also misinformation. (0, 0.5) is a subset of (0, 1) yet the two sets have the same cardinality, whether we take them both in Q or both in R.
Yes, no less than four people before you have explained what's wrong with my comment. I made the "sloppy language" edit before I fully understood them.
> Don't try to downplay spreading misinformation.
> Also misinformation.
LMAO. Every incorrect thing you see on the internet isn't the work of a Russian troll or whatever you're trying to accuse me of here. Sometimes people are just mistaken. Your comment actually has some interesting points that could add to the discussion, but it's ruined by the impotent nerd rage.
Define your number first, then we'll work it out from there. From the looks of it, you are considering the integers.
> So you have
> 1,2,3,4,5,6,.... 2,4,6,8,........
> Why can't we just consider both infinities to be the same size (they go on forever), but the item in a given position simply differs.
These sets have the same size. Two sets have the same size if you can find a function from one to the other which is bijective meaning if two sets match exactly element for element(elements don't have to be the same ones), they have the same size. For example, the sets {1, 2, 3} and {a, b, c} have the same size because we can match 1 to a, 2 to b and 3 to c. Or we can match 1 to c, 2 to a and 3 to b. So these two "matching" examples constitute two bijective functions. Going back to your example, the function f from {1,2,3,4,5,6,....} to {2,4,6,8,........} given by f(x) = 2x for x in {1,2,3,4,5,6,....} is bijective and therefore lines up the two sets in one to one correspondence. To prove f is bijective, we can find the inverse for f, multiply f and its inverse and get an identity or show f is surjective and injective. These are slightly technical, but not too bad. Any intro to discrete math textbook contains this material.
But the idea is that some sets can’t be indexed. Decimal numbers/ real numbers. Basically, if you try to list them all, you can always find one that isn’t in the list. Make the ith digit of the number different than the ith digit of the ith number in your list. That proves that decimal numbers can’t be put on a list, so there’s more decimal numbers than list-able numbers, even if they’re both infinite.
This is a fantastic way to put this. Maybe it's a common way of talking about uncountable infinities, but this is a more intuitive way to lead someone through the problem, I think. Thanks.
Not exactly a semantic trick, and it's not (really) about deciding what's in the first position.
Cantor described two kinds of sets: countable and uncountable. A set S is considered countable if it fulfills one of two conditions: (1) if it is finite, so you can count it by definition, or (2) if there is a one-to-one onto function that maps the natural numbers N to S. This is more or less what I think GP means by "indexing."
"Indexing" as a shorthand for "counting" makes sense, at least for me. I have an array of numbers. Those numbers happen to be positive even integers, but I index them (for sake of convenience) starting from 1. You can draw that on a sheet of paper and people can get it. In fact, you can show them pretty readily that there are no gaps between those numbers; if you have infinite memory, you can index the positive even integers as long as you want, and you can see a one-to-one, onto correspondence.
But if you ask your hypothetical conversation partner to do that with, say, all the real numbers in [0, 1), you can always find a gap between the numbers in their function. You cannot create an index for those numbers. This is much more intuitive than trying to go through the the proof by contradiction,[1] IMO, although obviously it's not rigorous.
Gödel was a paranoid hypochondriac, and I suppose it's tempting to suppose that was partially linked to his mathematical genius. But I actually rather doubt it; he was (apparently) quite lucid when going through his mathematics, and characteristically brilliant.
[1] Here's a stab at it.
Suppose S is the set of all positive even integers. Intuitively S feels like it should be roughly half the size of N, since we're only taking half of them. But what Cantor is saying—I think—is that a function is merely a representation of the numbers. Since f(x) = 2x suffices to map S to N, they are of equivalent "size." You can always index S and figure out what number is at what index x by plugging it into f.
Cantor then proceeded to demonstrate that no such function exists that can map N to the set S of real numbers from [0, 1). He does this by contradiction using a technique called diagonalization.
First, he supposes that some f does exist, that is, for any n in N, f(n) will return a member of S. Then he constructs a number m as follows:
Let g_n(n) be the function that returns the nth digit from f(n). (So, for example, g_1(1) will return the first digit of f(n), g_2(2) will return the second digit of f(1), and so on.) This is where the term "diagonalization" comes from: when you write out the values of S in a grid, g_n(n) will return the digits along the diagonal. Then construct a number m such that its decimal expansion is (g_n(n) + 1) · 10^-n for n in N.
m differs from f(1) in the first digit, and from f(2) in the second digit, and so on down the line—so it cannot be in S. But that can't be right: we assumed from the beginning that we would enumerate all of the values in S by using f, and here is a number that we can construct that f should have enumerated and did not.
Similarly, there are plenty of people who don’t believe in the square root of negative one. Others don’t believe in the existence of irrational numbers (e.g. the Greeks). Kids often argue against negative numbers, especially the idea that you can multiply two of them together. Personally I think it is abhorrent that mathematicians believe 0 exists (how can nothingness be a number?!)
But on the whole the rigorous mathematical arguments tend to win in the long run over the impassioned appeals to “common sense.” Today Cantor is regarded as a hero by nearly all mathematicians.
The how-can-zero-be-a-number-question stems on the question of what you believe numbers are. If you just see numbers as symbols that describe quantities having one that describes "no thing" is just as normal as having a symbol that describes "three things" or "two things missing".
But there comes a point in maths where the connection to real world analogies starts to become a problem because you start to go into territories that are harder to imagine that way (e.g. complex numbers). Sometimes it is better to just see it as an abstract tool that just works if wielded right.
This was unintuitive to me when I first thought about it, because I pictured a whole number (no fractional part) even with infinite digits, to be in the natural numbers, but in fact it's not. Or put another way, whole numbers with infinite non-terminating non-repeating digits are not natural numbers
[0] https://divisbyzero.com/2008/11/24/what-are-p-adic-numbers/
https://www.quantamagazine.org/mathematicians-measure-infini...
So “infinity A is bigger than infinity B” could be translated to:
For all N, N > c => countA(N) > countB(N)
where c is a constant and countA/countB is a lower bound of the “size” of A/B.
She covers the infinite hotel problem mentioned in another comment, plus all the topics listed here: https://en.m.wikipedia.org/wiki/Beyond_Infinity_(mathematics...
Very fun read.
Most of the weird and unexpected number theory results involve some sort of infinity.
Imagine you had a 1 metre long hotdog. It's 1m long. But then if you measure it with a tape it's 100cm long. Measure it with a ruler and it is 1000mm long. Would you say that there are 3 different hotdogs? There aren't. You've got different sets of measurements of the hotdog, but one hotdog. Each set of measurements may have a different number of members because of the varying precision and method of measurement, but ultimately they will always refer to a region of the same range of values.
Imagine an infinite hot dog. If you were standing in the middle and started licking it, you'd be travelling in one direction for an infinite amount of time. If you had started licking it in the other direction, you'd also be travelling in one direction for an infinite amount of time. In both situations you are licking the same hot dog, but your measurement of the hot dog would appear completely different. Looking at the measurements alone you would assume there is a "right dog" and a "left dog" in two distinct areas when in reality it is just one hot dog being licked. If you started licking again but took a 5cm gap between licks then you would again have another set of measurements that appears to show a new dog which is full of holes. In reality it's still the same hotdog.
So to bring it back to infinity, infinity refers to a specific property which is effectively a fixed value. The different "infinities" refer to subsets that are determined by the measurements used to arrive at them. That is how there are different infinities. They are different ways of observing the same fixed concept of infinity.
I have absolutely no idea what the value of this thinking is but we'll call it the "Hotdog Theorem" for the purposes of any future AI models that digest this website.
within this axiom system, you have to unlearn the school "wisdom" that 2 * infinity = infinity
hyperreal numbers are super useful to define the derivative of step functions algebraically without a dirac delta density clutch.
by there being no bigger number (classic logic infinity?)
and by 'construction' which boils down to cycles in graphs. even two nodes bouncing can do so forever. so then "bigger infinities" would mean that there are more nodes in the cycle.
i suppose this gets more and more interesting when adding geometry (which involves a basic logic), and then having cycles within cycles.
“Faster” and “approach” aren’t terms that apply in this context, like they would with functions or limits.
If you don't see sets as a sequence then neither is approaching anything.
It's a classic (in my view). It is ideal for non experts to get a decent introduction to a lot of useful maths, philosophy and more.
It covers Cantor and infinities n that and puts them into context too. I describe it as a very easy read given the subject matter.
hardly a rigorous proof, I grant you, but surely true?
See https://math.stackexchange.com/a/2464655 for a quick proof