Week-01

Maths 1: Week 01 - The Master Encyclopedia of Sets & Relations

1. The Genesis: Why Sets Exist 📜

1.1 The Origin Story

Before the late 19th century, mathematics was a collection of different “islands”—Geometry, Algebra, and Calculus—with no single bridge connecting them. In the 1870s, Georg Cantor revolutionized thought by introducing Set Theory. He realized that everything in math—numbers, shapes, functions—could be described as a “Collection.”

Sets are not just a topic in math; they are the Mother Tongue of all modern mathematics. Without sets, we cannot define probabilities, we cannot build databases, and we cannot understand infinity.

1.2 The Philosophical Intuition

A Set is a “Container of Distinction.” It allows us to draw a boundary around a group of objects and say: “These belong together, and everything else does not.” This act of grouping is the first step in human logic.

---

2. Axiomatic Foundations: The Rules of the Universe 🏛️

2.1 What is a Set? (The Naive vs. Axiomatic View)

Initially, people thought a set was just “any collection you can dream of.” However, this led to Russell’s Paradox (the set of all sets that don’t contain themselves—it breaks logic!).

To fix this, mathematicians created Zermelo-Fraenkel Set Theory (ZFC). Essentially, we follow these core rules:

1. Extensionality: Two sets are the same if they have the exact same members. $\{1,2\}=\{2,1\}$.
2. Empty Set: There exists a set with nothing in it, denoted as $\varnothing$ or $\{\}$. It is the “Atom” of Set Theory.
3. Well-Definedness: For any object $x$, it must be unequivocally true or false that $x\in S$.

2.2 Notations & Symbols (The Alphabet)

• $x\in S$: $x$ is an element of set $S$.
• $A\subseteq B$: $A$ is a subset of $B$ (Every item in $A$ is also in $B$).
• $A\subset B$: $A$ is a proper subset (A is in B, but B is bigger).
• $|S|$: The Cardinality (the count of how many unique items are inside).

---

3. The Calculus of Sets: Universal Operations 🛠️

3.1 The Big Four Operations

Everything you do with sets involves these four interactions. Imagine Two Circles ($A$ and $B$) in a Box ($U$):

1. Union ($A\cup B$): The “Collector.”
   • Logic: $\{x\mid x\in A\text{ OR }x\in B\}$.
   • Intuition: Combine both circles into one single shape.
2. Intersection ($A\cap B$): The “Filter.”
   • Logic: $\{x\mid x\in A\text{ AND }x\in B\}$.
   • Intuition: Only the shared area where the circles overlap.
3. Difference ($A\setminus B$ or $A-B$): The “Cutter.”
   • Logic: $\{x\mid x\in A\text{ AND }x\notin B\}$.
   • Intuition: Take circle A and slice off the part that touches B.
4. Complement ($A^c$ or $A^{\prime }$): The “Void.”
   • Logic: $\{x\mid x\in U\text{ AND }x\notin A\}$.
   • Intuition: Everything in the entire box EXCEPT A.

3.2 De Morgan’s Laws (The Mirror Laws)

These laws are the secret to simplifying complex logic. They tell us how the “Not” operator flips operations:

• $(A\cup B{)}^c=A^c\cap B^c$ (The “Not” of a Union is the Intersection of the Nots).
• $(A\cap B{)}^c=A^c\cup B^c$ (The “Not” of an Intersection is the Union of the Nots).

---

4. Relations: The Architecture of Connectivity 🕸️

4.1 The Cartesian Product ($A\times B$)

Before a relation can exist, we need a “Space” of all possible connections.

• Definition: $A\times B$ is the set of all ordered pairs $(a,b)$ where $a\in A$ and $b\in B$.
• Size: $|A\times B|=|A|\times |B|$.

4.2 What is a Relation?

A Relation $R$ from $A$ to $B$ is simply a subset of the Cartesian Product. It is a selection of specific pairs that “matter.”

4.3 The Trinity of Properties (The Soul of a Relation)

When we look at a relation on a single set $A$, we analyze it through three lenses:

Lens 1: Reflexivity

• The Rule: For every $a\in A$, the pair $(a,a)$ must be in $R$.
• Mental Model: “Everyone is their own friend.”
• Visual: If you draw the relation as a matrix, the main diagonal must be all $1$s.

Lens 2: Symmetry

• The Rule: If $(a,b)\in R$, then $(b,a)$ MUST be in $R$.
• Mental Model: “Friendship is a two-way street.”
• Visual: The matrix is symmetric across the diagonal.

Lens 3: Transitivity

• The Rule: If $(a,b)\in R$ and $(b,c)\in R$, then $(a,c)$ MUST be in $R$.
• Mental Model: “A friend of my friend is my friend.”
• Visual: The most complex to spot. Usually requires checking every chain of length 2.

---

5. Equivalence Relations & Partitions 🧩

5.1 The Equivalence Standard

If a relation is Reflexive, Symmetric, AND Transitive, it is an Equivalence Relation.

• The Power: It allows us to group elements into Equivalence Classes.
• Example: “Having the same remainder when divided by 2” is an equivalence relation. It splits all numbers into two piles: Evens and Odds.

5.2 The Partition Theorem

A set of equivalence classes forms a Partition of set $A$. This means:

1. The piles don’t overlap.
2. If you combine all piles, you get the whole set back. This is the mathematical basis for “Categorization.”

---

6. The Encyclopedia of Worked Examples (10 Case Studies) 📚

Case 1: The Power Set Construction

Problem: Construct the Power Set $\mathcal{P}(S)$ of $S=\{1,2,3\}$.

