Results 1 to 10 of 10
Like Tree4Thanks
  • 1 Post By emakarov
  • 1 Post By emakarov
  • 1 Post By emakarov
  • 1 Post By emakarov

Math Help - Cardinality of quotient set

  1. #1
    Junior Member
    Joined
    Nov 2012
    From
    Poland
    Posts
    40

    Cardinality of quotient set

    Hello,
    Here's a relation defined on the set \mathbb{N}^{ \mathbb{N}}.

    f is in relation with g when

    \exists_{c>0} \exists_{k>0} \forall_{n>k}(f(n) \le c*g(n) \wedge g(n) \le c*f(n))

    1)What's the cardinality of the quotient set for f such that f(n)=0 for every n \in \mathbb{N}

    In order for g to be in relation with f it has to always equal 0 after some time..

    1)What's the cardinality of the quotient set for f such that f(n)=1 for every n \in \mathbb{N}

    For g to be in relation with f after some time it can't go upwards from some chosen c.

    I have literally no idea how to even begin assigning cardinal number to those quotient sets. Could someone provide me a hint?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,559
    Thanks
    785

    Re: Cardinality of quotient set

    Quote Originally Posted by MachinePL1993 View Post
    1)What's the cardinality of the quotient set for f such that f(n)=0 for every n \in \mathbb{N}
    You probably mean "the equivalence class of f(n)=0" instead of "the quotient set" for f(n)=0. The quotient set is the set of all equivalence classes. See Wikipedia.

    Let f(n) = 0 for all n. What is the cardinality of \{g:\mathbb{N}\to\mathbb{N}\mid g(n)=0\text{ for }n>0\} (assuming \mathbb{N} starts with 0)? What is the cardinality of \{g:\mathbb{N}\to\mathbb{N}\mid g(n)=0\text{ for }n>1\}? Now, note that \{g:\mathbb{N}\to\mathbb{N}\mid g\sim f\}=\bigcup_{k>0}\{g:\mathbb{N}\to\mathbb{N}\mid g(n)=0\text{ for }n>k\}.

    Quote Originally Posted by MachinePL1993 View Post
    1)What's the cardinality of the quotient set for f such that f(n)=1 for every n \in \mathbb{N}
    Is \{1,2\}^{\mathbb{N}} a subset of that equivalence class?
    Thanks from MachinePL1993
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Nov 2012
    From
    Poland
    Posts
    40

    Re: Cardinality of quotient set

    Thanks, so I no longer have trouble with the second equivalence class, but still have trouble with the first.

    I tried proving \mathbb{N}^{k} \sim \mathbb{N} using Cantor-Bernstein theorem, and I have a function f: \mathbb{N} \to \mathbb{N}^{k}, but have trouble coming up with g: \mathbb{N}^{k} \to  \mathbb{N}. Can anyone give me a hint?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,559
    Thanks
    785

    Re: Cardinality of quotient set

    One of the simplest bijections for k = 2 is g(m, n) = 2^{m-1}(2n - 1). See also Cantor's pairing function.
    Thanks from MachinePL1993
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Nov 2012
    From
    Poland
    Posts
    40

    Re: Cardinality of quotient set

    Can it be something like this?

    f: \mathbb{N}^{k} \to \mathbb{N}
    For some finite sequence of length k A_{k} f(A_{k})=$\sum_{i=0}^k 2^i$..

    EDIT:

    It's wrong because f(<5,5>)=f(<6>)...
    Last edited by MachinePL1993; January 2nd 2013 at 03:47 AM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,559
    Thanks
    785

    Re: Cardinality of quotient set

    Quote Originally Posted by MachinePL1993 View Post
    Can it be something like this?

    f: \mathbb{N}^{k} \to \mathbb{N}
    For some finite sequence of length k A_{k} f(A_{k})=$\sum_{i=0}^k 2^i$..
    This f does not seem to depend on the elements of A_k, only on its length.

    Given a bijection g:\mathbb{N}\times\mathbb{N}\to\mathbb{N}, we can define bijections f_k:\mathbb{N}^k\to\mathbb{N} for k\ge2 by recursion on k:

    f_2(x_1,x_2)=g(x_1,x_2)
    f_{k+1}(x_1,\dots,x_{k+1})=g(f_k(x_1,\dots,x_k),x_  {k+1})
    Thanks from MachinePL1993
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Nov 2012
    From
    Poland
    Posts
    40

    Re: Cardinality of quotient set

    How do we know that a function defined like this is injective?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,559
    Thanks
    785

    Re: Cardinality of quotient set

    We prove it by induction on k.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Junior Member
    Joined
    Nov 2012
    From
    Poland
    Posts
    40

    Re: Cardinality of quotient set

    Say i define this function like this:

    For a set of two elements f_{2}(<k_{1},k_{2}>)=2^{k_{1}}*3^{k_2}
    For n elements f_{n}(<k_{1},k_{2},...k_{n},k_{n}>)=2^{f_{n-1}(<k_{1},k_{2},...k_{n-1}>)}*3^{k_n+1}

    So for k==2 is obviously injective, because because decomposition into prime factors is unequivocal which means that for each pair a unique  n \in N would be assigned. So let's assume that f_{n}(<k_{1},k_{2},...k_{n},k_{n}>)=x is a unique number, not assigned to any other sequence of numbers, therefore f_{n+1}(<k_{1},k_{2},...k_{n},k_{n},k_{n+1}>)=2^{x  }*3^{k_{n+1}} is unique for the same reasons the sequence of two elements was unique.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,559
    Thanks
    785

    Re: Cardinality of quotient set

    Yes, this works.
    Thanks from MachinePL1993
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Cardinality
    Posted in the Number Theory Forum
    Replies: 8
    Last Post: September 18th 2012, 11:00 AM
  2. Cardinality 2
    Posted in the Math Challenge Problems Forum
    Replies: 8
    Last Post: April 19th 2010, 10:06 PM
  3. Cardinality of R, [0,1], R^2, [0,1] x [0,1]
    Posted in the Differential Geometry Forum
    Replies: 11
    Last Post: March 18th 2010, 03:20 PM
  4. cardinality
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 15th 2008, 08:18 PM
  5. cardinality
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 9th 2008, 04:37 AM

Search Tags


/mathhelpforum @mathhelpforum