1.1 Sets

Detailed Theory: Sets

1. Basic Concepts and Definitions of Sets

1.1 What is a Set?

A set is a well-defined collection of distinct objects. The objects in a set are called its elements or members.

Key Characteristics:

• Well-defined: It must be clear whether a particular object belongs to the set or not

• Distinct: No element is repeated (each element appears only once)

• Order doesn't matter: $\ \{1, 2, 3\} = \{3, 1, 2\} = \{2, 3, 1\}$

1.2 Notation and Symbols

• Sets are denoted by capital letters: $A, B, C, \ldots$

• Elements are denoted by lowercase letters: $a, b, c, \ldots$

• Belongs to: $a \in A$ means "a is an element of A"

• Does not belong to: $a \notin A$ means "a is not an element of A"

• Such that: $|$ or $:$ (colon) means "such that"

Example: $A = \{1, 2, 3, 4, 5\}$ Here, $3 \in A$ but $7 \notin A$

1.3 Methods of Describing Sets

a) Roster/Tabular Method

All elements are listed within braces {}, separated by commas.

Examples:

1. Set of vowels in English alphabet: $V = \{a, e, i, o, u\}$

2. Set of first five natural numbers: $N_5 = \{1, 2, 3, 4, 5\}$

3. Set of even numbers between 1 and 10: $E = \{2, 4, 6, 8, 10\}$

b) Set-Builder Method

Specifies a property that characterizes all elements of the set.

General Form: $\{x : P(x)\}$ or $\{x \mid P(x)\}$ Read as: "The set of all x such that P(x) is true"

Examples:

1. $\{x : x \text{ is a natural number less than 6}\}$ This means: $\{1, 2, 3, 4, 5\}$

2. $\{x \in \mathbb{Z} : -3 < x < 4\}$ This means: $\{-2, -1, 0, 1, 2, 3\}$

3. $\{x : x = 2n, n \in \mathbb{N}\}$ This means the set of all even natural numbers: $\{2, 4, 6, 8, \ldots\}$

1.4 Types of Sets

a) Empty/Null Set

A set with no elements. Denoted by $\emptyset$ or $\{\}$.

Important: $\{\emptyset\}$ is NOT an empty set. It's a set containing one element (which is the empty set).

Examples:

• Set of natural numbers less than 1: $\emptyset$

• $\{x : x^2 = -1, x \in \mathbb{R}\} = \emptyset$

b) Singleton Set

A set with exactly one element.

Examples:

• $A = \{5\}$

• $B = \{\emptyset\}$ (This is a singleton set containing the empty set)

• Set of solutions of $x + 2 = 5$: $\{3\}$

c) Finite Set

A set with finite number of elements. We can count all elements.

Examples:

• $A = \{a, b, c, d\}$ has 4 elements

• Set of days in a week: $\{Sunday, Monday, \ldots, Saturday\}$ has 7 elements

• $B = \{x : x \text{ is a prime number less than 10}\} = \{2, 3, 5, 7\}$ has 4 elements

d) Infinite Set

A set with infinite number of elements. We cannot count all elements.

Examples:

• Set of all natural numbers: $\mathbb{N} = \{1, 2, 3, \ldots\}$

• Set of all integers: $\mathbb{Z} = \{\ldots, -2, -1, 0, 1, 2, \ldots\}$

• Set of all real numbers: $\mathbb{R}$

e) Equal Sets

Two sets A and B are equal if they have exactly the same elements.

Notation: $A = B$

Criteria: $A = B$ if and only if every element of A is in B and every element of B is in A.

Examples:

1. $\{1, 2, 3\} = \{3, 1, 2\} = \{2, 1, 3\}$

2. $\{x : x^2 - 3x + 2 = 0\} = \{1, 2\}$

3. $\{a, b, c\} \neq \{a, b, d\}$

f) Equivalent Sets

Two sets are equivalent if they have the same number of elements (same cardinality).

Notation: $A \sim B$

