Set Theory - Crash Course for UGC NET Computer science

Introduction

Set is a well‑defined unordered collection of distinct objects called elements or members. The phrase well‑defined means it must be possible to decide, for any given object, whether it belongs to the set or not.

• Roster (tabular) form: list elements inside braces, e.g., A = {1, 2, 3, …}.
• Set‑builder form: describe elements using a property, e.g., S = {x | x is a positive integer}.
• Order and repetition: order of elements does not matter and repetition is not allowed; {1, 2} and {2, 1} denote the same set, and {1, 1, 2} is the same as {1,2}.

Types of Sets

Basic classifications

• Finite set: a set with a finite number of elements, e.g., A = {1, 2, 3}.
• Infinite set: a set with infinitely many elements, e.g., {1, 2, 3, …}.
• Singleton set: a set with exactly one element, e.g., {a}.
• Empty set (Null set): a set with no elements. Denoted by ∅ or {}. Example: {x | x is a prime number and divisible by 2 and x ≠ 2} is ∅.
• Universal set: the set of all objects under current discussion or the ‘universe’ of discourse. Denoted by U.
• Equal sets:A = B when every element of A is in B and every element of B is in A.

Subset and Proper Subset

• Subset: A is a subset of B, written A ⊆ B, if every element of A belongs to B. 
  Example: A = {a, b, c}, B = {a, b, c, d}, then A ⊆ B.
• Proper subset: A is a proper subset of B, written A ⊂ B, if A ⊆ B and A ≠ B. 
  Example: B = {1, 2}, C = {1}, then C ⊂ B.
• Trivial subsets: For any set A, ∅ and A are called trivial (or improper) subsets of A.

Power set

• Power set of a set A, denoted P(A) or 2^A, is the set of all subsets of A.
  Example: If A = {1, 2} then P(A) = {∅, {1}, {2}, {1, 2}}.
• Cardinality of power set: If |A| = n (A finite) then |P(A)| = 2ⁿ.

Operations on Sets

Union

• A ∪ B is the set of all elements which belong to A or B (or both).
  Example: A = {1, 2, 3}, B = {4, 5}. Then A ∪ B = {1, 2, 3, 4, 5}.

Intersection

• A ∩ B is the set of all elements which belong to both A and B.
  Example: A = {1,2,3}, B = {3,4,5}. Then A ∩ B = {3}.

Set difference

• A − B (also written A \ B) is the set of elements that belong to A but not to B: A − B = {x | x ∈ A and x ∉ B}.
  Example: A = {1, 2, 3, 4}, B = {3, 4}. Then A − B = {1, 2}.

Complement

• Given a universal set U, the complement of A is A^c = {x ∈ U | x ∉ A}. It is also written Ā or Ac.

Symmetric difference

• A Δ B (also written A ⊕ B) consists of elements which belong to exactly one of A or B, but not both. Equivalently, A Δ B = (A ∪ B) − (A ∩ B) and A Δ B = (A − B) ∪ (B − A).
  Example: A = {1, 2, 3}, B = {3, 4}. Then A Δ B = {1, 2, 4}.

Cardinality and Counting Formulae

Cardinality of a set A, denoted |A|, is the number of distinct elements in A (finite case).
Two‑set formula:
|A ∪ B| = |A| + |B| − |A ∩ B|
Reason: elements common to A and B are counted twice in |A| + |B|, so subtract |A ∩ B| once.

Basic Laws and Properties

For any sets A, B, C (all subsets of a universal set U) the following laws hold.

Subset properties

• If A ⊆ B then A ∪ B = B and A ∩ B = A.
• Empty set:∅ ⊆ A for every A.
• Double complement: (A^c)^c = A.

Commutative and Associative laws

• Commutative: A ∪ B = B ∪ A, A ∩ B = B ∩ A, A Δ B = B Δ A.
• Associative: (A ∪ B) ∪ C = A ∪ (B ∪ C), (A ∩ B) ∩ C = A ∩ (B ∩ C), (A Δ B) Δ C = A Δ (B Δ C).

Distributive laws

• A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C).
• A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C).

De Morgan's laws

• (A ∪ B)^c = A^c ∩ B^c
• (A ∩ B)^c = A^c ∪ B^c

Idempotent and Absorption laws

• Idempotent: A ∪ A = A, A ∩ A = A.
• Absorption: A ∪ (A ∩ B) = A, A ∩ (A ∪ B) = A.

Modular laws

• (A ∪ B) ∩ C = A ∪ (B ∩ C) if A ⊆ C.
• (A ∩ B) ∪ C = A ∩ (B ∪ C) if C ⊆ A.

Other important identities

• A ∪ ∅ = A, A ∩ ∅ = ∅.
• A ∪ U = U, A ∩ U = A.
• A ∪ A^c = U, A ∩ A^c = ∅.

Proofs and Worked Examples

Proof: (A ∪ B)^c = A^c ∩ B^c

We prove equality by showing mutual inclusion.
Assume x ∈ (A ∪ B)^c.
Then x ∉ (A ∪ B).
Therefore x ∉ A and x ∉ B.
Hence x ∈ A^c and x ∈ B^c.
Thus x ∈ A^c ∩ B^c.
Conversely, assume x ∈ A^c ∩ B^c.
Then x ∉ A and x ∉ B.
Therefore x ∉ (A ∪ B).
Hence x ∈ (A ∪ B)^c.
Since both inclusions hold, the two sets are equal.

Example: cardinality of union

Let A = {1, 2, 3} and B = {3, 4, 5}.
|A| = 3.
|B| = 3.
|A ∩ B| = 1 (since {3}).
|A ∪ B| = |A| + |B| − |A ∩ B|.
|A ∪ B| = 3 + 3 − 1 = 5.
So A ∪ B = {1, 2, 3, 4, 5} and |A ∪ B| = 5.

Example: power set and its cardinality

Let A = {1,2,3}.
P(A) = {∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}.
|A| = 3, therefore |P(A)| = 2³ = 8.

Practical Notes and Tips

• When solving problems, always specify the universal set U if complements are used.
• Use element‑wise reasoning (take x and reason whether x is in sets) to prove set equalities or inclusions.
• Venn diagrams are a useful visual aid for two or three sets to understand union, intersection, difference and complements.
• Remember the identity for symmetric difference: A Δ B = (A − B) ∪ (B − A), which often simplifies counting problems.