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

Math Help - Find the Cardinality of the following Relation

  1. #1
    Junior Member
    Joined
    Mar 2010
    Posts
    52

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

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    774

    Re: Find the Cardinality of the following Relation

    Quote Originally Posted by GIPC View Post
    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 View Post
    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 View Post
    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).
    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,530
    Thanks
    774

    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.
    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,530
    Thanks
    774

    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.
    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
    18,614
    Thanks
    1582
    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.
    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.
    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,530
    Thanks
    774

    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 f:2^{\mathbb{N}}\to R_1 where 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 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.
    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 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,530
    Thanks
    774

    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 R_0 is 1, but because 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 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.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    774

    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.
    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: March 20th 2009, 11:17 AM
  2. Replies: 3
    Last Post: January 9th 2009, 08:44 PM
  3. find a recurrence relation...
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 27th 2008, 08:08 AM
  4. find a recurrence relation
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: June 13th 2008, 09:32 AM

Search Tags


/mathhelpforum @mathhelpforum