Cardinality of quotient set

Printable View

January 1st 2013, 02: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?
January 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 $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?
January 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 $\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?
January 2nd 2013, 02: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.
January 2nd 2013, 02: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>)$ ...
January 2nd 2013, 02: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})$
January 2nd 2013, 03:12 AM
MachinePL1993

Re: Cardinality of quotient set

How do we know that a function defined like this is injective?
January 2nd 2013, 03:13 AM
emakarov

Re: Cardinality of quotient set

We prove it by induction on k.
January 2nd 2013, 03:33 AM
MachinePL1993

Re: Cardinality of quotient set

Say i define this function like this:

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

Re: Cardinality of quotient set

Yes, this works.