Find the Cardinality of the following Relation

let the following relation:

for each let be the following group:

and let

What is the Cardinality of and

prove\disprove:

a. for each

b. for each

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

and

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

Quote:

Originally Posted by

**GIPC** prove\disprove:

a. for each

Let us write for the image of some function f. Let i = 0 and j = 1. Consider some such that . Then , so if , then there must be some g such that and . Can we have ?

Quote:

Originally Posted by

**GIPC** b. for each

We have iff and for some g. This means , and . But since for all k, we also have , so . 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: and (here 2 = {0, 1} and is the continuum). The natural bijection maps a set 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 and in post #5. As for , it is at least and at most .

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

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

Re: Find the Cardinality of the following Relation

Quote:

Originally Posted by

**emakarov** Can we have

?

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 is 1, but because 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

iff

and

for some g. This means

,

and

. But since

for all k, we also have

, so

. 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