Find the Cardinality of the following Relation

Printable View

Show 40 post(s) from this thread on one page

December 17th 2011, 02:12 PM
GIPC

Find the Cardinality of the following Relation

let $R\subseteq \mathds{N}^{\mathds{N}}\times\mathds{N}^{\mathds{N }}$ the following relation:
$R=\{(f,g): each\; i \;satisfies\; f(i)<=g(i)\}$

for each $i\in\mathds{N}$ let $\mathds{N}_{i}\subseteq\mathds{N}$ be the following group:
$\mathds{N}_{i}={0,1,...,i}$
and let $R_{i}=R\cap(\mathds{N}_{i}^{\mathds{N}}x\mathds{N} _{i}^{\mathds{N}})$

What is the Cardinality of $R_{0}$ and $R_{1}$

prove\disprove:
a. for each $i<=j\;\; R_{i}\circR_{j}=R_{j}$
b. for each $i<=j \;\;R_{j}\circR_{i}=R_{i}$

I am helpless and desperate
Please help me find the correct answers and i'll try to go and prove them from there
December 18th 2011, 03:20 AM
emakarov

Re: Find the Cardinality of the following Relation

Quote:

Originally Posted by GIPC

What is the Cardinality of $R_{0}$ and $R_{1}$

So, $N_0=\{0\}$ and $N_1=\{0,1\}$ . How many functions are there from N to {0}, i.e., what is the cardinality of $N_0^N$ ? How many functions are there from N to {0, 1}? Since $R_1$ is a reflexive relation, the cardinality of $R_1$ is at least as big as the cardinality of $N_1^N$ .

Quote:

Originally Posted by GIPC

prove\disprove:
a. for each $i<=j\;\; R_{i}\circ R_{j}=R_{j}$

Let us write $\mathop{\mathrm}{im}(f)$ for the image of some function f. Let i = 0 and j = 1. Consider some $f\in N_1^N$ such that $\mathop{\mathrm{im}}(f)=\{0,1\}$ . Then $f\mathrel{R_1}f$ , so if $R_{0}\circ R_{1}=R_1$ , then there must be some g such that $f\mathrel{R_0}g$ and $g\mathrel{R_1}f$ . Can we have $f\mathrel{R_0}g$ ?

Quote:

Originally Posted by GIPC

b. for each $i<=j \;\;R_{j}\circ R_{i}=R_{i}$

We have $f\mathrel{(R_j\circ R_i)}h$ iff $f\mathrel{R_j}g$ and $g\mathrel{R_i}h$ for some g. This means $\mathop{\mathrm{im}}(f)\subseteq N_j$ , $\mathop{\mathrm{im}}(g)\subseteq N_i$ and $\mathop{\mathrm{im}}(h)\subseteq N_i$ . But since $f(k)\le g(k)\le h(k)$ for all k, we also have $\mathop{\mathrm{im}}(f)\subseteq N_i$ , so $f\mathrel{R_i} h$ . The converse is also easy (take g = f).
December 18th 2011, 03:31 AM
GIPC

Re: Find the Cardinality of the following Relation

Okay, thanks for your help, I understood the prove and disprove parts but I'm still unsure about the cardinality of R_0 and R_1

I think your implying that the cardinality of R_0 is 1, and of R_1 is countable aleph null? If so, showing that |R_0|=1 is trivial, but how do I prove that R_1 is indeed aleph null?
December 18th 2011, 04:44 AM
GIPC

Re: Find the Cardinality of the following Relation

So i came to a conclusion that R_1 is NOT countable and not aleph zero.

I think its cardinality is P(N).

But I couldn't find a way to prove it (playing with some injective functions or finding the correct map).

So I hope someone could help me :)
December 18th 2011, 08:40 AM
emakarov

Re: Find the Cardinality of the following Relation

You are right: $|R_0|=1$ and $|2^{\mathbb{N}}|=|P(\mathbb{N})|=|\mathbb{N}^{ \mathbb{N}}|=\mathfrak{c}$ (here 2 = {0, 1} and $\mathfrak{c}$ is the continuum). The natural bijection $P(\mathbb{N})\to 2^{\mathbb{N}}$ maps a set $A\subseteq\mathbb{N}$ into its characteristic function.
December 18th 2011, 09:56 AM
GIPC

Re: Find the Cardinality of the following Relation

Okay, I can see that. And I have tried to prove that R_1 is indeed equal to that cardinality but didn't find the correct way.

I was tring to map P(N) to {0,1,2}^N with some injective function but couldn't find the correct one.

So if someone could help me find the correct map I would appreciate it tremendously.
December 18th 2011, 10:44 AM
emakarov

Re: Find the Cardinality of the following Relation

But I described the bijection between $P(\mathbb{N})$ and $2^{\mathbb{N}}$ in post #5. As for $|R_1|$ , it is at least $|2^{\mathbb{N}}|=\mathfrak c$ and at most $|\mathbb{N}^{\mathbb{N}}\times\mathbb{N}^{\mathbb{ N}}|=\mathfrak c\cdot \mathfrak c=\mathfrak c$ .
December 18th 2011, 10:55 AM
GIPC

Re: Find the Cardinality of the following Relation

I understand your point but the thing is, I have to somehow formally prove it.

