How to prove a one to one function A -> A is also a onto function?

  1. Oct 10, 2006 #1
    I was doing a math problem this morning and realized that the solution lied in the fact that if a function of A -> A is one to one then it is onto. It is so obvious that I have been taking it for granted for so long time.
    But now when I think of it deeply, I find it very interesting and relating to some foundational questions like set theory and relation.
    Hope you can join with me working on this.
     
  2. jcsd
  3. Oct 11, 2006 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    It isn't true. It is true if and only if A is finite.
     
  4. Oct 11, 2006 #3
    Yeah, sorry I forgot to say A is finite. It is obviously not true for infinite A(like 1->2, 2->4, 3->6.......).
    Thanks for that.:tongue2:

    And you reminded me that the one of the most interesting things is that a property applies to finite set but fail when it comes to infinite set. And that is one of the reasons why I put up this theme. I was thinking that proving that might give you a insight into the nature of finite sets and infinite sets.

    Hope you are not taking this a waste of time.
    More discussion please!
     
  5. Oct 11, 2006 #4
    I think it will make some sense to try this way:

    I assume that a set A is finite if and only if we can get a one to one function A->S(n) where S(n) is the set { 1, 2, ....., n }, and we say that set A is of size n.

    Since we want to prove that the ONE TO ONE function f(x) A->A is onto,
    we have to draw "for every x in A, there exist a 'a' such that f(a)=x" from "if x!=y, then f(x)!=f(y)"
    We do it exactly as planed. for every x, we need to find a 'a' such f(a)=x. We can get that 'a' this way:
    1: we set S=A, k=1
    2: we check whether f(k)=x, if yes, we are done, if no, we go on our process.
    3: we reset S=A-{k}, k=k+1, goto step2

    It is easy to prove that ether we find that 'a' within testing the first n-1 elements of A, which is wanted, or we have to go through testing the last element. In the latter case, S has a form of {v} of size 1, and k=n, which can be proved by induction. Since x has to be S now and before and S is of size 1, v has to be x, and f(k) always has to be in S, we get f(n)=x, which is also what we wanted.
    That is "for every x in A, there exist a 'a' such that f(a)=x"
    (by k,1...I mean elements of A)

    I did not give too much detail, for that would be boring.
     
    Last edited: Oct 11, 2006
  6. Oct 11, 2006 #5

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    I have no idea what you want to do, but this is wrong. if there is a one to one function from A to the set [1,..,n], then there is a one to one function from A to any set with more than n elements. Thus A has size n,n+1,n+2,....

    What is it you're trying to prove? That any injective function from a finite set to itself is bijective?
     
  7. Oct 11, 2006 #6
    Thanks, teacher! Your advise always helps!
    What a stupid mistake I made:surprised
    The right thing to do may be to say "a set A is finite if and only if we can get a one to one function A->S(n) where S(n) is the set { 1, 2, ....., n }, and we can also get a one to one function S(n)->A. And we say that set A is of size n"
    I don't know whether it is right this time. I once readed something about Cantor's work, I figure this is his way to count. I could be wrong.

    What did I try to prove?
    I was trying to prove "for every x in A, there exist a 'a' such that f(a)=x", which I called 'onto'.
    My English is not very good and I only have known the term 'one to one' and 'onto'. I figure 'injective' means 'one to one' and 'bijective' means 'one to one and onto'. Right?

    By the way, how can I put mathematical signs here? I saw someone do it once. Using natural language to express mathematics becomes a bad ideal sometime.
     
  8. Oct 13, 2006 #7

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Let A be a finite set with, say, n elements (which means there exist a one to one and onto function A-> {1, 2, ..., n}), f a one to one function from A to itself. If f were not "onto", then B= f(A) is a proper subset of A. Since B is a proper subset of finite set A, it smaller than A: there exist a one to one onto function B->{1, 2, ... m} with m< n. But then we have a one to one function from A onto B and so can define a one to one function from {1, 2, ..., n} onto {1, 2, ..., m}.
     
  9. Oct 13, 2006 #8
    Thanks, professor! That is a beautiful proof. I think my problem is solved.

    But, I can't help but show some interesting point here.
    First, I think a set A is finite if and only if there exist some n which we refer to as the size of A, such that "there exist a one to one and onto function A-> {1, 2, ..., n}" as the professor says.
    In the proof given by the professor, we should prove "Since B is a proper subset of finite set A, it smaller than A: there exist a one to one onto function B->{1, 2, ... m} with m< n." which seem obvious at first sight.

    The ground is this theorem: if there exist a one to one and onto function A-> {1, 2, ..., n}, then for any x in A the following is true: there exist a one to one and onto function Ax-> {1, 2, ..., n-1} where Ax={y|y is in A and y!=x}
    Proof: there has to be a p in A such f(p)=n, if we make f'(p)=f(x), f'(x)=n,f'(y)=f(y) elsewhere, f' is also an one to one and onto function.
    We make a function g Ax->{1,2,...,n-1} by g(y)=f'(y) which can be done because that if y is in Ax then it is also in A, and obviously g is an one to one and onto function.
     
    Last edited: Oct 13, 2006
  10. Oct 13, 2006 #9
    No, it may be not so obvious to you that g is onto, so let me add somthing.
    For any m in the set {1,2,...,n-1}, there is a y in A such that f'(y)=m(because f' is onto), but y!=x because f'(x)=n, which leed to that y is in Ax. So for any m in {1,2,...,n-1}, there is a y in Ax such that g(y)=m, which is to say "g is onto".
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Similar Discussions: How to prove a one to one function A -> A is also a onto function?
  1. One to one function (Replies: 1)

  2. One to one function (Replies: 1)

  3. One-to-One Function (Replies: 2)

Loading...