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

1. Oct 10, 2006

GreenApple

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. Oct 11, 2006

matt grime

It isn't true. It is true if and only if A is finite.

3. Oct 11, 2006

GreenApple

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.

4. Oct 11, 2006

GreenApple

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
5. Oct 11, 2006

matt grime

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?

6. Oct 11, 2006

GreenApple

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.

7. Oct 13, 2006

HallsofIvy

Staff Emeritus
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}.

8. Oct 13, 2006

GreenApple

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
9. Oct 13, 2006

GreenApple

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