Add an exponential number of elements, what will be the final cardinality?

[Anixx]

Suppose we construct a set, adding at each step a polynomial number of elements.
My impression that after we do countably infinite number of steps, the set will have countably infinite cardinality.

But what happens if we add exponential number of elements each step?

For instance, on step 0 we add 1 element, on step 1 we add 2 elements, on step 2 we add 4 elements, on step 3 we add 8 element, on step n we add 2^n elements?

For instance, by adding a binary register after the fractional point in a number we add 2^n elements:

One register after point, 2 elements:

0.0
0.1

Two registers after point, 4 elements:

0.00
0.01
0.10
0.11

and so on. After countably infinite steps we will have all numbers from the range [0,1].
But it has cardinality of continuum.

So, the question is, after adding 2^n elements on n-th step countably infinite times, will we have a set of uncountable cardinality?

Or, in other words, can we say that polynomial functions have germ at infinity, in a sense corresponding to countable infinity while an exponential function has a germ, corresponding to uncountable infinity?
Notice, the cardinality of continuum is often designated as $2^{\aleph_0}$ which hints this maybe the case.

I mean, yes, if we count all these numbers in the order of the steps, we would have only rational numbers, which is countable, but after we ALREADY COMPLETED the infinite number of steps, we not necessarily should count the numbers in the order of steps and we will have numbers with infinite expansions as well by that time.

P.S. Some people say that even after infinite number of steps the numbers with infinitely long binary representations are still not included. I cannot see, why.

PPS. Some other people said this is by definition. In that case I am interested to know what is the justification of such definition.

 

[SSequence]

We can write $B_\alpha$ (where $\alpha \in \mathrm{Ord}$) to mean the set denoting: "all binary strings of length equal to $\alpha$" . In that sense, $B_\omega$ will have the cardinality of real numbers. We have a 1-1 correspondence between the subsets of $\mathbb{N}$ and elements of $B_\omega$ .

Similarly, we will have elements of $B_{\omega_1}$ in 1-1 correspondence with subsets of $\omega_1$. If CH is true the cardinality of set $B_{\omega}$ will be $\aleph_1$ and if GCH is true then the cardinality $B_{\omega_1}$ will be $\aleph_2$. In fact if CH is true for example, then for any arbitrary $\alpha<\omega_1$ , the cardinality of the set $B_\alpha$ will be $\aleph_1$ again.

 

[FactChecker]

The set, S, consisting of the union of a countable number of countable sets is countable. It is simple to show how they can all be counted. So S is still countably infinite. (see Theorem: (Assuming the axiom of countable choice) The union of countably many countable sets is countable. )

 

[FactChecker]

For instance, by adding a binary register after the fractional point in a number we add 2^n elements:

One register after point, 2 elements:

0.0
0.1

Two registers after point, 4 elements:

0.00
0.01
0.10
0.11

and so on. After countably infinite steps we will have all numbers from the range [0,1].

No. There is no step where you have counted anything that requires infinite digits to specify.

P.S. Some people say that even after infinite number of steps the numbers with infinitely long binary representations are still not included. I cannot see, why.

Have you looked at Cantor's proof? That is important in this discussion.

PPS. Some other people said this is by definition. In that case I am interested to know what is the justification of such definition.

I'm not sure what definition you may be referring to.

 

[SSequence]

@ OP
I saw the MO version of your question, which I presume(?) is loosely related to this idea. Tbh, I didn't understand much of your idea.

I did find one mildly interesting point that I can add with regards to one of things you wrote:

The question is, can we somehow introduce a concept similar to numerocity to the uncountable sets, in such a way that it would reflect the volume of those sets? In other words, the set [0,2) should have twice he numerocity of [0,1). This is desirable...

Thinking about the idea of "volume" in a casual manner, what about the following ...

Suppose we have a $S \subseteq \mathbb{R} - \mathbb{R}^-=\{r \in \mathbb{R}|r \geq 0\}$ as a subset of non-negative real numbers. To calculate the volume of the set, identify all pair of points $a,b \in \mathbb{R} - \mathbb{R}^-$ satisfying the following conditions:
"$b>a$
$(a,b) \in S$
And there doesn't exist a $c>b$ such that the following is true:
$(a,c) \in S$
Nor there doesn't exist a $d<a$ such that the following is true:
$(d,b) \in S$"

