Sets, Relations, Functions & Proofs

TAKEAWAYS:

• Sets are collections of distinct objects; operations like union, intersection, and complement are fundamental in logic and databases.
• Relations model connections (e.g., "friend-of" in social networks) and can be classified as reflexive, symmetric, transitive, or equivalence relations.
• Functions map inputs to outputs uniquely; injective (one-to-one) and surjective (onto) functions are critical in algorithms and cryptography.
• Proof techniques (direct, contradiction, induction) are essential for validating mathematical claims, especially in algorithm correctness.
• Cartesian products and power sets are used in combinatorics and computer science (e.g., state machines, database relations).
• Hasse diagrams visually represent partial orders, while relation matrices help analyze properties like reflexivity.

1. Sets: Definitions and Operations

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

• Notation: $a\in A$ means "$a$ is an element of $A$", while $a\notin A$ means it is not.
• Set-builder notation: $A=\{x\mid P(x)\}$, where $P(x)$ is a property (e.g., $A=\{x\mid x\text{ is even}\}$).

Key Set Operations

Visualizing Set Operations

Shaded regions for operations:

• Union ($A\cup B$): Entire diagram (all regions).
• Intersection ($A\cap B$): Overlapping region only.
• Difference ($A\setminus B$): Only the left circle (excluding overlap).

Power Set and Cardinality

• The power set $\mathcal{P}(A)$ is the set of all subsets of $A$, including the empty set and $A$ itself.
  • If $A=\{1,2\}$, then $\mathcal{P}(A)=\{\varnothing ,\{1\},\{2\},\{1,2\}\}$.
• Cardinality $|A|$: Number of elements in $A$. For a finite set, $|\mathcal{P}(A)|=2^{|A|}$.

Example: If $A=\{a,b\}$, then $\mathcal{P}(A)$ has $2^2=4$ subsets.

2. Real-World Applications of Sets

Example 1: Database Queries (eSewa, Khalti)

• Union: Combining two sets of users (e.g., active and inactive users) to get all users.
• Intersection: Finding users who used both eSewa and Khalti in a month.
• Complement: Identifying users who did not make a transaction in a given period.

Example 2: Network Routing (NTC, Ncell)

• Cartesian Product: Representing possible paths between routers in a network.
  • If $A=\{\text{Router 1, Router 2}\}$ and $B=\{\text{Router 2, Router 3}\}$, then $A\times B$ gives all possible ordered connections.

Example 3: E-Commerce Inventory (Daraz)

• Difference: Items in stock ($A$) minus sold items ($B$) to track remaining inventory.
• Power Set: All possible combinations of product bundles (e.g., for discounts).

3. Relations: Definitions and Properties

A relation $R$ from set $A$ to set $B$ is a subset of $A\times B$. If $(a,b)\in R$, we write $aRb$.

Types of Relations

Equivalence Relations

A relation that is reflexive, symmetric, and transitive is called an equivalence relation.

• Equivalence Classes: Partition $A$ into disjoint subsets where all elements are related.
  • Example: $R=\{(1,1),(2,2),(3,3),(1,2),(2,1)\}$ on $A=\{1,2,3\}$.
    • Equivalence classes: $\{1,2\},\{3\}$.

Visualization:

Partial Orders

A relation that is reflexive, antisymmetric, and transitive is a partial order.

• Hasse Diagram: Visual representation of a partial order (omits redundant edges).
  • Example: $A=\{1,2,3\}$, $R=\{(1,1),(2,2),(3,3),(1,2),(1,3)\}$.

    graph TD
        1 --> 2
        1 --> 3

4. Real-World Applications of Relations

Example 1: Social Networks (Pathao, Facebook)

• Equivalence Relation: "Friends-of-friends" (transitive closure of the "friend" relation).
• Partial Order: Task dependencies in a project (e.g., "Task A must be completed before Task B").

Example 2: Traffic Routes (Kathmandu Roads)

• Relation: Roads connecting intersections can be modeled as a relation $R\subseteq \text{Intersections}\times \text{Intersections}$.
  • If $(A,B)\in R$, there is a road from intersection $A$ to $B$.
• Transitive Closure: Finding all possible routes between two points (e.g., Thamel to Lakshmi Path).

Example 3: Database Schema (Banks, NEPSE)

• Foreign Keys: Relations between tables (e.g., Customer and Account).
  • Example: $\text{Customer}\times \text{Account}$ where $(c,a)\in R$ means customer $c$ owns account $a$.

5. Functions: Definitions and Types

A function $f:A\to B$ assigns to each element of $A$ exactly one element of $B$.

• Domain: $A$ (set of inputs).
• Codomain: $B$ (set of possible outputs).
• Range: Actual outputs $\{f(a)\mid a\in A\}\subseteq B$.

Types of Functions

Visualizing Functions

flowchart TD
    A["Domain: {1, 2}"] -->|"f"| B["Codomain: {a, b}"]
    1 -->|"f(1) = a"| a
    2 -->|"f(2) = b"| b

