Learn Complete Set Theory For NIMCET & CUET PG MCA 2026 With Detailed Definitions, Venn Diagrams, Laws, And Formulas. Get Easy Examples, Solved Problems, And Quick Revision Notes For MCA Entrance Exams.

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)

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

1. Cardinality of a power set: If $|A|=5$, then $|\mathcal{P}(A)|=2^5=32$.
2. Counting with inclusion–exclusion (2 sets): If $|A|=40$, $|B|=35$, $|A\cap B|=10$, then $|A\cup B|=40+35-10=65$.
3. Subset test by intersections: $A\subseteq B\iff A\cap B=A$.
4. Disjointness: $A$ and $B$ disjoint $\iff A\cap B=\varnothing$.
5. 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)

1. Write $\{x\in\mathbb{Z}\mid -2\le x\le 2\}$ in roster form.
2. List $\mathcal{P}(\{1,2,3\})$ and verify it has $2^3$ elements.
3. Prove $A\setminus(B\cup C)=(A\setminus B)\cap(A\setminus C)$ using element method.
4. If $|A|=m$, $|B|=n$ (finite), find $|A\times B\times A|$.
5. 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$.”