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 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!
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!
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.
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
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 . Draw a vertical line through and project from this line through . You'll see that you hit one point on and one point on . This is then an injection. And since clearly the inclusion mapping 0,1)\hookrightarrow\mathbb{R}" alt="f0,1)\hookrightarrow\mathbb{R}" /> given by is an injection the other way the Schroder-Bernstein theorem finishes the argument
I'll try to think of a good hint, and get back to you!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
well....you can prove it like this..
we can define the exponation of cardinals like that:
if are cardinals of two sets , then is the cardinal of the set of all functions mappings to .
Let the cardinal of the natural numbers to be , and the cardinal of real numbers to be .
Then let be set of the all finite subsets of a continuum.
For every ,since is finite, there is a bijection from (meaning the set )to , thus every can be written as . But we can also see as mapping from to , letting all other natural number map to a strange element different from all real number. Thus now we have mapped all to some function from to (which have the same cardinality as ).And clearly this mapping is one-to-one.
Clearly we have . From above we also have .
But
So , it have the cardinality of a continuum.