> there are twice as many integers as odd integers
> 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).
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.
> There are only two types of infinities: countable and uncountable.
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.)
That's a good question -- this result is arguably the one that made Georg Cantor a legend. (It's called Cantor's theorem, after all!) I had to refresh myself on the proof, but it boils down to a less obvious kind of "diagonalization" (this time to construct a counterexample).
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.
> There are only two types of infinities: countable and uncountable.
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.
> Both of these are incorrect you can create a 1-1 mapping between all of these sets so they are the same "size".
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.
That's only useful in comparing subsets though and we need a way to compare the size of any possible pair or group of infinite sets, given that the bijection method makes way more sense. Even though it's slightly unintuitive to laymen how can one thing be larger than another if for every member of one group I can match them with a member of the other group, provably for all the infinite members of either group?
I get there's a conflict with intuition there but infinities an inherently unintuitive.
It's more an argument not to assume there are infinities of different sizes. That would also get rid of most mathematical paradoxes related to infinity.
> 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 but they're out there.
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.
I follow the line of the proof but finding those actual steps is where being out of the pure math game for 10 years catches up to me. I went into college on a pure math major but transferred to a CS degree. Only needed about 2 classes extra at the end but was tired of school and a simple BS in mathematics wouldn't get me too much in a generic CS career so I just stopped.
> 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.
https://math.stackexchange.com/posts/183383/revisions