MAT110 Sets (Copperbelt University)

Cheatsheet Content

1. Basic Concepts of Sets Definition: A set is a well-defined collection of distinct objects, called elements or members. Notation: Sets are usually denoted by capital letters (e.g., $A, B, C$), and elements by lowercase letters (e.g., $a, b, c$). Membership: $x \in A$: $x$ is an element of set $A$. $x \notin A$: $x$ is not an element of set $A$. Ways to Describe Sets: Roster Method (Listing Method): List all elements separated by commas within curly braces. Example: $A = \{1, 2, 3, 4, 5\}$ Example: $B = \{\text{red, green, blue}\}$ Set-Builder Notation (Rule Method): Describe the properties that elements must satisfy. Format: $A = \{x \mid P(x)\}$ where $P(x)$ is the property $x$ must satisfy. Example: $A = \{x \mid x \text{ is an integer and } 1 \le x \le 5\}$ Example: $B = \{x^2 \mid x \in \mathbb{N} \text{ and } x Special Sets: Empty Set (Null Set): A set containing no elements. Denoted by $\emptyset$ or $\{\}$. Example: $\{x \mid x \in \mathbb{N} \text{ and } x Universal Set ($U$): The set of all elements under consideration in a particular context. Finite Set: A set with a countable number of elements. Its cardinality is a non-negative integer. Infinite Set: A set with an uncountable number of elements. Example: $\mathbb{N} = \{1, 2, 3, ...\}$ (Natural Numbers) Example: $\mathbb{Z} = \{..., -2, -1, 0, 1, 2, ...\}$ (Integers) Example: $\mathbb{Q}$ (Rational Numbers), $\mathbb{R}$ (Real Numbers) 2. Relationships Between Sets Cardinality ($|A|$ or $n(A)$): The number of distinct elements in a finite set $A$. Example: If $A = \{a, b, c\}$, then $|A|=3$. Example: If $B = \{1, \{2, 3\}\}$, then $|B|=2$. Equality of Sets: $A = B$ if and only if they contain exactly the same elements. $\{1, 2, 3\} = \{3, 1, 2\}$ (order doesn't matter) $\{1, 1, 2\} = \{1, 2\}$ (repeated elements are counted once) Subset ($A \subseteq B$): $A$ is a subset of $B$ if every element of $A$ is also an element of $B$. $\emptyset$ is a subset of every set. Every set is a subset of itself ($A \subseteq A$). Proper Subset ($A \subset B$): $A$ is a proper subset of $B$ if $A \subseteq B$ and $A \ne B$. (i.e., $B$ contains at least one element not in $A$). Power Set ($\mathcal{P}(A)$ or $2^A$): The set of all subsets of $A$. If $|A|=n$, then $|\mathcal{P}(A)| = 2^n$. Example: If $A = \{1, 2\}$, then $\mathcal{P}(A) = \{\emptyset, \{1\}, \{2\}, \{1, 2\}\}$. 3. Operations on Sets (All operations assume sets are within a universal set $U$) Union ($A \cup B$): The set of all elements that are in $A$ or in $B$ (or both). $A \cup B = \{x \mid x \in A \text{ or } x \in B\}$ Example: If $A = \{1, 2, 3\}$, $B = \{3, 4, 5\}$, then $A \cup B = \{1, 2, 3, 4, 5\}$. Intersection ($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\}$ Example: If $A = \{1, 2, 3\}$, $B = \{3, 4, 5\}$, then $A \cap B = \{3\}$. Disjoint Sets: Two sets $A$ and $B$ are disjoint if $A \cap B = \emptyset$. 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\}$ Example: If $U = \{1, 2, 3, 4, 5\}$, $A = \{1, 2\}$, then $A' = \{3, 4, 5\}$. Set Difference ($A - B$ or $A \setminus 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\}$ Note: $A - B = A \cap B'$ Example: If $A = \{1, 2, 3\}$, $B = \{3, 4, 5\}$, then $A - B = \{1, 2\}$. Symmetric Difference ($A \Delta B$ or $A \oplus 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 \Delta B = (A \cup B) - (A \cap B)$ Example: If $A = \{1, 2, 3\}$, $B = \{3, 4, 5\}$, then $A \Delta B = \{1, 2, 4, 5\}$. 4. Properties of Set Operations Let $A, B, C$ be sets and $U$ be the universal set. Commutative Laws: $A \cup B = B \cup A$ $A \cap B = B \cap A$ Associative Laws: $(A \cup B) \cup C = A \cup (B \cup C)$ $(A \cap B) \cap C = A \cap (B \cap C)$ 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)$ Identity Laws: $A \cup \emptyset = A$ $A \cap U = A$ Complement Laws: $A \cup A' = U$ $A \cap A' = \emptyset$ $(A')' = A$ $U' = \emptyset$ $\emptyset' = U$ Idempotent Laws: $A \cup A = A$ $A \cap A = A$ De Morgan's Laws: $(A \cup B)' = A' \cap B'$ $(A \cap B)' = A' \cup B'$ Absorption Laws: $A \cup (A \cap B) = A$ $A \cap (A \cup B) = A$ 5. Cardinality of Sets Principle of Inclusion-Exclusion for Two Sets: $|A \cup B| = |A| + |B| - |A \cap B|$ Principle of Inclusion-Exclusion for Three Sets: $|A \cup B \cup C| = |A| + |B| + |C| - (|A \cap B| + |A \cap C| + |B \cap C|) + |A \cap B \cap C|$ Cardinality of Complement: $|A'| = |U| - |A|$ Cardinality of Set Difference: $|A - B| = |A| - |A \cap B|$ 6. Cartesian Products Ordered Pair: An ordered pair $(a, b)$ is a pair of elements where the order matters. $(a, b) = (c, d)$ if and only if $a=c$ and $b=d$. Cartesian Product ($A \times B$): The set of all possible ordered pairs where the first element is from $A$ and the second is from $B$. $A \times B = \{(a, b) \mid a \in A \text{ and } b \in B\}$ Example: If $A = \{1, 2\}$, $B = \{a, b\}$, then $A \times B = \{(1, a), (1, b), (2, a), (2, b)\}$. Cardinality of Cartesian Product: If $|A|=m$ and $|B|=n$, then $|A \times B| = mn$. Note: $A \times B \ne B \times A$ unless $A=B$ or one is the empty set. Cartesian Product of Multiple Sets: $A_1 \times A_2 \times \dots \times A_n = \{(a_1, a_2, \dots, a_n) \mid a_i \in A_i \text{ for } i=1, \dots, n\}$.