# Thread: Cardinality of quotient set

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

2. ## Re: Cardinality of quotient set

Originally Posted by MachinePL1993
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\}$.

Originally Posted by MachinePL1993
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?

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 $\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?

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

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

6. ## Re: Cardinality of quotient set

Originally Posted by MachinePL1993
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})$

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 $f_{2}()=2^{k_{1}}*3^{k_2}$
For $n$ elements $f_{n}()=2^{f_{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}()=x$ is a unique number, not assigned to any other sequence of numbers, therefore $f_{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.