Set Theory & Elementary Group Theory

Rules of set algebra

Set algebra forms the foundational bedrock of abstract mathematics, governed by idempotent, commutative, associative, distributive, and De Morgan's laws.

For: UP PGT Mathematics UP TGT Mathematics DSSSB PGT / TGT KVS / NVS PGT LT Grade

📖 Topic progress

○ Mark as complete

Definition and statement

Fundamental Laws of Set Algebra

Let $U$ be a universal set and $A, B, C \subseteq U$. The operations of union $(\cup)$, intersection $(\cap)$, and complementation $(^c)$ satisfy precise algebraic laws including idempotence ($A \cup A = A$), commutativity ($A \cup B = B \cup A$), associativity $((A \cup B) \cup C = A \cup (B \cup C))$, distributivity ($A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$), and De Morgan's laws ($(A \cup B)^c = A^c \cap B^c$).

📐 Geometric Interpretation

Represented via Venn diagrams where sets correspond to geometric regions in the plane. Union corresponds to region merging, intersection to overlapping areas, and complementation to the exterior relative to the universal boundary rectangle.

⚙️ Algebraic & Structural Meaning

Sets under union and intersection operations form a bounded distributive lattice and a Boolean algebra when coupled with complementation, establishing the algebraic structure for measure theory and probability.

Conditions and hypotheses

Check each condition and what changes when it is omitted:

Hypothesis / Condition	Domain / Interval	Necessity	What Fails If Condition Dropped
Universal Set Containment	`Subsets of a fixed universal set $U$`	Strictly Mandatory / Necessary	Complementation operations become ill-defined or lead to Russell-type paradoxes if not restricted to a well-defined universal set.
Binary Operation Closure	`Power set $\mathcal{P}(U)$`	Strictly Mandatory	Operations fail to yield unique subsets within the domain if closure under union, intersection, and complement is violated.
Disjointness / Partition Conditions	`Pairwise disjoint families`	Essential for simplified cardinal calculations	Additive formulas like $\|A \cup B\| = \|A\| + \|B\|$ overcount elements if sets are not disjoint, necessitating the Principle of Inclusion-Exclusion.

Useful results and shortcuts

Use these identities and results when their conditions apply:

De Morgan's Complement Duality

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

Rule: Push the complement symbol inside and invert the operation symbol: union becomes intersection, and vice versa.

Application: Directly tested in UP PGT for simplifying complex negated set expressions within seconds.

Set Difference to Intersection Conversion

$$ A \setminus B = A \cap B^c $$

Rule: Instantly convert set difference into an intersection with the complement of the subtrahend.

Application: Frequent utility in simplifying domain conditions and multi-set relational problems in KVS PGT.

Absorption Laws

$$ A \cup (A \cap B) = A, \quad A \cap (A \cup B) = A $$

Rule: When a smaller set operation is nested inside a larger outer operation with the same set repeated, the larger expression collapses to the repeated set.

Application: Classic 1-mark direct formula question in UP TGT Mathematics.

Principle of Duality in Boolean Expressions

$$ \text{If } A \cup B = A \cup C \text{ and } A \cap B = A \cap C \implies B = C \text{ (under modularity conditions)} $$

Rule: Swap $\cup$ and $\cap$, and swap $\emptyset$ and $U$, to instantly obtain dual valid algebraic identities.

Application: Used to verify options in abstract relation and set-theoretic identity matching questions.

Symmetric Difference Expansion

$$ A \triangle B = (A \setminus B) \cup (B \setminus A) = (A \cup B) \setminus (A \cap B) $$

Rule: Symmetric difference is the union minus the intersection; use this to resolve XOR logic questions rapidly.

Application: Appears in advanced DSSSB PGT screening sets involving algebraic properties of rings of sets.

Cardinality Inclusion-Exclusion for 3 Sets

$$ |A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |B \cap C| - |C \cap A| + |A \cap B \cap C| $$

Rule: Alternate signs: singletons (+), pairwise intersections (-), triple intersection (+).

Common errors and counterexamples

These examples show how a conclusion can fail when a condition is missing:

⚠️ COMMON ERROR #01

Cancellation Law Failure in Set Union/Intersection

Common Pitfall: Assuming $A \cup B = A \cup C \implies B = C$, or similarly for intersections.

Counterexample: Let $A = \{1, 2\}, B = \{1\}, C = \{1, 3\}$. Then $A \cup B = \{1, 2\} = A \cup C$, but $B \neq C$.

Why it fails: Set union and intersection operations do not possess cancellation properties in general algebraic structures.

