# Math Help - Prove: f is one-to-one iff f is onto

1. ## Prove: f is one-to-one iff f is onto

Suppose A and B are finite sets with |A| = |B| and that f: A $\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 $a_{i}\in A$ can be paired with exactly one $b_{i}\in B$. Now since f is injective, if $f(a_{i})=f(a_{j})=b_{i}$, then $a_{i}=a_{j}$. If f is not onto then there is a $b_{i}\in B$ for which there is no $a_{i}\in A$ such that $f(a_{i})=b_{i}$. But this is a contradiction since this would mean that at least two unequal $a_{i},a_{j}\in A$ would map to the same $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 $a_{i},a_{j}\in A$ and $b_{i}\in B$ such that $f(a_{i})=f(a_{j})=b_{i}where a_{i}\neq a_{j}$. Now again |A| = |B| means that every $a_{i}$ can be paired with exactly one $b_{i}$. If there exists an $a_{i}\neq a_{j}$ such that $f(a_{i})=f(a_{j})=b_{i}$ and $i\neq j$ then there must exist a $b_{j}$ for which there is no $a_{j}$ such that $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.

2. Here another approach.

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

If $f$ is onto $f(A)=B$ so $|B|=|A|\ge |f(A)|=|B|$.
That means that |A|=|f(A)|. Or $f$ is injective.

3. Thank you!

4. First, some of those subscript indexes are superfluous.

Second, you wrote:

"If there exists an $a_{i}\neq a_{j}$ such that $f(a_{i})=f(a_{j})=b_{i}$ and $i\neq j$ then there must exist a $b_{j}$ for which there is no $a_{j}$ such that $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.

5. Originally Posted by Plato
Because $f$ is injective we know that $|A|=|f(A)|$.
Now $f(A)\subseteq B$ so $|B|=|A|=|f(A)|\le |B|$.
Thus $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?

Originally Posted by Plato
If $f$ is onto $f(A)=B$
Yes, for this direction, by assumption f is onto B.

Originally Posted by Plato
so $|B|=|A|\ge |f(A)|=|B|$.
Yes.

Originally Posted by Plato
That means that |A|=|f(A)|. Or $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.

6. 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)

7. Originally Posted by aman_cc
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.

8. 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

9. Originally Posted by aman_cc
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.

10. Originally Posted by aman_cc
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).

11. The reson I said Axion of Choice -

Let f be a funciton from A -> B - which is ONTO but not ONE-ONE

For every b in B define a set S(b) = {a| f(a) = b}

Also define S'(b) = {First element of S(b)} ------------------>>>> Ins't this Axiom of Choice ???? The fact that S'(b) is properly defined I think relies on Axiom of Choice
Because f is ONTO S(b),S'(b) are never empty. Also S'(b) is proper subset of S(b) for some b (we have assumed f is not ONE-ONE)

Now define A' = Union of S'(b) for all b in B
Clearly
1. A' is a proper subset of A
2. There is a bijection betweem A' and B

so|A'| = |B|, but |B| = |A| => |A'| = |A| ---- contradiction for FINITE sets !!!

Hence I made the statement that proof will require Axiom of Choice.

So where did I go wrong? Is there a better approach? A proof without using Axiom of Choice implicity or explicity

12. This should not need the axiom of choice.

I haven't yet checked your argument just posted. But perhaps where you use "choice" it's really only choice over a finite set? We don't need the axiom of choice for that. We have a THEOREM for finite choice. For finite sets we can always assume choice functions without having to appeal to an additional axiom. (Perhaps you'd like to prove that as an additional exercise.)

As to a more "natural' approach to a proof here, try induction on the finite cardinality of A.

13. Originally Posted by aman_cc
So where did I go wrong?
You again assumed that no finite set is equinumerous with a proper subset of itself (i.e., as I mentioned, the pigeonhole principle). Well, that's true by definition IF 'finite' is defined as 'not Dedekind infinite'. But in the context of this exercise, I would think that is not the definition of 'finite' being used, but rather 'finite' is defined as 'equninumerous with some natural number' (or something that is equivalent in Z set theory without choice).

If the exercise is an interesting one then it doesn't assume that we've already proven the pigeonhole principle. (Though, I don't know the specific context of the exercise, so maybe the pigeonhole principle has been previously proven in context of this exercise.)

I.e., the pigeonhole principle is immediate if we define 'finite' as 'not Dedekind infinite' or, equivalently, as 'not equinumerous with a proper subset of itself'. But I'd think the definition of 'finite' here is 'equinumerous with some natural number' (or something that is equivalent in Z set theory with choice). In that case, we need to first PROVE the pigeonhole principle (i.e., that no finite set is equinumerous with a proper subset of itself) if we are to use it in this exercise.

As to the axiom of choice, we can use an actually weaker version (the axiom of countable choice) to prove the OTHER direction: If a set is not equinumerous with itself then it is finite.

To summarize:

n is (Tarski) finite <-> n is equinumerous with some natural number

n is Dedekind finite <-> n is not equinumerous with a proper subset of itself

theorem of Z set theory without choice (pigeonhole principle): if n is Tarski finite -> n is Dedekind finite
(i.e., if n is Dedekind infinite -> n is (Tarski) infinite)

theorem of Z set theory with countable choice: if n is Dedekind finite -> n is Tarski finite
(i.e. if n is Tarski infinite -> n is Dedekind infinite)