Register to reply 
How to prove a one to one function A > A is also a onto function? 
Share this thread: 
#1
Oct1006, 11:11 PM

P: 30

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
Oct1106, 02:17 AM

Sci Advisor
HW Helper
P: 9,398

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



#3
Oct1106, 02:44 AM

P: 30

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! 


#4
Oct1106, 02:26 PM

P: 30

How to prove a one to one function A > A is also a onto function?
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 n1 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. 


#5
Oct1106, 02:32 PM

Sci Advisor
HW Helper
P: 9,398

What is it you're trying to prove? That any injective function from a finite set to itself is bijective? 


#6
Oct1106, 03:17 PM

P: 30

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. 


#7
Oct1306, 02:31 AM

Math
Emeritus
Sci Advisor
Thanks
PF Gold
P: 39,311

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
Oct1306, 06:17 AM

P: 30

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, ..., n1} where Ax={yy 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,...,n1} 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. 


#9
Oct1306, 02:33 PM

P: 30

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,...,n1}, 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,...,n1}, there is a y in Ax such that g(y)=m, which is to say "g is onto". 


Register to reply 
Related Discussions  
How to prove a function is an isometry  Differential Geometry  4  
Prove a delta function identity  Calculus & Beyond Homework  0  
Prove a sum identity for bessel function  Calculus & Beyond Homework  5  
Probability Density Function, prove it  Precalculus Mathematics Homework  1  
The error function prove  Calculus  1 