Math Is Fun Forum

euclidcries

Guest

Proving set bijections

Hi, I know about cantor diagonalization argument, but are there any other ways of showing that there is a bijection between two sets? Like, maybe an example using rationals and integers? Or maybe a case where cantors diagonalization argument won't work?

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Proving set bijections

Hi;

Bijective simply means one to one and onto ( one to one correspondence ). The pickle diagram below shows that the two sets are in one to one correspondence.

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

All_Is_Number

Member

Registered: 2006-07-10

Posts: 258

Re: Proving set bijections

Are you wanting to show that two sets have the same cardinality?

---

You can shear a sheep many times but skin him only once.

All_Is_Number

Member

Registered: 2006-07-10

Posts: 258

Re: Proving set bijections

If there exists an injective function from A to B and there exists an injective function from B to A, then |A| = |B|, and therefore there is a bijection between A and B.

Last edited by All_Is_Number (2011-01-26 16:22:44)

---

You can shear a sheep many times but skin him only once.

euclidcries

Guest

Re: Proving set bijections

Hi all,

Bobbym I understand what you are saying, but how do I do this kind of pairing for infinite sets?

Are you wanting to show that two sets have the same cardinality?

Yes...but the only way I know is using Cantor's diagonalization argument

If there exists an injective function from A to B and there exists an injective function from B to A, then |A| = |B|, and therefore there is a bijection between A and B.

Hmm...okay,

when you say "injective function" are you saying one-to-one correspondence? Because that makes sense, if there is a "matching" from A to B and a matching from B to A then there is a bijection.

but, what does the notation |A| or |B| mean? (when you wrote |A| = |B|, what is this statement saying?) Also, how is this done for infinite sets?

Thanks for your replies!

All_Is_Number

Member

Registered: 2006-07-10

Posts: 258

Re: Proving set bijections

when you say "injective function" are you saying one-to-one correspondence?

No, not quite. An injective function is another name for a one to one function, which implies the following:

if f(a) = f(b), then a = b.

A one to one correspondence is another name for bijection between sets.

but, what does the notation |A| or |B| mean? (when you wrote |A| = |B|, what is this statement saying?) Also, how is this done for infinite sets?

|A| is the cardinality of set A.

By definition, |A| ≤ |B| if there is a one to one mapping of A into B. By the Schröder-Bernstein Theorem, if |A|≤|B| and |B|≤|A|, then |A|=|B|, which implies that there is a bijection between A and B. (See: <http://plato.stanford.edu/entries/set-theory/primer.html#5> and <http://mathworld.wolfram.com/Schroeder-BernsteinTheorem.html>)

I'll try to address the rest of your post later. I have to get to class right now.

Last edited by All_Is_Number (2011-01-27 06:46:52)

---

You can shear a sheep many times but skin him only once.

All_Is_Number

Member

Registered: 2006-07-10

Posts: 258

Re: Proving set bijections

Also, how is this done for infinite sets?

Just because two sets are infinite does not imply that their cardinality is the same. In other words, given two infinite sets |A| and |B|, we cannot conclude that |A|=|B| (although sometimes this is true).

For example,

E = {x | x/2 ∈ ℤ} is the even integers.

let f:E⇾ℤ defined by f(x)=x/2. f is a bijective function, so

|E|=|ℤ|.

But, can you come up with a bijection between ℤ and ℝ?

Last edited by All_Is_Number (2011-01-27 07:06:01)

---

You can shear a sheep many times but skin him only once.