Set Theory

---

Chapter 1: SET THEORY

A set is a fundamental concept in mathematics used to group objects or numbers. To qualify as a set, the collection must adhere to strict logical rules regarding what belongs in it and what doesn’t.

Definition

A Set is a “well-defined” collection of distinct objects or numbers.
By “well-defined,” it means there should be absolutely no ambiguity regarding the inclusion or exclusion of the objects.

Examples of Well-Defined vs. Not Well-Defined:

• Well-Defined (These are Sets):
  • Collection of natural numbers less than 100.
  • Collection of all roots of the equation $x^2-5x+6=0$.
  • Collection of all the vowels in English alphabets.
• Not Well-Defined (These are NOT Sets):
  • Collection of the “ten most talented” writers of India (Subjective).
  • A team of eleven “best” cricket batsmen (Subjective).
  • Group of “Intelligent” Students in a batch (Subjective).

---

Basic Terminology & Symbols

• Elements/Members: The distinct objects contained within a set. Usually denoted by small letters ($a,b,c$). Sets are denoted by capital letters ($A,B,C$).
• Cardinal Number / Order ($n(A)$ or $|A|$): The total number of elements present in a set.
  • Example: If $X=\{-3,-2,1,0,2\}$, then the cardinal number $n(X)=5$.
• $\in$ (Epsilon): “Belongs to” or “is an element of”. (e.g., $1\in A$)
• $\notin$: “Does not belong to”.
• $:$ or $|$: “Such that”.

---

Essential Number Systems

Symbol	Name	Elements / Definition
$N$	Natural Numbers	$\{1,2,3,4,5,...\}$
$W$	Whole Numbers	$\{0,1,2,3,4,...\}$ (Also known as non-negative integers)
$Z$ or $I$	Integers	$\{...,-3,-2,-1,0,1,2,3,...\}$
$Z^{+}$	Positive Integers	$\{1,2,3,...\}$ (Exactly the same as $N$)
$Z^{-}$	Negative Integers	$\{-1,-2,-3,...\}$
$Q$	Rational Numbers	Numbers in $p/q$ form, where $p,q\in Z$ and $q\ne 0$
$\bar{Q}$	Irrational Numbers	Non-repeating, non-terminating decimals (e.g., $\sqrt{2},\sqrt{3},\pi$)
$R$	Real Numbers	Rational + Irrational Numbers ($Q+\bar{Q}$)

Zero's Status

Zero ($0$) is neither positive nor negative; it is a neutral integer.

• Non-positive integers: $\{0,-1,-2,-3,...\}$.
• Non-negative integers: $\{0,1,2,3,...\}$ (Same as Whole Numbers $W$).

---

Representation of Sets

1. Roster Form (Tabular Form)

All elements are explicitly listed, separated by commas, and enclosed within curly braces { }.

Golden Rules of Roster Form

1. Order does not matter: $\{1,2,3\}$ is the same as $\{3,2,1\}$.
2. Repetition is NOT allowed: Each element must be written only once.

• Example: Set of letters in the word “HONOLULU” $\to X=\{H,O,N,L,U\}$. (Notice $O,L,U$ are not repeated, making $n(X)=5$).

2. Set-Builder Form (Property Form)

Instead of listing elements, you state the common property that all elements must satisfy.

• Format: $X=\{x|\text{property satisfied by }x\}$.
• Example: $A=\{1,4,9,16,25,...\}$ in Set-Builder is $A=\{x|x=n^2,n\in N\}$.

---

Types of Sets

1. Null / Empty / Void Set ($\varphi$ or $\{\}$): A set containing zero elements. $n(\varphi )=0$.
   • Trap: $\{\}$ is an empty set, but $\{0\}$ and $\{\varphi \}$ are singleton sets!
2. Finite Set: A set having a countable number of elements (Null set is considered finite).
3. Infinite Set: A set having an infinite (uncountable) number of elements (e.g., $R,Z$).
4. Singleton Set: A set containing exactly one element (e.g., Even prime numbers = $\{2\}$).
5. Equivalent Sets: Two sets $A$ and $B$ where $n(A)=n(B)$.
6. Equal Sets: Two sets $A$ and $B$ that have the exact same elements. (All equal sets are inherently equivalent, but not all equivalent sets are equal).

---

Subsets, Proper Subsets & Power Sets

1. Subsets ($A\subseteq B$)

If every element of $A$ is also an element of $B$, then $A$ is a subset of $B$. $B$ is the Superset.

• Empty set ($\varphi$) is a subset of every set.
• Every set is a subset of itself. ($A\subseteq A$)
• Proof logic: If $A\subset B$, then $C-B\subset C-A$.

2. Proper Subsets ($A\subset B$)

If $A$ is a subset of $B$, but $A\ne B$ (meaning $B$ has at least one extra element that $A$ doesn’t have), then $A$ is a proper subset.

3. Cardinality Formulas for Subsets

For any set $A$ containing $n$ elements:

• Total number of subsets $=2^n$
• Total number of proper subsets $=2^n-1$ (Subtracts the set itself)
• Total number of non-empty subsets $=2^n-1$ (Subtracts the $\varphi$ set)

JEE Trick: Subset Product Rules

If a set has $p$ total elements, and $q$ of those elements are odd numbers:

1. Product is Odd: For the product of a subset’s elements to be odd, all elements in that subset must be odd.
   • Number of non-empty subsets with an odd product = $2^q-1$
