# Cardinality of Sets

• May 2nd 2010, 11:19 PM
aman_cc
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)

• May 3rd 2010, 12:42 AM
Swlabr
Quote:

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 $f: A \rightarrow B$ be a surjection. Then there exists a function $f^{-1}:B \rightarrow A$ defined such that $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 $f$ is a surjection).

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

What can you say about this function $f^{-1}$?
• May 3rd 2010, 12:55 AM
aman_cc
Quote:

Originally Posted by Swlabr
Let $f: A \rightarrow B$ be a surjection. Then there exists a function $f^{-1}:B \rightarrow A$ defined such that $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 $f$ is a surjection).

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

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

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

But I'm sry, unable to take the argument forward.
• May 3rd 2010, 01:08 AM
Swlabr
Quote:

Originally Posted by aman_cc

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

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

Well, it is well-known that if there is an injection $h: A\rightarrow B$ then $|A| \leq |B|$. This is what I was heading for. Is this a fact that you know?
• May 3rd 2010, 01:20 AM
aman_cc
Quote:

Originally Posted by Swlabr
Well, it is well-known that if there is an injection $h: A\rightarrow B$ then $|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
• May 3rd 2010, 01:24 AM
Swlabr
Quote:

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.
• May 3rd 2010, 01:34 AM
aman_cc
Quote:

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?
• May 3rd 2010, 01:47 AM
aman_cc
Quote:

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 http://www.mathhelpforum.com/math-he...d68ba51e-1.gif then http://www.mathhelpforum.com/math-he...fbffdd67-1.gif. "

So, is this an axiom or a theorm. If later - any idea to prove it? Myabe that will help me get some clarity here
• May 3rd 2010, 01:49 AM
Swlabr
Quote:

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.
• May 3rd 2010, 01:56 AM
aman_cc
Quote:

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.
• May 3rd 2010, 06:56 AM
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!
• May 3rd 2010, 09:09 AM
aman_cc
Quote:

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!