Set Theory Notes - MTH331 Lecture Notes 01
Symbol Glossary
\in: Is an element of
\notin: Is not an element of
|A|: Cardinality (number of elements) of set A
\emptyset: The empty set
\subseteq: Is a subset of
\subset: Is a proper subset of
P(A): Power set of A
U: Universal set
\cap: Set intersection
\cup: Set union
A^c (or \overline{A}): Complement of set A
A \setminus B (or A - B): Set difference (elements in A but not in B)
A \oplus B: Symmetric difference (exclusive OR)
A \times B: Cartesian product of sets A and B
\mathbb{Z}: Integers
\mathbb{N}: Natural numbers
\mathbb{R}: Real numbers
\mathbb{R}^+: Positive real numbers
\mathbb{Q}: Rational numbers
\land: Logical AND
\lor: Logical OR
\iff: If and only if
1. Set Terminology
Intuitive Explanation: A set is a well-defined collection of distinct objects, called elements. Thinking of it as a "bag" of unique items helps.
Example sets and notation:
A = {Dartmouth, New Bedford, Fall River, Westport}
B = {Apple, Orange, Banana}
C = {Red, Blue, Green, Black, White}
A, B, C are sets; objects inside are elements.
Membership Notation:
If 'a' is an element of set A, then we write a \in A. For example, Apple \in B.
If 'b' is not an element of set A, then we write b \notin A. For example, Red \notin B.
Cardinality:
|A| denotes the cardinality (number of elements) of a finite set A. For example, |A| = 4 for set A above.
The empty set, denoted by \emptyset or {} , is a set containing no elements. Its cardinality is |\emptyset| = 0.
Common Sets (Examples):
\mathbb{Z} = {\ldots, -2, -1, 0, 1, 2, \ldots} (integers; 'Zahl' is German for number)
\mathbb{N} = {1, 2, 3, \ldots} (natural numbers, sometimes includes 0 depending on convention)
\mathbb{R}: Real numbers (all numbers on the number line, including decimals and irrationals)
\mathbb{R}^+: Positive real numbers (all real numbers greater than 0)
\mathbb{Q}: Rational numbers (numbers that can be expressed as a fraction p/q where p,q \in \mathbb{Z} and q \neq 0)
Predicate-Defined Sets:
Sets can be defined by a rule or condition: A = { x \in S : P(x) } or A = { x \in S \mid P(x) }, meaning "the set of all elements 'x' in set 'S' such that condition P(x) is true."
Example 1: A = { x \in \mathbb{R} : x^2 - x - 6 = 0 }
Solution: Factor the quadratic: (x-3)(x+2) = 0. So, the values of x are 3 and -2. Thus, A = {-2, 3}.
Example 2: A = { n \in \mathbb{Z} : n^2 \le 9 }
Solution: We need integers whose square is less than or equal to 9. These are -3, -2, -1, 0, 1, 2, 3. Thus, A = {-3, -2, -1, 0, 1, 2, 3}.
Subsets and Equality:
Definition: A set A is a subset of B if every element of A is also an element of B, denoted A \subseteq B.
Examples:
{a,b,d} \subseteq {a,b,c,d,e} because all elements {a, b, d} are found in the larger set.
\mathbb{N} \subseteq \mathbb{Z} because every natural number is also an integer.
Properties:
Reflexivity: For any set A, A \subseteq A holds (every set is a subset of itself).
The empty set is a subset of any set: \emptyset \subseteq A for all sets A.
Set Equality: A = B if and only if A \subseteq B and B \subseteq A. This means they contain exactly the same elements.
Proper Subset: A is a proper subset of B if A \subseteq B and A \neq B, denoted A \subset B. This means B contains at least one element not in A.
2. Subsets and Power Set
Definition: The power set of a set A is the set of all possible subsets of A. It is denoted by P(A), where P(A) = { B : B \subseteq A }.
Example 1: If A = {a, b}, then the subsets are {a}, {b}, {a,b}, and \emptyset.
So, P(A) = {{a}, {b}, {a,b}, \emptyset}.
Example 2: If A = \emptyset (the empty set), its only subset is itself.
So, P(\emptyset) = {\emptyset}.
Cardinality of a Power Set:
If a finite set A has n elements (i.e., |A| = n), then the size of its power set is P(A) = |P(A)| = 2^n. Each element can either be in a subset or not, giving 2 choices for each of the n elements.
Example 1: If A = {a,b}, then |A| = 2. So, |P(A)| = 2^2 = 4. (We found 4 subsets above).
Example 2: If A = {1,2,3}, then |A| = 3. The number of subsets (the size of its power set) is |P(A)| = 2^3 = 8. These subsets are: \emptyset, {1}, {2}, {3}, {1,2}, {1,3}, {2,3} , and {1,2,3}.
3. Countable and Uncountable Sets
Countable Set: A set is countable if its elements can be put into a one-to-one correspondence with the natural numbers, meaning they can be listed in a (finite or infinite) sequence.
Examples:
Any finite set (e.g., {a,b,c}) is countable.
The set of positive integers {1,2,3,\ldots} (\mathbb{N}) is countable. We can list them: 1st element is 1, 2nd is 2, etc.
The set of all integers (\mathbb{Z}) is countable. We can list them: 0, 1, -1, 2, -2, 3, -3, \ldots
Uncountable Set: An infinite set is uncountable if its elements cannot be listed in a sequence, no matter how clever the listing method.
Example: The interval [0,1] (all real numbers between 0 and 1, inclusive) is uncountable. This can be proven by Cantor's diagonalization argument, showing that any attempt to list them will always omit some numbers in the interval.
4. Venn Diagrams: Visualizing Sets
Definition: A Venn diagram is a pictorial representation used to show the relationships between sets. It helps to visualize overlaps and differences.
The universal set (U), which contains all possible elements under consideration for a particular problem, is represented by a rectangle.
Individual sets of interest (e.g., A, B, C) are represented by closed circles (or disks) within the rectangle.
The region inside a circle indicates membership in that set, while the region outside indicates non-membership.
Application: Venn diagrams are particularly useful for understanding set operations (union, intersection, complement) and are fundamental when we transition to probability.
5. Set Operations and their Probability Connection
5.1 Set Intersection
Definition: The intersection of two sets A and B, denoted A \cap B, contains all elements that are common to both A and B.
Formal Definition: x \in (A \cap B) \iff (x \in A) \land (x \in B).
Example: If A = {1, 2, 3, 5, 6} and B = {2, 4, 6, 8}, then A \cap B = {2, 6}.
Venn Diagram: The intersection is the overlapping area of the circles representing A and B.
Connection to Probability: If A and B are events in a probability experiment, A \cap B represents the event that both A and B occur. In probability notation, this is often written as P(A \text{ and } B) or P(A \cap B).
Example: If A is the event of rolling an even number on a die ({2, 4, 6}) and B is the event of rolling a number less than 4 ({1, 2, 3}), then A \cap B = {2}. This means the event "rolling an even number AND a number less than 4" is rolling a 2.
5.2 Set Union
Definition: The union of two sets A and B, denoted A \cup B, contains all elements that are in A, or in B, or in both.
Formal Definition: x \in (A \cup B) \iff (x \in A) \lor (x \in B).
Example: If A = {1, 2, 3, 5, 6} and B = {2, 4, 6, 8}, then A \cup B = {1, 2, 3, 4, 5, 6, 8}.
Venn Diagram: The union is the entire area covered by both circles A and B.
Connection to Probability: If A and B are events, A \cup B represents the event that A occurs OR B occurs (or both). In probability notation, this is often written as P(A \text{ or } B) or P(A \cup B).
Example: Using the die roll example (A: even numbers, B: numbers less than 4), A \cup B = {1, 2, 3, 4, 6}. This means the event "rolling an even number OR a number less than 4" includes 1, 2, 3, 4, and 6.
5.3 Complement of a Set
Definition: The complement of a set A, denoted A^c (or \overline{A}), consists of all elements in the universal set U that are not in A. It can be formally written as A^c = U \setminus A.
Example: If U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} and A = {1, 3, 5, 7, 9} (odd numbers), then A^c = {2, 4, 6, 8, 10} (even numbers).
Venn Diagram: The complement of A is the area within the universal set rectangle but outside the circle for A.
Connection to Probability: If A is an event, A^c represents the event that A does not occur. In probability, P(A^c) = 1 - P(A).
Example: If A is the event of drawing a red card from a deck, then A^c is the event of drawing a non-red card (i.e., a black card). If P(A) = 26/52 = 1/2, then P(A^c) = 1 - 1/2 = 1/2.
5.4 Set Difference
Definition: The set difference of A and B, denoted A \setminus B or A - B, contains all elements that are in A but not in B. This can also be expressed as A \cap B^c.
Example: If A = {1, 2, 3, 4, 9} and B = {3, 5, 7, 9}, then A - B = {1, 2, 4}.
Venn Diagram: The region for A - B is the part of circle A that does not overlap with circle B.
Connection to Probability: If A and B are events, A \setminus B represents the event that A occurs but B does not occur.
Example: If A is "passing a math exam" and B is "passing a science exam", then A \setminus B is "passing the math exam but failing the science exam."
5.5 Symmetric Difference
Definition: The symmetric difference of sets A and B, denoted A \oplus B, consists of elements that are in A or in B, but not in both. It's essentially the elements unique to A plus the elements unique to B. It can be written as (A \setminus B) \cup (B \setminus A).
Example: If A = {1, 2, 3, 4, 9} and B = {3, 5, 7, 9}, then:
A \setminus B = {1, 2, 4}
B \setminus A = {5, 7}
A \oplus B = {1, 2, 4, 5, 7}.
Venn Diagram: The symmetric difference is the combined area of both circles, excluding their overlap.
Connection to Probability: This corresponds to the event where exactly one of the two events A or B occurs.
6. Cartesian Product
Definition: The Cartesian product of two sets A and B is the set of all possible ordered pairs (a,b) where a is an element from A and b is an element from B.
\text{General Form:} \ A \times B = { (a,b) : a \in A \ \text{and} \ b \in B }
Examples:
Example 1: If A = {0,1} and B = {\emptyset, {1}, 2}, then:
A \times B = {(0, \emptyset), (0, {1}), (0, 2), (1, \emptyset), (1, {1}), (1, 2)}
Example 2 (Dice Rolls): If A = {1,2,3,4,5,6} (outcomes of die 1) and B = {1,2,3,4,5,6} (outcomes of die 2), then A \times B represents all possible ordered pairs when rolling two dice. This is the sample space for rolling two dice.
For instance, (1,1) (die 1 is 1, die 2 is 1), (1,2), …, (6,6).
The cardinality is |A \times B| = |A| \cdot |B| = 6 \times 6 = 36. There are 36 possible outcomes.
Example 3 (Clothing Combinations): If A = {\text{red, blue}} (shirt colors) and B = {\text{flag, curtain}} (pant styles), then:
A \times B = {(\text{red, flag}), (\text{red, curtain}), (\text{blue, flag}), (\text{blue, curtain})}
This gives all possible shirt-pant combinations.
Connection to Probability (Sample Spaces): The Cartesian product is often used to define the sample space (S or U) of a multi-stage experiment, which is the set of all possible outcomes. Events (subsets of the sample space) are then used with set operations to calculate probabilities.
7. Set Partition
Definition: A partition of a nonempty set A is a collection of nonempty subsets of A (let's call them S1, S2, \ldots, S_k) such that:
Every element of A belongs to exactly one of these subsets (meaning the subsets are mutually exclusive and their union covers all of A).
All subsets S_i are nonempty.
The subsets are pairwise disjoint: Si \cap Sj = \emptyset for all i \neq j.
The union of all subsets equals the original set: \bigcup{i=1}^{k} Si = A.
Example 1: Let A = {1,2,3,\ldots,10}.
A possible partition is: S1 = {1,7,8}, S2 = {2,5,9}, S3 = {4}, S4 = {3,6,10}.
Notice how each number from 1 to 10 appears in exactly one subset, and all subsets are non-empty.
Example 2 (Probability Context): Consider the universal set U = {\text{all students in a class}}. A partition of this set could be based on grade level: S1 = {\text{Freshmen}}, S2 = {\text{Sophomores}}, S3 = {\text{Juniors}}, S4 = {\text{Seniors}}. Each student belongs to exactly one grade level, and each level contains students.
8. Elementary Laws in Set Theory (Identity Laws)
Let A, B, C be sets, and U be the universal set.
8.1 Commutative Laws:
A \cap B = B \cap A (Order of intersection doesn't matter)
A \cup B = B \cup A (Order of union doesn't matter)
8.2 Associative Laws:
(A \cap B) \cap C = A \cap (B \cap C) (Grouping for intersection doesn't matter)
(A \cup B) \cup C = A \cup (B \cup C) (Grouping for union doesn't matter)
8.3 Distributive Laws:
A \cap (B \cup C) = (A \cap B) \cup (A \cap C)
Intuitive Explanation: Intersection distributes over union, similar to how multiplication distributes over addition (a(b+c) = ab + ac).
A \cup (B \cap C) = (A \cup B) \cap (A \cup C)
Intuitive Explanation: Union distributes over intersection. This is less intuitive than the first distributive law but holds true for sets.
9. De Morgan’s Laws
De Morgan's Laws describe how set complements interact with unions and intersections.
9.1 For Two Sets A, B:
(A \cup B)^c = A^c \cap B^c
Intuitive Explanation: The elements not in A OR B are the same as elements not in A AND not in B.
(A \cap B)^c = A^c \cup B^c
Intuitive Explanation: The elements not in A AND B are the same as elements not in A OR not in B.
9.2 For Three Sets A, B, C:
(A \cup B \cup C)^c = A^c \cap B^c \cap C^c
(A \cap B \cap C)^c = A^c \cup B^c \cup C^c
9.3 General De Morgan’s Laws (for infinite families of sets)
Let {S_n} be a (finite or infinite) family of sets. Then:
(\bigcup{n} Sn)^c = \bigcap{n} Sn^c
(\bigcap{n} Sn)^c = \bigcup{n} Sn^c
Sketch of Proof (for law 5):
Part 1 (\subseteq): If x \in (\bigcup{n} Sn)^c, it means x \notin \bigcup{n} Sn. This implies that for every n, x \notin Sn. Therefore, x \in Sn^c for all n (i.e., for every set in the family). If x is in every Sn^c, then x \in \bigcap{n} Sn^c. Thus, (\bigcup{n} Sn)^c \subseteq \bigcap{n} S_n^c.
Part 2 (\supseteq): The reverse inclusion follows similarly. If x \in \bigcap{n} Sn^c, then x \in Sn^c for all n. This means x \notin Sn for all n. Therefore, x \notin \bigcup{n} Sn, which implies x \in (\bigcup{n} Sn)^c. Thus, (\bigcup{n} Sn)^c \supseteq \bigcap{n} Sn^c.
Since both inclusions hold, the sets are equal.
These general laws highlight that De Morgan's laws apply universally, not just for a finite number of sets.