Set Theory & Functions: Operations, Mappings, and Cardinality

TAKEAWAYS

• Sets are collections of distinct objects; operations like union, intersection, and complement are fundamental for modeling data (e.g., user groups in eSewa).
• Functions map inputs to outputs; injective, surjective, and bijective functions are critical for algorithms (e.g., sorting, encryption).
• Cardinality quantifies set size; countable vs. uncountable sets underpin database indexing and computational complexity.
• Function composition chains operations (e.g., Daraz’s order processing pipeline: user → cart → payment → delivery).
• Proof techniques (direct, contradiction) validate set/function properties, essential for exam questions.
• Real-world ties: eSewa’s transaction validation uses set operations; Pathao’s route optimization relies on graph theory (covered later).

---

1. Sets: Definitions and Operations

A set is a well-defined collection of distinct objects. Objects are called elements or members.

1.1 Notation and Representation

• Roster form: List elements explicitly. $$A=\{1,2,3\}$$
• Set-builder notation: Describe a property. $$B=\{x\mid x\text{ is an even integer},1\le x\le 10\}$$

1.2 Basic Operations

1.3 Venn Diagrams for Operations

Each operation is visualized separately to show inclusion/exclusion:

1.4 Laws of Set Theory

Prove using Venn diagrams and truth tables:

• Commutative: $A\cup B=B\cup A$
• Associative: $(A\cup B)\cup C=A\cup (B\cup C)$
• Distributive: $A\cap (B\cup C)=(A\cap B)\cup (A\cap C)$

Worked Example (eSewa Transactions): eSewa categorizes transactions into:

• A: Successful payments (e.g., bills, transfers).
• B: Failed payments (e.g., insufficient funds).
• C: Refunded transactions.

Question: Find the set of transactions that were either successful or refunded but not failed. Solution: $$(A\cup C)\setminus B$$

---

2. Cardinality and Special Sets

2.1 Cardinality

• Finite set: Countable elements (e.g., $|A|=3$ for $A=\{1,2,3\}$).
• Infinite set: Uncountable (e.g., real numbers $\mathbb{R}$).
• Countable vs. Uncountable:
  • Countable: Can list elements (e.g., integers $\mathbb{Z}$).
  • Uncountable: Cannot list (e.g., $\mathbb{R}$ between 0 and 1).

2.2 Power Set

The set of all subsets of a set $A$ is called the power set, denoted $P(A)$. For $A=\{1,2\}$, $P(A)=\{\varnothing ,\{1\},\{2\},\{1,2\}\}$.

2.3 Cartesian Product

For sets $A$ and $B$, the Cartesian product $A\times B$ is the set of ordered pairs: $$A\times B=\{(a,b)\mid a\in A,b\in B\}$$ Example: If $A=\{1,2\}$ and $B=\{x,y\}$, then: $$A\times B=\{(1,x),(1,y),(2,x),(2,y)\}$$

Real-World Tie (Pathao Drivers): Pathao’s driver assignment can be modeled as a Cartesian product:

• Drivers (A): $\{D_1,D_2,D_3\}$
• Routes (B): $\{R_1,R_2\}$
• Assignments: $A\times B=\{(D_1,R_1),(D_1,R_2),\dots \}$

---

3. Functions: Definitions and Types

A function $f:A\to B$ assigns each element of set $A$ (domain) to exactly one element of set $B$ (codomain).

3.1 Types of Functions

3.2 Function Composition

If $f:A\to B$ and $g:B\to C$, then:

• $(f\circ g)(x)=f(g(x))$ (read as "f of g of x").
• $(g\circ f)(x)=g(f(x))$.

Worked Example (Daraz Order Processing): Let:

• $f(x)$ = Apply discount to item $x$.
• $g(x)$ = Calculate shipping cost for $x$.

Question: If a customer buys item $x$, what is the final cost after discount and shipping? Solution: $$(g\circ f)(x)=g(f(x))$$ If $f(x)=0.8x$ (20% discount) and $g(x)=5+0.1x$ (shipping), then: $$(g\circ f)(x)=5+0.1(0.8x)=5+0.08x$$

