Math Is Fun Forum

dchilow

Member

Registered: 2007-03-05

Posts: 27

Need Abstract Math Help!

Prove by induction the following:  Let f be a bijection from [m] to [n].  Prove that m=n.

Please someone help me.  Thank you.

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: Need Abstract Math Help!

Ah, the pigeon hole principle.  This is actually a lot easier than it looks.  Do your proof by induction on n.  Let n = 1.  Then there is only one element in [n], so there is at least 1 element in [m].  Also, by onto, you are guaranteed no more than 1 element in [m].  Thus, m = 1.

Now induct.  Add 1 to n.  Assume there is a bijection from from [n+1] to [m+1], remove k and f(k) from [n+1] and [m+1] to form [n] and [m], and thus, n = m, so n+1 = m+1.

It may seen like I'm cheating by using properties of 1-1 and onto mappings.  But this is exactly what you're expected to do.  Definitions are set up so that certain things become easy.

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

dchilow

Member

Registered: 2007-03-05

Posts: 27

Re: Need Abstract Math Help!

I understand the base case, but I am not sure how to set up my problem to take k away.  I am really confused by all of this because I have not seen any examples in class on this sort of proof.  My Prof. is in to discovery teaching, so he doesn't give us any examples.

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: Need Abstract Math Help!

You have never learned proof by induction?  There are other ways to do this, but they need other tools.  If you're proving things about finite functions, induction is a great thing to have.  So here is basically how it goes:

You wish to prove proposition P(n) for all natural numbers n = 1, 2, ...

First, we show that P(1) is true.  Typically, this is trivial, as in your case [1] bijected must go onto [1].

Now, we assume that P(n) is true, for some (not all) n, and use P(n) being true to prove that P(n+1) is true.  In your case, we assume that if there is a bijection from [n] to [m], then n = m.  Now we must show that if there is a bijection from [n+1] to [m+1], then n+1 = m+1.

Now here is the kicker.  We showed that P(1) is true.  We also showed that P(n) being true implies that P(n+1) is true as well.  So since P(1) is true, it must be that P(1 + 1) is true, or rather, P(2) is true.  But since P(2) is true, it must be that P(3) is true.  And since P(3) is true... and so on.  This way we cover all the natural numbers.

Does that make more sense?

Another way to do it:  card(S) means the cardinality of a set S (# of elements for finite sets)

A bijection from set S to T implies that card(S) = card(T).  Thus, if there is a bijection from [n] to [m], card([n]) = card([m]), but card([n]) = n and card([m]) = m. 

However, I would hesitate to do it this way.  It's practically assuming the conclusion.

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."