Set Theory & Relations: Sets, Operations, Relations, Functions & Equivalence

TAKEAWAYS:

• Sets are collections of distinct objects; operations like union, intersection, and complement are visualized via Venn diagrams and inclusion-exclusion principles.
• Relations (binary, n-ary) can be represented as matrices, digraphs, or tables, and their properties (reflexive, symmetric, transitive) determine equivalence classes and partitions.
• Functions (injective, surjective, bijective) map sets and are critical for algorithms, encryption, and data modeling.
• Equivalence relations partition sets into disjoint subsets, used in error-correction codes, social networks (friend groups), and traffic routing.
• Boolean matrices compactly represent relations, enabling efficient computation in pathfinding (e.g., shortest paths in Kathmandu traffic) and database queries.
• Closure properties (reflexive, symmetric, transitive) define when a relation can form a valid structure like a graph or equivalence class.

---

1. Sets: Definitions and Basic Operations

1.1 What is a Set?

A set is a well-defined collection of distinct objects, called elements or members. Sets are denoted by capital letters (e.g., $A,B,C$), and elements by lowercase letters (e.g., $a,b,c$).

• Roster method: List all elements explicitly. Example: $A=\{1,2,3\}$.
• Set-builder notation: Define properties elements must satisfy. Example: $B=\{x\mid x\text{ is a prime number }\le 5\}=\{2,3,5\}$.

1.2 Types of Sets

1.3 Set Operations

Visualize operations using Venn diagrams (shaded regions show results):

• Union ($A\cup B$): All elements in $A$ or $B$. $A\cup B=\{x\mid x\in A\text{ or }x\in B\}$. Example: $A=\{1,2\},B=\{2,3\}\Rightarrow A\cup B=\{1,2,3\}$.

• Intersection ($A\cap B$): Elements in both $A$ and $B$. $A\cap B=\{x\mid x\in A\text{ and }x\in B\}$. Example: $A\cap B=\{2\}$.

• Complement ($A^{\prime }$ or $A^c$): Elements not in $A$ but in the universal set $U$. $A^{\prime }=U\setminus A$. Example: If $U=\{1,2,3,4\}$, $A=\{1,2\}\Rightarrow A^{\prime }=\{3,4\}$.

• Difference ($A\setminus B$): Elements in $A$ but not in $B$. Example: $A\setminus B=\{1\}$.

• Symmetric Difference ($A△B$): Elements in either $A$ or $B$ but not both. $A△B=(A\setminus B)\cup (B\setminus A)$. Example: $A△B=\{1,3\}$.

1.4 Laws of Set Theory

1.5 Power Set and Cartesian Product

• Power Set ($\mathcal{P}(A)$): Set of all subsets of $A$. Example: If $A=\{1,2\}$, then $\mathcal{P}(A)=\{\varnothing ,\{1\},\{2\},\{1,2\}\}$. Size: If $|A|=n$, then $|\mathcal{P}(A)|=2^n$.

• Cartesian Product ($A\times B$): Set of all ordered pairs $(a,b)$ where $a\in A$ and $b\in B$. Example: $A=\{1,2\},B=\{x,y\}\Rightarrow A\times B=\{(1,x),(1,y),(2,x),(2,y)\}$. Size: $|A\times B|=|A|\times |B|$.

---

2. Relations: Definitions and Properties

2.1 What is a Relation?

A relation $R$ from set $A$ to set $B$ is a subset of the Cartesian product $A\times B$.

• Binary Relation: $R\subseteq A\times A$ (relation on a single set).
• Representation:
  • Roster form: List of ordered pairs. Example: $R=\{(1,2),(2,1),(3,3)\}$.
  • Matrix form: Boolean matrix where $M[i][j]=1$ if $(i,j)\in R$, else $0$.
  • Digraph: Directed graph where nodes are elements and edges represent pairs.

2.2 Properties of Relations

2.3 Types of Relations

2.4 Closure of Relations

Given a relation $R$ on $A$ and a property $P$ (e.g., reflexive), the closure is the smallest relation containing $R$ that satisfies $P$.

• Reflexive Closure: Add all pairs $(a,a)$ for $a\in A$.
• Symmetric Closure: Add $(b,a)$ for every $(a,b)\in R$.
• Transitive Closure: Add $(a,c)$ if $(a,b)$ and $(b,c)\in R$.

Example: Let $A=\{1,2\}$, $R=\{(1,2)\}$.

• Reflexive Closure: $R^{\prime }=\{(1,1),(2,2),(1,2)\}$.
• Transitive Closure: $R$ is already transitive (no new pairs).

2.5 Equivalence Relations and Partitions

An equivalence relation partitions a set into disjoint equivalence classes.

• Example: Let $A=\{1,2,3,4\}$, $R=\{(1,1),(2,2),(3,3),(4,4),(1,3),(3,1),(2,4),(4,2)\}$.
  • Equivalence classes: $\{1,3\}$, $\{2,4\}$.