Important: Equal sets are always equivalent, but equivalent sets may not be equal.

Examples:

• $A = \{1, 2, 3\}$ and $B = \{a, b, c\}$ are equivalent (both have 3 elements)

• $\{1, 2, 3\} \sim \{4, 5, 6\}$ (both have cardinality 3)

---

2. Subsets and Power Sets

2.1 Subset

Set A is a subset of set B if every element of A is also an element of B.

Notation: $A \subseteq B$ Read as: "A is a subset of B" or "A is contained in B"

Formal Definition: $A \subseteq B$ if and only if $x \in A \Rightarrow x \in B$ for all x

Examples:

1. $\{1, 2\} \subseteq \{1, 2, 3, 4\}$

2. $\mathbb{N} \subseteq \mathbb{Z} \subseteq \mathbb{Q} \subseteq \mathbb{R} \subseteq \mathbb{C}$

3. Every set is a subset of itself: $A \subseteq A$

2.2 Proper Subset

A is a proper subset of B if $A \subseteq B$ but $A \neq B$.

Notation: $A \subset B$ or $A \subsetneq B$

Examples:

1. $\{1, 2\} \subset \{1, 2, 3\}$

2. $\emptyset \subset \{1, 2, 3\}$ (Empty set is a proper subset of every non-empty set)

3. $\{a, b\} \subset \{a, b, c\}$

2.3 Important Facts about Subsets

1. Empty set is subset of every set: $\emptyset \subseteq A$ for any set A

2. Reflexive property: $A \subseteq A$ for any set A

3. Transitive property: If $A \subseteq B$ and $B \subseteq C$, then $A \subseteq C$

4. Antisymmetric property: If $A \subseteq B$ and $B \subseteq A$, then $A = B$

2.4 Number of Subsets

If a set A has n elements, then:

• Total number of subsets of A = $2^n$

• Number of proper subsets of A = $2^n - 1$

Proof: Each element has 2 choices: either be in a subset or not be in it. So for n elements, total possibilities = $2 \times 2 \times \cdots \times 2$ (n times) = $2^n$.

Example: For $A = \{a, b, c\}$ (n=3):

• Total subsets = $2^3 = 8$

• Proper subsets = $2^3 - 1 = 7$

2.5 Power Set

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

Notation: $P(A)$ or $2^A$ or $\mathcal{P}(A)$

Properties:

1. $\emptyset \in P(A)$ and $A \in P(A)$

2. If A has n elements, then $P(A)$ has $2^n$ elements

3. $A \subseteq B \Rightarrow P(A) \subseteq P(B)$

Example: For $A = \{1, 2\}$: $P(A) = \{\emptyset, \{1\}, \{2\}, \{1, 2\}\}$

Here, n(A) = 2, and n(P(A)) = $2^2 = 4$

---

3. Universal Set and Complement

3.1 Universal Set

The set that contains all objects under consideration in a particular context.

Notation: Usually denoted by U or $\xi$

Properties:

1. Every set under consideration is a subset of U

2. The choice of universal set depends on the context

Examples:

• In number theory: $U = \mathbb{N}$ or $\mathbb{Z}$

• In plane geometry: $U = \text{set of all points in the plane}$

• For a survey of students: $U = \text{set of all students in the school}$

3.2 Complement of a Set

The complement of a set A is the set of all elements in the universal set U that are not in A.

Notation: $A'$ or $A^c$ or $\overline{A}$ or $U - A$

Formal Definition: $A' = \{x : x \in U \text{ and } x \notin A\}$

Venn Diagram Representation: The region outside circle A but inside rectangle U.

Examples: Let $U = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}$ and $A = \{2, 4, 6, 8, 10\}$ Then $A' = \{1, 3, 5, 7, 9\}$

3.3 Properties of Complement

1. Complement Laws:

   • $A \cup A' = U$

   • $A \cap A' = \emptyset$

