1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Introduction to Proofs: One-to-One and Onto Problem

  1. Nov 3, 2011 #1
    1. Given: Let f: X → Y be a function. Then we have an associated function f-1: P(Y) → P(X), where f-1 (B)⊂X is the inverse image of B⊂Y.

    Question: Show that f^(-1) is one-to-one if and only if f is onto.

    [Notes: ⊂ represents subspace, I just couldn’t find a way to put the line under the symbol.
    f-1 indicates the inverse of f.]



    2. Ok so I know that One-to-one means we have f(x1)=f(x2), thus giving us x1=x2. And onto is ∀y∈Y, ∃x : f(x)=y.



    3. What I did was just say that f-1(y1)=f-1(y2)=x thus giving me y1=y2. Or I tried proving it the other way by way of Contradiction. Saying that if f-1(y1)=f-1(y2)=x, but y1≠y2. Then we would get f(x)=y1 and f(x)=y2 but y1≠y2, thus making it not a function. So that's what I was able to come up with.
     
  2. jcsd
  3. Nov 4, 2011 #2

    Deveno

    User Avatar
    Science Advisor

    the domain of f-1 isn't the elements of Y, it's the subsets of Y.

    it's not enough just to prove that f-1 is injective on singleton sets, without extending this to every subset of Y.

    what you want to do is something like this:

    suppose f-1(Y1) = f-1(Y2),

    for Y1,Y2 ⊆ Y.

    let y1 be an element of Y1.

    then if x1 is in f-1(y1), x1 is in f-1(Y1), (since f(x1) = y1, which is in Y1). <--the fact that f is onto used HERE (see below).

    but f-1(Y1) = f-1(Y2),

    so x1 is in f-1(Y2), so y1 = f(x1) is in Y2.

    thus Y1 ⊆ Y2.

    (you should now show that likewise, Y2 ⊆ Y1).

    there's one more subtle point to observe: we need to know that f-1(Y1) is non-empty for any non-empty subset Y1 of Y (so that our x1 in the proof actually exists).

    this is where the fact that f is onto comes into play, if y is ANY element of Y (including those y1 that live in Y1) then there exists x in f-1(y),
    which is a subset of f-1(Y).

    so if Y1 is non-empty, f-1(Y1) is non-empty (it contains at least one element that is a pre-image of at least one element of Y1).
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Introduction to Proofs: One-to-One and Onto Problem
  1. One to one and onto (Replies: 0)

  2. One-to-one and onto (Replies: 3)

Loading...