Example: Let $f:\{1,2,3\}\to \{a,b\}$ be defined by $f(1)=a$, $f(2)=b$, $f(3)=a$.

• Injective? No (both 1 and 3 map to $a$).
• Surjective? Yes (both $a$ and $b$ are covered).

6. Real-World Applications of Functions

Example 1: Encryption (Banks, Ncell)

• Injective Functions: Used in cryptography (e.g., hashing passwords).
  • Example: $f(\text{password})=\text{hash}$. No two passwords should hash to the same value.

Example 2: Mapping Users to Roles (eSewa)

• Function: $f:\text{Users}\to \text{Roles}$, where $f(u)=\text{role of user }u$.
  • If $f$ is injective, each user has a unique role.

Example 3: Algorithm Design (Sorting)

• Bijective Functions: Permutations in sorting algorithms (e.g., swapping elements in a list).

7. Proof Techniques

1. Direct Proof

Prove $P⟹Q$ by assuming $P$ is true and showing $Q$ must follow. Example: Prove: If $n$ is even, then $n^2$ is even.

• Proof: Let $n=2k$. Then $n^2=(2k{)}^2=4k^2=2(2k^2)$, which is even.

2. Proof by Contradiction

Assume $\neg Q$ and show it leads to a contradiction. Example: Prove: $\sqrt{2}$ is irrational.

• Proof: Assume $\sqrt{2}=\frac{a}{b}$ (lowest terms). Then $2b^2=a^2$, so $a^2$ is even ⇒ $a$ is even ⇒ $a=2k$. Substituting: $2b^2=(2k{)}^2=4k^2$ ⇒ $b^2=2k^2$, so $b$ is even. But this contradicts $\frac{a}{b}$ being in lowest terms.

3. Mathematical Induction

Prove a statement $P(n)$ for all $n\ge n_0$ by:

1. Base Case: Show $P(n_0)$ is true.
2. Inductive Step: Assume $P(k)$ is true (inductive hypothesis) and prove $P(k+1)$. Example: Prove: $1+2+\cdots +n=\frac{n(n+1)}{2}$.

• Base Case (n=1): $1=\frac{1\cdot 2}{2}$ ✓
• Inductive Step: Assume true for $n=k$. Then for $n=k+1$: $$1+2+\cdots +k+(k+1)=\frac{k(k+1)}{2}+(k+1)=\frac{(k+1)(k+2)}{2}$$ ✓ Thus, by induction, the formula holds for all $n$.

8. Exam Tip

1. Sets:

   • Memorize Venn diagrams for operations (union, intersection, complement).
   • For power sets, recall $|\mathcal{P}(A)|=2^{|A|}$.
   • Cartesian product is often tested in relation to functions (e.g., $f:A\to B$ is a subset of $A\times B$).

2. Relations:

   • Properties (reflexive, symmetric, transitive) are frequently asked. Use examples to test them.
   • Equivalence relations and partial orders are key. Draw Hasse diagrams for partial orders.
   • Relation matrices (adjacency matrices) are useful for analyzing properties programmatically.

3. Functions:

   • Injective/Surjective/Bijective: Know the definitions and how to test them.
   • Pigeonhole Principle: If $f:A\to B$ and $|A|>|B|$, then $f$ cannot be injective.

4. Proofs:

   • Direct proofs are straightforward but require logical steps.
   • Contradiction is powerful for "proving impossibility" (e.g., irrationality).
   • Induction is essential for recursive definitions (e.g., sequences, algorithms).
   • Always write "Assume..." and "Thus..." clearly in proofs.

5. Common Pitfalls:

   • Confusing subset ($A\subseteq B$) with element ($a\in A$).
   • Forgetting reflexivity in relations (e.g., $(a,a)$ must be included).
   • Misapplying Cartesian product (it’s ordered pairs, not just combinations).

9. Worked Example: Real-World Problem

Problem: In a small town, there are 3 bus routes:

• Route 1: Thamel ↔ Lakshmi Path
• Route 2: Thamel ↔ Garden of Dreams
• Route 3: Lakshmi Path ↔ Garden of Dreams

Model this as a relation and determine if it is transitive.

Solution:

1. Let $A=\{\text{Thamel (T)},\text{Lakshmi Path (L)},\text{Garden of Dreams (G)}\}$.
2. The relation $R$ (direct bus routes) is: $$R=\{(T,L),(L,T),(T,G),(G,T),(L,G),(G,L)\}$$
3. Check Transitivity:
   • Is $(T,L)\in R$ and $(L,G)\in R$ ⇒ $(T,G)\in R$? Yes (since $(T,G)\in R$).
   • Is $(L,T)\in R$ and $(T,G)\in R$ ⇒ $(L,G)\in R$? Yes.
   • All other combinations also satisfy transitivity.
   • Conclusion: $R$ is transitive.

Visualization:

Application: This model helps the NTC optimize routes by identifying redundant or missing connections for efficiency. For example, if $(T,G)$ is already covered, adding a direct route might be unnecessary.