Set theory - cardinality

[mar_f]

Hi,
how can I prove that the cardinalities of these two sets are equal? I know that I have to find a bijection between them, but I do not know exactly how.
Many thanks.

 

[Steven G]

You really have to try to find the bijection! Pick an arbitrary element in (0,1) and map it to something in (0,1) X {2,4,6}. Then do the reverse. Please post what you tried so we can help.

Also, are you sure that you need to find a bijection??

 

[mar_f]

We solved a similar one at school like this: We divided the interval (0,1] into three disjunct intervals, probably (0; 1/3) [1/3; 2/3) and [ 2/3; 1] in this case and then found a bijection between each of these and the interval (0,1]. But I am not really sure whether this is a correct approach :/

 

[Dr.Peterson]

That looks good as a general idea; but be very careful with your endpoints! Make sure you can actually state each of the three bijections.

 

[mar_f]

So I have to find the bijections [MATH] (0,1]\rightarrow \left(0,\frac{1}{3}\right)[/MATH] [MATH] (0,1]\rightarrow \left[\frac{1}{3},\frac{2}{3}\right)[/MATH] and
[MATH] (0,1]\rightarrow \left[\frac{2}{3},1\right][/MATH] ?
Or is there any better (or easier) solution ?

Thank you.

 

[Dr.Peterson]

I hinted that there is something wrong with the endpoints of your intervals. Do you see that you can make easy bijections if you change which are included in which interval? Once you fix that, I don't think it could be any easier.

I also said to state the bijections explicitly, because once you do that, it should become clear why you need to change your handling of the endpoints 1/3 and 2/3.

 

[Steven G]

Clearly (0,1) has infinite cardinality. Now you can map each point in (0,1) to three points in (0,1) x {2,4,6} and map a point in (0,1) x {2,4,6} to a point in (0.1).
Will that be enough? If yes, then clean it up.

 

[pka]

Hi,
how can I prove that the cardinalities of these two sets are equal? I know that I have to find a bijection between them, but I do not know exactly how.
Many thanks.
View attachment 11151

I will assume the question is \(\displaystyle \left( {0,1} \right] \leftrightarrow \left( {0,1} \right] \times \left\{ {2,4,6} \right\}\)
First define three pair-wise nonempty sets which form a partition of \(\displaystyle \left( {0,1} \right] \)
\(\displaystyle T = \left( {0,\frac{1}{3}} \right],S = \left( {\frac{2}{3},1} \right]\) AND \(\displaystyle Z= \left( {\frac{1}{3},\frac{2}{3}} \right]\)
\(\displaystyle \Theta(x)=\begin{cases}(x,2) &: x\in T \\ (x,4) &: x\in Z\\(x,6) &: x\in S\end{cases}\)
Can you show that \(\displaystyle \Theta\) is a bijection between (01] \(\displaystyle \times\) {2,4,6} ?

 

[mar_f]

So I tried finding the bijections:
For [MATH](0,1] \leftrightarrow (0, \frac{1}{3}] : \theta_{1} = \frac{x}{3} [/MATH] [MATH](0,1] \leftrightarrow (\frac{1}{3},\frac{2}{3}] : \theta_{2} = \frac{x+1}{3}[/MATH]and [MATH](0,1] \leftrightarrow (\frac{2}{3},1] : \theta_{3} = \frac{x+2}{3}[/MATH]
Is this correct, please? Thanks.

 

[Dr.Peterson]

That's correct. Note that, for example, the third pairs up 0 (which is not in the domain) with 2/3 (which is not in the codomain), and 1 (which is in the domain) with 1 (which is in the codomain). That was the important fact about the endpoints.

Now, of course, you need to write the actual single bijection between the two original sets.

 

[mar_f]

Thank you for your reply.
So I came up with this:
[MATH] \theta(x,m) = \begin{cases} \frac{x + \lfloor{ \frac{m}{3}} \rfloor }{3} \wedge m \in \{2,4,6\} \end{cases} [/MATH]
Is that please correct? Thanks.

 

[Dr.Peterson]

I'm not quite sure of your notation; you have an unmatched (or unnecessary) left brace, and it's not clear what role the "∧" is playing. The basic idea is good, though.

However, though it seems to turn out okay, I wouldn't have used ⌊m/3⌋, but (m/2)-1, with no need for the floor function. That makes more logical sense.

 

[mar_f]

Thank you for your help. Can I have one more question please? How can I prove that [MATH]|(a,b)| = |[a,b]|[/MATH] ?
Or for example, [MATH] |(0,1)| = |[0,1)|[/MATH] I know how to find a bijection between intervals that have the same endpoints but not otherwise.
Thanks.

 

[Dr.Peterson]

I had to look up some ideas, but here is a simple way to do a simple case.

I'll make a bijection between (0, 1] and (0, 1). What I need to do is to tuck the 1 into an infinite pocket within (0, 1) that has room to hide an extra point. So consider the set P = {1, 1/2, 1/4, 1/8, ...}. This is a countably infinite subset of (0, 1]. That's my infinitely deep "pocket".

Now consider this function f: (0, 1] -> (0, 1):

[MATH]f(x) = \left\{\begin{matrix}\frac{x}{2} \text{ if } x\in P \\ x \text{ if } x\notin P\end{matrix}\right.[/MATH]
See how it works? f(P) turns out to be P - {1}, which is just what we need!

 

[mar_f]

Thank you.
Can I solve the [MATH]|(a,b)| = |[a,b] | [/MATH] example in a similar way?

 

[Dr.Peterson]

Give it a try! I intentionally just showed you the simplest case, so you can experiment with others on your own.

I can imagine several ways you might modify my method; the version that gave me my ideas dealt with |(a,b)|=|[a,b]|, by pushing both 0 and 1 into the same infinite set. You could do something similar, or use two separate sets.

 

[Steven G]

Dr P, does my suggestion in post #7 have any hope. Please understand that it is not complete.

 

[Dr.Peterson]

Clearly (0,1) has infinite cardinality. Now you can map each point in (0,1) to three points in (0,1) x {2,4,6} and map a point in (0,1) x {2,4,6} to a point in (0.1).
Will that be enough? If yes, then clean it up.

Dr P, does my suggestion in post #7 have any hope. Please understand that it is not complete.

I figured you might have been answering the wrong question. Mapping one point to three doesn't meet the need here. (Or are you assuming there are theorems available saying that a finite-to-one mapping implies the same cardinality?)

 

[Steven G]

I figured you might have been answering the wrong question. Mapping one point to three doesn't meet the need here. (Or are you assuming there are theorems available saying that a finite-to-one mapping implies the same cardinality?)

Let N represent the natural numbers. I thought that N and 3N had the same cardinality??
Yes I am assuming there are theorems available saying that a finite-to-one mapping implies the same cardinality if one of the set (and hence the other set) have alpeh null as its cardinality.

 

[Dr.Peterson]

My understanding of the original question,

how can I prove that the cardinalities of these two sets are equal? I know that I have to find a bijection between them, but I do not know exactly how.

is that a direct bijection was required, not the application of a theorem -- perhaps no theorems have been proved yet. This is another of those cases where, if I were tutoring face-to-face, I would have grabbed the student's textbook and checked out what theorems or definitions were available in the context. Wish we could add that feature to the site ...