3 ms·
> 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 a
by rtkwe 4y ago
> 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).
http://www.cwladis.com/math100/Lecture5Sets.htm#:~:text=the%20natural%20numbers%3F-,The%20Cardinality%20of%20the%20Set%20of%20Rational%20Numbers,-We%20recall%20that 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 https://math.stackexchange.com/posts/183383/revisions
- hallucy 4y agoThis is literally the point of the comment. 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).
- deleted 4y ago[deleted]
- jimsimmons 4y agoThat’s not what GP says though. They say their last statement is correct when it’s not. There are only two types of infinities: countable and uncountable. Both reals and rationals are not countable
- Others 4y agoThere are more than two kinds of infinities. Consider the set of all subsets of the real numbers. Also the rationals are countable by diagonalization.
- LanceH 4y agorationals are countable
- Twisol 4y ago> 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.)
- jimsimmons 4y agoThanks. A suspicion lingered as soon as I wrote that comment. I guess I was going off of some YouTube video. Now I see rationals are countable. 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?
- neonskies 4y ago> 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.
- rtkwe 4y agoI 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.
- deleted 4y ago[deleted]
- deepsun 4y agoAll of them are incorrect except for the last one.
- cubefox 4y ago> 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.
- rtkwe 4y agoThat'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.
- cubefox 4y agoIt'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.