Functions and Relations — Mappings Between Sets
Functions and Relations
Relations and functions are the fundamental language in which all of mathematics is written. Every equation, every transformation, every structure in analysis, algebra, and geometry is ultimately a function between sets. This post builds the complete foundation — from ordered pairs and equivalence relations all the way to bijections, composition, and inverses.
🇮🇳 हिंदी में पढ़ेंRelations and Equivalence Relations
A relation from set $A$ to set $B$ is any subset $R \subseteq A \times B$. We write $a\,R\,b$ to mean $(a, b) \in R$. A relation on $A$ is a subset of $A \times A$.
A relation $\sim$ on $A$ is an equivalence relation if it satisfies all three of:
(i) Reflexive: $a \sim a$ for all $a \in A$.
(ii) Symmetric: $a \sim b \Rightarrow b \sim a$.
(iii) Transitive: $a \sim b$ and $b \sim c \Rightarrow a \sim c$.
The equivalence class of $a$ is $[a] = \{x \in A : x \sim a\}$. The collection $A/{\sim}$ of all equivalence classes is called the quotient set — it is a partition of $A$ into disjoint non-empty subsets.
A function $f \colon A \to B$ is a relation from $A$ to $B$ such that every element of $A$ is related to exactly one element of $B$.
Domain: $A$ | Codomain: $B$ | Range (Image): $f(A) = \{f(a) : a \in A\} \subseteq B$
Note: range $\subseteq$ codomain; equality holds if and only if $f$ is surjective.
← Sets and Basic Notation — sets and Cartesian products are the raw material from which relations and functions are built.
← Logic and Proof Methods — the $\forall/\exists$ quantifiers and implication are used in all injectivity and surjectivity proofs.
Intuition — Injective, Surjective, Bijective
Think of a function $f \colon A \to B$ as an assignment of outputs to inputs. The three key properties describe how "good" this assignment is:
🧵 Injective (1-1)
No two inputs share the same output.
$f(a_1)=f(a_2)\Rightarrow a_1=a_2$
Like: each student gets a unique seat
🎯 Surjective (onto)
Every output is hit by at least one input.
$f(A) = B$
Like: every seat is occupied by someone
↔️ Bijective
Both injective AND surjective.
Perfect one-to-one correspondence.
Like: exactly one student per seat, every seat filled
Composition: If $f \colon A \to B$ and $g \colon B \to C$, then $(g \circ f) \colon A \to C$ with $(g \circ f)(a) = g(f(a))$. Note: apply $f$ first, then $g$.
Inverse: $f \colon A \to B$ has an inverse $f^{-1} \colon B \to A$ satisfying $f^{-1} \circ f = \mathrm{id}_A$ and $f \circ f^{-1} = \mathrm{id}_B$ if and only if $f$ is bijective. Here, $\mathrm{id}_A$ is the identity mapping on the set A, i.e., $\mathrm{id}_A(x) = x $\forall x \in A$.
Composition inverse law: $(g \circ f)^{-1} = f^{-1} \circ g^{-1}$ (order reverses).
Composition preserves type: If $f$ and $g$ are both injective (resp. surjective, bijective), then so is $g \circ f$.
सम्बन्ध (Relation) समुच्चय $A\times B$ का कोई उपसमुच्चय है। तुल्यता सम्बन्ध (Equivalence Relation) के लिए तीन गुण चाहिए: स्वतुल्यता (Reflexive), सममिति (Symmetric) और संक्रामकता (Transitive)। फलन (Function) $f\colon A\to B$ में प्रत्येक $a\in A$ का ठीक एक प्रतिबिम्ब होता है। एकैकी (Injective): भिन्न इनपुट के भिन्न आउटपुट। आच्छादी (Surjective): प्रत्येक $b\in B$ का पूर्वप्रतिबिम्ब हो। द्विएकैकी (Bijective): दोनों — तभी प्रतिलोम फलन $f^{-1}$ अस्तित्व में है।
Solved Examples
Injective: Suppose $f(x_1)=f(x_2)$, i.e. $2x_1+1=2x_2+1$. Then $x_1=x_2$. $\checkmark$
Surjective: Given $y\in\mathbb{R}$, set $x=\dfrac{y-1}{2}\in\mathbb{R}$. Then $f(x)=2\cdot\dfrac{y-1}{2}+1=y$. $\checkmark$
Conclusion: $f$ is bijective with $f^{-1}(y)=\dfrac{y-1}{2}$. $\blacksquare$
Reflexive: $3\mid(a-a)=0$. $\checkmark$
Symmetric: If $3\mid(a-b)$, say $a-b=3k$, then $b-a=-3k=3(-k)$, so $3\mid(b-a)$. $\checkmark$
Transitive: If $3\mid(a-b)$ and $3\mid(b-c)$, say $a-b=3k$ and $b-c=3m$, then $a-c=3(k+m)$. $\checkmark$
Equivalence classes (three, partitioning $\mathbb{Z}$):
$[0]=\{\ldots,-3,0,3,6,\ldots\}$,
$[1]=\{\ldots,-2,1,4,7,\ldots\}$,
$[2]=\{\ldots,-1,2,5,8,\ldots\}$. $\blacksquare$
$f\colon\mathbb{R}\to\mathbb{R}$, $f(x)=x+1$; $\;g\colon\mathbb{R}\to(0,\infty)$, $g(x)=e^x$.
Composition: $(g\circ f)(x)=g(f(x))=g(x+1)=e^{x+1}$, so $g\circ f\colon\mathbb{R}\to(0,\infty)$.
Injective: $e^{x_1+1}=e^{x_2+1}\Rightarrow x_1=x_2$. $\checkmark$
Surjective: For $y>0$, set $x=\ln y-1$; then $(g\circ f)(x)=e^{\ln y}=y$. $\checkmark$
Inverse: $(g\circ f)^{-1}(y)=\ln y - 1$.
Verification: $f^{-1}(y)=y-1$ and $g^{-1}(y)=\ln y$, so $(f^{-1}\circ g^{-1})(y)=f^{-1}(\ln y)=\ln y-1$. $\checkmark$ $\blacksquare$
Let $f\colon A\to B$ and $g\colon B\to C$.
Part (i): $g\circ f$ injective $\Rightarrow f$ injective.
Suppose $f(a_1)=f(a_2)$. Then $g(f(a_1))=g(f(a_2))$, i.e. $(g\circ f)(a_1)=(g\circ f)(a_2)$. Since $g\circ f$ is injective, $a_1=a_2$. Hence $f$ is injective. $\blacksquare$
Part (ii): $g\circ f$ surjective $\Rightarrow g$ surjective.
Let $c\in C$. Since $g\circ f$ is surjective, $\exists\,a\in A$ with $(g\circ f)(a)=c$, i.e. $g(f(a))=c$. Setting $b=f(a)\in B$, we have $g(b)=c$. Hence $g$ is surjective. $\blacksquare$
Remark — converses are FALSE: $g\circ f$ injective does NOT imply $g$ injective. $g\circ f$ surjective does NOT imply $f$ surjective. (Counter-example: $A=\{1\}$, $B=\{1,2\}$, $C=\{1\}$, $f(1)=1$, $g(1)=g(2)=1$; then $g\circ f$ is surjective but $f$ is not.)
Quick Revision Cards
📊 A — Key Definitions
- Injective: $f(a_1)=f(a_2)\Rightarrow a_1=a_2$
- Surjective: $f(A)=B$
- Bijective: injective AND surjective
- $(g\circ f)(a)=g(f(a))$
- $(g\circ f)^{-1}=f^{-1}\circ g^{-1}$
- Equiv. rel.: Reflexive + Symmetric + Transitive
⚙️ B — Conditions & Edge Cases
- Range ⊆ Codomain; equal iff surjective
- $f^{-1}$ (function) needs bijectivity
- $f^{-1}(S)$ (preimage of set) always defined
- $g\circ f$ injective $\Rightarrow f$ injective (not $g$)
- $g\circ f$ surjective $\Rightarrow g$ surjective (not $f$)
- Equiv. classes: identical or disjoint
🎯 C — Exam Tips
- 🔵 CSIR NET: Disprove injective: find $a_1\neq a_2$ with $f(a_1)=f(a_2)$
- 🟢 GATE: Know both parts of Example 4 + both counterexamples
- 🟠 IIT JAM: Range ≠ Codomain — classic MCQ trap
- 🔴 B.Sc. Raj.: Verify ALL 3 equiv. rel. properties explicitly
Common Mistakes
❌ Errors to Avoid
Wrong: "The range of $f(x)=x^2$ on $\mathbb{R}\to\mathbb{R}$ is $\mathbb{R}$." | Correct: Range $=[0,\infty)\subsetneq\mathbb{R}$. Codomain is $\mathbb{R}$; they are equal only when $f$ is surjective.
Wrong: Writing $f^{-1}$ for a non-bijective $f$. | Correct: The inverse function $f^{-1}$ exists if and only if $f$ is bijective. The preimage $f^{-1}(S)$ is always a set, but not always a function.
Wrong: $(g\circ f)^{-1}=g^{-1}\circ f^{-1}$. | Correct: $(g\circ f)^{-1}=f^{-1}\circ g^{-1}$. The order reverses — like putting on shoes then socks, and reversing: socks off first, then shoes.
Wrong: Checking only reflexivity and symmetry. | Correct: All three properties must be verified. Without transitivity, the relation is merely symmetric — not an equivalence relation.
Real-World Applications
Cryptographic Hash Functions
A hash $h\colon\{0,1\}^*\to\{0,1\}^{256}$ is designed to be computationally injective (collision-resistant) but deliberately NOT surjective or invertible.
Database: Functional Dependencies
A functional dependency $A\to B$ in a schema is exactly the statement that the projection onto $A$ is a function — each $A$-value determines a unique $B$-value.
Type Theory (CS)
Functions between types are morphisms in the category of types. Bijections are type isomorphisms — lossless, reversible data conversions.
Modular Arithmetic
$\mathbb{Z}/n\mathbb{Z}$ is the quotient set of $\mathbb{Z}$ under congruence mod $n$ — the foundation of clock arithmetic, check digits, and public-key cryptography.
Summary Table & Key Result
| Concept | Statement / Formula | Condition | Reference |
|---|---|---|---|
| Equiv. Relation | Reflexive + Symmetric + Transitive | On $A\times A$ | Apostol §1.3 |
| Injective | $f(a_1)=f(a_2)\Rightarrow a_1=a_2$ | $f\colon A\to B$ | Apostol §1.4 |
| Surjective | $f(A)=B$ | $f\colon A\to B$ | Apostol §1.4 |
| Bijective | Injective AND Surjective | $f\colon A\to B$ | Apostol §1.4 |
| Inverse exists | $f^{-1}\colon B\to A$ iff $f$ bijective | $f\colon A\to B$ | Rudin §2.1 |
| Comp. inverse | $(g\circ f)^{-1}=f^{-1}\circ g^{-1}$ | $f,g$ bijective | Standard |
The Central Equivalence:
$$f\colon A\to B \text{ bijective} \;\Longleftrightarrow\; f^{-1}\colon B\to A \text{ exists} \;\Longleftrightarrow\; \lvert A\rvert = \lvert B\rvert \text{ (finite sets)}$$
Every equivalence relation on $A$ partitions $A$ into disjoint equivalence classes.
Cross-References & Related Posts
← Prerequisite: Sets and Basic Notation — A Foundation for Mathematics — sets and Cartesian products are the raw material for relations and functions.
← Prerequisite: Logic and Proof Methods — The Language of Mathematics — the $\forall/\exists$ quantifiers and implication used in all injectivity and surjectivity proofs.
→ Next Topic: Countability and Cardinality — bijections between infinite sets are the tool for comparing cardinalities of $\mathbb{N}$, $\mathbb{Z}$, $\mathbb{Q}$, and $\mathbb{R}$.
📖 Further Reading: Apostol, Ch. 1, §§1.3–1.6; Rudin, Ch. 2, §§2.1–2.5; Bartle & Sherbert, Ch. 1.
How did you find this post?
Tap a reaction — counts update in real time across all devices.
Have a question, doubt, or thought about this post? Choose how you want to join the discussion below.
💬 Comment on Telegram — No account neededRequires a free GitHub account — takes 30 seconds to create with just an email address.