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

In summary, according to the author, the set after adding an infinite number of elements will have an uncountable cardinality.
  • #1
Anixx
80
12
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.
 
Physics news on Phys.org
  • #2
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.
 
Last edited:
  • Like
Likes Jarvis323
  • #4
Anixx said:
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.
 
  • #5
@ 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.
 
Last edited:
  • #6
The question was not about finding the volume, so it seem your post is missing the point.
 
  • #7
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.
 
  • #8
@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.
 
  • #10
phyzguy said:
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.
 
  • #11
Anixx said:
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".
 
Last edited:
  • #12
Anixx said:
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.
 
  • #13
phyzguy said:
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##?
 
  • #14
FactChecker said:
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.
 
  • #15
FactChecker said:
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.
 
  • #16
Anixx said:
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?
 
  • #17
Thread closed. The question in post #1 has been asked and answered.
 
  • Like
Likes jim mcnamara

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

1. What does it mean to add an exponential number of elements?

Adding an exponential number of elements means increasing the number of elements in a set or group by a factor of a constant value raised to a power. This results in a rapid growth in the size of the set.

2. How is the final cardinality affected by adding an exponential number of elements?

The final cardinality, or the total number of elements in the set, will increase significantly when adding an exponential number of elements. This is because the exponential growth leads to a rapid increase in the size of the set.

3. Is there a limit to the final cardinality when adding an exponential number of elements?

There is no limit to the final cardinality when adding an exponential number of elements. As long as the exponential growth continues, the size of the set will continue to increase without any upper bound.

4. How does the rate of growth differ between adding an exponential number of elements and a linear number of elements?

The rate of growth is much faster when adding an exponential number of elements compared to a linear number of elements. This is because the exponential growth leads to a rapid increase in the size of the set, while the linear growth increases at a constant rate.

5. What are the potential implications of adding an exponential number of elements?

Adding an exponential number of elements can have significant implications, especially in fields such as computer science and mathematics. It can lead to exponential growth in data and can also have practical applications in fields such as finance and population growth studies.

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
9
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
6
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
21
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
3
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
4
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
5
Views
1K
  • Set Theory, Logic, Probability, Statistics
2
Replies
55
Views
5K
  • Set Theory, Logic, Probability, Statistics
Replies
4
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
20
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
548
Back
Top