Results 1 to 10 of 10

Math Help - a theorem about one to one functions

  1. #1
    Member
    Joined
    Oct 2010
    From
    Mumbai, India
    Posts
    203

    a theorem about one to one functions

    hi

    I am trying to prove the following theorem.

    Suppose A,B,C are sets and f:B\longrightarrow C

    Suppose that A\neq \varnothing and for all functions g\;and
    h from A\longrightarrow B

    [(f\circ g=f\circ h)\Rightarrow (g=h)]

    Prove that f is one-to-one.

    Since a universal statement about functions g and h is given , I think we are
    supposed to exploit this. I am not able to come up with functions g and h suitable for the situation. Can anybody give some hints ?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,963
    Thanks
    1784
    Awards
    1

    Re: a theorem about one to one functions

    Quote Originally Posted by issacnewton View Post
    Suppose A,B,C are sets and f:B\longrightarrow C
    Suppose that A\neq \varnothing and for all functions g\;and h from A\longrightarrow B
    [(f\circ g=f\circ h)\Rightarrow (g=h)]
    Prove that f is one-to-one.
    Suppose that \{s,t\}\subseteq B and s\ne t but f(s)=f(t).

    Define \left( {\forall x \in A} \right)\left[ {g:x \mapsto s\;\& \,h:x \mapsto t} \right].

    What happens now?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Oct 2010
    From
    Mumbai, India
    Posts
    203

    Re: a theorem about one to one functions

    thanks plato for replying

    I was thinking about the nature of the sets A,B,C . lets consider the cases.
    first if both B and C are empty sets then only empty function is possible from B to C.
    There is one condition given in the problem. Let me put that in logical format.

    \forall g\forall h[(g:A\mapsto B)\wedge(h:A\mapsto B)\Rightarrow ((f\circ g=f\circ h)\Rightarrow (g=h))]

    so in the case when B=\varnothing \; C=\varnothing , the above condition is satisfied since the antecedent will always be false. Also the only empty function is also one to one since the condition

    \forall b_1 \forall b_2[(b_1\in B)\wedge(b_2\in B)\Rightarrow(f(b_1)=f(b_2)\Rightarrow b_1=b_1)]

    will always be satisfied.

    Next, consider the case where B=\varnothing \; C\neq \varnothing

    again , similar reasoning holds. the only function from B to C is an empty function, which satisfies both of the above conditions.

    Now consider the case where , B\neq \varnothing \; C=\varnothing

    here the only relation from B to C is an empty relation, which is not a function.
    since the problem states that f:B\mapsto C , we need not consider this case.

    So we finally come to the case where , B\neq \varnothing \;C\neq \varnothing

    now here I have problem with your reply. Whenever we have a statement of the
    form B\neq \varnothing , we immediately use existential statement
    \exists b\in B and we then do existential instantiation. But you
    say

    "Suppose \{s,t\}\subseteq B"

    how do we know there are two elements in B ?. All we can do here is existential instantiation, like I said.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,963
    Thanks
    1784
    Awards
    1

    Re: a theorem about one to one functions

    Quote Originally Posted by issacnewton View Post
    So we finally come to the case where , B\neq \varnothing \;C\neq \varnothing
    "Suppose \{s,t\}\subseteq B"

    how do we know there are two elements in B ?. All we can do here is existential instantiation, like I said.
    If set B has only one element then any f:B\to C is one-to-one.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Oct 2010
    From
    Mumbai, India
    Posts
    203

    Re: a theorem about one to one functions

    so we will need to make that a special case then. so after that is done ,.... we proceed as follows..

    we argue that let B have more than one element and I think your reply now makes sense and I will think about it.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,963
    Thanks
    1784
    Awards
    1

    Re: a theorem about one to one functions

    Quote Originally Posted by issacnewton View Post
    so we will need to make that a special case then. so after that is done ,.... we proceed as follows..
    we argue that let B have more than one element and I think your reply now makes sense and I will think about it.
    I really think you are making far to much out of a simple problem.
    f:B\to C is injective if and only if f(s)=f(t) \Rightarrow \,s = t.

    Equivalently f:B\to C is injective if and only if s\ne t \Rightarrow \,f(s)\ne f(t).
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4

    Re: a theorem about one to one functions

    It's quite simple (using Plato's hint):

    Suppose, toward a contradiction, that f is not 1-1.

    So there is an s in B and a t in B such that ~s=t but f(s) = f(t).

    Let g = {<x s> | x is in A} and h = {<x t> | x is in A}.

    Both g and h are functions from A into B.

    And for all x in A, we have f(g(x)) = f(s) = f(t) = f(h(x)).

    So g=h.

    Let x be in A. So <x s> = <x t>. So s=t. Contradiction.

    /

    That does it. There's no need for fussing about whether B is empty or not, and no need for any queries as to the nature of C in any way at all.
    Last edited by MoeBlee; September 19th 2011 at 10:04 AM.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    Oct 2010
    From
    Mumbai, India
    Posts
    203

    Re: a theorem about one to one functions

    Quote Originally Posted by Plato View Post
    I really think you are making far to much out of a simple problem.
    probably. But since the problem is from Velleman's "How to prove it", I am just trying to be logically rigorous. The book emphasizes that point. But the author states that these logical steps are for us to understand the logical structure of the proof. In actual proof, we skip these steps and shorten the proof.

    Moeblee, that was the line on which I was thinking. But problem just states that B, C are sets , so I was wondering the consequences of their being empty. Since empty function is possible , I just wanted to explore where it leads to..........

    \smile
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4

    Re: a theorem about one to one functions

    Of course, no harm in exploring where things lead. My only point is that for the proof, it's not required to wonder what happens when B is empty nor is any wondering whatsoever about C needed.

    When we take the reductio ad absurdum assumption that f is not 1-1, we get that B has at least two distinct members, call them 's' and 't'. And, as to C, the proof doesn't rely on mentioning anything particular about C. Indeed the problem doesn't even have to mention C or even B. It could just be:

    Suppose f is a function.

    Suppose A is nonempty.

    Suppose, for all g and h, if g is function from A into the domain of f, and h is a function from A into the domain of f, and fog = foh, then g=h.

    Show: f is 1-1.
    Last edited by MoeBlee; September 20th 2011 at 07:37 AM.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Member
    Joined
    Oct 2010
    From
    Mumbai, India
    Posts
    203

    Re: a theorem about one to one functions

    gotcha
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Counter Example for Theorem about Monotonic Functions
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: April 20th 2011, 09:02 PM
  2. Solutions to functions using Liouville's Theorem
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: December 2nd 2010, 04:00 PM
  3. Replies: 8
    Last Post: November 13th 2010, 08:14 PM
  4. Mean value theorem for harmonic functions
    Posted in the Differential Geometry Forum
    Replies: 6
    Last Post: March 27th 2010, 06:59 PM
  5. Replies: 6
    Last Post: May 4th 2009, 12:29 PM

/mathhelpforum @mathhelpforum