Hacker News Reader

Comment by mopierotti | Hacker News Reader

There are many comments saying that one infinity can be larger than another because a bijective mapping can't be formed, but why does the presence of a mapping imply anything about the "size" of an infinity? For any infinite set, you could select unique values out of them indefinitely.

From my uninformed perspective, this seems like a co-opting of the word "size" to mean something different than its typical usage.

View on HN

Once you get to infinities, you can no longer denote the "size" of a set using naturals numbers, which is the typical usage of the word "size" (there are three apples in my basket and three is a natural number).

So to me this is just quibbling about the definition of the word "size" which isn't a productive conversation. Stop calling it "size" and give it a specific terminology ("cardinality") instead and the whole unintuitive naming problem is sidestepped.

You can even give in a little more without accepting the blatant takeover of "bigger": accept that there are different qualities in infinite comparisons. A difference in cardinality can certainly be considered a stronger difference than everything mappable, but denying infinites like "number of points on an infinite line" it's smaller-than relative to "number of points on two infinite lines" is just ridiculous. It's snobbish, pure vanity.

My point is that intuitive but imprecise naming misleads people. There's no way to talk about "number of points on an infinite line" because there isn't a specific natural number that you can find to denote the number of points here. Infinity is not a number.

That's why we need a proper concept of cardinality.

How would you well-define the "typical" usage of "size". The bijective mapping is completely consistent with our daily understanding for finite quantities, it's only in the infinite realm where it "feels weird" but those are just feels man.

I would say the number of items in a set, so by that logic the number of items in every type of infinite set would each seem to be infinity.

Maybe where I'm struggling is that I'm not familiar with why this notion of differently sized infinities is useful.

Defining the number of items in a set requires the existence of natural numbers in the first place. (In typical set theory, people start with the existence of sets and then define natural numbers from sets.) And it doesn't help when dealing with sets that are as numerous as the natural numbers, or more.

That said it's not wrong to lump together all infinite sets and say their size is infinite. That's how third graders understand the size of a set anyways. It just isn't precise.

The clearest example is probably the diagonalization argument. Suppose you have a complete, infinite list of real numbers. You can construct a number by taking the i'th digit of the i'th number and changing it to a different digit. This number is not on the list, and yet it is still a real number.

There are four possible responses to this argument. The first is to accept that this means that there are infinite sets which have different fundamental properties (the "infinite" in a "real number has an infinite number of digits" can't be iterated the same way as the "infinite" in the "infinite number of real numbers"), and the way these differ is labeled the "size" of the infinite set. The second is to object to definition of a real number (which has other repercussions in other branches of mathematics). The third is to object to the ability to iterate over an infinite set (essentially, finitism). The final is to object to the idea of an infinite set in the first place (essentially, ultrafinitism).

The response to Cantor's proof of the uncountability of real numbers was basically for mathematicians to explore all the different responses, and ultimately, the first response is the one that is accepted by the majority of mathematicians, although some still work under models that object to the proof's correctness in some fashion.

> the number of items in a set,

That's a good start. Now we need to precisely define "number of" and "in".

Suppose I put a few bonbons on a plate in front of you. How would you assign "the number" of items in the "set of bonbons on the plate in front of you"?

If you couldn't count, you could still figure out that both of your hands had the same number of fingers by matching each with a corresponding finger on the other hand. In other words there exists a bijection between the set of fingers on your right hand and the set of fingers on your left hand. Same reasoning can be applied to arbitrary sets, including infinite ones.

For finite sets, bijection is equivalent to counting the number of elements. A set of size N has an 1-to-1 mapping to the set {1,...,N}. For infinite sets, counting no longer makes sense but bijection does. From this point of view, the bijection trick is a way to extend the usual notion of set size, so that it also works for infinite sets.

That said, it's certainly not an "obvious" idea and in fact it took many years until it was widely adopted by the mathematical community.

There is a reason mathematicians prefer to talk about 'cardinality' rather than size.

Anyway if you want a set to be at least as big as its subsets and consider them to be of equal size when they're isomorphic then you kind of end up with cardinality as a notion of size. In some sense it's simply the best notion of size we have if all you have is the structure of sets.

There are of course other structures you could choose, like topological spaces, vector spaces etc. Those can fail to be isomorphic even when the underlying sets are, so you get a richer notion of 'size'.

> but why does the presence of a mapping imply anything about the "size" of an infinity?

It is used like this because it corresponds to an intuitive property of size. If I say that set X is larger than set Y, it comes naturally to assume that, if I were to lay out their elements one by one in pairs, at some point I would run out of elements from Y but still have more elements in X.

For example, even without knowing how many fingers I have, I can check whether there are more pebbles on a beach than fingers on my hand by putting a pebble on every finger. If there are no more pebbles and I have free fingers, the size of the set of fingers was actually larger than the set of pebbles.

And while of course I would never finish if I started doing this with the naturals and the rationals, I can still prove that it can be done if given infinite time; but that, given infinite time, when comparing the naturals to the reals in the same way, we would run out of naturals and still have more reals left.

> but why does the presence of a mapping imply anything about the "size" of an infinity?

Merely by definition.

>For any infinite set, you could select unique values out of them indefinitely.

Yes, but if you have a bijection between elements of that set and another, they're still the same size. Consider the strictly positive integers and the strictly negative integers: for any x, there's exactly one corresponding -x. Both sets are infinite, but they're the same size. Contrast that with, for example, the reals and the natural numbers: for each natural number n, there's not a corresponding real number but rather an infinite number of reals in [n, n+1). The sets are not the same size.

The existence of a bijection is 7indeed just a possibility to define "size". But since it leads to counterintuitive results (some sets have bijections to proper subsets of themselves) this is hardly the definition of our intuitive concept of size. It leads also to many mathematical paradoxes, in fact most mathematical paradoxes involve infinities and this definition of size, e.g. the Ross–Littlewood paradox and the Banach–Tarski paradox.

The reals are a superset of the integers, and a bijective mapping cannot be formed between the two, thus there are "more" elements in the set of reals than the set of integers.

It's worth noting that R=2^N: reals is the set of all subsets of integers, simply because any real in binary form appears as a sequence of 1s and 0s that select a subset of N. And for some reason it's not possible to know if there's anything in between N and 2^N. This makes me think that infinite sets grow in discrete exponential jumps: N, 2^N, 2^R and so on. N seems to be the smallest infinite set.

What you described is called Continuum hypothesis[1]. Surprisingly it cannot be proven to be either true or false from(is independent of) ZFC set theory.

[1] https://en.m.wikipedia.org/wiki/Continuum_hypothesis

Indeed, and nowadays set theorists have rich experiences both in worlds where the Continuum Hypothesis holds and in worlds where it does not.

I tried to explain the resulting "multiverse philosophy" (not really related to the idea of physical alternate universes) here: https://iblech.gitlab.io/bb/multiverse.html

Reply on news.ycombinator.com