2

Suppose that $f$ is a function from $A$ to $B$, where $A$ and $B$ are finite sets with $|A|=|B|$. Show that $f$ is one-to-one if and only if it is onto.

My prof. wants us to use the Schröder-Bernstein theorem to prove this. I am not really sure how to go about solving this at all any

Community
  • 1
user131264
  • 23
  • 1
    Do you mean $|A| = |B|$? –  Feb 24 '14 at 23:59
  • Yah its $|A| = |B|$. It looks like our professor copied it wrong from the book to our handout. I think that makes more sense now. – user131264 Feb 25 '14 at 00:03
  • Ok, so based on that I can prove that f is one-to-one based on the theorem, but I am not sure how to show that it is only one-to-one if it is onto. – user131264 Feb 25 '14 at 00:07
  • it seems highly unlikely to use CSB here. Prove by induction makes much more sense. I really don't see what the instructor intended with this question. I'm curious... – Ittay Weiss Feb 25 '14 at 00:13

1 Answers1

0

Draw some diagrams. Draw a vertical line of say, 5 dots, and then another one about 10cm away. Call them $A$ and $B$. Draw lines from the dots in $A$ to the dots in $B$ (i.e., represent some function) and get a feel for why injectivity and surjectivity are equivalent for finite sets of the same size (and so further, understand why one need only check for either injectivity or surjectivity to be sure of bijectivity). I would imagine from this it will begin to become transparent, and a proof should come to mind.

FireGarden
  • 5,835
  • this does not quite answer the question. The question was how to use CSB in order to prove this result. Personally though, I don't quite understand what the instructor had in mind. – Ittay Weiss Feb 25 '14 at 00:12
  • 1
    To me, CSB says if $f:A\mapsto B$ and $g:B\mapsto A$ are both injective then a bijection $h$ exists. I don't really see why you'd want to use that at all! I thought some advice leading to a proof would be better than nothing.. – FireGarden Feb 25 '14 at 00:16