2. Product is Even: For the product to be even, the subset must contain at least one even number.
   • Number of non-empty subsets with an even product = $(2^p-1)-(2^q-1)=2^{\mathbf{p}}-2^{\mathbf{q}}$

4. Power Set $P(A)$

The collection of all subsets of a set $A$ is called the power set of $A$.

• Formula: $n(P(A))=2^{n(A)}$
• Example: If $A=\{1,2\}$, its subsets are $\varphi ,\{1\},\{2\},\{1,2\}$.
  Therefore, $P(A)=\{\varphi ,\{1\},\{2\},\{1,2\}\}$.
• Null Set property: $n(P(P(\varphi )))=2^1=2$.

5. Universal Set ($U$)

A set consisting of all possible elements which occur in the context of a particular discussion or problem. Every other set is a subset of $U$.

---

Operations on Sets

Operation	Symbol	Meaning
Union	$A\cup B$	Elements in $A$, or $B$, or both (Combined).
Intersection	$A\cap B$	Elements common to both $A$ and $B$.
Difference	$A-B$	Elements in $A$ but NOT in $B$ (Exactly/Only $A$). Formula: $A-B=A-(A\cap B)$
Symmetric Difference	$A\Delta B$	Elements in exactly one of the sets. Formula: $A\Delta B=(A-B)\cup (B-A)$
Complement	$\bar{A}$ or $A^{\prime }$	Elements in the Universal set $U$ but not in $A$. Formula: $A^{\prime }=U-A$

Disjoint Sets

If two sets have no elements in common, they are Disjoint Sets.
Mathematical condition: $A\cap B=\varphi$

---

Laws of Algebra of Sets

Mastering these laws is critical for simplifying complex set equations without drawing Venn diagrams every time.

1. Idempotent Laws: * $A\cup A=A$
   • $A\cap A=A$
2. Identity Laws: * $A\cup \varphi =A$
   • $A\cap U=A$
   • $A\cup U=U$
   • $A\cap \varphi =\varphi$
3. Commutative Laws: * $A\cup B=B\cup A$
   • $A\cap B=B\cap A$
   • $A\Delta B=B\Delta A$
   • (Note: Difference $A-B$ is NOT commutative).
4. Associative Laws: * $(A\cup B)\cup C=A\cup (B\cup C)$
   • $(A\cap B)\cap C=A\cap (B\cap C)$
5. Distributive Laws: (Highly tested)
   • $A\cup (B\cap C)=(A\cup B)\cap (A\cup C)$
   • $A\cap (B\cup C)=(A\cap B)\cup (A\cap C)$
6. De Morgan’s Laws: * $(A\cup B{)}^{\prime }=A^{\prime }\cap B^{\prime }$ (The complement of a union is the intersection of complements)
   • $(A\cap B{)}^{\prime }=A^{\prime }\cup B^{\prime }$ (The complement of an intersection is the union of complements)
7. Complement Laws: * $A\cup A^{\prime }=U$
   • $A\cap A^{\prime }=\varphi$
   • $(A^{\prime }{)}^{\prime }=A$

---

Cardinality Formulas & Practical Problems

To solve word problems, use the following formulas derived from Venn Diagram regions:

Two-Set Logic ($A$ and $B$)

• Standard Union: $n(A\cup B)=n(A)+n(B)-n(A\cap B)$
• If Disjoint: $n(A\cup B)=n(A)+n(B)$
• Difference (Only A): $n(A-B)=n(A)-n(A\cap B)$
• Exactly One (Symmetric Difference): $n(A\Delta B)=n(A)+n(B)-2n(A\cap B)$
• Neither A nor B: $n(A^{\prime }\cap B^{\prime })=n(U)-n(A\cup B)$ (Via De Morgan’s)

Three-Set Logic ($A,B,C$)

The master formula for the union of three sets:
$n(A\cup B\cup C)=n(A)+n(B)+n(C)-n(A\cap B)-n(B\cap C)-n(A\cap C)+n(A\cap B\cap C)$

Deconstructing the 3-Set Venn Diagram:
Let regions be $a,b,c,d,e,f,g$.

• Exactly 3 (All): The center intersection ($A\cap B\cap C$).
• Exactly 2: The “petals” around the center, minus the center itself.
• Exactly 1: The outer moon-shaped regions of each circle.
• None: Everything outside the three circles ($U-(A\cup B\cup C)$).

The "At Least" / "At Most" Translation Guide

When interpreting word problems:

• At Least 1 = (Exactly 1) + (Exactly 2) + (Exactly 3) = $n(A\cup B\cup C)$
• At Least 2 = (Exactly 2) + (Exactly 3)
• At Most 1 = (Exactly 0) + (Exactly 1)
• At Most 2 = (Exactly 0) + (Exactly 1) + (Exactly 2)

Strategy for Max/Min Problems

When asked to find the maximum or minimum possible values of an intersection ($A\cap B$) or union ($A\cup B$):

• Max Intersection: Occurs when the smaller set is entirely a subset of the larger set. $Max(n(A\cap B))=\text{min}(n(A),n(B))$.
• Min Intersection: Occurs when the sets are pushed as far apart as possible without exceeding the Universal set. $Min(n(A\cap B))=n(A)+n(B)-n(U)$ (If $>0$, else $0$).