# Thread: set of all finite subsets of a continuum has cardinality continuum

1. ## set of all finite subsets of a continuum has cardinality continuum

Hi. I'm learning about equivalent sets in a real analysis class and am struggling a bit with the abstractness of it. Would someone be able to explain in very basic language how to:

Prove that the set of all finite subsets of a continuum has the cardinality of continuum.

I guess I'm not totally sure what a continuum is. Is it just any set with a bijection between it and the set of real numbers?

From what I know a set has cardinality of continuum if it is equivalent to the set of all sequences whose elements are the digits 0 and 1 (which is equivalent to the set of real numbers).

So I need a way to write each finite subset as a sequence of 1s and 0s to create a bijection between it and the set of all sequences whose elements are the digits 0 and 1?

I'm definitely confused about where to start, and would really appreciate some help!

Thanks!

2. Originally Posted by minivan15
Hi. I'm learning about equivalent sets in a real analysis class and am struggling a bit with the abstractness of it. Would someone be able to explain in very basic language how to:

Prove that the set of all finite subsets of a continuum has the cardinality of continuum.

I guess I'm not totally sure what a continuum is. Is it just any set with a bijection between it and the set of real numbers?

From what I know a set has cardinality of continuum if it is equivalent to the set of all sequences whose elements are the digits 0 and 1 (which is equivalent to the set of real numbers).

So I need a way to write each finite subset as a sequence of 1s and 0s to create a bijection between it and the set of all sequences whose elements are the digits 0 and 1?

I'm definitely confused about where to start, and would really appreciate some help!

Thanks!
I could prove this whole thing for you...but I have a feeling that's not what you want.

So, what exactly DO you want?

3. Well ideally I would like to understand how to prove it myself. If you could show me your proof with explanations that might be very helpful! If you are unwilling to do that, I guess the next best thing would be a very good starting point to answering the question!

Thanks!

4. Originally Posted by minivan15
Well ideally I would like to understand how to prove it myself. If you could show me your proof with explanations that might be very helpful! If you are unwilling to do that, I guess the next best thing would be a very good starting point to answering the question!

Thanks!
Well, my point was that I could either give you a one-line proof, but that depends on how much you know. If you really want to understand the one-line proof I may have to prove quite a few laborious lemmas. What's your background in cardinal numbers?

5. I'm afraid I don't know any of the cardinality symbols (e.g. aleph-naught), or how to operate on them (I've been researching my problem and have seen stuff about adding and subtracting cardinalities, but I haven't seen that stuff before).

I know Cantor's proof that R is uncountable. I can prove the set of all sequences whose elements are 0 and 1 is uncountable (basically the same method that Cantor used). I can prove that R is equivalent to this set. I've seen the Cantor-Bernstein-Schroeder Theorem. ...unfortunately that's about the extent of my knowledge.

If you are able to prove the result without using cardinality symbols, I'm sure I could follow. Maybe if you have a particular lemma that you want to avoid proving, you could mention the result and I can tell you if I understand it/ have seen it?

Thanks!

6. Originally Posted by minivan15
I'm afraid I don't know any of the cardinality symbols (e.g. aleph-naught), or how to operate on them (I've been researching my problem and have seen stuff about adding and subtracting cardinalities, but I haven't seen that stuff before).

I know Cantor's proof that R is uncountable. I can prove the set of all sequences whose elements are 0 and 1 is uncountable (basically the same method that Cantor used). I can prove that R is equivalent to this set. I've seen the Cantor-Bernstein-Schroeder Theorem. ...unfortunately that's about the extent of my knowledge.

If you are able to prove the result without using cardinality symbols, I'm sure I could follow. Maybe if you have a particular lemma that you want to avoid proving, you could mention the result and I can tell you if I understand it/ have seen it?

Thanks!
How about that the set of all reals is equipotent to the power set of the natural numbers.

7. Sorry, I haven't seen that.

In my class we've been working through a bunch of problems, and that hasn't come up yet. Is there a way to prove the result without using it?

8. Originally Posted by minivan15
Sorry, I haven't seen that.

In my class we've been working through a bunch of problems, and that hasn't come up yet. Is there a way to prove the result without using it?
I COMPLETELY misread your question. The set of all finite subsets of $\mathbb{N}$ is countable (has the cardinality of $\mathbb{N}$). Ok? So do you still want me to prove it?

9. Yeah, I would like to see a proof of the bold statement in my first post:

Prove that the set of all finite subsets of a continuum has the cardinality of continuum.

Another problem I want to do is:

prove that the set of all sequences of positive integers has cardinality continuum.

I'm hoping to see an explanation of one of these problems, and use the example to figure out how to do the other one. You can do whichever you'd like.

10. Originally Posted by minivan15
Yeah, I would like to see a proof of the bold statement in my first post:

Prove that the set of all finite subsets of a continuum has the cardinality of continuum.

Another problem I want to do is:

prove that the set of all sequences of positive integers has cardinality continuum.

I'm hoping to see an explanation of one of these problems, and use the example to figure out how to do the other one. You can do whichever you'd like.
How about an idea, and you try to prove the second one. It will be good for you. It can be shown pretty easily that the open unit interval has the same cardinality as the continuum, so think about numbers like $.12453145632147...$ don't they sort of remind you of $\{1,2,4,5,3,1,\cdots\}$.

11. yeah I actually did a problem where I had to come up with a bijection between R and (0,1). I came up with

