# Cardinality of quotient set

• Jan 1st 2013, 02:05 PM
MachinePL1993
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?
• Jan 1st 2013, 04:44 PM
emakarov
Re: Cardinality of quotient set
Quote:

Originally Posted by MachinePL1993
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
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?
• Jan 2nd 2013, 02:18 AM
MachinePL1993
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?
• Jan 2nd 2013, 02:29 AM
emakarov
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.
• Jan 2nd 2013, 02:41 AM
MachinePL1993
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>)$...
• Jan 2nd 2013, 02:49 AM
emakarov
Re: Cardinality of quotient set
Quote:

Originally Posted by MachinePL1993
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})$
• Jan 2nd 2013, 03:12 AM
MachinePL1993
Re: Cardinality of quotient set
How do we know that a function defined like this is injective?
• Jan 2nd 2013, 03:13 AM
emakarov
Re: Cardinality of quotient set
We prove it by induction on k.
• Jan 2nd 2013, 03:33 AM
MachinePL1993
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.
• Jan 2nd 2013, 03:38 AM
emakarov
Re: Cardinality of quotient set
Yes, this works.