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

  • #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
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).

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