Set Theory Cheatsheet

Cheatsheet Content

### Introduction to Sets A **Set** is a well-defined collection of distinct objects. - Objects are called **elements** or **members**. - Denoted by capital letters (e.g., A, B, C). - Elements are denoted by small letters (e.g., x, y, z). - $x \in A$: x belongs to A. - $x \notin A$: x does not belong to A. #### Well-defined examples: - Collection of even numbers. - Collection of all vowels in English alphabets: $\{a, e, i, o, u\}$. - Collection of roots of equation $x^2 - 5x + 6 = 0$: $\{2, 3\}$. #### Not well-defined (subjective/ambiguous): - Collection of Best Teachers. - Collection of Most Talented writers. #### Important Symbols - ` : ` or ` | ` : "Such that" - ` ∈ ` : "belongs to" - ` ∉ ` : "doesn't belong to" #### Cardinal Number of a Set - Also known as the Order of a Set, or Number of elements in a set. - Denoted by $n(A)$ or $|A|$. - Example: If $A = \{1, 2, 5\}$, then $n(A) = 3$. ### Representation of Sets #### 1. Roster Form (Tabular Form) - Elements are listed within curly braces, separated by commas. - **Structure:** $A = \{element_1, element_2, ...\}$ - **Note:** - Repetition of elements is not allowed. - Order of elements is not important. - **Example 1:** Set of all vowels: $X = \{a, e, i, o, u\}$, $n(X) = 5$. - **Example 2:** Letters of the word HONOLULU: $X = \{H, O, N, L, U\}$, $n(X) = 5$. #### 2. Set-Builder Form - Elements are described by a property they satisfy. - **Structure:** $A = \{x \mid \text{properties satisfied by x}\}$ - **Example 1:** $A = \{x \mid x \in \mathbb{N}, x ### Types of Sets #### 1. Empty Set (Null Set / Void Set) - A set containing no elements. - Denoted by $\emptyset$ or `{}`. - **Note:** - ` {0} ` is not an empty set (it contains the element 0). - ` {∅} ` is not an empty set (it contains the empty set as an element). - $n(\emptyset) = 0$. #### 2. Finite Set - A set with a countable number of elements. - **Example:** $X = \{x \mid x^2 - 5x + 6 = 0\} = \{2, 3\}$ (finite set). #### 3. Infinite Set - A set with an infinite number of elements. - **Examples:** - Natural Numbers ($\mathbb{N}$), Whole Numbers ($\mathbb{W}$), Rational Numbers ($\mathbb{Q}$), Real Numbers ($\mathbb{R}$). - $X = \{x \mid 2 ### Subsets #### 1. Definition of Subset - A is a **subset** of B (denoted $A \subseteq B$) if every element of A is also an element of B. - B is a **Superset** of A (denoted $B \supseteq A$). - **Example:** If $A = \{1, 2, 3, 4\}$ and $B = \{1, 2, 3, 4, 6, 7, 8\}$, then $A \subseteq B$ and $B \supseteq A$. #### 2. Proper Subset - A is a **proper subset** of B (denoted $A \subset B$) if $A \subseteq B$ and $A \neq B$. - The number of proper subsets = (Number of subsets) - 1. #### 3. Important Subset Points - The empty set $\emptyset$ is a subset of every set. - Every set is a subset of itself ($A \subseteq A$). - If $A \subseteq B$ and $B \subseteq A$, then $A = B$. #### 4. Number of Subsets - Number of subsets of any set A = $2^{n(A)}$. - Number of proper subsets = $2^{n(A)} - 1$. - Number of non-empty subsets = $2^{n(A)} - 1$. - **Example:** For set $A = \{1, 2, 3, 4, 5\}$, $n(A) = 5$. - Number of subsets = $2^5 = 32$. - Number of proper subsets = $2^5 - 1 = 31$. - Number of non-empty subsets = $2^5 - 1 = 31$. ### Power Set - The **Power Set** of a set A, denoted by $P(A)$, is the collection of all subsets of A. - The number of elements in the power set of A is $n(P(A)) = 2^{n(A)}$. - **Example:** If $A = \{1\}$, then $n(A) = 1$. - Subsets of A are $\emptyset$ and $\{1\}$. - $P(A) = \{\emptyset, \{1\}\}$. - $n(P(A)) = 2^1 = 2$. - **Example:** For the empty set $\emptyset$: - $P(\emptyset) = \{\emptyset\}$. - $n(P(\emptyset)) = 2^0 = 1$. - $P(P(\emptyset)) = \{\emptyset, \{\emptyset\}\}$. - $n(P(P(\emptyset))) = 2^1 = 2$. ### Universal Set - A **Universal Set**, denoted by $U$, is a set that contains all elements relevant to a particular discussion. - All other sets in that discussion are subsets of the universal set. ### Venn Diagrams - Geometrical representation of sets. - The Universal Set $U$ is represented by a rectangle. - Any set within $U$ is represented by a circle. ### Operations on Sets #### 1. Union ($\cup$) - $A \cup B$: The set of all elements that are in A, or in B, or in both. - $A \cup B = \{x \mid x \in A \text{ or } x \in B\}$. #### 2. Intersection ($\cap$) - $A \cap B$: The set of all elements that are common to both A and B. - $A \cap B = \{x \mid x \in A \text{ and } x \in B\}$. #### 3. Difference ($-$) - $A - B$: The set of all elements that are in A but not in B. - $A - B = \{x \mid x \in A \text{ and } x \notin B\} = A - (A \cap B)$. - $B - A$: The set of all elements that are in B but not in A. - $B - A = \{x \mid x \in B \text{ and } x \notin A\} = B - (A \cap B)$. #### 4. Symmetric Difference ($\Delta$) - $A \Delta B$: The set of elements that are in A or B but not in their intersection. - $A \Delta B = (A - B) \cup (B - A) = (A \cup B) - (A \cap B)$. #### 5. Complement ($'$) - $A'$ (or $A^c$ or $\bar{A}$): The set of all elements in the universal set $U$ that are not in A. - $A' = \{x \mid x \in U \text{ and } x \notin A\} = U - A$. - **Example:** If A and B are two sets, then $(A - B) \cup (B - A) \cup (A \cap B) = A \cup B$. ### Laws of Set Algebra #### 1. De Morgan's Laws - $(A \cup B)' = A' \cap B'$ - $(A \cap B)' = A' \cup B'$ #### 2. Idempotent Laws - $A \cup A = A$ - $A \cap A = A$ #### 3. Identity Laws - $A \cup \emptyset = A$ - $A \cap U = A$ - $A \cap \emptyset = \emptyset$ #### 4. Commutative Laws - $A \cup B = B \cup A$ - $A \cap B = B \cap A$ - $A \Delta B = B \Delta A$ #### 5. Associative Laws - $(A \cup B) \cup C = A \cup (B \cup C)$ - $(A \cap B) \cap C = A \cap (B \cap C)$ #### 6. Distributive Laws - $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$ - $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$ ### Important Formulas for Cardinality #### 1. For Two Sets - $n(A \cup B) = n(A) + n(B) - n(A \cap B)$ - If A and B are disjoint sets ($A \cap B = \emptyset$), then $n(A \cup B) = n(A) + n(B)$. - $n(A - B) = n(A) - n(A \cap B)$ - $n(A \Delta B) = n(A \cup B) - n(A \cap B)$ #### 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)$ #### 3. Example Problem **Problem:** In a survey of 600 students, 150 were writing JEE, and 225 were writing NEET. 100 were taking both JEE and NEET. Find how many students are taking neither JEE nor NEET? **Solution:** - Total students, $n(U) = 600$. - Students writing JEE, $n(J) = 150$. - Students writing NEET, $n(N) = 225$. - Students writing both JEE and NEET, $n(J \cap N) = 100$. 1. **Students taking at least one exam (JEE or NEET):** $n(J \cup N) = n(J) + n(N) - n(J \cap N)$ $n(J \cup N) = 150 + 225 - 100 = 375 - 100 = 275$. 2. **Students taking neither JEE nor NEET:** This is the complement of $J \cup N$ with respect to $U$. $n((J \cup N)') = n(U) - n(J \cup N)$ $n((J \cup N)') = 600 - 275 = 325$. **Answer:** 325 students are taking neither JEE nor NEET.