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.
see here, or here
a proof by contradiction should work. you may use the first proof to help you.Second, Let f: A --> B be an injection between two finite sets of the same size. From this, Prove the f is a bijection.
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 .....