---

4. Relations and Partial Orders

4.1 Relations

A relation $R$ from set $A$ to $B$ is a subset of $A\times B$. Example: For $A=\{1,2\}$, $B=\{a,b\}$, $R=\{(1,a),(2,b)\}$.

4.2 Partial Orders

A relation $\le$ on a set $A$ is a partial order if it is:

1. Reflexive: $a\le a$ for all $a\in A$.
2. Antisymmetric: If $a\le b$ and $b\le a$, then $a=b$.
3. Transitive: If $a\le b$ and $b\le c$, then $a\le c$.

Example (Nepalese Cities by Elevation): Let $A=\{\text{Kathmandu},\text{Pokhara},\text{Jumla}\}$ with:

• $\text{Kathmandu}\le \text{Pokhara}$ (lower elevation).
• $\text{Pokhara}\le \text{Jumla}$. This defines a partial order.

---

5. Proof Techniques for Sets and Functions

5.1 Direct Proof

Show $P⟹Q$ by assuming $P$ and deriving $Q$. Example: Prove $A\subseteq B\cup C⟹A\cap B\subseteq B$. Proof: Assume $x\in A\cap B$. Then $x\in A$ and $x\in B$. Since $A\subseteq B\cup C$, $x\in B\cup C$. But $x\in B$, so $x\in B$. Thus, $A\cap B\subseteq B$.

5.2 Proof by Contradiction

Assume the opposite of what you want to prove and find a contradiction. Example: Prove $\sqrt{2}$ is irrational. Proof: Assume $\sqrt{2}$ is rational, so $\sqrt{2}=\frac{p}{q}$ where $p,q$ are integers with no common factors. Then $2q^2=p^2$, implying $p^2$ is even, so $p$ is even. Let $p=2k$. Then $2q^2=(2k{)}^2⟹q^2=2k^2$, so $q$ is even. This contradicts $p,q$ having no common factors. Hence, $\sqrt{2}$ is irrational.

---

In the Real World

1. eSewa Transaction Validation

   • Idea: Set operations filter transactions.
   • How: eSewa uses $A\cap B$ to find duplicate transactions (where $A$ = all transactions, $B$ = recent transactions).
   • Example: If a user transfers ₹100 twice, $A\cap B$ flags the second entry.

2. Daraz Order Queue

   • Idea: Functions model order processing.
   • How: Orders pass through stages: cart → checkout → payment → delivery. This is a composition of functions $f_1\circ f_2\circ f_3\circ f_4$.
   • Worked Example: If 100 orders arrive, and $f_1$ (checkout) processes 50 orders/hour, the queue length is $100-50t$ (where $t$ is time in hours).

3. NTC Network Routing

   • Idea: Graph theory (covered later) models network paths, but set theory defines available routes.
   • How: NTC’s routers use $A\cup B$ to combine primary and backup paths for reliability.
   • Example: If primary path $A=\{1,2,3\}$ fails, NTC switches to backup $B=\{4,5,6\}$, ensuring connectivity via $A\cup B$.

---

Exam Tip

• Focus on definitions: Always define terms like injective, surjective, and partial order clearly with examples.
• Practice proofs: Expect 1–2 proof questions per exam. Use Venn diagrams for set proofs and logical steps for function proofs.
• Function composition: Memorize $(f\circ g)(x)=f(g(x))$ and practice swapping order (e.g., $(g\circ f)(x)\ne (f\circ g)(x)$ unless $f$ and $g$ commute).
• Cardinality: Know when to use $|\cdot |$ for finite sets and when to discuss countable vs. uncountable.
• Real-world mapping: Relate set operations to apps (e.g., eSewa’s $A\setminus B$ for failed transactions) to score extra marks.
• Time management: Spend 10–15 minutes per question. For proofs, write each step clearly with justifications.