Notes / Unit 3 · Module 2 · Midterm

Functions

A function is a relation that gives every element of its domain exactly one image. The exam asks you to spot one, read its domain, codomain and range, classify it as one-to-one, onto or a bijection, invert and compose it, and evaluate floor and ceiling.

3.1What makes a function

For non-empty sets A and B, a function f from A to B, written f: A → B, assigns exactly one element of B to each element of A. When f assigns b to a we write f(a) = b. As a set of ordered pairs, f is a subset of A × B in which every a ∈ A appears as a first coordinate exactly once.

Every element of A has an image, and only one. An element of A with two images, or with none, makes it not a function.
An element of B may be the image of several elements of A, or of none at all. Both are allowed.
Every function is a relation; not every relation is a function.

Domain: A, the set of inputs. Every element must be used.
Codomain: B, the set the outputs are declared to lie in.
Image: f(a), the element a is sent to.
Preimage: An a with f(a) = b. An element of B can have zero, one or many.
Range: The set of images actually produced, {f(a) | a ∈ A}. Always a subset of the codomain.

Worked example

Function or not? (pairs from the lecture)

1R1 = {(2, 0), (3, 4), (4, 6)}: the x-coordinates 2, 3, 4 never repeat, so R1 is a function.
2R2 = {(−4, 0), (0, 0), (2, 0)}: every x is different. All three share the output 0, which is allowed, so R2 is a function.
3R3 = {(−1, 3), (−1, 1), (2, 7)}: −1 is paired with both 3 and 1, so R3 is not a function.

TrapThe slides sometimes say "range" when they mean the codomain. In answers keep them apart: the codomain is declared in f: A → B, the range is what f actually hits.

3.2Range, image of a subset and preimage

For a subset S of the domain, the image f(S) is the set of images of its elements. For a subset T of the codomain, the preimage f⁻¹(T) is the set of domain elements that land in T.

f(S) = {f(s) | s ∈ S} f⁻¹(T) = {a ∈ A | f(a) ∈ T}

The range is f(A), the image of the whole domain.

Worked example

Lecture Example 4: A = {a1, …, a5}, B = {b1, …, b5}, f = {(a1, b2), (a2, b3), (a3, b3), (a4, b1), (a5, b4)}

1Domain A; codomain B.
2Range {b1, b2, b3, b4}. b5 is in the codomain but has no preimage.
3The preimage of b3 is {a2, a3}; the preimage of b5 is ∅.
4f({a1, a2, a3}) = {b2, b3}, with b3 written once.

number of functions A → B = |B|^|A|

|A|, |B|: the sizes of the finite sets A and B

Each element of A picks one of |B| images independently. With |A| = 2 and |B| = 3 there are 3² = 9.

3.3One-to-one, onto and bijections

One-to-one (injective): Different inputs give different outputs: f(x) = f(y) → x = y. Equivalently x ≠ y → f(x) ≠ f(y).
Onto (surjective): Every element of the codomain is hit: for every b ∈ B there is an a ∈ A with f(a) = b. The range equals the codomain.
Bijection (one-to-one correspondence): Both one-to-one and onto. Exactly the functions that have an inverse.

	One-to-one	Onto	Bijection
In the arrow diagram	No element of B has two arrows in	Every element of B has at least one arrow in	Every element of B has exactly one arrow in
To prove	Assume f(x) = f(y), show x = y	Take any b ∈ B, find an a with f(a) = b	Prove both
To disprove	Find x ≠ y with f(x) = f(y)	Find a b ∈ B nobody maps to	Disprove either one
Finite sets need	\|A\| ≤ \|B\|	\|A\| ≥ \|B\|	\|A\| = \|B\|

Worked example

Lecture Example 6: A = {a, b, c, d}, B = {1, 2, 3, 4}

1R1 = {(a, 4), (b, 1), (c, 3), (d, 2)}: each element of B is hit exactly once, so R1 is one-to-one and onto, a bijection.
2R2 = {(a, 2), (b, 1), (c, 2), (d, 3)}: f(a) = f(c) = 2, so not one-to-one; 4 has no preimage, so not onto. R2 is neither.

When |A| = |B| and both are finite, one-to-one and onto come together: the images are all different exactly when they cover B. With |A| > |B| two inputs must share an image (the pigeonhole principle), so f cannot be one-to-one.

3.4Functions given by a formula

The same formula can be one-to-one or onto on one pair of sets and not on another, so always read the domain and codomain first.

f	Domain → codomain	One-to-one?	Onto?
2x	ℤ → ℤ	Yes	No: 1 is never reached
2x	ℝ → ℝ	Yes	Yes: y comes from y/2
x + 3	ℤ → ℤ	Yes	Yes: y comes from y − 3
x²	ℤ → ℤ	No: f(−1) = f(1)	No: −1 is never a square
x²	ℕ → ℕ	Yes	No: 2 is not a square
x²	ℝ → {y \| y ≥ 0}	No	Yes: y comes from √y
⌊x⌋	ℝ → ℤ	No: ⌊2.1⌋ = ⌊2.7⌋	Yes

Worked example

Prove f(x) = 2x + 3 on ℤ is one-to-one but not onto

