Functions: one-to-one, onto, inverse, composition, floor and ceiling

You know the concept of a function from high school math, but in discrete mathematics a function is not a formula, it is a mapping. An almost certain midterm question: “Determine whether $f$ is one-to-one, onto, both or neither. Prove your answers. If it is a bijection, find its inverse.” This question is solved with a template. It is usually accompanied by a floor/ceiling computation or a composition.

Golden rules:

1. Function = exactly one output for every element of the domain. If there are two outputs or none, it is not a function.
2. A 1-1 proof starts with $f(x) = f(y)$ and ends with $x = y$.
3. An onto proof starts with an arbitrary $y$, you solve for $x$, and you say that $x$ is in the domain.
4. To say “not”, one concrete example is enough.
5. The domain and codomain change the answer. The same formula can be a bijection on $\mathbb{R}$ and not on $\mathbb{Z}$.

Definition

Let $A$ and $B$ be nonempty sets. A function $f: A \to B$ assigns to each $a$ in $A$ exactly one $f(a)$ from $B$.

The range is always a subset of the codomain. The definition of preimage does not require an inverse function; it is defined for every function.

Things that are not functions: $f: \mathbb{R} \to \mathbb{R}$, $f(x) = 1/x$ (no output for $x = 0$), or $f(x) = \pm\sqrt{x}$ (two outputs). If a finite mapping is given, check that each input has exactly one arrow leaving it.

One-to-one, onto, bijection

The contrapositive form of the 1-1 definition is also used: $a \ne b \Rightarrow f(a) \ne f(b)$.

Shortcuts for finite sets. If $\lvert A \rvert > \lvert B \rvert$, $f$ cannot be 1-1 (pigeonhole). If $\lvert A \rvert < \lvert B \rvert$, it cannot be onto. If $\lvert A \rvert = \lvert B \rvert$, 1-1 and onto are the same thing; showing one is enough.

Template and worked examples

Example 1. $f: \mathbb{R} \to \mathbb{R}$, $f(x) = 4 - 3x$.

One-to-one. Suppose f(x) = f(y). Then 4 − 3x = 4 − 3y, so −3x = −3y
and x = y. Hence f is one-to-one.
Onto. Let y ∈ R be arbitrary. Take x = (4 − y)/3. Then x ∈ R and
f(x) = 4 − 3·(4 − y)/3 = 4 − (4 − y) = y. Hence f is onto.
So f is a bijection, and f⁻¹(y) = (4 − y)/3.

Where did you find $x$? On scratch paper you solved $y = 4 - 3x$ for $x$. On the exam, write the result, not the scratch work, and don’t forget to say "$x \in \mathbb{R}$".

Example 2. $g: \mathbb{Z} \to \mathbb{Z}$, $g(n) = n^2$.

• Not 1-1: $g(2) = g(-2) = 4$, but $2 \ne -2$.
• Not onto: since $g(n) \ge 0$, $-1$ never appears. (Or 2: it is not a perfect square.)

Example 3. $h: \mathbb{Z} \to \mathbb{Z}$, $h(n) = \lfloor n/2 \rfloor$.

• Not 1-1: $h(4) = h(5) = 2$.
• Onto: for $m \in \mathbb{Z}$ take $n = 2m$, $h(2m) = m$.

Example 4. $f: \mathbb{Z} \to \mathbb{Z}$, $f(n) = 2n + 3$ versus $f: \mathbb{R} \to \mathbb{R}$, $f(x) = 2x + 3$. Both are 1-1. The real version is onto ($x = \tfrac{y-3}{2}$). The integer version is not onto: $2n + 3$ is always odd, and no integer maps to $0$.

PITFALL · Skipping that $x$ is in the domain in an onto proof. You found $x = \tfrac{y - 3}{2}$. If the domain is $\mathbb{R}$, no problem. If the domain is $\mathbb{Z}$, this $x$ is not an integer for most $y$, and the proof collapses. The sentence “Take $x = \dots \in A$” is half the marks.

Inverse function

If $f$ is a bijection, $f^{-1}: B \to A$, $f^{-1}(b) = a \iff f(a) = b$. If it is not a bijection, there is no inverse function: if it is not 1-1, some $b$ has two ways back; if it is not onto, some $b$ have no way back at all.

Method: write $y = f(x)$ and isolate $x$. Check: $f^{-1}(f(x)) = x$.

For a finite function, reverse the arrows: if $f(1) = c$, $f(2) = a$, $f(3) = b$ then $f^{-1}(a) = 2$, $f^{-1}(b) = 3$, $f^{-1}(c) = 1$.

Composition

For $f: A \to B$, $g: B \to C$, $(g \circ f)(x) = g(f(x))$. It is read right to left: first $f$, then $g$.

Example. $f(x) = x + 2$, $g(x) = 3x^2$. $(g \circ f)(x) = 3(x + 2)^2$, $(f \circ g)(x) = 3x^2 + 2$. In general $g \circ f \ne f \circ g$.

Useful facts:

• If $f$ and $g$ are 1-1, then $g \circ f$ is also 1-1. If both are onto, $g \circ f$ is also onto.
• If $g \circ f$ is 1-1, then $f$ is 1-1 (question 12). If $g \circ f$ is onto, then $g$ is onto.
• $f^{-1} \circ f = \iota_A$ (identity function), $f \circ f^{-1} = \iota_B$.

Floor and ceiling

⌊2.4⌋ = 2     ⌈2.4⌉ = 3
⌊−2.4⌋ = −3   ⌈−2.4⌉ = −2     (for negatives, "chop off the decimals" is WRONG)
⌊3⌋ = ⌈3⌉ = 3

Properties ($n$ an integer): $\lfloor x + n \rfloor = \lfloor x \rfloor + n$, $\lceil x + n \rceil = \lceil x \rceil + n$, $\lceil -x \rceil = -\lfloor x \rfloor$, $x - 1 < \lfloor x \rfloor \le x \le \lceil x \rceil < x + 1$. Careful: $\lfloor x + y \rfloor$ is in general not $\lfloor x \rfloor + \lfloor y \rfloor$ ($x = y = 0.5$: $1$ versus $0$).

Worked proof: $\lfloor 2x \rfloor = \lfloor x \rfloor + \lfloor x + \tfrac12 \rfloor$

Write $x = n + \varepsilon$, $n = \lfloor x \rfloor$, $0 \le \varepsilon < 1$. Two cases:

Case 1: 0 ≤ ε < 1/2.
  2x = 2n + 2ε with 0 ≤ 2ε < 1, so ⌊2x⌋ = 2n.
  x + 1/2 = n + (ε + 1/2) with 1/2 ≤ ε + 1/2 < 1, so ⌊x + 1/2⌋ = n.
  Right side: n + n = 2n. Equal.
Case 2: 1/2 ≤ ε < 1.
  2x = 2n + 1 + (2ε − 1) with 0 ≤ 2ε − 1 < 1, so ⌊2x⌋ = 2n + 1.
  x + 1/2 = (n + 1) + (ε − 1/2) with 0 ≤ ε − 1/2 < 1/2, so ⌊x + 1/2⌋ = n + 1.
  Right side: n + (n + 1) = 2n + 1. Equal.  ∎

The general trick in floor/ceiling proofs: write $x$ as “integer part + fraction” and split into cases by the range of the fraction.

Common mistakes