Freethought & Rationalism Archive

Jayjay · 12-31-2002, 07:00 PM

I'm pretty sure that the following is true:

Let A, B be arbitrary sets. If there exist functions f: A->B and g: B->A such that f and g are injections, then there exists a bijection from A to B.

But I'm having trouble figuring out a simple enough proof that wouldn't require more than your average high school math.

wade-w · 12-31-2002, 08:01 PM

IIRC, we talked about cardinal numbers in high school. Lets denote the cardinality of a set S by |S|. How about this:

Since f and g are both injective, |A| <= |B| and |B| <= |A|. Hence |A|=|B| and therefore there is a bijection from A to B.

Jayjay · 12-31-2002, 08:12 PM

Quote:

Originally posted by wade-w
...Hence |A|=|B| and therefore there is a bijection from A to B.

Actually, this is the "therefore" that I'd like to see proven. Or alternatively, how exactly do you construct a bijection if you have two arbitrary injections?

EDIT: Oops, is |A|=|B| defined as "there exists a bijection between A and B? In that case ignore what I just said.

I'd still like to see the construction of bijection from two injections though, if there is a simple way of doing it... (i.e. not just showing that a bijection exists, but actually providing it.)

Principia · 12-31-2002, 08:22 PM

If the cardinality of the two sets are the same, then f and g are also surjections. In that case, by definition, f and g are also bijections.

wade-w · 12-31-2002, 08:23 PM

Exactly, Jayjay. That is the definition of |A|=|B| (if one accepts the axiom of choice, that is).

As far as providing an explicit bijection, that is going to be entirely dependent on the properties of A and B. I don't know that there is an algorithm for constructing a bijection given two arbitrary injections. Its an interesting question, I'll give you that! And one I think I will look into myself.

tk · 12-31-2002, 08:26 PM

Apply the pigeon-hole principle to prove that |A| < |B| < |A|.

(|X| = number of elements in X)

Principia · 12-31-2002, 08:26 PM

This proof assumes that A and B are finite sets, right?

Jayjay · 12-31-2002, 08:27 PM

Quote:

Originally posted by Principia
If the cardinality of the two sets are the same, then f and g are also surjections.

Hmm this can't be true...

Set A = all natural numbers
Set B = even natural numbers

f:A->B, f(x)=4*x
g:B->A, g(x)=x

Now |A|=|B|, f and g are injections, but they aren't surjections...? Did I make a mistake?

wade-w · 12-31-2002, 08:38 PM

Quote:

Originally posted by Principia
This proof assumes that A and B are finite sets, right?

No, Principia. All it assumes is the definition of cardinality; specifically, what it means for two sets to have the same cardinality.

Principia · 12-31-2002, 08:41 PM

OK, then I goofed. It doesn't follow that f and g are surjections.

12-31-2002, 07:00 PM	#1
Jayjay Veteran Member Join Date: Apr 2002 Location: Finland Posts: 6,261	Help with simple math proof I'm pretty sure that the following is true: Let A, B be arbitrary sets. If there exist functions f: A->B and g: B->A such that f and g are injections, then there exists a bijection from A to B. But I'm having trouble figuring out a simple enough proof that wouldn't require more than your average high school math.

Thread Tools	Search this Thread
Show Printable Version	Search this Thread: Advanced Search

12-31-2002, 08:01 PM	#2
wade-w Veteran Member Join Date: Aug 2002 Location: Silver City, New Mexico Posts: 1,872	IIRC, we talked about cardinal numbers in high school. Lets denote the cardinality of a set S by \|S\|. How about this: Since f and g are both injective, \|A\| <= \|B\| and \|B\| <= \|A\|. Hence \|A\|=\|B\| and therefore there is a bijection from A to B.

12-31-2002, 08:22 PM	#4
Principia Veteran Member Join Date: Mar 2002 Location: anywhere Posts: 1,976	If the cardinality of the two sets are the same, then f and g are also surjections. In that case, by definition, f and g are also bijections.

12-31-2002, 08:23 PM	#5
wade-w Veteran Member Join Date: Aug 2002 Location: Silver City, New Mexico Posts: 1,872	Exactly, Jayjay. That is the definition of \|A\|=\|B\| (if one accepts the axiom of choice, that is). As far as providing an explicit bijection, that is going to be entirely dependent on the properties of A and B. I don't know that there is an algorithm for constructing a bijection given two arbitrary injections. Its an interesting question, I'll give you that! And one I think I will look into myself.

12-31-2002, 08:26 PM	#6
tk Regular Member Join Date: Dec 2002 Location: Singapore Posts: 158	Apply the pigeon-hole principle to prove that \|A\| < \|B\| < \|A\|. (\|X\| = number of elements in X)

12-31-2002, 08:41 PM	#10
Principia Veteran Member Join Date: Mar 2002 Location: anywhere Posts: 1,976	OK, then I goofed. It doesn't follow that f and g are surjections.

Freethought & Rationalism Archive

The archives are read only.