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

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

 

[matt grime]

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

 

[GreenApple]

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

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.

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!

 

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

 

[matt grime]

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.

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?

 

[GreenApple]

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?

Thanks, teacher! Your advise always helps!
What a stupid mistake I made
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.

 

[HallsofIvy]

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

 

[GreenApple]

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

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.

 

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