I would like to preface by saying that I have no significant experience working with set theory, so I'm probably making an intuitive mistake. I have figured out where the mistake probably is, but I can't figure out why it IS a mistake. I figured that this was the best outlet to ask my question.


I was reading about the Continuum Hypothesis on Wikipedia recently, particularly about the fact that it's undecidable in ZFC -- which means that it is undecidable whether or not there is an infinite set whose size is strictly between that of the natural numbers and that of the real numbers. Now, intuitively, a proof that it cannot be disproved would immediately give way to the fact that no counterexample could be constructed (for such a counterexample would disprove it, which is impossible), and thus it must therefore be true. But that's not where I'm going with this.
Cantor proved that the rational numbers are countable -- that there exists a counting method such that, given any integer, you could determine the unique rational number which corresponds to it, and given any rational number, you could determine the unique integer which corresponds to it. The proof is fairly cool, but that's not where I'm going, either. Essentially, this demonstrated that $\aleph\_0^2 = \aleph\_0$. Then, he went on to prove that all *algebraic* numbers were countable, which proved the stronger statement that for any finite *n*, $\aleph\_0^n = \aleph\_0$. But yet, the cardinality of the real numbers is still strictly greater.
He explicitly determined the cardinality of the real numbers as $2^{\aleph\_0}$, or, strictly speaking, for any $\alpha > 1, \mathfrak c = \alpha^{\aleph\_0}$, because, no matter which base you're in, the number of real numbers doesn't change. This means that the cardinality of the real numbers is strictly *exponential*, whereas the cardinality of the countable numbers is strictly *polynomial*.
This is where my confusion arises. If I construct a set whose size after an infinite number of steps is bounded by *any* polynomial, it is countable, whereas a set whose size is greater than *every* polynomial would *not* be countable.
The [Adleman–Pomerance–Rumely\_primality\_test](http://en.wikipedia.org/wiki/Adleman%25E2%2580%2593Pomerance%25E2%2580%2593Rumely_primality_test) has running time, for a given *n*, of $n^{O\log(\log(n))}$, which is of super-polynomial running time -- there exists no polynomial that is strictly greater than that function. However, it is also sub-exponential -- there exists no exponential function that is strictly *less* than it, either. Therefore, it exists between the polynomials and exponentials.
Using this, I can construct a set of numbers whose size after *n* steps is equal to $f(n) = n^{O\log(\log(n))}$ by appending approximately f'(n) unique values to the end of the set. I have now explicitly constructed an infinite set whose size is $\aleph\_0^{\log(\log(\aleph\_0))}$, have I not? And, as I said before, it is, eventually, larger than any set whose size grows polynomially. But it is also smaller than every set whose size grows exponentially.
Of course, it also turns out that this set is countable -- I can give you the numbers in the set, if you so wish. But that's only part of the problem.
Using the same method, I can also construct a set whose size grows exponentially, if I only change my function to $f(n) = 2^n$. I then append f'(n) unique values to the end of my set and, voila, as I take a countably infinite number of steps, namely $\aleph\_0$, the size of my set becomes $2^{\aleph\_0}$, the cardinality of the continuum -- but, as before, I can tell the *n*th item in my set, and if you give me any item in my set, I can tell you exactly where it lies.
**Thus is my question: What did I do wrong? Either I have shown that $2^{\aleph\_0} = \aleph\_0$, which is exceedingly unlikely, or my assumption that my new set's size is equal to $2^{\aleph\_0}$ is incorrect, and I cannot understand why.**
Any help would be appreciated, thanks!


--Gabriel Benamy





















Explicitly constructing an infinite set with particular size
The problem lies with your interpretation of the notation $2^{\aleph\_0}$ and $\aleph\_0^n.$ These do not mean that your set is constructed from finite sets with a specified rate of growth.


Let $A$ be the cardinality of a set. e.g. $A = 2$ or $A=\aleph\_0.$


$A^n$ is the cardinality of the n-fold cartesian product of a set with cardinality $A.$


$2^{A}$ is the cardinality of the power set, i.e. the set of all subsets, of a set with cardinality $A.$


Your interpretation in terms of rates of growth does not work. The reason for this notation is that when $A$ is finite, the arithmetic interpretation works. That is, if $S$ is a set with $k$ elements, then $S^n$ has $k^n$ elements, and there are $2^k$ subsets of $S.$


