Can someone explain to me how there can be different kinds of infinities?
I was reading "The man who loved only numbers" by Paul Hoffman and came across the concept of countable and uncountable infinities, but they're only words to me.
Any help would be appreciated.
Suppose no one ever taught you the names for ordinary numbers. Then suppose that you and I agreed that we would trade one bushel of corn for each of my sheep. But there's a problem, we don't know how to count the bushels or the sheep! So what do we do?
We form a "bijection" between the two sets. That's just fancy language for saying you pair things up by putting one bushel next to each of the sheep. When we're done we swap. We've just proved that the number of sheep is the same as the number of bushels without actually counting.
We can try doing the same thing with infinite sets. So suppose you have the set of positive integers and I have the set of rational numbers and you want to trade me one positive integer for each of my rationals. Can you do so in a way that gets all of my rational numbers?
Perhaps surprisingly the answer is yes! You make the rational numbers into a big square grid with the numerator and denominators as the two coordinates. Then you start placing your "bushels" along diagonals of increasing size, see wikipedia.
This says that the rational numbers are "countable" that is you can find a clever way to count them off in the above fashion.
The remarkable fact is that for the real numbers there's no way at all to count them off in this way. No matter how clever you are you won't be able to scam me out of all of my real numbers by placing a natural number next to each of them. The proof of that is Cantor's clever "diagonal argument."
How there can be different kinds of infinities?
This is very simple to see. This is because of:
Claim: A given set $X$ and its power set $\mathcal{P}(X)$ can never be in bijection.
Proof: By contradiction. Let $f$ be any function from $X$ to $\mathcal{P}(X)$. It suffices to prove $f$ cannot be surjective. That means that some member of $\mathcal{P}(X)$, i.e. some subset of $X$, is not in the image of $f$. Consider the set:$$T=\{x\in X:x\not \in f(x)\}.$$For every $x$ in $X$, either $x$ is in $T$ or it is not. If $x$ is in $T$, then by definition of $T$, $x$ is not in $f(x)$, so the set $T$ can not be the set $f(x)$ (because $x\in T$ but $x\not \in f(x)$). On the other hand, if $x$ is not in $T$, then by definition of $T$, $x$ is in $f(x)$, so again the set $T$ can not be the set $f(x)$. We just proved that $T$ is NOT $f(x)$ for any $x$, and so $f$ is not surjective. $\mathsf{QED}$
Thus take any infinite set you like. Then take its power set, its power set, and so on. You get an infinite sequence of sets of increasing cardinality (here I am skipping a little; but a use of the Cantor-Schröder-Bernstein theorem will fix things).
A countably infinite set is a set for which you can list the elements: $a_1,a_2,a_3,\ldots$.
For example, the set of all integers is countably infinite since I can list its elements as follows:$$0,1,-1,2,-2,3,-3,\ldots .$$So is the set of rational numbers, but this is more difficult to see. Let's start with the positive rationals. Can you see the pattern in this listing?$$\frac{1}{1},\frac{1}{2},\frac{2}{1},\frac{1}{3},\frac{2}{2},\frac{3}{1},\frac{1}{4},\frac{2}{3},\frac{3}{2},\frac{4}{1},\frac{1}{5},\frac{2}{4},\ldots .$$(Hint: Add the numerator and denominator to see a different pattern.)
This listing has lots of repeats, e.g. $\dfrac{1}{1}=\dfrac{2}{2}$ and $\dfrac{1}{2}=\dfrac{2}{4}$. That's ok since I can condense the listing by skipping over any repeats.$$\frac{1}{1},\frac{1}{2},\frac{2}{1},\frac{1}{3},\frac{3}{1},\frac{1}{4},\frac{2}{3},\frac{3}{2},\frac{4}{1},\frac{1}{5},\ldots .$$Let's write $q_n$ for the $n$-th element of this list. Then $0,q_1,-q_1,q_2,-q_2,q_3,-q_3,\ldots$ is a listing of all rational numbers.
A countable set is a set which is either finite or countably infinite; an uncountable set is a set which is not countable.
Thus, an uncountable set is an infinite set which has no listing of all of its elements (as in the definition of countably infinite set).
An example of an uncountable set is the set of all real numbers. To see this, you can use the diagonal method. Ask another question to see how this works.
The basic concept is thus:
The key to seeing this is using the 'diagonal slash' argument as originally put forward by Cantor. With a countable infinity, you can create a list of all the items in the set and assign each one a different natural number. This can be done with the naturals (obviously) and the complete range of integers (including negative numbers) and even the rational numbers (so including fractions). It cannot be done with the reals due to the diagonal slash argument:
This shows a difference between two obviously infinite sets and leads to the somewhat scary conclusion that there are (at least) 2 different forms of infinity.
Infinity is an overloaded term that can mean many things.
One common non-mathematical use of infinity is to refer to everything in the universe. This is not what mathematicians mean when they say infinity. That would be a kin to the set of all sets, which is a paradoxical concept that is not part of mathematical discourse.
Mathematicians will use infinity as a way to represent a process that continues indefinitely. This is a kin to saying "take the limit as n goes to infinity", which is close to saying "continue this process indefinitely."
Infinity is also use infinity to talk about size. All sets are either infinite or finite.
The story doesn't stop there. There is something fundamentally different about sets like the points on a line, where there are no holes, and sets like the integers where there are holes. They are both infinite but one seems denser then the other.
That's where whole countable uncountable thing comes in. Infinite sets have a size, but it is not a number in the traditional sense. Its more like "relative size". Bijections are how we determine size for infinite sets, which are explained well on this page, so I won't repeat the explanation.
A more in-depth, but still understandable explanation is given in Computability and Logic by George Boolos.
You can see that there are infinitely many natural numbers $1,2,3,\ldots $, and infinitely many real numbers, such as $0$, $1$, $\pi$, etc. But are these two infinities the same?
Well, suppose you have two sets of objects, e.g. people and horses, and you want to know if the number of objects in one set is the same as in the other. The simplest way is to find a way of corresponding the objects one-to-one. For instance, if you see a parade of people riding horses, you will know that there are as many people as there are horses, because there is such a one-to-one correspondence.
We say that an set with infinitely many things is countable, if we can find a one-to-one correspondence between the things in this set and the natural numbers.
E.g., the integers are countable: $1\leftrightarrow 0$, $2\leftrightarrow -1$, $3\leftrightarrow 1$, $4\leftrightarrow -2$, $5\leftrightarrow 2$, etc. gives such a correspondence.
However, the set of real numbers is NOT countable! This was proven for the first time by Georg Cantor. Here is a proof using the so-called diagonal argument.
This is an answer to the following question marked as duplicate which redirects here: "I've known for some time that infinitary numbers can be different in order, such as the integers (countable), and the real numbers (uncountable). I read that you can always find a higher order of infinity given any order of infinity. Since infinity is the limit of the natural numbers under the successor function, I would like to know if there is a similar concept for orders of infinity under taking power-sets, if there is a sort of "super-infinity", a limit to the orders of infinity."
Yes, there is such a concept: the smallest strongly inaccessible cardinal. Roughly, it is the smallest uncountable infinity that can not be reached by taking either unions or power sets of infinities under it, see here http://en.wikipedia.org/wiki/Limit_cardinal. Existence of such cardinals is widely believed to be independent of the standard axioms of set theory (ZFC), in other words it can neither be proved nor disproved from them. However, there are many works, where people postulate existence of strongly inaccessible cardinals and see what they can derive from it.
Of course, even with such a postulate you still don't get the "infinity of all infinities", such a concept is self-contradictory according to the Russel paradox, but the smallest strongly inaccessible cardinal is in a similar relation to the ones under it regarding power sets as the countable cardinal is regarding successors and unions.
Just simple intuitive explanation.
How many Natural (Integers) Numbers could you count? There are infinitely many, yet you can count them. It's called Countable Set.
How many Real Numbers are there?
Infinitely as well (Since at least every Natural Number is a Real Number).
Yet you won't be able to count them (Intuitively, Let's say you name a number the first, then find the second, I can, for sure, find a number in between, their average which is Real Number as well).
It's called Uncountable Set.
What you are after is how we define how big is a given set.
Then you should look for Cardinality.
