PROOF 119

Prove.

An inverse function requires injectivity

On sets and correspondences.

A way to read this proof

First separate what is assumed from what is to be proved. At each step, ask which definition or earlier result permits the move. If it is unclear, return to that premise rather than skipping to the conclusion.

Definition D1

When each element x of X corresponds to exactly one element of Y, the correspondence is called a function f: X → Y and that one element is written f(x).

Proof.

(1)If f(a) = b and f(a) = c, then b = c.A1

(2)Hence the symbol f(a) refers to a single object.(1)

∎

Definition D2

f is injective when, for all a, b ∈ X, f(a) = f(b) implies a = b.

Proof.

In contrapositive form: if a ≠ b, then f(a) ≠ f(b).A2

∎

Definition D3

The correspondence obtained by reversing the ordered pairs of f: X → Y is called f⁻. To y ∈ Y, f⁻ assigns the x ∈ X with f(x) = y.

Proof.

We do not write f⁻(y). Whether the corresponding x is unique has not yet been settled.convention

∎

Definition D4

f is surjective when for every y ∈ Y there is an x ∈ X with f(x) = y.

Proof.

If f is not surjective, there is a y to which f⁻ assigns nothing.convention, D3

∎

Lemma L1

If f is not injective, then f⁻ is not a function.

Proof.

(1)Since f is not injective, there are a, b ∈ X with f(a) = f(b) and a ≠ b.D2

(2)Let y = f(a) = f(b) be the common value.(1)

(3)f⁻ assigns both a and b to y.(1), (2), D3

(4)Since a ≠ b, what corresponds to y is not unique.(1), (3)

(5)Hence f⁻ does not satisfy the condition of D1.(4), D1

∎

Lemma L2

If f is injective, then to each y ∈ Y, f⁻ assigns at most one element.

Proof.

(1)Suppose f(a) = y and f(b) = y.assumption, D3

(2)f(a) = f(b), so a = b(1), D2

(3)Hence at most one x corresponds to y.(2), D3

∎

Theorem T1

f⁻ is a function from Y to X when, and only when, f is injective and surjective.

Proof.

(1)Suppose f⁻ is a function.assumption

(2)If f were not injective, f⁻ would not be a function; so by the contrapositive, f is injective.(1), L1, A2

(3)Each y ∈ Y has one value under f⁻, so there is an x with f(x) = y.(1), D1, D3

(4)Hence f is surjective.(3), D4

(5)Conversely, suppose f is injective and surjective.assumption

(6)At most one x corresponds to each y.(5), L2

(7)By surjectivity, there is at least one.(5), D4

(8)Hence there is exactly one, and f⁻ is a function.(6), (7), D1

∎

Corollary C

f(x) = x² has no inverse function as ℝ → ℝ. Restricting both domain and codomain to [0, ∞), it has one.

Proof.

(1)(−1)² = 1² and −1 ≠ 1, so f is not injective on ℝ.A3, A4, D2

(2)Hence f⁻ is not a function as ℝ → ℝ.(1), L1

(3)Also u² ≠ −1, so −1 is the value of no x, and f is not surjective either.A7, D4

(4)Now restrict both domain and codomain to [0, ∞).assumption

(5)If u, v ≥ 0 and u² = v², then u = v, so f is injective.(4), A5, D2

(6)If y ≥ 0, then √y ≥ 0 and (√y)² = y, so f is surjective.(4), A6, D4

(7)Hence the restricted f has an inverse function.(5), (6), T1

∎

Remark

Can A1 be removed from this proof?

Separate reversing the ordered pairs from calling the reversal a function. Check which line does which.