Functions

Jim Hefferon · GFDL + CC BY-SA 2.5 · Introduction to Proofs

A function from A to B assigns exactly one element of B to each element of A. Three properties matter: injective (one-to-one), surjective (onto), and bijective (both). A function has an inverse if and only if it is bijective.

Injective (one-to-one)

A function f is injective if f(a) = f(b) implies a = b. No two inputs map to the same output. To prove injectivity: assume f(a) = f(b), then show a = b.

Scheme

; Injective: f(a) = f(b) implies a = b
; f(x) = 2x + 1 is injective.
; Proof: 2a + 1 = 2b + 1 => 2a = 2b => a = b. QED.

(define (f x) (+ (* 2 x) 1))

; g(x) = x^2 is NOT injective on all integers: g(2) = g(-2) = 4

(define (g x) (* x x))

(display "f(3) = ") (display (f 3)) (newline)
(display "f(5) = ") (display (f 5)) (newline)
(display "f injective? Different outputs: ") (display (not (= (f 3) (f 5)))) (newline)
(newline)
(display "g(2) = ") (display (g 2)) (newline)
(display "g(-2) = ") (display (g -2)) (newline)
(display "g injective? Same output: ") (display (= (g 2) (g -2)))
; g is not injective: two different inputs, same output.

Surjective (onto)

A function f: A to B is surjective if every element of B is hit. For every b in B, there exists an a in A with f(a) = b. To prove surjectivity: given arbitrary b in B, find an explicit a.

Scheme

; Surjective: f(x) = 2x + 1 from Z to odd integers is surjective.
; Given any odd integer b, solve: 2x + 1 = b => x = (b-1)/2.
; Since b is odd, (b-1) is even, so (b-1)/2 is an integer. QED.

(define (f x) (+ (* 2 x) 1))
(define (f-preimage b) (/ (- b 1) 2))

(display "Target b=7: preimage = ") (display (f-preimage 7))
(display ", f(preimage) = ") (display (f (f-preimage 7))) (newline)

(display "Target b=13: preimage = ") (display (f-preimage 13))
(display ", f(preimage) = ") (display (f (f-preimage 13))) (newline)

; f(x) = x^2 from Z to Z is NOT surjective: no integer squares to -1.
(display "Is -1 a perfect square? No.")

Bijective and inverse functions

A function is bijective if it is both injective and surjective. Bijections have inverses: f-inverse(b) is the unique a with f(a) = b. Composition of bijections is a bijection.

Scheme

; Bijection: f(x) = 2x + 1 is a bijection from Z to odd Z.
; Its inverse: f^{-1}(y) = (y - 1) / 2

(define (f x) (+ (* 2 x) 1))
(define (f-inv y) (/ (- y 1) 2))

; Verify: f(f^{-1}(y)) = y and f^{-1}(f(x)) = x
(display "f(f-inv(7)) = ") (display (f (f-inv 7))) (newline)
(display "f-inv(f(3)) = ") (display (f-inv (f 3))) (newline)

; Composition of bijections
(define (g x) (+ (* 3 x) 2))
(define (g-inv y) (/ (- y 2) 3))

(define (compose h k) (lambda (x) (h (k x))))

(define gf (compose g f))
(define gf-inv (compose f-inv g-inv))

(display "g(f(4)) = ") (display (gf 4)) (newline)
(display "gf-inv(29) = ") (display (gf-inv 29))
; g(f(4)) = g(9) = 29. gf-inv(29) = f-inv(g-inv(29)) = f-inv(9) = 4.

Composition

If f: A to B and g: B to C, then g composed with f: A to C. Composition preserves injectivity and surjectivity. If g composed with f is injective, then f is injective. If g composed with f is surjective, then g is surjective.

Scheme

; Composition preserves properties.
; If g . f is injective, f must be injective.
; Proof: suppose f(a) = f(b). Then g(f(a)) = g(f(b)).
; Since g.f is injective, a = b. So f is injective. QED.

(define (compose g f) (lambda (x) (g (f x))))

(define (f x) (* 2 x))        ; injective
(define (g x) (+ x 1))        ; injective

(define gf (compose g f))

; gf(3) = g(f(3)) = g(6) = 7
; gf(4) = g(f(4)) = g(8) = 9
(display "gf(3) = ") (display (gf 3)) (newline)
(display "gf(4) = ") (display (gf 4)) (newline)
(display "Different? ") (display (not (= (gf 3) (gf 4))))
; Both injective, so composition is injective.

Neighbors

🐱 Milewski Ch.2 — types and functions as objects and arrows
📐 Linear Algebra Ch.3 — linear maps are functions preserving structure
🐱 Category Theory Ch.2 — functions as morphisms between types
∫ Calculus Ch.1 — functions and graphs: the same objects used in calculus
🔗 Abstract Algebra Ch.3 — homomorphisms are structure-preserving functions

← Sets by june.kim Relations →