Comment by rtkwe | Hacker News Reader

Comment by rtkwe | Hacker News Reader

Parent Full thread

> 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%...

> 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

This 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).

That’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

> 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.)

Thanks. 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?

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.

This basically made my day/week. Thanks a ton!

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.

> 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.

We shall wait for the day when a highly competent chatbot can explain this to us peasants

Rationals are countable. It's actually pretty neat if hard to express as a function, but that's not required.

http://www.cwladis.com/math100/Lecture5Sets.htm#:~:text=the%...

There are more than two kinds of infinities. Consider the set of all subsets of the real numbers.

Also the rationals are countable by diagonalization.

rationals are countable

> 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.

All of them are incorrect except for the last one.

Reply on news.ycombinator.com