• Thinking Process: There are 3 elements, so there must be $2^3=8$ subsets.
• The Build:
  • Size 0: $\{\varnothing \}$
  • Size 1: $\{\{1\},\{2\},\{3\}\}$
  • Size 2: $\{\{1,2\},\{1,3\},\{2,3\}\}$
  • Size 3: $\{\{1,2,3\}\}$
• Result: $\mathcal{P}(S)=\{\varnothing ,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\}$.

Case 2: PIE for Three Sets (The Survey Trap)

Problem: In a group of 100 students, 50 like Python, 40 like Java, 30 like C++. 20 like Python & Java, 15 like Java & C++, 10 like Python & C++. 5 like all three. How many like at least one?

• Thinking Process: Use Principle of Inclusion-Exclusion (PIE).
• Procedure: $(50+40+30)-(20+15+10)+5$.
• Calculation: $120-45+5=80$.
• Result: 80 students like at least one language.

Case 3: Proving Reflexivity in Algebra

Problem: Let $R$ be a relation on $\mathbb{Z}$ defined by $xRy⟺x-y$ is even. Is it reflexive?

• Thinking Process: For reflexivity, we need $xRx$ for every $x$.
• Logic: $xRx$ means $x-x$ is even. $x-x=0$. Is $0$ even? Yes.
• Result: $R$ is reflexive.

Case 4: The Transitivity Test

Problem: $R=\{(1,2),(2,3)\}$ on $\{1,2,3\}$. Is it Transitive?

• Thinking Process: Look for a chain. $1\to 2$ and $2\to 3$ exists.
• Requirement: For transitivity, we need the shortcut $1\to 3$.
• Check: $(1,3)$ is NOT in $R$.
• Result: $R$ is NOT transitive.

Case 5: Defining the Codomain vs Range

Problem: $f:\mathbb{R}\to \mathbb{R}$ where $f(x)=x^2$. Identify the Codomain and Range.

• Thinking Process: Codomain is the “Target Box” given in the definition ($\mathbb{R}$). Range is the “Actual Outputs.”
• Logic: Squaring any real number never gives a negative.
• Result: Codomain = $\mathbb{R}$. Range = $[0,\infty )$.

Case 6: The Bijection Proof

Problem: Prove $f(x)=2x+1$ is bijective from $\mathbb{R}\to \mathbb{R}$.

• Step 1: Injective: $2x_1+1=2x_2+1⟹2x_1=2x_2⟹x_1=x_2$. (Yes!)
• Step 2: Surjective: Let $y=2x+1$. Solve for $x$: $x=(y-1)/2$. Since $(y-1)/2$ is always a real number, every $y$ has an $x$. (Yes!)
• Result: It is Bijective.

Case 7: Complement of Intersection

Problem: $U=\{1,\dots ,10\},A=\{2,4,6\},B=\{4,5,6\}$. Find $(A\cap B{)}^c$.

• Step 1: Find intersection: $A\cap B=\{4,6\}$.
• Step 2: Everything in $U$ except 4 and 6.
• Result: $\{1,2,3,5,7,8,9,10\}$.

Case 8: Number of Relations

Problem: If $|A|=3$, how many possible relations exist on $A$?

• Thinking Process: A relation is a subset of $A\times A$.
• Step 1: Find $|A\times A|=3\times 3=9$.
• Step 2: Number of subsets of a set with 9 items is $2^9$.
• Result: $512$ possible relations.

Case 9: Inverse Function Calculation

Problem: Find $f^{-1}(x)$ for $f(x)=\frac{3x-1}{x+2}$.

• Step 1: $y=\frac{3x-1}{x+2}$.
• Step 2: $y(x+2)=3x-1⟹xy+2y=3x-1$.
• Step 3: $xy-3x=-1-2y⟹x(y-3)=-(2y+1)$.
• Step 4: $x=\frac{2y+1}{3-y}$.
• Result: $f^{-1}(x)=\frac{2x+1}{3-x}$.

Case 10: Symmetry vs Antisymmetry

Problem: $R=\{(1,2),(2,1),(1,1)\}$ on $\{1,2\}$. Is it Antisymmetric?

• Thinking Process: Antisymmetry says: If $(a,b)$ and $(b,a)$ exist, then $a$ must equal $b$.
• Check: $(1,2)$ and $(2,1)$ exist. But $1\ne 2$.
• Result: NO, it’s not antisymmetric. It is, however, Symmetric.

---

7. Fundamental “How-To” Recipes 🍳

Recipe: Listing a Partition

1. Find the Equivalence Classes: Pick an element, find everything related to it. That’s Class 1.
2. Pick an Unused Element: Repeat until everyone has a class.
3. The List: Your final list $\{\text{Class 1, Class 2, ...}\}$ is the partition.

Recipe: Identifying Functions in Pairs

1. Check Lead Elements: Look at the first number in every pair $(x,y)$.
2. Check for Repeats: If any $x$ value appears twice with different $y$ values, it is NOT a function.
3. Check Coverage: Make sure every $x\in \text{Domain}$ is represented at least once.

---

8. Encyclopedia Mastery Challenge 🏆

1. The Axiom Test: Why can’t we have a set of “all sets”? (Research Russell’s Paradox).
2. The Power Trick: If a set has $2^n$ total relations, how many are reflexive? (Advanced: Think about the diagonal of the matrix).
3. The Composite Range: If $f(x)=\sqrt{x}$ and $g(x)=x^2-4$, what is the Domain of $f\circ g$? Explain the “security check” logic in depth.
4. The Partition Challenge: Given a set of 10 items, what is the maximum number of equivalence classes possible? What about the minimum?

---

🚀 Master Status: You have completed the Encyclopedic Foundation of Discrete Mathematics. You now possess the tools to construct any mathematical system from its most basic atoms.