PGDDSA Study · Semester 1

Core Titles

Key headlines and terms for quick recall

Set — well-defined collection of distinct objects
Subset, Proper Subset, Power Set ( $2^A$ )
Union ∪, Intersection ∩, Complement, Difference, Symmetric Difference
Cartesian Product $A \times B$
Cardinality $|A|$
Principle of Inclusion–Exclusion (PIE)
De Morgan's Laws

Basic Idea

What it is, why it matters, how it works

What is a set?

A set is a well-defined collection of distinct objects called elements. We write $x \in A$ if $x$ is in $A$ . Sets are described by roster (listing: $A = \{1,2,3\}$ ) or set-builder form ( $A = \{x : x \text{ is even}\}$ ).

Key operations

Union: $A \cup B = \{x : x \in A \text{ or } x \in B\}$
Intersection: $A \cap B = \{x : x \in A \text{ and } x \in B\}$
Difference: $A - B = \{x : x \in A, x \notin B\}$
Complement: $A^c = U - A$ (relative to universal set $U$ )
Cartesian product: $A \times B = \{(a,b) : a \in A, b \in B\}$ , so $|A \times B| = |A| \cdot |B|$
Power set: $\mathcal{P}(A)$ has $2^{|A|}$ elements.

Principle of Inclusion–Exclusion (PIE)

Why it matters: When sets overlap, simple addition double-counts. PIE corrects this.

For two sets: $|A \cup B| = |A| + |B| - |A \cap B|$

For three sets: $|A \cup B \cup C| = |A|+|B|+|C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$

General form for $n$ sets — alternately add and subtract intersections of every size.

De Morgan's Laws

$(A \cup B)^c = A^c \cap B^c, \qquad (A \cap B)^c = A^c \cup B^c$

Why this matters in Data Science

Sets underpin database queries (SQL UNION/INTERSECT), feature engineering, and probability (events are sets of outcomes).

Mind Map

Visual structure of the concept

SETS
├── Definition (well-defined, distinct elements)
├── Representations
│   ├── Roster {1,2,3}
│   └── Set-builder {x : P(x)}
├── Operations
│   ├── Union ∪
│   ├── Intersection ∩
│   ├── Complement Aᶜ
│   ├── Difference A − B
│   └── Cartesian product A × B
├── Special sets
│   ├── Empty ∅
│   ├── Universal U
│   └── Power set 𝒫(A), size 2^|A|
└── Counting (PIE)
    ├── 2 sets: |A∪B| = |A|+|B| − |A∩B|
    ├── 3 sets: + |A∩B∩C|
    └── n sets: alternating sum

Exam Q&A

Part A (2 marks) and Part B (20 marks) style questions

Part A (2 marks each)

Q1. Define a set with an example. A set is a well-defined collection of distinct objects called elements. Example: $A = \{2,4,6,8\}$ — the set of even numbers less than 10.

Q2. State the Principle of Inclusion–Exclusion for two sets. $|A \cup B| = |A| + |B| - |A \cap B|$ .

Q3. If $|A|=3$ , what is $|\mathcal{P}(A)|$ ? $|\mathcal{P}(A)| = 2^3 = 8$ .

Q4. State De Morgan's laws. $(A \cup B)^c = A^c \cap B^c$ and $(A \cap B)^c = A^c \cup B^c$ .

Part B (20 marks)

Q. State and prove the Principle of Inclusion–Exclusion for three sets. Hence find how many integers from 1 to 100 are divisible by 2, 3 or 5.

Statement. For finite sets $A, B, C$ : $|A \cup B \cup C| = |A|+|B|+|C| - |A\cap B| - |A\cap C| - |B\cap C| + |A\cap B\cap C|$

Proof sketch. Take any element $x \in A \cup B \cup C$ . Suppose $x$ lies in exactly $k$ of the sets ( $k = 1, 2, 3$ ). On the LHS it is counted once. On the RHS:

It is counted $\binom{k}{1}$ times in the singletons,
$\binom{k}{2}$ times in the pair-intersections (subtracted),
$\binom{k}{3}$ times in the triple intersection (added back).

Total = $\binom{k}{1} - \binom{k}{2} + \binom{k}{3} = 1$ for $k=1,2,3$ (by binomial identity). So every element is counted exactly once on both sides. ∎

Application — multiples of 2, 3, 5 in $\{1,\dots,100\}$ : Let $A_2$ , $A_3$ , $A_5$ be the sets of multiples of 2, 3, 5 respectively.

$|A_2| = 50$ , $|A_3| = 33$ , $|A_5| = 20$
$|A_2 \cap A_3| = \lfloor 100/6 \rfloor = 16$
$|A_2 \cap A_5| = \lfloor 100/10 \rfloor = 10$
$|A_3 \cap A_5| = \lfloor 100/15 \rfloor = 6$
$|A_2 \cap A_3 \cap A_5| = \lfloor 100/30 \rfloor = 3$

By PIE: $50 + 33 + 20 - 16 - 10 - 6 + 3 = \boxed{74}$ .

Sets and the Principle of Inclusion-Exclusion