Mathematics.

binary relations

Functions as Relations

Set Theory25 minDifficulty4 out of 10

You should know: relations, cartesian products

Overview

A function f: X → Y can be defined set-theoretically as nothing more than a special binary relation on X × Y: a set of ordered pairs (x, y) that satisfies two extra constraints beyond being a relation. First, it must be total — every x in the domain X appears as a first coordinate in some pair. Second, it must be functional (single-valued) — no x appears as the first coordinate of two different pairs. Together these say that each input is assigned exactly one output, which is the everyday meaning of 'function' recast entirely in the language of sets. This viewpoint unifies functions and relations under one framework: every function IS a relation, but most relations are not functions, since a general relation can leave inputs unassigned or assign several outputs to the same input.

Intuition

A general relation is a wiring diagram where a source node can send zero, one, or many arrows to targets, and a target can receive any number of arrows. A function is the same diagram with two extra rules imposed: every source node must send out exactly one arrow (never zero, never two) — you can think of it as a strict 'vending machine' where pressing a button always gives exactly one, well-defined item. Injectivity then says no two different buttons dispense the same item; surjectivity says every item on the shelf is dispensed by SOME button. Because a function is really just its graph — the set of (input, output) pairs — two functions with the same domain, codomain, and set of pairs are literally the same function, no matter how differently they were 'described' or computed.

Formal Definition

Definition

A relation f ⊆ X × Y is a function from X to Y, written f: X → Y, if it satisfies totality and functionality (single-valuedness). Injectivity, surjectivity, and bijectivity are then properties of this set of pairs.

f⊆X×Yf \subseteq X \times Y
A function is first of all a relation
∀x∈X,  ∃y∈Y,  (x,y)∈f\forall x \in X,\; \exists y \in Y,\; (x,y) \in f
Totality: every input has some output
(x,y1)∈f∧(x,y2)∈f  ⟹  y1=y2(x,y_1) \in f \land (x,y_2) \in f \implies y_1 = y_2
Functionality (single-valuedness): each input has at most one output
f is injective  ⟺  [(x1,y)∈f∧(x2,y)∈f  ⟹  x1=x2]f \text{ is injective} \iff \big[(x_1,y)\in f \land (x_2,y)\in f \implies x_1=x_2\big]
Injective: distinct inputs never share an output
f is surjective  ⟺  ∀y∈Y, ∃x∈X, (x,y)∈ff \text{ is surjective} \iff \forall y \in Y,\, \exists x \in X,\, (x,y)\in f
Surjective: every element of Y is hit

Notation

NotationMeaning
f:X→Yf: X \to Yf is a function with domain X and codomain Y
f(x)f(x)The unique y with (x,y) ∈ f
graph⁡(f)\operatorname{graph}(f)The set of pairs {(x, f(x)) : x ∈ X} — identical to f itself as a set
f−1f^{-1}The converse relation {(y,x) : (x,y) ∈ f}; a function only when f is a bijection

Properties

Total

∀x∈X,  ∃y∈Y,  (x,y)∈f\forall x \in X,\; \exists y \in Y,\; (x,y) \in f

Single-valued (functional)

(x,y1),(x,y2)∈f  ⟹  y1=y2(x,y_1),(x,y_2) \in f \implies y_1=y_2

Injective

(x1,y),(x2,y)∈f  ⟹  x1=x2(x_1,y),(x_2,y) \in f \implies x_1 = x_2

Surjective (onto)

∀y∈Y,  ∃x,  (x,y)∈f\forall y \in Y,\; \exists x,\; (x,y) \in f

Bijective

f is both injective and surjectivef \text{ is both injective and surjective}

Example: The converse f⁻¹ is then also a function, from Y to X

Worked Examples

  1. Check R₁: every element of X (1,2,3) appears exactly once as a first coordinate, so R₁ is total and single-valued.

    R1={(1,a),(2,a),(3,b)}R_1 = \{(1,a),(2,a),(3,b)\}

  2. Check R₂: element 1 appears as the first coordinate of two pairs, (1,a) and (1,b), so R₂ is not single-valued. Also 3 never appears, so it also fails totality.

    (1,a)∈R2∧(1,b)∈R2,  a≠b(1,a) \in R_2 \land (1,b) \in R_2,\; a \ne b

Answer: R₁ is a function X → Y; R₂ is not (it fails single-valuedness and totality).

Practice Problems

Difficulty 3/10

Explain why the relation R = {(x,y) ∈ ℝ×ℝ : x² + y² = 1} (the unit circle) is NOT a function from ℝ to ℝ.

Difficulty 3/10

Which extra condition turns a general binary relation R ⊆ X × Y into a function?

Difficulty 5/10

A shipping system assigns each of 500 packages to exactly one of 500 lockers, with no locker holding two packages and no locker left empty. As a relation on Packages × Lockers, what kind of function is this, and why does its converse relation also define a function?

Quiz

As a set of ordered pairs, a function f: X → Y must satisfy:
If a relation f ⊆ X × Y has (x, y₁) and (x, y₂) both in f with y₁ ≠ y₂, then f is:
A function's converse relation f⁻¹ = {(y,x) : (x,y) ∈ f} is itself a function precisely when f is:

Summary

  • A function f: X → Y is a binary relation on X × Y satisfying totality (every x has some y) and single-valuedness (each x has at most one y).
  • Every function is a relation, but most relations are not functions — they can leave inputs unassigned or assign multiple outputs.
  • Injective, surjective, and bijective are properties of the function's underlying set of ordered pairs (its graph).
  • The converse of a relation is a function again exactly when the original function is a bijection.

References

  1. WebsiteWikipedia — Function (mathematics)
  2. WebsiteWikipedia — Binary relation