Register to reply

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

by GreenApple
Tags: function, prove
Share this thread:
GreenApple
#1
Oct10-06, 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.
Phys.Org News Partner Science news on Phys.org
Hoverbike drone project for air transport takes off
Earlier Stone Age artifacts found in Northern Cape of South Africa
Study reveals new characteristics of complex oxide surfaces
matt grime
#2
Oct11-06, 02:17 AM
Sci Advisor
HW Helper
P: 9,398
It isn't true. It is true if and only if A is finite.
GreenApple
#3
Oct11-06, 02:44 AM
P: 30
Quote Quote by matt grime
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
#4
Oct11-06, 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 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
#5
Oct11-06, 02:32 PM
Sci Advisor
HW Helper
P: 9,398
Quote Quote by 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.
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
#6
Oct11-06, 03:17 PM
P: 30
Quote Quote by 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?
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
#7
Oct13-06, 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}.
GreenApple
#8
Oct13-06, 06:17 AM
P: 30
Quote Quote by 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}.
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
#9
Oct13-06, 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,...,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".


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