Find the Cardinality of the following Relation

let $\displaystyle R\subseteq \mathds{N}^{\mathds{N}}\times\mathds{N}^{\mathds{N }} $the following relation:

$\displaystyle R=\{(f,g): each\; i \;satisfies\; f(i)<=g(i)\}$

for each$\displaystyle i\in\mathds{N}$ let$\displaystyle \mathds{N}_{i}\subseteq\mathds{N} $ be the following group:

$\displaystyle \mathds{N}_{i}={0,1,...,i}$

and let$\displaystyle R_{i}=R\cap(\mathds{N}_{i}^{\mathds{N}}x\mathds{N} _{i}^{\mathds{N}})$

What is the Cardinality of$\displaystyle R_{0}$ and $\displaystyle R_{1}$

prove\disprove:

a. for each$\displaystyle i<=j\;\; R_{i}\circR_{j}=R_{j}$

b. for each$\displaystyle i<=j \;\;R_{j}\circR_{i}=R_{i}$

I am helpless and desperate

Please help me find the correct answers and i'll try to go and prove them from there

Re: Find the Cardinality of the following Relation

Quote:

Originally Posted by

**GIPC** What is the Cardinality of$\displaystyle R_{0}$ and $\displaystyle R_{1}$

So, $\displaystyle N_0=\{0\}$ and $\displaystyle N_1=\{0,1\}$. How many functions are there from N to {0}, i.e., what is the cardinality of $\displaystyle N_0^N$? How many functions are there from N to {0, 1}? Since $\displaystyle R_1$ is a reflexive relation, the cardinality of $\displaystyle R_1$ is at least as big as the cardinality of $\displaystyle N_1^N$.

Quote:

Originally Posted by

**GIPC** prove\disprove:

a. for each$\displaystyle i<=j\;\; R_{i}\circ R_{j}=R_{j}$

Let us write $\displaystyle \mathop{\mathrm}{im}(f)$ for the image of some function f. Let i = 0 and j = 1. Consider some $\displaystyle f\in N_1^N$ such that $\displaystyle \mathop{\mathrm{im}}(f)=\{0,1\}$. Then $\displaystyle f\mathrel{R_1}f$, so if $\displaystyle R_{0}\circ R_{1}=R_1$, then there must be some g such that $\displaystyle f\mathrel{R_0}g$ and $\displaystyle g\mathrel{R_1}f$. Can we have $\displaystyle f\mathrel{R_0}g$?

Quote:

Originally Posted by

**GIPC** b. for each$\displaystyle i<=j \;\;R_{j}\circ R_{i}=R_{i}$

We have $\displaystyle f\mathrel{(R_j\circ R_i)}h$ iff $\displaystyle f\mathrel{R_j}g$ and $\displaystyle g\mathrel{R_i}h$ for some g. This means $\displaystyle \mathop{\mathrm{im}}(f)\subseteq N_j$, $\displaystyle \mathop{\mathrm{im}}(g)\subseteq N_i$ and $\displaystyle \mathop{\mathrm{im}}(h)\subseteq N_i$. But since $\displaystyle f(k)\le g(k)\le h(k)$ for all k, we also have $\displaystyle \mathop{\mathrm{im}}(f)\subseteq N_i$, so $\displaystyle f\mathrel{R_i} h$. The converse is also easy (take g = f).

Re: Find the Cardinality of the following Relation

Okay, thanks for your help, I understood the prove and disprove parts but I'm still unsure about the cardinality of R_0 and R_1

I think your implying that the cardinality of R_0 is 1, and of R_1 is countable aleph null? If so, showing that |R_0|=1 is trivial, but how do I prove that R_1 is indeed aleph null?

Re: Find the Cardinality of the following Relation

So i came to a conclusion that R_1 is NOT countable and not aleph zero.

I think its cardinality is P(N).

But I couldn't find a way to prove it (playing with some injective functions or finding the correct map).

So I hope someone could help me :)

Re: Find the Cardinality of the following Relation

You are right: $\displaystyle |R_0|=1$ and $\displaystyle |2^{\mathbb{N}}|=|P(\mathbb{N})|=|\mathbb{N}^{ \mathbb{N}}|=\mathfrak{c}$ (here 2 = {0, 1} and $\displaystyle \mathfrak{c}$ is the continuum). The natural bijection $\displaystyle P(\mathbb{N})\to 2^{\mathbb{N}}$ maps a set $\displaystyle A\subseteq\mathbb{N}$ into its characteristic function.

Re: Find the Cardinality of the following Relation

Okay, I can see that. And I have tried to prove that R_1 is indeed equal to that cardinality but didn't find the correct way.

I was tring to map P(N) to {0,1,2}^N with some injective function but couldn't find the correct one.

So if someone could help me find the correct map I would appreciate it tremendously.

Re: Find the Cardinality of the following Relation

But I described the bijection between $\displaystyle P(\mathbb{N})$ and $\displaystyle 2^{\mathbb{N}}$ in post #5. As for $\displaystyle |R_1|$, it is at least $\displaystyle |2^{\mathbb{N}}|=\mathfrak c$ and at most $\displaystyle |\mathbb{N}^{\mathbb{N}}\times\mathbb{N}^{\mathbb{ N}}|=\mathfrak c\cdot \mathfrak c=\mathfrak c$.

Re: Find the Cardinality of the following Relation

