Set Theory – Detailed Notes
1. Basics & Notation
A set is a well-defined collection of objects called elements. We write $x\in A$ if $x$ belongs to set $A$, and $x\notin A$ otherwise.
- Roster (list) form: $A=\{1,2,3\}$
- Set-builder form: $A=\{x\mid \text{property of }x\}$, e.g. $A=\{x\in\mathbb{Z}\mid 1\le x\le 3\}$
- Common sets: $\mathbb{N}=\{1,2,3,\dots\}$, $\mathbb{Z}$ (integers), $\mathbb{Q}$ (rationals), $\mathbb{R}$ (reals), $\mathbb{C}$ (complex)
- Empty set: $\varnothing$ (no elements)
- Universal set: $U$ (context dependent, the “universe” under discussion)
2. Types of Sets
- Finite: has finitely many elements, e.g. $\{2,4,6,8\}$
- Infinite: not finite, e.g. $\mathbb{N}$
- Singleton: exactly one element, e.g. $\{0\}$
- Equal sets: $A=B$ iff every element of $A$ is in $B$ and vice versa
- Subset: $A\subseteq B$ iff $(\forall x)(x\in A\Rightarrow x\in B)$
- Proper subset: $A\subset B$ iff $A\subseteq B$ and $A\ne B$
3. Power Set & Cardinality
- Power set: $\mathcal{P}(A)=\{\text{all subsets of }A\}$
- If $|A|=n$ (finite), then $|\mathcal{P}(A)|=2^n$
- Example: If $A=\{a,b\}$, then $\mathcal{P}(A)=\{\varnothing,\{a\},\{b\},\{a,b\}\}$
4. Operations on Sets
- Union: $A\cup B=\{x\mid x\in A\text{ or }x\in B\}$
- Intersection: $A\cap B=\{x\mid x\in A\text{ and }x\in B\}$
- Difference: $A\setminus B=\{x\mid x\in A\text{ and }x\notin B\}$
- Complement (w.r.t. $U$): $A^{c}=U\setminus A$
- Symmetric difference: $A\triangle B=(A\setminus B)\cup(B\setminus A)$
5. Algebra of Sets (Identities)
| Law | Identity (using $U$ and $\varnothing$) |
|---|---|
| Commutative | $A\cup B=B\cup A,\quad A\cap B=B\cap A$ |
| Associative | $(A\cup B)\cup C=A\cup(B\cup C)$, $(A\cap B)\cap C=A\cap(B\cap C)$ |
| Distributive | $A\cap(B\cup C)=(A\cap B)\cup(A\cap C)$ $A\cup(B\cap C)=(A\cup B)\cup(A\cup C)$ |
| Idempotent | $A\cup A=A,\quad A\cap A=A$ |
| Identity | $A\cup\varnothing=A,\quad A\cap U=A$ |
| Domination | $A\cup U=U,\quad A\cap \varnothing=\varnothing$ |
| Complement | $A\cup A^{c}=U,\quad A\cap A^{c}=\varnothing$ |
| Double complement | $(A^{c})^{c}=A$ |
| De Morgan | $(A\cup B)^{c}=A^{c}\cap B^{c}$, $(A\cap B)^{c}=A^{c}\cup B^{c}$ |
| Absorption | $A\cup(A\cap B)=A,\quad A\cap(A\cup B)=A$ |
6. Venn Counting & Inclusion–Exclusion
- Two sets: $|A\cup B|=|A|+|B|-|A\cap B|$
- Three sets: $$ |A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|B\cap C|-|C\cap A|+|A\cap B\cap C| $$
- Disjoint sets: $A\cap B=\varnothing\Rightarrow |A\cup B|=|A|+|B|$
7. Cartesian Product & Tuples
- $A\times B=\{(a,b)\mid a\in A,\ b\in B\}$
- If $|A|=m$ and $|B|=n$ (finite), then $|A\times B|=mn$
- Generally $A^k=\underbrace{A\times A\times\cdots\times A}_{k\text{ times}}$ (ordered $k$-tuples)
8. Relations (Brief)
- A relation $R$ on $A$ is a subset of $A\times A$
- Reflexive: $(\forall a\in A)\ (a,a)\in R$
- Symmetric: $(a,b)\in R\Rightarrow (b,a)\in R$
- Antisymmetric: $(a,b)\in R\ \&\ (b,a)\in R\Rightarrow a=b$
- Transitive: $(a,b)\in R\ \&\ (b,c)\in R\Rightarrow(a,c)\in R$
- Equivalence relation: reflexive, symmetric, transitive → partitions $A$ into equivalence classes
- Partial order: reflexive, antisymmetric, transitive (poset)
9. Functions (Brief)
- A function $f:A\to B$ is a relation with exactly one image for each $a\in A$
- Injective (one–one): $f(a_1)=f(a_2)\Rightarrow a_1=a_2$
- Surjective (onto): $\operatorname{Im}(f)=B$
- Bijective: injective and surjective → inverse $f^{-1}:B\to A$ exists
- Composition: $(g\circ f)(x)=g(f(x))$ where domains/codomains match
10. Partitions & Indexed Families
- A partition of $A$ is a collection of nonempty, pairwise-disjoint subsets whose union is $A$
- Indexed family: $\{A_i\}_{i\in I}$ with index set $I$; operations extend as $$ \bigcup_{i\in I}A_i=\{x\mid (\exists i\in I)\ x\in A_i\},\quad \bigcap_{i\in I}A_i=\{x\mid (\forall i\in I)\ x\in A_i\} $$
11. Countability (Overview)
- Finite: $|A|=n$ for some $n\in\mathbb{N}$
- Countably infinite: there is a bijection with $\mathbb{N}$ (e.g. $\mathbb{Z},\ \mathbb{Q}$)
- Uncountable: strictly larger than countable (e.g. $\mathbb{R}$)
12. Typical Exam Identities & Tricks
- $A\setminus(B\cup C)=(A\setminus B)\cap(A\setminus C)$
- $A\setminus(B\cap C)=(A\setminus B)\cup(A\setminus C)$
- $A\triangle B=(A\cup B)\setminus(A\cap B)$, and $(A\triangle B)\triangle C=A\triangle(B\triangle C)$
- $A\subseteq B\iff A\cup B=B\iff A\cap B=A$
13. Worked Mini-Examples
- Cardinality of a power set: If $|A|=5$, then $|\mathcal{P}(A)|=2^5=32$.
- Counting with inclusion–exclusion (2 sets): If $|A|=40$, $|B|=35$, $|A\cap B|=10$, then $|A\cup B|=40+35-10=65$.
- Subset test by intersections: $A\subseteq B\iff A\cap B=A$.
- Disjointness: $A$ and $B$ disjoint $\iff A\cap B=\varnothing$.
- Cartesian product size: If $|A|=3$, $|B|=4$, then $|A\times B|=12$.
14. Common Pitfalls
- $\{a\}$ vs $a$: the former is a set containing $a$; the latter is the element itself
- $\varnothing\ne\{\varnothing\}$: the first has no elements, the second has one element (the empty set)
- Order matters in tuples: $(a,b)\ne(b,a)$ in general
- In complements, always specify/remember the universe $U$
15. Quick Practice (Self-check)
- Write $\{x\in\mathbb{Z}\mid -2\le x\le 2\}$ in roster form.
- List $\mathcal{P}(\{1,2,3\})$ and verify it has $2^3$ elements.
- Prove $A\setminus(B\cup C)=(A\setminus B)\cap(A\setminus C)$ using element method.
- If $|A|=m$, $|B|=n$ (finite), find $|A\times B\times A|$.
- Give an example of a relation that is reflexive and transitive but not symmetric.
Tip for exams (NIMCET/CUET-PG/MAH-MCA-CET): Master the identity table and inclusion–exclusion. For proofs, prefer the element-chasing style: “Let $x$ be arbitrary… show both directions $\Rightarrow$ and $\Leftarrow$.”