What are the different sizes of infinity?

So whole numbers and odd numbers and rational numbers etc. are called countably infinite. We can prove that a set is the same size as those sets above, and therefore is countably infinite, by finding a bijection between the set we want to prove (call it the domain) and one of the sets I listed above (call it the codomain). A bijection means there is both an injection and a surjection. An injection means that no two elements in the domain correspond to the same element in the codomain. A surjection means that there is no element in the codomain that does not correspond to any element in the domain. And these terms only apply to functions, and the restrictions upon functions are that there is no element in the domain that doesn’t correspond to any element in the codomain, and there is no element in the domain that corresponds to more than one element in the codomain. Whew.

Check here for other discussion on this, as it confused me for awhile and it wasn’t until I got some jelly help that I felt I understood. I’m still a little rocky on it. I don’t think it’s supposed to feel intuitive.

A counterexample is real numbers. It is not an intuitive proof, but it is shown with a method called diagonalization. It’s an indirect proof – that is, you assume something that is not true and then show that this leads to a contradiction.

Assume you have an infinitely long list of numbers, and you claim that that that there are no real numbers between 0 and 1 that are not in your list. Because they are listable, they are presumed to be countably infinite. Well we can show this cannot be by using diagonalization. Here’s just an example:

1.) .2357
2.) .4516
3.) .5447
etc.

Now we want to prove that this list doesn’t contain all the real numbers by finding a number that isn’t in the list. Well, you can always do this, because you can pick the first digit of the first number, and choose a digit other than that for the first digit of your number. Say, 4. Then do the same on the second digit of the second number, etc. And now your number will necessarily differ from everything on the list in at least one digit.

The size of the set of real numbers (and I don’t know the proof for this) is actually the power set of the natural numbers. The power set is the set of all subsets of a set. So the magnitude of this infinity is 2 to the power of the magnitude of countable infinity. And then you can take the power set of THIS size of infinity, and get an even larger infinity. And there’s no limit to the number of times you can repeat this, which is why there are infinite infinities.

I don’t know the answer to your last question.

Following up on @Mariah‘s magnificent answer: If a set has cardinality N and its power set has cardinality N+1, then isn’t there a 1-to-1 correspondence between cardinalities & integers? That would make the “number of infinities” aleph-null. Or might there be an unknown number of cardinalities lying in-between those of a set and its power set, complicating the question? Also, is bijection the same as 1-to-1 correspondence?

I remember someone saying something about the number of possible curves on a plane being a higher order of infinity than real numbers. Is this true?

After doing some research, I have found that the answer to my last question might be unsolvable, literally.

http://en.wikipedia.org/wiki/Continuum_hypothesis

This is a link to the wiki article on the continuum hypothesis. In a nutshell, it seems like the hypothesis states “there is no size of infinity strictly between the integers and the reals.” It was proven to be both unprovable and undisprovable in the ZFC set theory. This is Gödel doing what Gödel does best: messing stuff up.

Yeah good thoughts there @gasman and unfortunately I don’t know the answers.

One to one is a term used to describe injection. Bijection is more restrictive – both one to one and onto (“onto” describes surjection).

@Mariah Yeah, now I remember why I always preferred applied math over pure lol.

The number of curves that can be drawn on a plane is a larger infinity than the set of real numbers.

PS A similar question was asked last year

In most real-life applications we only need two kinds of infinities, one we can create a list for and for one we can’t. As far as I know there’s an infinite set of different kind of infinities. So there’s for example also a larger infinity than that for the number of curves that can be drawn on a plane.

Determining the cardinality of the set of all infinities is problematic. We could say that the set of all sets must be the largest infinity. The problem, known as Cantor’s Paradox, is that the set of all sets belongs to its own power set, which would imply that its magnitude is less than its own magnitude.

Infinity does not have a size. It is exactly that. Infinity. It is endless and cannot possibly be measured by the fragile human mind. If we knew all that is in the infinite cosmos surrounding us, our minds would be driven to madness. We would fear all and hold not dear our lifes.

@LostInParadise I’m not 100% convinced that Cantor’s paradox applies to counting the number of infinities.

If all of the different sizes of infinity can be described as aleph-null, aleph-one, aleph-two, etc, then the number of infinities will clearly be aleph-null, without creating a paradox. This is not a set of all possible sets, merely a set of all possible unique sizes of infinity.

You can’t simply combine two infinities to create a new one, for example
aleph-null + aleph-one = aleph-one
If this were possible, then I think that this would be a case of Cantor’s paradox.

However, this assumes that there aren’t infinities between the other infinities.

Also, since it seems like it is possible to always order infinities in increasing size, this would mean that we could always assign each infinities a real number. If one infinity is between two others when comparing size, it would be assigned a real number between the real numbers that are assigned to those other two infinities.

Does this make sense to you?

If so, and assuming the transitive property of inequality, I would suspect that the number of infinities in no larger than aleph-one.

Does the set of all sets belong to any of the enumerated infinities? It can’t because none of them belong to their own power set.

I found this site (skip to the last section), which I confess I do not fully understand, but it seems to indicate that the number of infinities is beyond description.

For every set X, I denote its cardinality and its power set by |X| and P(X), respectively.

The set of all cardinalities does not exists; i.e. there are too many cardinalities to be fit into a set.

Assume otherwise; i.e. let A be a set consisting of a single set from each possible cardinality.

Let B be the union of all sets in A. Let C be an element of A. By definition, C is a subset of B, therefore |C| =< |B|. This means cardinality of B is more than or equal to the cardinality of C for every C in A. Therefore, since A consists of a set from each possible cardinality, |B| is the largest cardinality.

This is a contradiction because |P(B)| > |B|.

@LostInParadise, I am not sure what you mean by “the set of all sets”, the collection of all sets is not a set.

@LostInParadise never mind. It seems you are showing the collection of all sets is not a set.

@BonusQuestion For some reason, your proof made sense to me.

Ok, so if it is not possible to have a set of all of the infinities, is it possible to simply know the number of different infinities?

As in, is there a set A such that the members of the set have a one-to-one correspondence with the different cardinalities? This would avoid the above paradox because set A does not actually contain the different infinities. This is more in line with what I was trying to ask, but now it is specified better.

@PhiNotPi, I am not sure I understand what you are asking. Isn’t what you are asking precisely what I proved above? What I proved above is that the set of all “infinities” does not exists. I chose exactly one set from each given cardinality.

You cannot make sense of the “number of all infinities” unless you can put them in a set and then talk about the cardinality of this set. So, no you cannot talk about the “number” of all infinities.