Prove: f is one-to-one iff f is onto

Oct 2009
255
20
St. Louis Area
Suppose A and B are finite sets with |A| = |B| and that f: A \(\displaystyle \longrightarrow \)B is a function. Prove: f is one-to-one iff f is onto.

Proof that f is onto: Suppose f is injective and f is not onto. Since |A| = |B| every \(\displaystyle a_{i}\in A\) can be paired with exactly one \(\displaystyle b_{i}\in B\). Now since f is injective, if \(\displaystyle f(a_{i})=f(a_{j})=b_{i}\), then \(\displaystyle a_{i}=a_{j}\). If f is not onto then there is a \(\displaystyle b_{i}\in B\) for which there is no \(\displaystyle a_{i}\in A\) such that \(\displaystyle f(a_{i})=b_{i}\). But this is a contradiction since this would mean that at least two unequal \(\displaystyle a_{i},a_{j}\in A\) would map to the same \(\displaystyle b_{i}\in B\). Therefore f must be onto if f is injective.

Proof that f is injective: Suppose f is onto and f is not injective. Then there exists \(\displaystyle a_{i},a_{j}\in A\) and \(\displaystyle b_{i}\in B\) such that \(\displaystyle f(a_{i})=f(a_{j})=b_{i}where a_{i}\neq a_{j}\). Now again |A| = |B| means that every \(\displaystyle a_{i}\) can be paired with exactly one \(\displaystyle b_{i}\). If there exists an \(\displaystyle a_{i}\neq a_{j}\) such that \(\displaystyle f(a_{i})=f(a_{j})=b_{i}\) and \(\displaystyle i\neq j\) then there must exist a \(\displaystyle b_{j}\) for which there is no \(\displaystyle a_{j}\) such that \(\displaystyle f(a_{j})=b_{j}\) which is a contradiction. This means that f is injective if f is onto. QED

Would someone be kind enough to critique this proof? Thanks.
 

Plato

MHF Helper
Aug 2006
22,507
8,664
Here another approach.

Because \(\displaystyle f\) is injective we know that \(\displaystyle |A|=|f(A)|\).
Now \(\displaystyle f(A)\subseteq B\) so \(\displaystyle |B|=|A|=|f(A)|\le |B|\).
Thus \(\displaystyle f\) is onto.

If \(\displaystyle f\) is onto \(\displaystyle f(A)=B\) so \(\displaystyle |B|=|A|\ge |f(A)|=|B|\).
That means that |A|=|f(A)|. Or \(\displaystyle f\) is injective.
 
Feb 2010
470
154
First, some of those subscript indexes are superfluous.

Second, you wrote:

"If there exists an \(\displaystyle a_{i}\neq a_{j}\) such that \(\displaystyle f(a_{i})=f(a_{j})=b_{i}\) and \(\displaystyle i\neq j\) then there must exist a \(\displaystyle b_{j}\) for which there is no \(\displaystyle a_{j}\) such that \(\displaystyle f(a_{j})=b_{j}\)"

That is question begging, since you give no argument for it, and it is essentially what you need to prove anyway. You're basically just asserting what is at the heart of what you need to prove.

One approach to proving the theorem would be to use induction on the finite size of A.
 
Feb 2010
470
154
Because \(\displaystyle f\) is injective we know that \(\displaystyle |A|=|f(A)|\).
Now \(\displaystyle f(A)\subseteq B\) so \(\displaystyle |B|=|A|=|f(A)|\le |B|\).
Thus \(\displaystyle f\) is onto.
Yes (and removing the unnecessary cardinality operator here) A, B and the range of f are all 1-1 with one another, f is an injection from A into B, and the range of f injects into B. But you have not shown (yet) that f itself is a bijection between A and B. So how did you derive that f is onto B?

If \(\displaystyle f\) is onto \(\displaystyle f(A)=B\)
Yes, for this direction, by assumption f is onto B.

so \(\displaystyle |B|=|A|\ge |f(A)|=|B|\).
Yes.

That means that |A|=|f(A)|. Or \(\displaystyle f\) is injective.
We may conclude, as you do, that A is 1-1 with the range of f, but you haven't (yet) shown that f itself is a bijection witnessing that A is 1-1 with the range of f, which is essentially the problem of the exercise.

What is telling about your arguments is that no use of the FINITENESS of A and B is used (or at least not explicitly).

My suggestion would be to use induction on the finite cardinality of A and B.

P.S. There was another thread a short while back in which I corrected an errant assertion by you. I wonder whether you had made note of it.
 
Apr 2009
678
140
I feel this is not entirely rigorous - for e.g. why should f(ai) = (aj) = bi? There is no requirement for that

Only tools you have is that |A| = |B| and tha the cardinality is FINITE. so
1. There exists a bijection between A and B (by definition)
2. A or B cannot be put into one-one mapping with a proper subet of its own. (by lemma of finite cardinality)

I think using this you can proceed with your proof. Plato has used the above implictly in his proof.

PS: It will be interesting to note why this doesn't hold true for infinite set (because of reason 2 above)
 
Feb 2010
470
154
IA or B cannot be put into one-one mapping with a proper subet of its own. (by lemma of finite cardinality)
That is the pigeonhole principle. But it has not been stated that it is a previously proven theorem in the context of this exercise. If we may use the pigeonhole principle as a previously proven theorem, then, if I'm not mistaken, the exercise is pretty easy. On the other hand, without the pigeonhole principle at our disposal, then I would suggest either first proving it (by induction, if I recall) or using induction for the exercise itself.
 
Apr 2009
678
140
Sure MoeBlee - I took the two points I wrote as well proven results which can be used directly.

I have a question on this - To prove that if f is ONTO => f is ONE-ONE - This proof uses Axiom of Choice in some way or the other? Am I correct please. Thanks
 

Plato

MHF Helper
Aug 2006
22,507
8,664
I have a question on this - To prove that if f is ONTO => f is ONE-ONE - This proof uses Axiom of Choice in some way or the other? Am I correct please. Thanks
Again remember that the sets are finite.
Here is a useful page on the axiom of choice.
 
  • Like
Reactions: aman_cc
Feb 2010
470
154
To prove that if f is ONTO => f is ONE-ONE - This proof uses Axiom of Choice in some way or the other?
Two points:

(1) In the exercise, the sets are finite, so the axiom of choice is not needed.

(2) If we don't assume that the sets are finite, then even WITH the axiom of choice,

we can NOT prove:

(2a) (A and B are 1-1 & f is a function from A onto B) -> f is an injection

and we can NOT prove:

(2b) (A and B are 1-1 & f is an injection from A into B) -> f is onto B

It should be easy for you to show that (assuming Z set theory is consistent, which we ordinarily take as a tacit assumption) we can not prove (2a) and we can not prove (2b).
 
  • Like
Reactions: aman_cc