Visualization:

---

3. Functions: Types and Properties

3.1 Definition of a Function

A function $f$ from set $A$ (domain) to set $B$ (codomain) assigns to each $a\in A$ exactly one $b\in B$.

• Notation: $f:A\to B$, $f(a)=b$.

3.2 Types of Functions

3.3 Composition of Functions

If $f:A\to B$ and $g:B\to C$, then the composition $g\circ f:A\to C$ is defined by $(g\circ f)(a)=g(f(a))$.

Example: Let $f:\{1,2\}\to \{a,b\}$ where $f(1)=a,f(2)=b$, and $g:\{a,b\}\to \{x,y\}$ where $g(a)=x,g(b)=y$. Then $(g\circ f)(1)=g(f(1))=g(a)=x$.

---

4. Applications in the Real World

4.1 Set Theory in Everyday Systems

1. eSewa and Khalti (Digital Payments):

   • Set Operations: Transactions are grouped into sets (e.g., all payments to a merchant). Union operations combine transaction logs, while intersections identify duplicate payments.
   • Cartesian Product: Used to generate all possible user-merchant pairs for fraud detection (e.g., $\text{Users}\times \text{Merchants}$).

2. Pathao (Ride-Hailing):

   • Relations: Represents "driver available at location $L$" as a relation $R\subseteq \text{Drivers}\times \text{Locations}$.
   • Equivalence Classes: Groups users by pickup zones (e.g., all users near Thapathali form one class).

3. NTC (Telecom Network Routing):

   • Graph Theory: Networks are modeled as graphs where nodes are switches and edges are connections. Relations define reachability between nodes.
   • Transitive Closure: Computes all possible paths between any two switches to optimize routing.

4.2 Worked Example: Kathmandu Traffic Routes

Problem: Model traffic routes in Kathmandu as a relation and find the transitive closure to determine all possible paths between major intersections. Assumptions:

• Sets: $A=\{\text{Thapathali},\text{Kantipath},\text{Baneshwor}\}$.
• Initial relation $R=\{(\text{Thapathali},\text{Kantipath}),(\text{Kantipath},\text{Baneshwor})\}$.

Steps:

1. Reflexive Closure: Add $(\text{Thapathali},\text{Thapathali})$, etc.
2. Transitive Closure: Add $(\text{Thapathali},\text{Baneshwor})$ because $(\text{Thapathali},\text{Kantipath})$ and $(\text{Kantipath},\text{Baneshwor})\in R$.

Result:

4.3 Relations in Databases

• Foreign Keys: Represent relations between tables (e.g., Orders and Customers).
• Equivalence Classes: Used in data deduplication (e.g., grouping similar customer records).

---

5. Exam Tip: How to Score Full Marks

1. For Set Operations:

   • Always draw Venn diagrams to visualize unions/intersections.
   • Use inclusion-exclusion for proofs: $|A\cup B|=|A|+|B|-|A\cap B|$.
   • Memorize De Morgan’s laws for negations.

2. For Relations:

   • Prove properties step-by-step:
     • Reflexive: Show $(a,a)\in R$ for all $a$.
     • Symmetric: For every $(a,b)$, show $(b,a)$.
     • Transitive: For $(a,b)$ and $(b,c)$, show $(a,c)$.
   • Boolean matrices: Construct them systematically (rows = domain, columns = codomain).

3. For Functions:

   • To prove injective, assume $f(a)=f(b)$ and show $a=b$.
   • To prove surjective, show for every $y\in B$, there exists $x\in A$ such that $f(x)=y$.

4. Common Pitfalls:

   • Confusing subset ($\subseteq$) with proper subset ($\subset$).
   • Forgetting to include all pairs in reflexive/symmetric closures.
   • Misapplying transitive closure (only add pairs if intermediate steps exist).

5. Past Exam Patterns:

   • Brief Questions: Define terms like "equivalence relation," "Boolean matrix," or "ceiling function."
   • Proofs: Always start with "Let $(a,b)\in R$..." and proceed logically.
   • Applications: Relate to databases, networks, or traffic systems (as above).

---

6. Practice Problems

1. Let $A=\{1,2,3\}$, $B=\{2,3,4\}$. Find:
   • $A\cup B$, $A\cap B$, $A\setminus B$, $A△B$.
2. Define a relation $R$ on $\{1,2,3\}$ by $R=\{(1,2),(2,1),(2,3),(3,2)\}$. Is $R$ reflexive? Symmetric? Transitive?
3. Prove that the relation $R=\{(a,b)\mid a-b\text{ is even}\}$ on integers is an equivalence relation.
4. Given $f:\mathbb{R}\to \mathbb{R}$ defined by $f(x)=x^2$, determine if $f$ is injective, surjective, or bijective.
5. Find the transitive closure of $R=\{(1,2),(2,3)\}$ on $\{1,2,3\}$.