# Find the Cardinality of the following Relation

Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last
• Dec 17th 2011, 03:12 PM
GIPC
Find the Cardinality of the following Relation
let $R\subseteq \mathds{N}^{\mathds{N}}\times\mathds{N}^{\mathds{N }}$the following relation:
$R=\{(f,g): each\; i \;satisfies\; f(i)<=g(i)\}$

for each $i\in\mathds{N}$ let $\mathds{N}_{i}\subseteq\mathds{N}$ be the following group:
$\mathds{N}_{i}={0,1,...,i}$
and let $R_{i}=R\cap(\mathds{N}_{i}^{\mathds{N}}x\mathds{N} _{i}^{\mathds{N}})$

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

prove\disprove:
a. for each $i<=j\;\; R_{i}\circR_{j}=R_{j}$
b. for each $i<=j \;\;R_{j}\circR_{i}=R_{i}$

I am helpless and desperate
• Dec 18th 2011, 04:20 AM
emakarov
Re: Find the Cardinality of the following Relation
Quote:

Originally Posted by GIPC
What is the Cardinality of $R_{0}$ and $R_{1}$

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

Quote:

Originally Posted by GIPC
prove\disprove:
a. for each $i<=j\;\; R_{i}\circ R_{j}=R_{j}$

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

Quote:

Originally Posted by GIPC
b. for each $i<=j \;\;R_{j}\circ R_{i}=R_{i}$

We have $f\mathrel{(R_j\circ R_i)}h$ iff $f\mathrel{R_j}g$ and $g\mathrel{R_i}h$ for some g. This means $\mathop{\mathrm{im}}(f)\subseteq N_j$, $\mathop{\mathrm{im}}(g)\subseteq N_i$ and $\mathop{\mathrm{im}}(h)\subseteq N_i$. But since $f(k)\le g(k)\le h(k)$ for all k, we also have $\mathop{\mathrm{im}}(f)\subseteq N_i$, so $f\mathrel{R_i} h$. The converse is also easy (take g = f).
• Dec 18th 2011, 04:31 AM
GIPC
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?
• Dec 18th 2011, 05:44 AM
GIPC
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 :)
• Dec 18th 2011, 09:40 AM
emakarov
Re: Find the Cardinality of the following Relation
You are right: $|R_0|=1$ and $|2^{\mathbb{N}}|=|P(\mathbb{N})|=|\mathbb{N}^{ \mathbb{N}}|=\mathfrak{c}$ (here 2 = {0, 1} and $\mathfrak{c}$ is the continuum). The natural bijection $P(\mathbb{N})\to 2^{\mathbb{N}}$ maps a set $A\subseteq\mathbb{N}$ into its characteristic function.
• Dec 18th 2011, 10:56 AM
GIPC
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.
• Dec 18th 2011, 11:44 AM
emakarov
Re: Find the Cardinality of the following Relation
But I described the bijection between $P(\mathbb{N})$ and $2^{\mathbb{N}}$ in post #5. As for $|R_1|$, it is at least $|2^{\mathbb{N}}|=\mathfrak c$ and at most $|\mathbb{N}^{\mathbb{N}}\times\mathbb{N}^{\mathbb{ N}}|=\mathfrak c\cdot \mathfrak c=\mathfrak c$.
• Dec 18th 2011, 11:55 AM
GIPC
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?
• Dec 18th 2011, 12:20 PM
Plato
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.
$A\sim B$ means that $A~\&~B$ have the same cardinality.
We know that if $A\sim B~\&~X\sim Y$ then $A^X\sim B^Y$.

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

Thus $\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.
• Dec 18th 2011, 12:49 PM
GIPC
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.
• Dec 18th 2011, 01:33 PM
emakarov
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 $f:2^{\mathbb{N}}\to R_1$ where $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 $R_1$ to $2^{\mathbb{N}}\times2^{\mathbb{N}}$.

This way, you have shown that $|2^{\mathbb{N}}|\le|R_1|\le|2^{\mathbb{N}}\times2^ {\mathbb{N}}|$. It is left to prove that $|2^{\mathbb{N}}|=|2^{\mathbb{N}}\times2^{\mathbb{N }}|$, and then $|2^{\mathbb{N}}|=|R_1|$ would follow by Cantor-Bernstein-Schroeder theorem.
• Dec 19th 2011, 09:24 AM
GIPC
Re: Find the Cardinality of the following Relation
Quote:

Originally Posted by emakarov
Can we have $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?
• Dec 19th 2011, 09:34 AM
emakarov
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 $R_0$ is 1, but because $R_0$ consists of a pair whose elements are constant zero functions. But yes, that's the reason.
• Dec 19th 2011, 10:50 AM
GIPC
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 $f\mathrel{(R_j\circ R_i)}h$ iff $f\mathrel{R_j}g$ and $g\mathrel{R_i}h$ for some g. This means $\mathop{\mathrm{im}}(f)\subseteq N_j$, $\mathop{\mathrm{im}}(g)\subseteq N_i$ and $\mathop{\mathrm{im}}(h)\subseteq N_i$. But since $f(k)\le g(k)\le h(k)$ for all k, we also have $\mathop{\mathrm{im}}(f)\subseteq N_i$, so $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.
• Dec 19th 2011, 10:57 AM
emakarov
Re: Find the Cardinality of the following Relation
If $f\mathrel{R_i} h$, then $f\mathrel{R_j} f$ and $f\mathrel{R_i} h$, so $f\mathrel{(R_j\circ R_i)}h$.
Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last