🛡️ Exam Defense: Never cancel sets across unions or intersections unless accompanied by disjointness or specific complement constraints.

⚠️ COMMON ERROR #02

Confusing Proper Subset with Subset

Common Pitfall: Treating $A \subset B$ as strictly excluding equality when standard Indian examination notations often use $\subset$ interchangeably with $\subseteq$.

Counterexample: If $A = B$, $A \subseteq B$ is true, but $A \subset B$ (proper subset) is false.

Why it fails: Misinterpretation leads to incorrect selection in 'statement correct/incorrect' assertion-reasoning questions.

🛡️ Exam Defense: Check context; look for $\subseteq$ for non-strict and $\subsetneq$ for strict inclusion if the paper uses modern formal notation.

Comparison

Concept / Theorem	Hypotheses / Assumptions	Key Formula / Outcome	Geometric Meaning	Exam Identification Clue
Idempotent Law	Any set $A \subseteq U$	$A \cup A = A, \, A \cap A = A$	Merging or intersecting a region with itself yields identical region	Simplification of repeated set terms
De Morgan's Law	Sets $A, B \subseteq U$	$(A \cup B)^c = A^c \cap B^c$	Complement of union is intersection of complements	Negation of compound set conditions
Distributive Law	Sets $A, B, C \subseteq U$	$A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$	Cross-distribution of union over intersection	Expanding or factoring set expressions
Absorption Law	Sets $A, B \subseteq U$	$A \cup (A \cap B) = A$	Outer set dominates the nested intersection term	Redundant term elimination

Solved examples

Each problem includes a full solution and a shorter method:

CANONICAL PROBLEM 01 Dual-Method Breakdown

If $A$ and $B$ are two sets, then $A \cap (A \cup B)^c$ is equal to:

(A) $A$(B) $B$(C) $\emptyset$(D) $A \setminus B$

📚 Method A: Formal Textbook Derivation

Step 1: Apply De Morgan's Law to $(A \cup B)^c$ to get $A^c \cap B^c$. Step 2: Expression becomes $A \cap (A^c \cap B^c)$. Step 3: Use associative law: $(A \cap A^c) \cap B^c$. Step 4: Since $A \cap A^c = \emptyset$, result is $\emptyset \cap B^c = \emptyset$.

⚡ Method B: 25-Second Exam Shortcut

Venn diagram visualization: $A \cup B$ covers both, its complement covers everything outside. Intersecting with $A$ yields nothing since outside $A \cup B$ has no overlap with $A$.

💡 Tip: Whenever you see a complement over a union outside an intersection, immediately apply De Morgan's law.

CANONICAL PROBLEM 02 Dual-Method Breakdown

For any three sets $A, B, C$, the expression $A \setminus (B \setminus C)$ is identical to:

(A) $(A \setminus B) \setminus C$(B) $(A \setminus B) \cup (A \cap C)$(C) $(A \cap B^c) \cup C$(D) $A \cap B^c \cap C$

📚 Method A: Formal Textbook Derivation

Step 1: Rewrite set differences as intersections with complements: $A \cap (B \cap C^c)^c$. Step 2: Apply De Morgan's law inside: $A \cap (B^c \cup C)$. Step 3: Use distributive law: $(A \cap B^c) \cup (A \cap C)$. Step 4: Convert back to set difference notation: $(A \setminus B) \cup (A \cap C)$.

⚡ Method B: 25-Second Exam Shortcut

Test with small sets: Let $U = \{1, 2, 3\}$, $A = \{1, 2\}$, $B = \{2\}$, $C = \{3\}$. $B \setminus C = \{2\}$. $A \setminus (B \setminus C) = \{1\}$. Check options for set yielding $\{1\}$.

💡 Tip: Numerical counterexamples with 2-3 element sets eliminate wrong options.

Practice questions

Choose an answer to check it and see the solution:

MCQ 1: If $A$ and $B$ are disjoint sets, then $A \cap (A^c \cup B)$ is equal to:

A $A$

B $B$

C $\emptyset$

D $A \cup B$

Derivation & Analysis:

Using distributive law: $(A \cap A^c) \cup (A \cap B) = \emptyset \cup (A \cap B)$. Since $A$ and $B$ are disjoint, $A \cap B = \emptyset$. Thus, $\emptyset \cup \emptyset = \emptyset$.

MCQ 2: The simplified form of $(A \cup B) \cap (A \cup B^c)$ is:

A $A$

B $B$

C $U$

D $\emptyset$

Derivation & Analysis:

Apply distributive law: $A \cup (B \cap B^c) = A \cup \emptyset = A$.

MCQ 3: If $A \subseteq B$, then the simplified form of $A \cup (B \setminus A)$ is:

