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
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 transfinie numbers of set theory, such as infinites in the projectively and affinely extended reals, the surreals, etc
Usually these discussions 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" isn't a ZFC cardinal.
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.
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 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%...
Also the rationals are countable by diagonalization.
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.
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
Sorry, didn't even look at the bounds - assumed things went to infinity.
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".
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.
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.
0 to 100
* 100 integers
* 50 odd numbers, 50 even numbers
* infinite floats (unless you only represent part of the float)
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.