1. ## Cardinality of Sets

Q: Consider set A and B.

Their exists 'f' an onto mappping from A -> B
Similarliy their exists 'g' an onto mapping from B -> A

Prove that their exists a bijection between A,B. (i.e. they have same cardinality)

2. Originally Posted by aman_cc
Q: Consider set A and B.

Their exists 'f' an onto mappping from A -> B
Similarliy their exists 'g' an onto mapping from B -> A

Prove that their exists a bijection between A,B. (i.e. they have same cardinality)

Let $\displaystyle f: A \rightarrow B$ be a surjection. Then there exists a function $\displaystyle f^{-1}:B \rightarrow A$ defined such that $\displaystyle f(f^{-1}(a)) = a$ - essentially, you look at the sets of pre-images of elements in B and choose a specific element from each set (this is a function as $\displaystyle f$ is a surjection).

So, for example, if $\displaystyle A = \mathbb{Q}$ and $\displaystyle B = \mathbb{N}$ with $\displaystyle f:a.x_1x_2 \mapsto a$ (truncate the decimal expansion) then set $\displaystyle f^{-1}(a) = a$, but equally it could be $\displaystyle a.5$ or $\displaystyle a.14159\ldots$ etc. Does that make sense?...

What can you say about this function $\displaystyle f^{-1}$?

3. Originally Posted by Swlabr
Let $\displaystyle f: A \rightarrow B$ be a surjection. Then there exists a function $\displaystyle f^{-1}:B \rightarrow A$ defined such that $\displaystyle f(f^{-1}(a)) = a$ - essentially, you look at the sets of pre-images of elements in B and choose a specific element from each set (this is a function as $\displaystyle f$ is a surjection).

So, for example, if $\displaystyle A = \mathbb{Q}$ and $\displaystyle B = \mathbb{N}$ with $\displaystyle f:a.x_1x_2 \mapsto a$ (truncate the decimal expansion) then set $\displaystyle f^{-1}(a) = a$, but equally it could be $\displaystyle a.5$ or $\displaystyle a.14159\ldots$ etc. Does that make sense?...

What can you say about this function $\displaystyle f^{-1}$?

$\displaystyle f^{-1}$ is an into function from $\displaystyle B \rightarrow A$

But I'm sry, unable to take the argument forward.

4. Originally Posted by aman_cc

$\displaystyle f^{-1}$ is an into function from $\displaystyle B \rightarrow A$

But I'm sry, unable to take the argument forward.
Well, it is well-known that if there is an injection $\displaystyle h: A\rightarrow B$ then $\displaystyle |A| \leq |B|$. This is what I was heading for. Is this a fact that you know?

5. Originally Posted by Swlabr
Well, it is well-known that if there is an injection $\displaystyle h: A\rightarrow B$ then $\displaystyle |A| \leq |B|$. This is what I was heading for. Is this a fact that you know?
Yes I know that. So your argument is |A|<=|B| and similarliy |A|>=|B| and thus conclude |A| = |B|. Am I correct?

But I was trying to establish that
1. there exists a bijection
2. construct this bijection (if possible) and
3. then arrive at |A| = |B|.

(definition I am using is if there is bijection between A and B then |A| = |B|)

Any idea there?

Thanks

6. Originally Posted by aman_cc
Yes I know that. So your argument is |A|<=|B| and similarliy |A|>=|B| and thus conclude |A| = |B|. Am I correct?

But I was trying to establish that
1. there exists a bijection
2. construct this bijection (if possible) and
3. then arrive at |A| = |B|.

(definition I am using is if there is bijection between A and B then |A| = |B|)

Any idea there?

Thanks
But surely this proves that there is a bijection? If two sets have the same cardinality, there exists a bijection between them.

What I would now do is look at the proof of the injectivity and see if this is a constructive proof. I recon it should be. This will then give you your answer.

7. Originally Posted by Swlabr
But surely this proves that there is a bijection? If two sets have the same cardinality, there exists a bijection between them.

What I would now do is look at the proof of the injectivity and see if this is a constructive proof. I recon it should be. This will then give you your answer.
Yes it surely does.

But I'm more interested in finding out a bijection.

Can you guide me where can I read the approach you suggested further plz?

8. Originally Posted by aman_cc
Yes it surely does.

But I'm more interested in finding out a bijection.

Can you guide me where can I read the approach you suggested further plz?
On second thought - you said

" Well, it is well-known that if there is an injection then . "

So, is this an axiom or a theorm. If later - any idea to prove it? Myabe that will help me get some clarity here

9. Originally Posted by aman_cc
Yes it surely does.

But I'm more interested in finding out a bijection.

Can you guide me where can I read the approach you suggested further plz?
The theorem is called, I believe, the Schroeder–Bernstein theorem. So, pick your favourite undergraduate introduction to pure mathematics and look in there.

There is, apparently, a proof on wiki. I haven't read over it though.

10. Originally Posted by Swlabr
The theorem is called, I believe, the Schroeder–Bernstein theorem. So, pick your favourite undergraduate introduction to pure mathematics and look in there.

There is, apparently, a proof on wiki. I haven't read over it though.
Thanks this is exactly what I was looking for. Thanks for your help.

11. I agree that for this particular problem, it's probably better to refer to a textbook proof, since it is not the kind of problem a beginner is likely able to solve by him or herself.

By the way, some proofs use recursion on the set of natural numbers (thus supposing the axiom of infinity), but other proofs don't rely on recursion. Two very different proofs (neither relying on recursion) can be found, e.g., in two different Dover textbooks: One by Stoll and one by Suppes. I think the proof in Stoll is the nicest I've seen. The one in Suppes is very clever too, but what a crazy winding road it is!

12. Originally Posted by MoeBlee
I agree that for this particular problem, it's probably better to refer to a textbook proof, since it is not the kind of problem a beginner is likely able to solve by him or herself.

By the way, some proofs use recursion on the set of natural numbers (thus supposing the axiom of infinity), but other proofs don't rely on recursion. Two very different proofs (neither relying on recursion) can be found, e.g., in two different Dover textbooks: One by Stoll and one by Suppes. I think the proof in Stoll is the nicest I've seen. The one in Suppes is very clever too, but what a crazy winding road it is!