f(x) = ( arctan(x) + pi/2 ) / pi

(hopefully that's right!) Anyways, finding a bijection between the two sets proves they are of the same cardinality.

And I see what you're saying... each sequence is like a decimal, so all of the sequences is like the all of the numbers in the interval (0,1). Since this interval has the same cardinality as R, and since the set of all sequences of positive integers is like the interval (0,1) (I'll write it up more mathematically), it has the same cardinality as R, therefore cardinality of the continuum!

Thanks for the great hint! hopefully that will give me an idea for the other one. Feel free to drop in another hint though

12. Originally Posted by minivan15
yeah I actually did a problem where I had to come up with a bijection between R and (0,1). I came up with

f(x) = ( arctan(x) + pi/2 ) / pi

(hopefully that's right!) Anyways, finding a bijection between the two sets proves they are of the same cardinality.
I'll take your word that's a bijection. A nice geometrical proof goes as follows. Take the interval and bend it up to form a semi-circle $C$. Draw a vertical line through $\frac{1}{2}$ and project from this line through $C$. You'll see that you hit one point on $C$ and one point on $\mathbb{R}$. This is then an injection. And since clearly the inclusion mapping $f0,1)\hookrightarrow\mathbb{R}" alt="f0,1)\hookrightarrow\mathbb{R}" /> given by $x\mapsto x$ is an injection the other way the Schroder-Bernstein theorem finishes the argument

And I see what you're saying... each sequence is like a decimal, so all of the sequences is like the all of the numbers in the interval (0,1). Since this interval has the same cardinality as R, and since the set of all sequences of positive integers is like the interval (0,1) (I'll write it up more mathematically), it has the same cardinality as R, therefore cardinality of the continuum!

Thanks for the great hint! hopefully that will give me an idea for the other one. Feel free to drop in another hint though
I'll try to think of a good hint, and get back to you!

13. Originally Posted by minivan15
Hi. I'm learning about equivalent sets in a real analysis class and am struggling a bit with the abstractness of it. Would someone be able to explain in very basic language how to:

Prove that the set of all finite subsets of a continuum has the cardinality of continuum.

I guess I'm not totally sure what a continuum is. Is it just any set with a bijection between it and the set of real numbers?

From what I know a set has cardinality of continuum if it is equivalent to the set of all sequences whose elements are the digits 0 and 1 (which is equivalent to the set of real numbers).

So I need a way to write each finite subset as a sequence of 1s and 0s to create a bijection between it and the set of all sequences whose elements are the digits 0 and 1?

I'm definitely confused about where to start, and would really appreciate some help!

Thanks!
well....you can prove it like this..

we can define the exponation of cardinals like that:
if $k_1,k_2$are cardinals of two sets $A,B$, then $k_1^{k_2}$is the cardinal of the set of all functions mappings $B$to $A$.
Let the cardinal of the natural numbers to be $\aleph_0$, and the cardinal of real numbers to be $\aleph$.
Then let $S$ be set of the all finite subsets of a continuum.
For every $x\in S$,since $x$is finite, there is a bijection $f_x$ from $n$(meaning the set $\{0,...,n-1\}$)to $x$, thus every $y\in x$can be written as $f_x(m)$. But we can also see $f_x$ as mapping from $\mathbb{N}$ to $x$, letting all other natural number map to a strange element $a$different from all real number. Thus now we have mapped all $x\in S$ to some function from $\mathbb{N}$ to $\mathbb{R}\cup \{a\}$(which have the same cardinality as $\mathbb{R}$).And clearly this mapping is one-to-one.
Clearly we have $S\succeq \aleph$. From above we also have $S\preceq\aleph^{\aleph_0}$.
But $S\preceq\aleph^{\aleph_0}=(2^{\aleph_0})^{\aleph_0 }=2^{\aleph_0\cdot\aleph_0}=2^{\aleph_0}=\aleph$
So $S\sim\aleph$, it have the cardinality of a continuum.

14. Originally Posted by ynj
well....you can prove it like this..

we can define the exponation of cardinals like that:
if $k_1,k_2$are cardinals of two sets $A,B$, then $k_1^{k_2}$is the cardinal of the set of all functions mappings $B$to $A$.
Let the cardinal of the natural numbers to be $\aleph_0$, and the cardinal of real numbers to be $\aleph$.
Then let $S$ be set of the all finite subsets of a continuum.
For every $x\in S$,since $x$is finite, there is a bijection $f_x$ from $n$(meaning the set $\{0,...,n-1\}$)to $x$, thus every $y\in x$can be written as $f_x(m)$. But we can also see $f_x$ as mapping from $\mathbb{N}$ to $x$, letting all other natural number map to a strange element $a$different from all real number. Thus now we have mapped all $x\in S$ to some function from $\mathbb{N}$ to $\mathbb{R}\cup \{a\}$(which have the same cardinality as $\mathbb{R}$).And clearly this mapping is one-to-one.
Clearly we have $S\succeq \aleph$. From above we also have $S\preceq\aleph^{\aleph_0}$.
But $S\preceq\aleph^{\aleph_0}=(2^{\aleph_0})^{\aleph_0 }=2^{\aleph_0\cdot\aleph_0}=2^{\aleph_0}=\aleph$
So $S\sim\aleph$, it have the cardinality of a continuum.
The poster said that he is not familiar with cardinal arithmetic, so this doesn't work. Also, even if he would accept it I always found cardinal arithmetic to be a little unconvincing.