Page 1 of 2 12 LastLast
Results 1 to 15 of 17

Thread: Find the Cardinality of the following Relation

  1. #1
    Junior Member
    Joined
    Mar 2010
    Posts
    52

    Find the Cardinality of the following Relation

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


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

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

    prove\disprove:
    a. for each$\displaystyle i<=j\;\; R_{i}\circR_{j}=R_{j}$
    b. for each$\displaystyle 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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,577
    Thanks
    790

    Re: Find the Cardinality of the following Relation

    Quote Originally Posted by GIPC View Post
    What is the Cardinality of$\displaystyle R_{0}$ and $\displaystyle R_{1}$
    So, $\displaystyle N_0=\{0\}$ and $\displaystyle N_1=\{0,1\}$. How many functions are there from N to {0}, i.e., what is the cardinality of $\displaystyle N_0^N$? How many functions are there from N to {0, 1}? Since $\displaystyle R_1$ is a reflexive relation, the cardinality of $\displaystyle R_1$ is at least as big as the cardinality of $\displaystyle N_1^N$.

    Quote Originally Posted by GIPC View Post
    prove\disprove:
    a. for each$\displaystyle i<=j\;\; R_{i}\circ R_{j}=R_{j}$
    Let us write $\displaystyle \mathop{\mathrm}{im}(f)$ for the image of some function f. Let i = 0 and j = 1. Consider some $\displaystyle f\in N_1^N$ such that $\displaystyle \mathop{\mathrm{im}}(f)=\{0,1\}$. Then $\displaystyle f\mathrel{R_1}f$, so if $\displaystyle R_{0}\circ R_{1}=R_1$, then there must be some g such that $\displaystyle f\mathrel{R_0}g$ and $\displaystyle g\mathrel{R_1}f$. Can we have $\displaystyle f\mathrel{R_0}g$?

    Quote Originally Posted by GIPC View Post
    b. for each$\displaystyle i<=j \;\;R_{j}\circ R_{i}=R_{i}$
    We have $\displaystyle f\mathrel{(R_j\circ R_i)}h$ iff $\displaystyle f\mathrel{R_j}g$ and $\displaystyle g\mathrel{R_i}h$ for some g. This means $\displaystyle \mathop{\mathrm{im}}(f)\subseteq N_j$, $\displaystyle \mathop{\mathrm{im}}(g)\subseteq N_i$ and $\displaystyle \mathop{\mathrm{im}}(h)\subseteq N_i$. But since $\displaystyle f(k)\le g(k)\le h(k)$ for all k, we also have $\displaystyle \mathop{\mathrm{im}}(f)\subseteq N_i$, so $\displaystyle f\mathrel{R_i} h$. The converse is also easy (take g = f).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Mar 2010
    Posts
    52

    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?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Mar 2010
    Posts
    52

    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
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,577
    Thanks
    790

    Re: Find the Cardinality of the following Relation

    You are right: $\displaystyle |R_0|=1$ and $\displaystyle |2^{\mathbb{N}}|=|P(\mathbb{N})|=|\mathbb{N}^{ \mathbb{N}}|=\mathfrak{c}$ (here 2 = {0, 1} and $\displaystyle \mathfrak{c}$ is the continuum). The natural bijection $\displaystyle P(\mathbb{N})\to 2^{\mathbb{N}}$ maps a set $\displaystyle A\subseteq\mathbb{N}$ into its characteristic function.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Mar 2010
    Posts
    52

    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,577
    Thanks
    790

    Re: Find the Cardinality of the following Relation

    But I described the bijection between $\displaystyle P(\mathbb{N})$ and $\displaystyle 2^{\mathbb{N}}$ in post #5. As for $\displaystyle |R_1|$, it is at least $\displaystyle |2^{\mathbb{N}}|=\mathfrak c$ and at most $\displaystyle |\mathbb{N}^{\mathbb{N}}\times\mathbb{N}^{\mathbb{ N}}|=\mathfrak c\cdot \mathfrak c=\mathfrak c$.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Junior Member
    Joined
    Mar 2010
    Posts
    52

    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?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,741
    Thanks
    2812
    Awards
    1

    Re: Find the Cardinality of the following Relation

    Quote Originally Posted by GIPC View Post
    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.
    $\displaystyle A\sim B$ means that $\displaystyle A~\&~B$ have the same cardinality.
    We know that if $\displaystyle A\sim B~\&~X\sim Y$ then $\displaystyle A^X\sim B^Y$.

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

    Thus $\displaystyle \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.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Junior Member
    Joined
    Mar 2010
    Posts
    52

    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.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,577
    Thanks
    790

    Re: Find the Cardinality of the following Relation

    Quote Originally Posted by GIPC View Post
    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 $\displaystyle f:2^{\mathbb{N}}\to R_1$ where $\displaystyle f(g)=\langle g,g\rangle$.

    Quote Originally Posted by GIPC View Post
    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 $\displaystyle R_1$ to $\displaystyle 2^{\mathbb{N}}\times2^{\mathbb{N}}$.

    This way, you have shown that $\displaystyle |2^{\mathbb{N}}|\le|R_1|\le|2^{\mathbb{N}}\times2^ {\mathbb{N}}|$. It is left to prove that $\displaystyle |2^{\mathbb{N}}|=|2^{\mathbb{N}}\times2^{\mathbb{N }}|$, and then $\displaystyle |2^{\mathbb{N}}|=|R_1|$ would follow by Cantor-Bernstein-Schroeder theorem.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Junior Member
    Joined
    Mar 2010
    Posts
    52

    Re: Find the Cardinality of the following Relation

    Quote Originally Posted by emakarov View Post
    Can we have $\displaystyle 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?
    Follow Math Help Forum on Facebook and Google+

  13. #13
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,577
    Thanks
    790

    Re: Find the Cardinality of the following Relation

    Quote Originally Posted by GIPC View Post
    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 $\displaystyle R_0$ is 1, but because $\displaystyle R_0$ consists of a pair whose elements are constant zero functions. But yes, that's the reason.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Junior Member
    Joined
    Mar 2010
    Posts
    52

    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 View Post
    We have $\displaystyle f\mathrel{(R_j\circ R_i)}h$ iff $\displaystyle f\mathrel{R_j}g$ and $\displaystyle g\mathrel{R_i}h$ for some g. This means $\displaystyle \mathop{\mathrm{im}}(f)\subseteq N_j$, $\displaystyle \mathop{\mathrm{im}}(g)\subseteq N_i$ and $\displaystyle \mathop{\mathrm{im}}(h)\subseteq N_i$. But since $\displaystyle f(k)\le g(k)\le h(k)$ for all k, we also have $\displaystyle \mathop{\mathrm{im}}(f)\subseteq N_i$, so $\displaystyle 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.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,577
    Thanks
    790

    Re: Find the Cardinality of the following Relation

    If $\displaystyle f\mathrel{R_i} h$, then $\displaystyle f\mathrel{R_j} f$ and $\displaystyle f\mathrel{R_i} h$, so $\displaystyle f\mathrel{(R_j\circ R_i)}h$.
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. Find solution to a recurrence relation...
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Mar 20th 2009, 11:17 AM
  2. Replies: 3
    Last Post: Jan 9th 2009, 08:44 PM
  3. find a recurrence relation...
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Oct 27th 2008, 08:08 AM
  4. find a recurrence relation
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Jun 13th 2008, 09:32 AM

Search Tags


/mathhelpforum @mathhelpforum