2. Double Complement Law: $(A')' = A$

3. Universal and Empty Set Complements:

   • $U' = \emptyset$

   • $\emptyset' = U$

4. De Morgan's Laws:

   • $(A \cup B)' = A' \cap B'$

   • $(A \cap B)' = A' \cup B'$

Proof of De Morgan's Law: $(A \cup B)' = A' \cap B'$ Let $x \in (A \cup B)'$ $\Rightarrow x \notin (A \cup B)$ $\Rightarrow x \notin A \text{ and } x \notin B$ $\Rightarrow x \in A' \text{ and } x \in B'$ $\Rightarrow x \in (A' \cap B')$ Thus, $(A \cup B)' \subseteq A' \cap B'$

Conversely, let $x \in A' \cap B'$ $\Rightarrow x \in A' \text{ and } x \in B'$ $\Rightarrow x \notin A \text{ and } x \notin B$ $\Rightarrow x \notin (A \cup B)$ $\Rightarrow x \in (A \cup B)'$ Thus, $A' \cap B' \subseteq (A \cup B)'$

Therefore, $(A \cup B)' = A' \cap B'$

---

4. Operations on Sets

4.1 Union of Sets

The union of sets A and B is the set of all elements that are in A, in B, or in both.

Notation: $A \cup B$

Formal Definition: $A \cup B = \{x : x \in A \text{ or } x \in B\}$

Venn Diagram: The entire shaded region of both circles.

Examples:

1. $\{1, 2, 3\} \cup \{3, 4, 5\} = \{1, 2, 3, 4, 5\}$

2. $\{a, b\} \cup \{c, d\} = \{a, b, c, d\}$

3. $\{x : x > 0\} \cup \{x : x < 5\} = \mathbb{R} - \{0\}$ (all real numbers except 0)

4.2 Intersection of Sets

The intersection of sets A and B is the set of all elements common to both A and B.

Notation: $A \cap B$

Formal Definition: $A \cap B = \{x : x \in A \text{ and } x \in B\}$

Venn Diagram: The overlapping region of the two circles.

Examples:

1. $\{1, 2, 3\} \cap \{3, 4, 5\} = \{3\}$

2. $\{a, b, c\} \cap \{c, d, e\} = \{c\}$

3. $\{x : x > 2\} \cap \{x : x < 5\} = \{x : 2 < x < 5\}$

Disjoint Sets

Two sets are disjoint if their intersection is empty.

Definition: A and B are disjoint if $A \cap B = \emptyset$

Examples:

• $\{1, 2\}$ and $\{3, 4\}$ are disjoint

• Set of even numbers and set of odd numbers are disjoint

4.3 Difference of Sets

The difference of sets A and B is the set of elements that are in A but not in B.

Notation: $A - B$ or $A \setminus B$

Formal Definition: $A - B = \{x : x \in A \text{ and } x \notin B\}$

Important: $A - B \neq B - A$ in general

Examples:

1. $\{1, 2, 3, 4\} - \{3, 4, 5\} = \{1, 2\}$

2. $\{3, 4, 5\} - \{1, 2, 3, 4\} = \{5\}$

3. $\{a, b, c\} - \{b, c, d\} = \{a\}$

Properties:

• $A - B = A \cap B'$

• $A - A = \emptyset$

• $A - \emptyset = A$

• $\emptyset - A = \emptyset$

• $A - U = \emptyset$

4.4 Symmetric Difference

The symmetric difference of sets A and B is the set of elements that are in either A or B but not in both.

Notation: $A \triangle B$ or $A \ominus B$

Formal Definitions:

1. $A \triangle B = (A \cup B) - (A \cap B)$

2. $A \triangle B = (A - B) \cup (B - A)$

Venn Diagram: The non-overlapping parts of both circles.

Examples:

1. $\{1, 2, 3\} \triangle \{3, 4, 5\} = \{1, 2, 4, 5\}$

2. $\{a, b, c\} \triangle \{b, c, d\} = \{a, d\}$

Properties:

1. Commutative: $A \triangle B = B \triangle A$

2. Associative: $(A \triangle B) \triangle C = A \triangle (B \triangle C)$

3. $A \triangle A = \emptyset$

4. $A \triangle \emptyset = A$

5. $A \triangle U = A'$

---

5. Laws of Set Algebra

5.1 Commutative Laws

1. $A \cup B = B \cup A$

2. $A \cap B = B \cap A$

Proof of $A \cup B = B \cup A$: Let $x \in A \cup B$ $\Rightarrow x \in A \text{ or } x \in B$ $\Rightarrow x \in B \text{ or } x \in A$ $\Rightarrow x \in B \cup A$ Thus, $A \cup B \subseteq B \cup A$

Similarly, $B \cup A \subseteq A \cup B$ Therefore, $A \cup B = B \cup A$

5.2 Associative Laws

1. $(A \cup B) \cup C = A \cup (B \cup C)$

2. $(A \cap B) \cap C = A \cap (B \cap C)$

Example Verification: Let $A = \{1, 2\}, B = \{2, 3\}, C = \{3, 4\}$ LHS: $(A \cup B) \cup C = (\{1, 2, 3\}) \cup \{3, 4\} = \{1, 2, 3, 4\}$ RHS: $A \cup (B \cup C) = \{1, 2\} \cup \{2, 3, 4\} = \{1, 2, 3, 4\}$ LHS = RHS

5.3 Distributive Laws

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

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

Proof of $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$: Let $x \in A \cup (B \cap C)$ Case 1: If $x \in A$, then $x \in A \cup B$ and $x \in A \cup C$ So $x \in (A \cup B) \cap (A \cup C)$

Case 2: If $x \in B \cap C$, then $x \in B$ and $x \in C$ So $x \in A \cup B$ and $x \in A \cup C$ Thus $x \in (A \cup B) \cap (A \cup C)$

Therefore, $A \cup (B \cap C) \subseteq (A \cup B) \cap (A \cup C)$

Conversely, let $x \in (A \cup B) \cap (A \cup C)$ Then $x \in A \cup B$ and $x \in A \cup C$

If $x \in A$, then $x \in A \cup (B \cap C)$ If $x \notin A$, then from $x \in A \cup B$, we get $x \in B$ And from $x \in A \cup C$, we get $x \in C$ So $x \in B \cap C$, hence $x \in A \cup (B \cap C)$

Therefore, $(A \cup B) \cap (A \cup C) \subseteq A \cup (B \cap C)$

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

5.4 Identity Laws

1. $A \cup \emptyset = A$

2. $A \cap U = A$

5.5 Complement Laws

1. $A \cup A' = U$

2. $A \cap A' = \emptyset$

5.6 Idempotent Laws

1. $A \cup A = A$

2. $A \cap A = A$

5.7 Absorption Laws

1. $A \cup (A \cap B) = A$

2. $A \cap (A \cup B) = A$

5.8 De Morgan's Laws (Already proved in section 3.3)

1. $(A \cup B)' = A' \cap B'$

2. $(A \cap B)' = A' \cup B'$

5.9 Involution Law

$(A')' = A$

---

6. Cardinality of Sets

6.1 Cardinal Number

The number of elements in a finite set A is called its cardinal number.

Notation: $n(A)$ or $|A|$ or $\text{card}(A)$

Examples:

1. For $A = \{a, b, c, d\}$, $n(A) = 4$

2. For $B = \{1, 3, 5, 7, 9\}$, $n(B) = 5$

3. $n(\emptyset) = 0$

6.2 Inclusion-Exclusion Principle

For Two Sets:

$n(A \cup B) = n(A) + n(B) - n(A \cap B)$

Derivation: When we add $n(A)$ and $n(B)$, elements in $A \cap B$ are counted twice. So we subtract $n(A \cap B)$ once to count them only once.

Example: Let $A = \{1, 2, 3, 4\}, B = \{3, 4, 5, 6\}$

• $n(A) = 4, n(B) = 4$

• $A \cap B = \{3, 4\}, n(A \cap B) = 2$

• $A \cup B = \{1, 2, 3, 4, 5, 6\}, n(A \cup B) = 6$

• Verify: $6 = 4 + 4 - 2$

For Three Sets:

$n(A \cup B \cup C) = n(A) + n(B) + n(C) - n(A \cap B) - n(B \cap C) - n(C \cap A) + n(A \cap B \cap C)$

Example: In a survey of 100 students:

• 60 like Math (M)

• 50 like Science (S)

• 40 like English (E)

• 30 like Math and Science

• 20 like Science and English

• 15 like Math and English

• 10 like all three

How many like at least one subject?

Solution: $n(M \cup S \cup E) = 60 + 50 + 40 - 30 - 20 - 15 + 10 = 95$

So 95 students like at least one subject.

6.3 Cardinality Formulas

1. $n(A - B) = n(A) - n(A \cap B)$

2. $n(A \triangle B) = n(A) + n(B) - 2n(A \cap B)$

3. $n(A') = n(U) - n(A)$

4. $n(A \times B) = n(A) \cdot n(B)$

5. $n(P(A)) = 2^{n(A)}$

---

7. Cartesian Product

7.1 Definition

The Cartesian product of two sets A and B is the set of all ordered pairs (a, b) where a ∈ A and b ∈ B.

Notation: $A \times B$

Formal Definition: $A \times B = \{(a, b) : a \in A \text{ and } b \in B\}$

Important:

• $(a, b)$ is an ordered pair, so $(a, b) \neq (b, a)$ unless a = b

• $A \times B \neq B \times A$ in general

7.2 Examples

1. Let $A = \{1, 2\}, B = \{a, b\}$ $A \times B = \{(1, a), (1, b), (2, a), (2, b)\}$ $B \times A = \{(a, 1), (a, 2), (b, 1), (b, 2)\}$ Clearly, $A \times B \neq B \times A$

2. $\mathbb{R} \times \mathbb{R} = \mathbb{R}^2$ (the Cartesian plane)

3. If $A = \emptyset$ or $B = \emptyset$, then $A \times B = \emptyset$

7.3 Number of Elements

If A has m elements and B has n elements, then $A \times B$ has $m \times n$ elements.

Proof: For each of the m elements in A, we can pair it with any of the n elements in B.

Example: For $A = \{1, 2, 3\}$ (m=3) and $B = \{a, b\}$ (n=2): $n(A \times B) = 3 \times 2 = 6$

7.4 Properties of Cartesian Product

1. Non-commutative: $A \times B \neq B \times A$ (unless A = B or one is empty)

2. Non-associative: $(A \times B) \times C \neq A \times (B \times C)$

3. Distributive over union: $A \times (B \cup C) = (A \times B) \cup (A \times C)$

4. Distributive over intersection: $A \times (B \cap C) = (A \times B) \cap (A \times C)$

5. Distributive over difference: $A \times (B - C) = (A \times B) - (A \times C)$

7.5 Cartesian Product of Three or More Sets

For sets A, B, C: $A \times B \times C = \{(a, b, c) : a \in A, b \in B, c \in C\}$

Number of elements: $n(A \times B \times C) = n(A) \cdot n(B) \cdot n(C)$

Example: $A = \{1, 2\}, B = \{a, b\}, C = \{x, y\}$ $A \times B \times C = \{(1, a, x), (1, a, y), (1, b, x), (1, b, y), (2, a, x), (2, a, y), (2, b, x), (2, b, y)\}$ Total elements = $2 \times 2 \times 2 = 8$

---

8. Solved Examples

Example 1: Basic Set Operations

Let $U = \{1, 2, 3, 4, 5, 6, 7, 8\}, A = \{2, 4, 6, 8\}, B = \{3, 6, 7, 8\}$

Find:

1. $A \cup B$

2. $A \cap B$

3. $A - B$

4. $B - A$

5. $A'$

6. $A \triangle B$

Solution:

1. $A \cup B = \{2, 3, 4, 6, 7, 8\}$

2. $A \cap B = \{6, 8\}$

3. $A - B = \{2, 4\}$

4. $B - A = \{3, 7\}$

5. $A' = U - A = \{1, 3, 5, 7\}$

6. $A \triangle B = (A - B) \cup (B - A) = \{2, 4\} \cup \{3, 7\} = \{2, 3, 4, 7\}$

Example 2: Cardinality Problem

In a class of 50 students:

• 30 like Mathematics

• 25 like Physics

• 20 like Chemistry

• 15 like Mathematics and Physics

• 10 like Physics and Chemistry

• 8 like Mathematics and Chemistry

• 5 like all three subjects

Find:

1. How many like at least one subject?

2. How many like exactly one subject?

3. How many like none of the subjects?

Solution: Let M, P, C represent sets of students liking Mathematics, Physics, Chemistry respectively.

Given: $n(U) = 50, n(M) = 30, n(P) = 25, n(C) = 20$ $n(M \cap P) = 15, n(P \cap C) = 10, n(M \cap C) = 8, n(M \cap P \cap C) = 5$

1. Using inclusion-exclusion: $n(M \cup P \cup C) = 30 + 25 + 20 - 15 - 10 - 8 + 5 = 47$ So 47 students like at least one subject.

2. Students liking exactly one subject:

   • Only M: $n(M) - n(M \cap P) - n(M \cap C) + n(M \cap P \cap C) = 30 - 15 - 8 + 5 = 12$

   • Only P: $n(P) - n(M \cap P) - n(P \cap C) + n(M \cap P \cap C) = 25 - 15 - 10 + 5 = 5$

   • Only C: $n(C) - n(M \cap C) - n(P \cap C) + n(M \cap P \cap C) = 20 - 8 - 10 + 5 = 7$ Total = 12 + 5 + 7 = 24 students

3. Students liking none: $n(U) - n(M \cup P \cup C) = 50 - 47 = 3$

Example 3: Set Algebra Proof

Prove that $A - (B \cup C) = (A - B) \cap (A - C)$

Proof: Let $x \in A - (B \cup C)$ Then $x \in A$ and $x \notin (B \cup C)$ $\Rightarrow x \in A$ and $x \notin B$ and $x \notin C$ $\Rightarrow x \in A$ and $x \notin B$ and $x \in A$ and $x \notin C$ $\Rightarrow x \in (A - B)$ and $x \in (A - C)$ $\Rightarrow x \in (A - B) \cap (A - C)$ Thus, $A - (B \cup C) \subseteq (A - B) \cap (A - C)$

Conversely, let $x \in (A - B) \cap (A - C)$ Then $x \in A - B$ and $x \in A - C$ $\Rightarrow x \in A$ and $x \notin B$ and $x \in A$ and $x \notin C$ $\Rightarrow x \in A$ and $x \notin B$ and $x \notin C$ $\Rightarrow x \in A$ and $x \notin (B \cup C)$ $\Rightarrow x \in A - (B \cup C)$ Thus, $(A - B) \cap (A - C) \subseteq A - (B \cup C)$

Therefore, $A - (B \cup C) = (A - B) \cap (A - C)$

---

9. Practice Tips for Exams

1. Venn Diagrams: Always draw Venn diagrams for visualization

2. Set Notation: Be precise with notation: $\in, \subseteq, \subset, \cup, \cap, \setminus, \triangle$

3. Cardinality Formulas: Memorize inclusion-exclusion principle

4. Proof Techniques: For proofs, use element method (show $x \in LHS \Rightarrow x \in RHS$ and vice versa)

5. Special Cases: Remember edge cases: empty set, universal set, disjoint sets

6. Order Matters: Remember $A \times B \neq B \times A$ and $A - B \neq B - A$

This comprehensive coverage includes all aspects of Set Theory with detailed explanations and examples, providing a solid foundation for solving MCQs and complex problems in the entrance examination.