Cardinality of Sets

**aman_cc** · May 2nd 2010, 11:19 PM

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)

Can anyone please help me get started with this?

**Swlabr** · May 3rd 2010, 12:42 AM

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)

Can anyone please help me get started with this?

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}$ ?

**aman_cc** · May 3rd 2010, 12:55 AM

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}$ ?

Yes I follow you -

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

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

**Swlabr** · May 3rd 2010, 01:08 AM

Originally Posted by aman_cc

Yes I follow you -

$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?

**aman_cc** · May 3rd 2010, 01:20 AM

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

**Swlabr** · May 3rd 2010, 01:24 AM

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.

**aman_cc** · May 3rd 2010, 01:34 AM

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?

**aman_cc** · May 3rd 2010, 01:47 AM

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

**Swlabr** · May 3rd 2010, 01:49 AM

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.

**aman_cc** · May 3rd 2010, 01:56 AM

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.

**MoeBlee** · May 3rd 2010, 06:56 AM

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!

**aman_cc** · May 3rd 2010, 09:09 AM

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!

Thanks for your help

Thread: Cardinality of Sets

LinkBack

Thread Tools

Display

Cardinality of Sets

Similar Math Help Forum Discussions

[SOLVED] Cardinality of Sets and Power Sets

cardinality of sets

Cardinality of these sets!

Cardinality of sets Q and R

Cardinality of sets

Search Tags