Results 1 to 13 of 13

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

  1. #1
    Member oldguynewstudent's Avatar
    Joined
    Oct 2009
    From
    St. Louis Area
    Posts
    241

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member oldguynewstudent's Avatar
    Joined
    Oct 2009
    From
    St. Louis Area
    Posts
    241
    Thank you!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    Quote Originally Posted by Plato View Post
    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?

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

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

    Quote Originally Posted by Plato View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Apr 2009
    Posts
    677
    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)
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    Quote Originally Posted by aman_cc View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Super Member
    Joined
    Apr 2009
    Posts
    677
    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
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1
    Quote Originally Posted by aman_cc View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    Quote Originally Posted by aman_cc View Post
    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).
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Super Member
    Joined
    Apr 2009
    Posts
    677
    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
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    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.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    Quote Originally Posted by aman_cc View Post
    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)
    Last edited by MoeBlee; June 25th 2010 at 10:21 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Prove a(AB)=(aA)B=A(aB) ..
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: September 29th 2010, 04:14 AM
  2. how to prove abs(a-b) <= abs(a) + abs(b)?
    Posted in the Calculus Forum
    Replies: 5
    Last Post: September 27th 2010, 06:52 PM
  3. Replies: 2
    Last Post: August 28th 2009, 02:59 AM
  4. Please prove
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: April 7th 2009, 01:58 PM
  5. Prove this .
    Posted in the Math Topics Forum
    Replies: 5
    Last Post: February 18th 2009, 04:09 AM

Search Tags


/mathhelpforum @mathhelpforum