You recognise symbols such as ∈, ⊆, ∪, and ∩, but lose marks when membership, subsets, and counting meet in one question. Connect the notation to visible sets and calculate each region instead of guessing. Set algebra, power-set counting and inclusion-exclusion decide most GATE-style set questions, and each one is a short calculation once the regions are on paper. The rest of the subject sits in GATE CS Exam Preparation.
Set theory foundations: elements, notation and types of sets
A set is a well-defined collection of distinct objects. Each object is an element, and cardinality is the number of elements. With U = {1,2,3,...,12}, the roster form A = {2,4,6,8,10,12} lists every member. The set-builder form {x ∈ U : x is divisible by 2} describes the same set by a rule, so |A| = 6.
Order and repetition change nothing: {2,4,4,6} = {6,4,2}. The empty set ∅ has no elements; {7} is a singleton; {1,2,3} is finite; the positive integers form an infinite set; and U is the universal set for the current discussion.
Equal sets contain exactly the same elements. Equivalent sets only have the same cardinality. Thus {a,b,c} and {4,5,6} are equivalent because each has three elements, but they are not equal.
Subsets and power sets: how the counts grow
A set T is a subset of S when every element of T belongs to S. For S = {p,q,r}, enumerate before applying a formula:
P(S) = {∅,{p},{q},{r},{p,q},{p,r},{q,r},{p,q,r}}.
The power set has |P(S)| = 2^3 = 8 members. A proper subset can be anything except S itself, giving 7 proper subsets. Excluding ∅ as well leaves 6 non-empty proper subsets.
The exponent comes from a two-way choice for each element: include it or leave it out. Therefore an n-element set has 2^n subsets, while exactly k selected elements can be chosen in C(n,k) ways. For a 6-element set, the checks are 2^6 = 64 total subsets and C(6,2) = 6!/(2!4!) = (6 × 5)/2 = 15 two-element subsets.
Set operations and laws: union, intersection and complements
Keep U = {1,2,3,...,12}, A = {2,4,6,8,10,12}, and B = {1,2,3,4,6,12}. Direct calculation gives:
A∪B = {1,2,3,4,6,8,10,12}A∩B = {2,4,6,12}A−B = {8,10}andB−A = {1,3}AΔB = {1,3,8,10}
Difference keeps members of the first set absent from the second, so A−B = A∩B^c. Symmetric difference keeps members appearing in exactly one set, so AΔB = (A−B)∪(B−A).
Relative to U, A^c = {1,3,5,7,9,11} and B^c = {5,7,8,9,10,11}. De Morgan's law is visible: (A∪B)^c = {5,7,9,11} = A^c∩B^c.
Law | Union form | Intersection form |
|---|---|---|
Commutative |
|
|
Associative |
|
|
Distributive |
|
|
Identity |
|
|
Idempotent |
|
|
Absorption |
|
|
Complement |
|
|
De Morgan |
|
|
Inclusion-exclusion principle: counting every region of a three-set Venn diagram
Take a class of 100 students in which 55 chose C, 48 chose Java, and 40 chose Python. Of those, 25 chose both C and Java, 18 chose both C and Python, 15 chose both Java and Python, and 8 chose all three. Find how many chose at least one language, how many chose none, how many chose exactly one, and how many chose exactly two.
First apply three-set inclusion-exclusion:
|C∪J∪P| = 55+48+40−25−18−15+8 = 93.
Therefore, none is 100−93 = 7.
The pair totals include the central group of 8. Subtract it once from each pair:
C and Java only:
25−8 = 17C and Python only:
18−8 = 10Java and Python only:
15−8 = 7
Now remove the relevant pair-only regions and the central region from each set:
C only:
55−17−10−8 = 20Java only:
48−17−7−8 = 16Python only:
40−10−7−8 = 15
Exactly one is 20+16+15 = 51. Exactly two is 17+10+7 = 34. The check is 51+34+8+7 = 100.
Cartesian products: the bridge from sets to relations
Let X = {1,2} and Y = {a,b,c}. Their Cartesian product is
X × Y = {(1,a),(1,b),(1,c),(2,a),(2,b),(2,c)},
so |X × Y| = |X| × |Y| = 2 × 3 = 6. Ordered pairs preserve position. Therefore Y × X contains pairs such as (a,1), not (1,a), and is different from X × Y.
A relation from X to Y is any subset of X × Y. Since a six-element set has 2^6 subsets, these sets permit 64 possible relations. One concrete example is R = {(1,a),(2,c)}. Properties such as reflexivity, symmetry, transitivity, equivalence and partial order belong to the next step, covered in Set theory and relations: closures, equivalence and partial orders.
Set theory traps: notation and counting mistakes
These common notation errors change the mathematical object.
Trap | Why it happens | Wrong consequence | Fix |
|---|---|---|---|
Membership versus subset | An element resembles its singleton | Writing | Write |
Empty set |
| Giving both cardinality zero |
|
Directional difference | Subtraction looks symmetric | Assuming both results match |
|
Complement without a universe | The outside is unstated | Claiming one fixed complement | Define |
Union counting | Common members occur twice | Adding | Subtract 4 common elements: |
Power-set counting | Only non-empty choices are listed | Counting one too few | Include |
Set theory in GATE and interviews: the question patterns
Common GATE-style forms ask you to simplify an expression with set laws, compute a union cardinality, count subsets or relations, translate set-builder notation, or connect predicates to sets. A useful nested check is |P(P({a,b}))| = 2^(2^2) = 16: {a,b} has 2 elements, its first power set has 4, and the next has 2^4 = 16. The equivalence and negation habits used here also carry into Propositional and Predicate Logic: Truth Tables to Proofs.
In an interview, the same ideas appear as data operations. Deduplicating [4,2,4,1,2,7] yields the set {1,2,4,7}. Intersecting it with {2,3,4,8} yields {2,4}. A hash set does both in linear expected time in the combined input size, while preserving the original input order needs a second pass or an order-preserving structure.
Once you can recompute these results without looking back, the GATE Test Series puts the same patterns under timed mixed practice.
Set theory short version and the next step
Read the universal set before taking a complement.
Distinguish element membership
∈from the subset relation⊆.Derive set laws from what the operations mean instead of memorising symbols alone.
Draw disjoint regions before doing inclusion-exclusion arithmetic.
Check every subset count against
2^n.
If you want set theory placed inside a structured full-subject plan, GATE Guidance by Sanchit Sir provides the broader GATE CS route. Work through it once membership, subset counting and inclusion-exclusion run without hesitation.
