# Cardinality of quotient set

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

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

Quote:

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

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