1One-to-one: suppose f(x) = f(y). Then 2x + 3 = 2y + 3, so 2x = 2y and x = y.
2Not onto: every output 2x + 3 is odd, so the even number 4 has no preimage in ℤ.
3On ℝ the same formula is onto: y comes from x = (y − 3)/2.

3.5The inverse function

If f: A → B is a bijection, its inverse f⁻¹: B → A sends each b back to the unique a with f(a) = b. On an arrow diagram, reverse every arrow. On ordered pairs, swap each pair.

f⁻¹(b) = a ⇔ f(a) = b

f⁻¹(f(a)) = a and f(f⁻¹(b)) = b.

Only a bijection is invertible. If f is not onto, some b has no a to go back to. If f is not one-to-one, some b would have to go back to two different a's. Either way the reversed relation is not a function.

Worked example

Lecture Example 7: f = {(1, 6), (2, 7), (3, 5), (4, 8)} from {1, 2, 3, 4} to {5, 6, 7, 8}

1Every element of B is hit exactly once, so f is a bijection.
2Swap each pair: f⁻¹ = {(6, 1), (7, 2), (5, 3), (8, 4)}, or sorted, {(5, 3), (6, 1), (7, 2), (8, 4)}.

Worked example

Lecture Example 8: f(a) = 1, f(b) = 3, f(c) = 4 from {a, b, c} to {1, 2, 3, 4}

12 has no preimage, so f is not onto.
2f is not a bijection, so it is not invertible.

Worked example

Inverse of f(x) = 2x − 3 on ℝ

1Write y = 2x − 3.
2Solve for x: x = (y + 3)/2.
3Rename the variable: f⁻¹(x) = (x + 3)/2. Check: f⁻¹(f(5)) = f⁻¹(7) = 10/2 = 5.

3.6Composition

For f: A → B and g: B → C, the composition g ∘ f: A → C applies f first, then g. Read it right to left: the function nearest x acts first.

(g ∘ f)(x) = g(f(x)) (f ∘ g)(x) = f(g(x))

Composition is not commutative: in general f ∘ g ≠ g ∘ f.

Worked example

f(x) = 2x + 3, g(x) = 3x + 2

1(f ∘ g)(x) = f(3x + 2) = 2(3x + 2) + 3 = 6x + 7.
2(g ∘ f)(x) = g(2x + 3) = 3(2x + 3) + 2 = 6x + 11.
3The two orders give different functions.

Worked example

Lecture Example 9: f(2) = 3, f(3) = 4, f(4) = f(5) = 5; g(3) = g(4) = 7, g(5) = g(9) = 11

1Follow each element through f, then g: 2 → 3 → 7, 3 → 4 → 7, 4 → 5 → 11, 5 → 5 → 11.
2g ∘ f = {(2, 7), (3, 7), (4, 11), (5, 11)}, a function from A to C.

Worked example

Lecture Example 10: f = {(1, 2), (3, 5), (4, 1)}, g = {(2, 3), (5, 1), (1, 3)}

1f ∘ g applies g first: 2 → 3 → 5, 5 → 1 → 2, 1 → 3 → 5, so f ∘ g = {(2, 5), (5, 2), (1, 5)}.
2g ∘ f applies f first: 1 → 2 → 3, 3 → 5 → 1, 4 → 1 → 3, so g ∘ f = {(1, 3), (3, 1), (4, 3)}.

3.7Floor and ceiling

Floor ⌊x⌋: The greatest integer less than or equal to x. Round down.
Ceiling ⌈x⌉: The least integer greater than or equal to x. Round up.

⌊x⌋ = n ⇔ n ≤ x < n + 1 ⌈x⌉ = n ⇔ n − 1 < x ≤ n

n: an integer
x: a real number

x	⌊x⌋	⌈x⌉
2.3	2	3
−2.3	−3	−2
5	5	5
−0.5	−1	0

⌈x⌉ − ⌊x⌋ is 0 when x is an integer and 1 otherwise.
⌊−x⌋ = −⌈x⌉ and ⌈−x⌉ = −⌊x⌋.
⌊x + n⌋ = ⌊x⌋ + n and ⌈x + n⌉ = ⌈x⌉ + n for any integer n.
⌊n/2⌋ + ⌈n/2⌉ = n for every integer n.

Worked example

How many bytes hold 100 bits?

1100/8 = 12.5.
2A part-filled byte still has to be sent, so round up: ⌈100/8⌉ = 13 bytes.

Check yourself

Answer these out loud, without scrolling up. Any you can't, reread that section — then let the drill mark you.

1.Is {(1, a), (2, a), (3, b)} a function from {1, 2, 3} to {a, b, c}? Is it one-to-one? Onto?
2.f: ℤ → ℤ, f(x) = 3x. What is its codomain and what is its range?
3.Why is x² one-to-one on ℕ but not on ℤ?
4.Only bijections have inverses. What goes wrong when you reverse the arrows of a function that is not onto?
5.For f(x) = x + 1 and g(x) = x², work out (f ∘ g)(2) and (g ∘ f)(2).
6.What are ⌊−4.5⌋, ⌈−4.5⌉ and ⌊7/2⌋ + ⌈7/2⌉?