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.