Results 1 to 6 of 6

Math Help - Proof involving functions.

  1. #1
    Member
    Joined
    May 2009
    Posts
    211

    Proof involving functions.

    I have a statement to prove:

    If f: A-->B is onto ... then prove that there exists a function g: B-->A such that g is one-to-one.

    .
    .

    What i've come up with as a proof is the following:

    Let xeA, and yeB, and f(x)=y, and g(y)=x (e is "element of")

    Then suppose f is onto.
    Thus: For all y there exists some x s.t. f(x)=y
    Thus: There exists a y s.t. f(x*)=y or there exists a y s.t. f(x**)=y
    Thus: If there exists a y s.t. f(x*)=y=f(x**); then by definition of a function, we know that x*=x**
    Thus: for all x s.t. f(x)=y, then f(x*)=f(x**) means that x*=x**
    ...Aplying the equivalences given at the beggining:
    if y*=y** then we can deduce that g(y*)=g(y**)

    Thus: (with insecurity =( ...) There exists a function g: B-->A such that g is one-to-one.


    I know i am commiting logical errors, but i cant seem to find another way to do this proof. Any suggestions will be greatly appreciated!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,969
    Thanks
    1788
    Awards
    1

    Re: Proof involving functions.

    Quote Originally Posted by Arturo_026 View Post
    prove:
    If f: A-->B is onto ... then prove that there exists a function g: B-->A such that g is one-to-one.
    {\forall t \in B} define A_t such that x\in A_t if and only if f(x)=t.
    Because f is onto, each A_t\not=\emptyset.
    Moreover if t\in B~\&~s\in B such that t\ne s then A_t\cap A_s=\emptyset.
    Now use those sets to construct a one-to-one function g:B\to A.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: Proof involving functions.

    Plato's idea is correct. I'd like to comment on your proof.

    Thus: If there exists a y s.t. f(x*)=y=f(x**); then by definition of a function, we know that x*=x**
    The definition of a function says that if f(x) = y* and f(x) = y**, then y* = y**. What you wrote is true only if f is one-to-one.

    Concerning the rest, writing a proof should be similar to writing a computer program, which is a sequence of instructions for building certain objects. In a program, it is important that every object that you use has already been built, and it is important to know the scope of each object, i.e., places where you can refer to it.

    Quote Originally Posted by Arturo_026 View Post
    Let xeA, and yeB, and f(x)=y, and g(y)=x (e is "element of")
    Quote Originally Posted by Arturo_026 View Post
    Thus: There exists a y s.t. f(x*)=y or there exists a y s.t. f(x**)=y
    Here you used g, x* and x** without defining them. Using g is especially problematic because this is what the problem asks to construct in the first place.

    Typically, ways to introduce a variable x are:
    (1) "for all x ..."
    (2) "there exists an x such that ..."
    (3) "let x = ..."
    (4) "fix some x from the set ..."

    In (1) and (2), the scope of x is the current sentence, which means that you usually can't refer to x in the following sentences. In (3) and (4), the scope of x is the rest of the proof. In those cases, of course, it is not good to introduce other objects later with the same names.

    Usually if a variable is used without such introductions, it is assumed that it is introduced by "for all". E.g.,

    "Since f is onto, if y ∈ B, then there exists an x ∈ A such that f(x) = y"

    means

    "Since f is onto, for all y, if y ∈ B, then there exists an x ∈ A such that f(x) = y."

    So, in your future proofs, ask yourself for each variable that you use, how this variable was introduced and what its scope is.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    May 2009
    Posts
    211

    Re: Proof involving functions.

    Quote Originally Posted by emakarov View Post
    So, in your future proofs, ask yourself for each variable that you use, how this variable was introduced and what its scope is.
    This was, and will be tremendously helpful. Thank you so much!
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    May 2009
    Posts
    211

    Re: Proof involving functions.

    Quote Originally Posted by Plato View Post
    {\forall t \in B} define A_t such that x\in A_t if and only if f(x)=t.
    Because f is onto, each A_t\not=\emptyset.
    Moreover if t\in B~\&~s\in B such that t\ne s then A_t\cap A_s=\emptyset.
    Now use those sets to construct a one-to-one function g:B\to A.
    I am very surprised and also scared to know that I was supposed to come up with something like this.

    Anyways, taking your guidence, I've spent a lot of time trying to construct g s.t. it is 1-1.
    And this is what I was able to think of:

    Let A be a set s.t A=A_t U A_s
    Thus we can construct a function g:B-->A s.t. if teB & seB such that s "not equal to" t, then there exists A_t "subset of" A & A_s "subset of" A s.t. A_t "not equal to" A_s.
    Therefore there exists a g s.t. this is one-to-one.

    How close (or far) was I?

    Thank you
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,969
    Thanks
    1788
    Awards
    1

    Re: Proof involving functions.

    Quote Originally Posted by Arturo_026 View Post
    Thus we can construct a function g:B-->A
    By the choice axiom we can choose one element from each A_t call it \mathbf{c}_t
    Then if t\in B define g(t)=\mathbf{c}_t
    Last edited by Plato; September 8th 2011 at 03:35 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Proof involving closures of functions in metric spaces
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: November 2nd 2010, 06:23 AM
  2. Replies: 1
    Last Post: September 10th 2010, 10:35 PM
  3. Proof involving an integral of a product of 2 functions
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: April 12th 2010, 04:29 AM
  4. Analytical Q involving cos and e functions
    Posted in the Trigonometry Forum
    Replies: 0
    Last Post: May 31st 2009, 05:47 AM
  5. Proof involving functions
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 27th 2007, 01:04 PM

Search Tags


/mathhelpforum @mathhelpforum