======

Now starting from the real number $0$ if we write the (transfinite) list of all the $a$'s (and the corresponding $b$'s) in the order in which we encounter them:
$a_0$, $a_1$,... $a_i$,... (goes till some ordinal $\alpha$) ******1******
$b_0$, $b_1$,... $b_i$,... (goes till some ordinal $\alpha$) ******1******

For each stage defining, $d_i=b_i-a_i$ we have a length function $f:\alpha \rightarrow \mathbb{R}^+$ defined by $f(i)=d_i$. Now I have extremely limited in analysis knowledge, but I think if we describe a reasonable way to define supremum of the "partial sums (which might also involve supremum) of the list (described by $f$)" then we have a kind of metric for volume?

===================================

Though the the above is still quite limited (and perhaps not particularly useful). Obvious subsets such as:
[0,1) union [2,4) union [5,8) union [9,13),...
will still give undefined answer. So using above method, these sets will not get distinguished from the set: $\mathbb{R}-\mathbb{R}^-$.*******1******
Sorry I am being dumb, nevermind. The enumeration isn't guaranteed to lead to an ordinal (because of infinite descents in some subsets $S$). So the idea is even less useful than I thought.

 

[Anixx]

The question was not about finding the volume, so it seem your post is missing the point.

 

[SSequence]

Alright. I guessed that perhaps the question had some relation to it (since I didn't understand it).

Nevertheless, a certain point came to my mind and I mentioned it. This is a discussion forum (and not a strict question/answer forum) so some degree of deviation from the main question/topic is fine. Anyway, I see your point.

 

[phyzguy]

@Anixx , didn't post #3 from @FactChecker answer your question? Even with adding an exponentially growing number of elements at each step, the final set is still countably infinite.

 

[SSequence]

@phyzguy
Here is the corresponding mathoverflow thread mentioned in post#5 (for the sake of reference): https://mathoverflow.net/questions/...ut-counting-reals-somehow-put-on-solid-ground

 

[Anixx]

Even with adding an exponentially growing number of elements at each step, the final set is still countably infinite.

The set would be countably infinite only after finite number of steps. After infinite number of steps, we have an infinite binary representation with any digit at each position. It would include any real number between 0 and 1, including those with infinite binary representations.

 

[FactChecker]

The set would be countably infinite only after finite number of steps. After infinite number of steps, we have an infinite binary representation with any digit at each position. It would include any real number between 0 and 1, including those with infinite binary representations.

For any number that you counted, I can give you an infinite set that you missed counting. Everything you count ends in a finite number of digits. Suppose you count a number, r, that ends after (for instance) 10 digits. Attach any of the never-ending sequences onto it from digit 11 onward. None of those numbers ever get counted, and there are many more uncounted numbers than counted numbers. If you say that they are counted, which step are they counted on? Please be specific.

EXAMPLE: You say that the number .1010101010101010... would be counted. If so, there must be one specific step that it gets counted on. If it was counted, that counting number was assigned in a finite step, not in some vague "infinite time".

 

[phyzguy]

The set would be countably infinite only after finite number of steps. After infinite number of steps, we have an infinite binary representation with any digit at each position. It would include any real number between 0 and 1, including those with infinite binary representations.

Not true. As long as the number of steps is countably infinite, the total set would still be countably infinite.

 

[Anixx]

As long as the number of steps is countably infinite, the total set would still be countably infinite.

Do you claim, countably infinite number of digits after the point is not enough to represent $\pi$?

 

[Anixx]

Everything you count ends in a finite number of digits.

Only before I completed infinite number of steps, and so added infinite number of digits.

 

[Anixx]

None of those numbers ever get counted

Even after I added infinite number of digits? I disagree. After I added infinite number of digits, all possible infinite sequences of digits are counted.

 

[FactChecker]

Even after I added infinite number of digits? I disagree. After I added infinite number of digits, all possible infinite sequences of digits are counted.

Suppose a number, r=.101010101010101010..., is counted and it is counted as number $N$. Since $N \lt \infty$, it must have been counted in a finite step, $S \lt \infty$, where the count reached $N$. Using your method, how can that happen?

 

[Mark44]

Thread closed. The question in post #1 has been asked and answered.