So I see you did a little sandwich there and bounded R_1, but I can't just take this fact for granted, I have to somehow prove and show this for myself. So that is what I am trying to do, first find some map using some injective function f between 2^N to R_1 and then some map between R_1 to N^NcrossN^N. and actually, saying that R_1<N^NcrossN^N (but not <=)is not good enough because I wat to prove that R_1~P(N).

Unless there is some other way to prove that |R_1|=|P(N)| that i am missing?
December 18th 2011, 11:20 AM
Plato

Re: Find the Cardinality of the following Relation

Quote:

Originally Posted by GIPC

I understand your point but the thing is, I have to somehow formally prove it.
So I see you did a little sandwich there and bounded R_1, but I can't just take this fact for granted, I have to somehow prove and show this for myself. So that is what I am trying to do, first find some map using some injective function f between 2^N to R_1 and then some map between R_1 to N^NcrossN^N. and actually, saying that R_1<N^NcrossN^N (but not <=)is not good enough because I wat to prove that R_1~P(N).
Unless there is some other way to prove that |R_1|=|P(N)| that i am missing?

It seems that you are the one not seeing that emakarov has given you all the details possible.

So I doubt that this will help. If you are working at this level then you should know some of the basic facts of cardinal arithmetic.
$A\sim B$ means that $A~\&~B$ have the same cardinality.
We know that if $A\sim B~\&~X\sim Y$ then $A^X\sim B^Y$ .

Moreover $\mathbb{N}\sim \mathbb{N}\times\mathbb{N}$

Thus $\mathcal{P}(\mathbb{N})\sim 2^{\mathbb{N}}\sim 2^{\mathbb{N}\times\mathbb{N}}$ .

Now if you have not seen these theorems then try to prove them.
December 18th 2011, 11:49 AM
GIPC

Re: Find the Cardinality of the following Relation

I am familiar with these theorems but I don't see how they apply to the subject of finding the cardinality of R_1.

Why are you saying that |R_1|=|2^N|? Is that some trivial fact that i'm missing? What i'm seeing is that i have to prove that |R_1|=|2^N| and go from there. I don't understand why you're saying that R1=2^N just like that with no justification.
December 18th 2011, 12:33 PM
emakarov

Re: Find the Cardinality of the following Relation

Quote:

Originally Posted by GIPC

So that is what I am trying to do, first find some map using some injective function f between 2^N to R_1

Consider $f:2^{\mathbb{N}}\to R_1$ where $f(g)=\langle g,g\rangle$ .

Quote:

Originally Posted by GIPC

and then some map between R_1 to N^NcrossN^N.

This is the identity function. However, I would recommend consider the identity function as an injection from $R_1$ to $2^{\mathbb{N}}\times2^{\mathbb{N}}$ .

This way, you have shown that $|2^{\mathbb{N}}|\le|R_1|\le|2^{\mathbb{N}}\times2^ {\mathbb{N}}|$ . It is left to prove that $|2^{\mathbb{N}}|=|2^{\mathbb{N}}\times2^{\mathbb{N }}|$ , and then $|2^{\mathbb{N}}|=|R_1|$ would follow by Cantor-Bernstein-Schroeder theorem.
December 19th 2011, 08:24 AM
GIPC

Re: Find the Cardinality of the following Relation

Quote:

Originally Posted by emakarov

Can we have $f\mathrel{R_0}g$ ?

Let me see if I understand.
We can't have such g because then it would imply that Im(f)={0} because the cardinality of R_0 is 1? And we assumed that Im(f)={0,1} so we can't have that?

Is that a good reasoning to finish the claim?
December 19th 2011, 08:34 AM
emakarov

Re: Find the Cardinality of the following Relation

Quote:

Originally Posted by GIPC

Let me see if I understand.
We can't have such g because then it would imply that Im(f)={0} because the cardinality of R_0 is 1?

Not just because the cardinality of $R_0$ is 1, but because $R_0$ consists of a pair whose elements are constant zero functions. But yes, that's the reason.
December 19th 2011, 09:50 AM
GIPC

Re: Find the Cardinality of the following Relation

Okay, thanks, i'm trying to formally prove this question and I have more and more follow up questions.

Regarding:

Quote:

Originally Posted by emakarov

We have $f\mathrel{(R_j\circ R_i)}h$ iff $f\mathrel{R_j}g$ and $g\mathrel{R_i}h$ for some g. This means $\mathop{\mathrm{im}}(f)\subseteq N_j$ , $\mathop{\mathrm{im}}(g)\subseteq N_i$ and $\mathop{\mathrm{im}}(h)\subseteq N_i$ . But since $f(k)\le g(k)\le h(k)$ for all k, we also have $\mathop{\mathrm{im}}(f)\subseteq N_i$ , so $f\mathrel{R_i} h$ . The converse is also easy (take g = f).

How exacly do I prove the converse? I'm taking some g Ri h and I have to somehow prove g RjRi h... but I don't see the connection.
December 19th 2011, 09:57 AM
emakarov

Re: Find the Cardinality of the following Relation

If $f\mathrel{R_i} h$ , then $f\mathrel{R_j} f$ and $f\mathrel{R_i} h$ , so $f\mathrel{(R_j\circ R_i)}h$ .

Show 40 post(s) from this thread on one page

All times are GMT -8. The time now is 01:40 PM.

Copyright © 2005-2013 Math Help Forum. All rights reserved.

Copyright © 2005-2013 Math Help Forum. All rights reserved.