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

Thread: 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 $\displaystyle \mathbb{N}^{ \mathbb{N}}$.

    $\displaystyle f$ is in relation with $\displaystyle g$ when

    $\displaystyle \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 $\displaystyle f$ such that $\displaystyle f(n)=0$ for every $\displaystyle n \in \mathbb{N}$

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

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

    For $\displaystyle g$ to be in relation with $\displaystyle f$ after some time it can't go upwards from some chosen $\displaystyle 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,577
    Thanks
    790

    Re: Cardinality of quotient set

    Quote Originally Posted by MachinePL1993 View Post
    1)What's the cardinality of the quotient set for $\displaystyle f$ such that $\displaystyle f(n)=0$ for every $\displaystyle n \in \mathbb{N}$
    You probably mean "the equivalence class of $\displaystyle f(n)=0$" instead of "the quotient set" for $\displaystyle 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 $\displaystyle \{g:\mathbb{N}\to\mathbb{N}\mid g(n)=0\text{ for }n>0\}$ (assuming $\displaystyle \mathbb{N}$ starts with 0)? What is the cardinality of $\displaystyle \{g:\mathbb{N}\to\mathbb{N}\mid g(n)=0\text{ for }n>1\}$? Now, note that $\displaystyle \{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$\displaystyle f$ such that $\displaystyle f(n)=1$ for every$\displaystyle n \in \mathbb{N}$
    Is $\displaystyle \{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 $\displaystyle \mathbb{N}^{k} \sim \mathbb{N}$ using Cantor-Bernstein theorem, and I have a function $\displaystyle f: \mathbb{N} \to \mathbb{N}^{k}$, but have trouble coming up with $\displaystyle 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,577
    Thanks
    790

    Re: Cardinality of quotient set

    One of the simplest bijections for k = 2 is $\displaystyle 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?

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

    EDIT:

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

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

    Re: Cardinality of quotient set

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

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

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

    $\displaystyle f_2(x_1,x_2)=g(x_1,x_2)$
    $\displaystyle 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,577
    Thanks
    790

    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 $\displaystyle f_{2}(<k_{1},k_{2}>)=2^{k_{1}}*3^{k_2}$
    For $\displaystyle n$ elements $\displaystyle 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 $\displaystyle k==2$ is obviously injective, because because decomposition into prime factors is unequivocal which means that for each pair a unique $\displaystyle n \in N$ would be assigned. So let's assume that $\displaystyle f_{n}(<k_{1},k_{2},...k_{n},k_{n}>)=x$ is a unique number, not assigned to any other sequence of numbers, therefore $\displaystyle 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,577
    Thanks
    790

    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: Sep 18th 2012, 10:00 AM
  2. Cardinality 2
    Posted in the Math Challenge Problems Forum
    Replies: 8
    Last Post: Apr 19th 2010, 09: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: Mar 18th 2010, 02:20 PM
  4. cardinality
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Apr 15th 2008, 07:18 PM
  5. cardinality
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Apr 9th 2008, 03:37 AM

Search Tags


/mathhelpforum @mathhelpforum