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

[rdr3]

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(x₁)=f(x₂), thus giving us x₁=x₂. And onto is ∀y∈Y, ∃x : f(x)=y.



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

 

[Deveno]

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(Y₁) = f^-1(Y₂),

for Y₁,Y₂ ⊆ Y.

let y₁ be an element of Y₁.

then if x₁ is in f^-1(y₁), x₁ is in f^-1(Y₁), (since f(x₁) = y₁, which is in Y₁). <--the fact that f is onto used HERE (see below).

but f^-1(Y₁) = f^-1(Y₂),

so x₁ is in f^-1(Y₂), so y₁ = f(x₁) is in Y₂.

thus Y₁ ⊆ Y₂.

(you should now show that likewise, Y₂ ⊆ Y₁).

there's one more subtle point to observe: we need to know that f^-1(Y₁) is non-empty for any non-empty subset Y₁ of Y (so that our x₁ 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 y₁ that live in Y₁) then there exists x in f^-1(y),
which is a subset of f^-1(Y).

so if Y₁ is non-empty, f^-1(Y₁) is non-empty (it contains at least one element that is a pre-image of at least one element of Y₁).