Paradox: Creating an uncountable set of natural numbers

104 Views Asked by At

Consider the following (contrived) way of enumerating and counting the natural numbers.

Step 1.
Enumerate the first numbers 0 and 1. These are all the numbers less than $2^1$. Collect these numbers in a set $A_1=\{0, 1\}.$

Step $k$.
In step $k$, beginning with $k=2$ after step 1, continue the previous enumeration with the numbers from $2^{k-1}$ up to and excluding $2^k$. Collect all the numbers in a set: $A_k=\{j: j\lt 2^k\}.$ Note that the cardinality (number of members) of $A_k$ is $2^k$.

Note that
(a) The sets $A_k$ can be viewed as a sequence of sets $(A_k)$ with increasing index $k=1,2,\dots$
(b) The successive cardinalities of $(A_k)$ can be viewed as a sequence of natural numbers $(s_k)$ with increasing index $k=1,2,\dots$; where $s_k=2^k$.
(c) It takes an infinite number of steps to enumerate all the natural numbers. So $k$ must approach infinity.

The final cardinality of the completed set of all natural numbers is then
$$\lim_{k\to\infty}s_k= \lim_{k\to\infty}2^k;$$ Using cardinal exponentiation, and observing that countable infinity has the cardinal number $\aleph_0$, i.e. $k\to\aleph_0$, the limit appears to become $$\lim_{k\to\aleph_0}2^k =2^{\aleph_0},$$ which is an uncountable cardinal number.

But we only enumerated all the natural numbers. They are supposed to be countable.

How is this paradox resolved? There must be at least one logical error somewhere.


Update: Thanks for all comments and answers. The evaluation of the limit above is not valid.

Follow-up question: What is a correct way to perform the computation of the limit stated above: $$ \lim_{k\to\infty}2^k=? \lim_{k\to\aleph_0}2^k \ ? $$

First off, is the second form a well-formed expression at all? (I.e. is it valid to apply limits to cardinals?)

Second, (when) is it valid to transform "$\infty$" to a transfinite number such as $\omega$ (ordinal) or $\aleph_0$ (cardinal)? (My understanding is that "$\infty$" symbolises "[increase] forever, indefinitely" rather than any particular transfinite end value.)

Third, how does one reason towards the correct result, which in this case ought to be $$ 2^\omega = \omega = \aleph_0 \ ? $$

$2^k$ originates from cardinality. It is less obvious whether the index variable $k$ should be ordinal or cardinal.

Could one say that the original logical error was in thinking that $k$ is a cardinal when it should have been ordinal in the context of this example?