Overview
This chapter introduces Relations and Functions — fundamental concepts that formalize connections between elements of sets. A relation is any subset of a cartesian product; a function is a special relation that assigns each element of a domain a unique image in a codomain. The chapter explains how to represent relations (ordered pairs, digraphs, matrices), classifies relations (reflexive, symmetric, transitive) and develops the important notion of equivalence relations and the partitions they induce. For functions, the chapter covers precise definitions (domain, codomain, range), types (one–one, onto, bijection, into), composition and inverse of functions, and criteria for invertibility. Importance: these ideas are foundational for algebra, calculus, linear algebra and discrete mathematics; they train students in precise definitions, proof techniques and algebraic manipulation. By the end of the chapter a student will be able to test and prove properties of relations, represent them in different ways, work with equivalence classes and partitions, determine and construct various types of functions, compose functions, decide invertibility and find inverse functions when they exist.
Learning Objectives
- Define relation, domain, codomain and range and give examples from finite and infinite sets
- Explain reflexive, symmetric, transitive, antisymmetric and irreflexive properties with examples
- Determine whether a given relation on a set is reflexive, symmetric and/or transitive and justify your answer
- Verify whether a relation is an equivalence relation and describe its equivalence classes and the corresponding partition
- Define function and distinguish between a function and a general relation using examples
- Identify domain, codomain, range, image and preimage for a given function and for subsets of the domain/codomain
- Test and prove whether a given function is one-one (injective), onto (surjective) or bijective; provide counterexamples when false
- Find the inverse of a given bijective function algebraically and verify it by composition
Topics in this chapter
2 topics · tap a topic title to jump straight to it.
Relations
Relations
Core Principle: Relation R from A to B: R ⊆ A × B
What is a relation?
A relation R from set A to set B is any subset of the Cartesian product A × B. If (a, b) ∈ R we say "a is related to b" by R. When A = B we call R a relation on A.
Representations of a relation
- Set of ordered pairs: R = {(a, b), ...}.
- Arrow/Directed graph (digraph): vertices are elements of the set; draw an arrow a → b when (a,b) ∈ R. Loops indicate (a,a).
- Adjacency (characteristic) matrix M_R: M_R[i,j] = 1 if (a_i,a_j) ∈ R, else 0.
- Table/grid inside A × B marking cells for pairs present in R.
Key properties of relations (on a set A)
- Reflexive: every element relates to itself: for all a ∈ A, (a,a) ∈ R.
- Irreflexive (anti-reflexive): for all a, (a,a) ∉ R.
- Symmetric: (a,b) ∈ R ⇒ (b,a) ∈ R.
- Antisymmetric: if (a,b) ∈ R and (b,a) ∈ R then a = b.
- Transitive: (a,b) ∈ R and (b,c) ∈ R ⇒ (a,c) ∈ R.
Important special relations
- Equivalence relation: reflexive, symmetric and transitive. Equivalence relations partition the set into disjoint equivalence classes. The equivalence class of a is [a] = {x ∈ A | (a,x) ∈ R}.
- Partial order (poset): reflexive, antisymmetric and transitive. Can be visualized by a Hasse diagram (transitive reduction).
Inverse and composition
- Inverse relation: R-1 = {(b,a) | (a,b) ∈ R}.
- Composition: If R ⊂ A × B and S ⊂ B × C, then S ○ R = {(a,c) | exists b in B with (a,b) ∈ R and (b,c) ∈ S}.
Counting relations
If |A| = m and |B| = n, the total number of relations from A to B is 2^(m n). In particular, on an n-element set the number of relations is 2^(n^2).
How to check properties (practical tips)
- Use the adjacency matrix: reflexive ⇒ all diagonal entries 1; symmetric ⇒ matrix is symmetric; transitive ⇒ whenever M[i,j] = 1 and M[j,k] = 1 then M[i,k] must be 1.
- Use digraph: symmetry = arrows come in opposite pairs; transitivity = presence of indirect paths implies direct arrow.
Why relations matter (intuition and applications)
Relations generalize functions and orderings: they model connections such as "is friend of" (symmetric), "is ancestor of" (transitive), "divides" (partial order) and "congruent modulo n" (equivalence). They are used in databases (relationships between records), graph theory, logic and classification problems.
- Simple relation on A = {1,2,3}: R = {(1,1),(2,2),(3,3),(1,2)}. R is reflexive; not symmetric (1,2 in R but 2,1 not); not transitive unless (1,2) and (2,?) give (1,?).
- Divides relation (|) on positive integers: a | b iff a divides b. This relation is reflexive, antisymmetric (for positive integers), and transitive — a classic partial order.
- Congruence modulo n on integers: a ≡ b (mod n). This is an equivalence relation. Equivalence classes are residues {0,1,...,n−1}.
- 'Is a friend of' on a social network (assuming friendship is mutual): symmetric, not necessarily reflexive (usually people are not considered 'friend of themselves'), not necessarily transitive.
- 'Is ancestor of' on family tree: transitive (if A is ancestor of B and B of C then A of C); not symmetric; typically not reflexive if 'ancestor' excludes 'self'.
- \[Relation R from A to B: R ⊆ A × B\]
- \[Domain(R) = { a ∈ A | ∃ b ∈ B such that (a,b) ∈ R }\]
- \[Range(R) = { b ∈ B | ∃ a ∈ A such that (a,b) ∈ R }\]
- \[Inverse: R^{-1} = { (b,a) | (a,b) ∈ R }\]
- \[Composition: if R ⊆ A×B and S ⊆ B×C then S ∘ R = { (a,c) | ∃ b ∈ B with (a,b) ∈ R and (b,c) ∈ S }\]
- \[Number of relations from A to B: 2^{|A|·|B|}\]\[On an n-element set: 2^{n^2}.\]
Functions
Functions
Core Principle: Function notation: f: A → B, f(x) ∈ B for every x ∈ A.
Definition: A function f from a set A (domain) to a set B (codomain) is a rule that assigns to each element x in A exactly one element f(x) in B. We write f: A → B.
Key terms:
- Domain: the set A of allowed inputs.
- Codomain: the set B containing possible outputs specified by the function.
- Range (Image): the actual set of outputs {f(x): x ∈ A}, a subset of the codomain.
Types of functions:
- One-to-one (injective): different inputs give different outputs. Formally, f(x1)=f(x2) ⇒ x1=x2.
- Onto (surjective): every element of the codomain is an output; range = codomain.
- Bijective: both injective and surjective. Bijective functions have inverses.
- Constant, identity (I(x)=x), polynomial, rational, exponential, logarithmic, piecewise and absolute value are common classes.
Operations on functions:
- Composition: (f ∘ g)(x) = f(g(x)). Composition is associative but not generally commutative.
- Inverse: If f: A → B is bijective, there exists f⁻¹: B → A with f⁻¹(f(x)) = x and f(f⁻¹(y)) = y.
- Image and preimage: For S ⊆ A, f(S) = {f(x): x ∈ S}. For T ⊆ B, f⁻¹(T) = {x ∈ A: f(x) ∈ T} (preimage exists even if f has no inverse).
Graphical tests:
- Vertical line test verifies whether a curve in the xy-plane is a function (each x gives at most one y).
- Horizontal line test checks injectivity: if some horizontal line meets the graph more than once, the function is not one-to-one.
- The graph of the inverse f⁻¹ is the reflection of the graph of f across the line y = x.
Why functions matter: Functions model relationships where one quantity depends on another — physics formulas, economic models, temperature conversions, scoring rules, and many algorithmic mappings are all functions. Understanding types and properties of functions lets you invert relationships, compose processes, and reason about reachability (range) and uniqueness (injectivity).
- Temperature conversion: f(C) = (9/5)C + 32 maps Celsius (domain) to Fahrenheit (codomain). This is bijective (inverse exists).
- Area of a circle: A(r) = πr^2 maps radius r ≥ 0 to area A ≥ 0. Not injective on R but injective if domain restricted to r ≥ 0.
- Student roll mapping: f(student) = roll number. If each student has a unique roll number and every possible roll number is used, f is bijective; usually injective but not onto.
- Salary after tax: f(gross) = gross − tax(gross). This maps gross salary to net salary; may be many-to-one if different gross salaries give same net.
- f(x) = x^2 from R → R is not injective (f(2)=f(−2)) and not onto (no negative outputs). Restrict domain to x ≥ 0 to make it injective onto [0,∞).
- Exponential and logarithm: f(x) = e^x maps R → (0,∞) (injective, not onto R). Its inverse f⁻¹(y) = ln y maps (0,∞) → R.
- \[Function notation: f: A → B\]\[f(x) ∈ B for every x ∈ A.\]
- \[Injective condition: f(x1) = f(x2) ⇒ x1 = x2.\]
- \[Surjective condition: range(f) = codomain(B).\]
- \[Bijective ⇔ injective + surjective\]\[bijective ⇒ inverse exists.\]
- \[Inverse composition: (f ∘ g)⁻¹ = g⁻¹ ∘ f⁻¹ (when inverses exist).\]
- \[Identity function: I_A(x) = x for x ∈ A\]\[f ∘ I_A = I_B ∘ f = f.\]
Key Concepts
- Relation
- A relation from set A to set B is any subset of the Cartesian product A × B; it pairs some elements of A with elements of B.
- Domain
- The set of all first components (inputs) of ordered pairs in a relation or all permissible inputs of a function.
- Codomain
- The set B in a function f: A → B that contains all possible outputs (may include elements not actually achieved).
- Range (Image)
- The set of actual outputs of a relation or function; subset of the codomain consisting of values attained.
- Function (Mapping)
- A relation f from A to B in which every element of A is associated with exactly one element of B.
- One-to-one (Injective)
- A function f is injective if distinct inputs have distinct outputs: f(x1)=f(x2) implies x1=x2.
- Onto (Surjective)
- A function f: A → B is surjective if every element of B is the image of at least one element of A.
- Bijective (One-to-one Correspondence)
- A function that is both injective and surjective; it establishes a one-to-one correspondence between domain and codomain.
- Composite Function
- Given f: A→B and g: B→C, the composite g∘f is the function from A to C defined by (g∘f)(x)=g(f(x)).
- Inverse Function
- For a bijective f: A→B, the inverse f^{-1}: B→A satisfies f^{-1}(f(x))=x and f(f^{-1}(y))=y for all x in A, y in B.
- Graph of a Function
- The set of ordered pairs {(x,f(x)) : x in domain} in the Cartesian plane (or A×B) representing the function.
- Binary Relation
- A relation on a single set A is a subset of A × A; it relates elements of A with elements of A.
- Reflexive Relation
- A relation R on A is reflexive if (a,a) ∈ R for every a ∈ A.
- Symmetric Relation
- A relation R on A is symmetric if (a,b) ∈ R implies (b,a) ∈ R for all a,b ∈ A.
- Transitive Relation
- A relation R on A is transitive if (a,b) ∈ R and (b,c) ∈ R imply (a,c) ∈ R for all a,b,c ∈ A.
- Equivalence Relation
- A relation that is reflexive, symmetric and transitive. It partitions the set into equivalence classes.
- Partition
- A collection of nonempty, pairwise disjoint subsets of A whose union is A. Equivalence classes of an equivalence relation form a partition.
- Partial Order (Poset)
- A binary relation that is reflexive, antisymmetric and transitive; the set with such a relation is called a partially ordered set (poset).
- Identity Function
- The function id_A: A → A defined by id_A(x)=x for every x in A; it maps each element to itself.
- Constant Function
- A function that maps every element of the domain to the same fixed element of the codomain.
Practice Questions
-
Define a relation R from set A to set B. / समुच्चय A से समुच्चय B पर संबंध R को परिभाषित कीजिए।
Show answer
A relation R from A to B is any subset of the Cartesian product A x B; (a,b) in R means a is related to b. / A से B पर संबंध R, कार्तीय गुणनफल A x B का कोई उपसमुच्चय है; (a,b) ∈ R का अर्थ है a, b से संबंधित है।
-
Show that congruence modulo n on integers is an equivalence relation. / पूर्णांकों पर मॉड्यूलो n सर्वांगसमता एक तुल्यता संबंध है, दर्शाइए।
Show answer
a≡a (reflexive); a≡b ⇒ b≡a (symmetric); a≡b and b≡c ⇒ a≡c (transitive), so it is an equivalence relation with classes {0,1,...,n-1}. / a≡a (स्वतुल्य); a≡b ⇒ b≡a (सममित); a≡b व b≡c ⇒ a≡c (संक्रामक), अतः यह तुल्यता संबंध है जिसकी श्रेणियाँ {0,1,...,n-1} हैं।
-
If |A| = m and |B| = n, how many relations exist from A to B? / यदि |A| = m और |B| = n हो, तो A से B पर कितने संबंध होते हैं?
Show answer
The number of relations is 2^(mn); on an n-element set it is 2^(n^2). / संबंधों की संख्या 2^(mn) है; n अवयवों वाले समुच्चय पर यह 2^(n^2) होती है।
-
Distinguish between the codomain and the range of a function. / किसी फलन के सहप्रांत और परिसर में अंतर कीजिए।
Show answer
The codomain is the set B of possible outputs, while the range is the actual set {f(x)} of attained outputs, a subset of the codomain. / सहप्रांत संभावित निर्गतों का समुच्चय B है, जबकि परिसर वास्तव में प्राप्त निर्गतों का समुच्चय {f(x)} है, जो सहप्रांत का उपसमुच्चय है।
-
Prove that f: R → R, f(x) = x^2 is neither one-one nor onto. / सिद्ध कीजिए कि f: R → R, f(x) = x^2 न तो एकैकी है और न आच्छादक।
Show answer
f(2)=f(-2)=4 so not one-one; negative numbers have no preimage (range = [0,∞) ≠ R) so not onto. / f(2)=f(-2)=4 अतः एकैकी नहीं; ऋणात्मक संख्याओं का पूर्वप्रतिबिम्ब नहीं (परिसर = [0,∞) ≠ R) अतः आच्छादक नहीं।
-
State the condition for a function to have an inverse and write (f∘g)^{-1}. / किसी फलन के व्युत्क्रमणीय होने की शर्त लिखिए तथा (f∘g)^{-1} लिखिए।
Show answer
f must be bijective (one-one and onto) to have an inverse; then (f∘g)^{-1} = g^{-1}∘f^{-1}. / व्युत्क्रम के लिए f का एकैकी आच्छादक (bijective) होना आवश्यक है; तब (f∘g)^{-1} = g^{-1}∘f^{-1}।
-
For the temperature map f(C) = (9/5)C + 32, find f^{-1} and verify by composition. / तापमान फलन f(C) = (9/5)C + 32 का f^{-1} ज्ञात कर संयोजन द्वारा सत्यापित कीजिए।
Show answer
f^{-1}(F) = (5/9)(F - 32); f^{-1}(f(C)) = (5/9)((9/5)C+32-32) = C, confirming inversion. / f^{-1}(F) = (5/9)(F - 32); f^{-1}(f(C)) = (5/9)((9/5)C+32-32) = C, जो व्युत्क्रम की पुष्टि करता है।
-
Test the relation R = {(1,1),(2,2),(3,3),(1,2)} on A={1,2,3} for the three properties. / A={1,2,3} पर संबंध R = {(1,1),(2,2),(3,3),(1,2)} की तीन गुणों के लिए जाँच कीजिए।
Show answer
Reflexive (all (a,a) present); not symmetric ((1,2)∈R but (2,1)∉R); transitive (no chain violates it). / स्वतुल्य (सभी (a,a) उपस्थित); सममित नहीं ((1,2)∈R किंतु (2,1)∉R); संक्रामक (कोई शृंखला उल्लंघन नहीं करती)।
Related Laws & Principles
Explore allFoundational laws & principles connected to this chapter — tap to open in the Laws Explorer.