A $A$

B $B$

C $A \cap B$

D $A^c$

Derivation & Analysis:

Since $A \subseteq B$, the union of $A$ and the elements in $B$ not in $A$ precisely reconstructs the set $B$.

MCQ 4: Which of the following is always true for any sets $A, B, C$?

A $A \cup (B \cap C) = (A \cup B) \cap C$

B $A \setminus (B \cup C) = (A \setminus B) \cap (A \setminus C)$

C $(A \cup B)^c = A^c \cup B^c$

D $A \cap (B \cup C) = (A \cap B) \cup C$

Derivation & Analysis:

By De Morgan's law on set differences: $A \setminus (B \cup C) = A \cap (B \cup C)^c = A \cap (B^c \cap C^c) = (A \cap B^c) \cap (A \cap C^c) = (A \setminus B) \cap (A \setminus C)$.

MCQ 5: If $P$ and $Q$ are two sets, then $P \cup (Q \setminus P)$ is equivalent to:

A $P \cap Q$

B $P \cup Q$

C $Q \setminus P$

D $P$

Derivation & Analysis:

$Q \setminus P = Q \cap P^c$. Then $P \cup (Q \cap P^c) = (P \cup Q) \cap (P \cup P^c) = (P \cup Q) \cap U = P \cup Q$.

MCQ 6: The dual of the statement $(A \cup B) \cap C = (A \cap C) \cup (B \cap C)$ is:

A $(A \cap B) \cup C = (A \cup C) \cap (B \cup C)$

B $(A \cup B) \cup C = (A \cap C) \cap (B \cap C)$

C $(A \cap B) \cap C = (A \cup C) \cup (B \cup C)$

D $(A \cup B) \cap C = (A \cup C) \cup (B \cap C)$

Derivation & Analysis:

Swap $\cup$ and $\cap$: $\cap$ becomes $\cup$ and $\cup$ becomes $\cap$, yielding $(A \cap B) \cup C = (A \cup C) \cap (B \cup C)$.

MCQ 7: If $A, B$ are subsets of $U$, then $(A \setminus B) \cup (B \setminus A) \cup (A \cap B)$ simplifies to:

A $A \cap B$

B $A \cup B$

C $A^c \cup B^c$

D $U$

Derivation & Analysis:

$(A \setminus B) \cup (B \setminus A)$ is symmetric difference $A \triangle B$, which combined with $A \cap B$ covers the exact union $A \cup B$.

MCQ 8: Assertion (A): If $A \subseteq B$, then $B^c \subseteq A^c$. Reason (R): Complementation reverses the inclusion relation.

A Both (A) and (R) are true and (R) is the correct explanation of (A)

B Both (A) and (R) are true and (R) is not the correct explanation of (A)

C (A) is true but (R) is false

D (A) is false but (R) is true

Derivation & Analysis:

If $x \in B^c$, then $x \notin B$. Since $A \subseteq B$, $x \notin A$, meaning $x \in A^c$. Thus $B^c \subseteq A^c$, and complementation indeed reverses inclusion.

MCQ 9: If $A = \{x \in \mathbb{R} : x^2 - 3x + 2 = 0\}$ and $B = \{x \in \mathbb{R} : x^2 = 4\}$, then $A \setminus B$ is:

A $\{1\}$

B $\{2\}$

C $\{1, 2\}$

D $\emptyset$

Derivation & Analysis:

Solve $A$: $x^2 - 3x + 2 = 0 \implies x \in \{1, 2\}$. Solve $B$: $x^2 = 4 \implies x \in \{-2, 2\}$. $A \setminus B = \{1, 2\} \setminus \{-2, 2\} = \{1\}$.

Q10

MCQ 10: For any set $A$, $A \cup A^c$ and $A \cap A^c$ respectively equal:

A $\emptyset, U$

B $U, \emptyset$

C $A, A^c$

D $U, U$

Derivation & Analysis:

By complement laws, the union of a set with its complement is the universal set $U$, and their intersection is the empty set $\emptyset$.

Common questions

Yes! Every set identity corresponds directly to a logical proposition using propositional equivalence, where union corresponds to disjunction ($\lor$), intersection to conjunction ($\land$), and complement to negation $(\neg)$.

Failure to properly distribute complements or misapplying cancellation laws where they do not hold (e.g., assuming $A \cap B = A \cap C \implies B = C$).

Employing the 'counterexample method' by testing options with small sets like $\{1\}$ or $\{1, 2\}$, or applying rapid Venn diagram sketching, allows candidates to bypass lengthy algebraic derivations.