[hallucy]

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

[jimsimmons]

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

[Twisol]

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

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?

[Twisol]

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.

[jimsimmons]

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.

[skissane]

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

[jimsimmons]

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

[rtkwe]

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

[Others]

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.

[LanceH]

rationals are countable