# Thread: Cardinality of quotient set

1. ## 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?

2. ## Re: Cardinality of quotient set

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\}$.

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?

3. ## 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?

4. ## 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.

5. ## 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>)$...

6. ## Re: Cardinality of quotient set

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})$

7. ## Re: Cardinality of quotient set

How do we know that a function defined like this is injective?

8. ## Re: Cardinality of quotient set

We prove it by induction on k.

9. ## 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.

10. ## Re: Cardinality of quotient set

Yes, this works.