Thread: Proofs: pigeonhole principle and functions

I need help with two proofs.

First, I must prove the pigeon hole principle.

Second, Let f: A --> B be an injection between two finite sets of the same size. From this, Prove the f is a bijection.

Originally Posted by jzellt

I need help with two proofs.

First, I must prove the pigeon hole principle.

see here, or here

Second, Let f: A --> B be an injection between two finite sets of the same size. From this, Prove the f is a bijection.

a proof by contradiction should work. you may use the first proof to help you.

assume to the contrary that f:A --> B is an injection between sets A and B with |A|=|B|, but f is NOT an bijection. then it would mean that either f is not injective, or not surjective. by assumption, it is injective, so it must be the case that it is not surjective, that is, not onto. but that would mean .....