I understand your point but the thing is, I have to somehow formally prove it.

So I see you did a little sandwich there and bounded R_1, but I can't just take this fact for granted, I have to somehow prove and show this for myself. So that is what I am trying to do, first find some map using some injective function f between 2^N to R_1 and then some map between R_1 to N^NcrossN^N. and actually, saying that R_1<N^NcrossN^N (but not <=)is not good enough because I wat to prove that R_1~P(N).

Unless there is some other way to prove that |R_1|=|P(N)| that i am missing?

Re: Find the Cardinality of the following Relation

Quote:

Originally Posted by

**GIPC** I understand your point but the thing is, I have to somehow formally prove it.

So I see you did a little sandwich there and bounded R_1, but I can't just take this fact for granted, I have to somehow prove and show this for myself. So that is what I am trying to do, first find some map using some injective function f between 2^N to R_1 and then some map between R_1 to N^NcrossN^N. and actually, saying that R_1<N^NcrossN^N (but not <=)is not good enough because I wat to prove that R_1~P(N).

Unless there is some other way to prove that |R_1|=|P(N)| that i am missing?

It seems that you are the one not seeing that **emakarov** has given you all the details possible.

So I doubt that this will help. If you are working at this level then you should know some of the basic facts of *cardinal arithmetic*.

$\displaystyle A\sim B$ means that $\displaystyle A~\&~B$ have the same cardinality.

We know that if $\displaystyle A\sim B~\&~X\sim Y$ then $\displaystyle A^X\sim B^Y$.

Moreover $\displaystyle \mathbb{N}\sim \mathbb{N}\times\mathbb{N}$

Thus $\displaystyle \mathcal{P}(\mathbb{N})\sim 2^{\mathbb{N}}\sim 2^{\mathbb{N}\times\mathbb{N}}$.

Now if you have not seen these theorems then try to prove them.

Re: Find the Cardinality of the following Relation

I am familiar with these theorems but I don't see how they apply to the subject of finding the cardinality of R_1.

Why are you saying that |R_1|=|2^N|? Is that some trivial fact that i'm missing? What i'm seeing is that i have to prove that |R_1|=|2^N| and go from there. I don't understand why you're saying that R1=2^N just like that with no justification.

Re: Find the Cardinality of the following Relation

Quote:

Originally Posted by

**GIPC** So that is what I am trying to do, first find some map using some injective function f between 2^N to R_1

Consider $\displaystyle f:2^{\mathbb{N}}\to R_1$ where $\displaystyle f(g)=\langle g,g\rangle$.

Quote:

Originally Posted by

**GIPC** and then some map between R_1 to N^NcrossN^N.

This is the identity function. However, I would recommend consider the identity function as an injection from $\displaystyle R_1$ to $\displaystyle 2^{\mathbb{N}}\times2^{\mathbb{N}}$.

This way, you have shown that $\displaystyle |2^{\mathbb{N}}|\le|R_1|\le|2^{\mathbb{N}}\times2^ {\mathbb{N}}|$. It is left to prove that $\displaystyle |2^{\mathbb{N}}|=|2^{\mathbb{N}}\times2^{\mathbb{N }}|$, and then $\displaystyle |2^{\mathbb{N}}|=|R_1|$ would follow by Cantor-Bernstein-Schroeder theorem.

Re: Find the Cardinality of the following Relation

Quote:

Originally Posted by

**emakarov** Can we have $\displaystyle f\mathrel{R_0}g$?

Let me see if I understand.

We can't have such g because then it would imply that Im(f)={0} because the cardinality of R_0 is 1? And we assumed that Im(f)={0,1} so we can't have that?

Is that a good reasoning to finish the claim?

Re: Find the Cardinality of the following Relation

Quote:

Originally Posted by

**GIPC** Let me see if I understand.

We can't have such g because then it would imply that Im(f)={0} because the cardinality of R_0 is 1?

Not just because the cardinality of $\displaystyle R_0$ is 1, but because $\displaystyle R_0$ consists of a pair whose elements are constant zero functions. But yes, that's the reason.

Re: Find the Cardinality of the following Relation

Okay, thanks, i'm trying to formally prove this question and I have more and more follow up questions.

Regarding:

Quote:

Originally Posted by

**emakarov** We have $\displaystyle f\mathrel{(R_j\circ R_i)}h$ iff $\displaystyle f\mathrel{R_j}g$ and $\displaystyle g\mathrel{R_i}h$ for some g. This means $\displaystyle \mathop{\mathrm{im}}(f)\subseteq N_j$, $\displaystyle \mathop{\mathrm{im}}(g)\subseteq N_i$ and $\displaystyle \mathop{\mathrm{im}}(h)\subseteq N_i$. But since $\displaystyle f(k)\le g(k)\le h(k)$ for all k, we also have $\displaystyle \mathop{\mathrm{im}}(f)\subseteq N_i$, so $\displaystyle f\mathrel{R_i} h$. The converse is also easy (take g = f).

How exacly do I prove the converse? I'm taking some g Ri h and I have to somehow prove g RjRi h... but I don't see the connection.

Re: Find the Cardinality of the following Relation

If $\displaystyle f\mathrel{R_i} h$, then $\displaystyle f\mathrel{R_j} f$ and $\displaystyle f\mathrel{R_i} h$, so $\displaystyle f\mathrel{(R_j\circ R_i)}h$.