Set Theory Notes

Finite Set vs. Infinite Set

• Finite Set:

  • A set where the number of elements can be counted.

  • Example: $A = {2, 4, 6, 8}$

    • This set has four elements.

• Infinite Set:

  • A set where the number of elements cannot be counted; it goes on indefinitely.

  • Example: The set of all natural numbers.

    • $A = {1, 2, 3, 4, … }$ (continues to infinity)

Cardinal Number

• Definition: The number of elements in a finite set.

• Example:

  • Set $A = {1, 3, 5, 7, 9}$

  • The cardinal number of A, denoted as $|A|$, is 5 because there are five elements.

Types of Sets

Empty Set (Null Set)

• Definition: A set that contains no elements.

• Symbol: $\emptyset$ or ${}$

• Example 1:

  • $A = {x \mid x \text{ is an odd number divisible by 2} }$

  • There is no odd number divisible by 2, so A is empty.

• Example 2:

  • The set of natural numbers less than 1. Natural numbers start from 1, so no natural number is less than 1.

Singleton Set

• Definition: A set that contains only one element.

• Example:

  • $A = {x \mid x \text{ is a prime number which is also even} }$

  • The only even prime number is 2, so $A = {2}$.

Subset of a Set

• Definition: If A and B are two sets, B is a subset of A if every element of B is also an element of A.

• Symbol: $B \subseteq A$ (B is a subset of A)

• Example:

  • $A = {1, 3, 5, 7, 9, 11}$

  • $B = {3, 7, 11}$

  • Every element of B (3, 7, 11) is also in A, so B is a subset of A.

Possible Subsets of a Set

• Given a set, we can list all its possible subsets.

• Example: If $A = {1, 2, 3}$, the possible subsets are:

  • ${1}$, ${2}$, ${3}$

  • ${1, 2}$, ${1, 3}$, ${2, 3}$

  • ${1, 2, 3}$

  • $\emptyset$ (the empty set)

Power Set

• Definition: The set of all possible subsets of a given set.

• If $A = {1, 2, 3}$, then the power set of A is:

  • ${{1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}, \emptyset}$

Number of Subsets (Cardinality of Power Set)

• If a set A has $p$ elements (i.e., cardinal number of A is $p$), then the number of subsets of A is $2^p$.

• Example: If $A = {1, 2, 3}$, then $p = 3$, and the number of subsets is $2^3 = 8$.

Universal Set

• Definition: A set that contains all elements under consideration. All given sets are subsets of the universal set.

• Symbol: Usually represented by $U$.

Representation of Sets

Roster Form

• Listing all the elements of a set within curly brackets.

• Example: ${1, 3, 5, 7}$, ${2, 4, 6, 8}$

Set Builder Form

• Defining a set by describing a property that its elements must satisfy.

• Example: $A = {x \mid x \text{ is an even number less than 9} }$

  • This describes the set of even numbers less than 9, which is ${2, 4, 6, 8}$

Venn Diagrams

• Visual representation of sets using diagrams.

• Usually, the universal set is represented by a rectangle, and sets are represented by circles within the rectangle.

• Overlapping regions between circles represent common elements between sets.

Complement of a Set

• Definition: The complement of a set A (denoted as $A'$ or $A^c$) is the set of all elements in the universal set that are not in A.

• Example:

  • Universal set $U = {1, 2, 3, 4, 5, 6}$

  • Set $A = {2, 4}$

  • The complement of A is $A' = {1, 3, 5, 6}$

Operations on Sets

Union

• Definition: The union of two sets A and B (denoted as $A \cup B$) is the set of all elements that are in A, or in B, or in both.

• Example:

  • $A = {1, 3, 5, 7}$

  • $B = {5, 8, 10}$

  • $A \cup B = {1, 3, 5, 7, 8, 10}$

• Venn Diagram: The union is represented by shading all regions of both circles A and B.

Intersection

• Definition: The intersection of two sets A and B (denoted as $A \cap B$) is the set of all elements that are common to both A and B.

• Example:

  • $A = {1, 3, 5, 7}$

  • $B = {3, 7, 9, 13}$

  • $A \cap B = {3, 7}$

• Venn Diagram: The intersection is represented by shading the overlapping region between circles A and B.

Disjoint Sets

• Definition: Sets that have no elements in common.

• For disjoint sets A and B, $A \cap B = \emptyset$.

• Venn Diagram: Represented by two non-overlapping circles.

Difference of Sets

• Definition: The difference of two sets A and B (denoted as $A - B$) is the set of all elements that are in A but not in B.

• Example:

  • $A = {1, 3, 5, 7, 9}$

  • $B = {3, 7, 8, 10}$

  • $A - B = {1, 5, 9}$

• Venn Diagram: Represented by shading the region of circle A that does not overlap with circle B.

Laws of Set Operations

Identity Laws

• $A \cup \emptyset = A$

• $A \cap U = A$

Idempotent Laws

• $A \cup A = A$

• $A \cap A = A$

Associative Laws

• $(A \cup B) \cup C = A \cup (B \cup C)$

• $(A \cap B) \cap C = A \cap (B \cap C)$

Commutative Laws

• $A \cup B = B \cup A$

• $A \cap B = B \cap A$

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)$

De Morgan's Laws

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

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

Application of Set Theory

• Formula for the number of elements in the union of two sets:

  • $|A \cup B| = |A| + |B| - |A \cap B|$

  • This formula is used to avoid double-counting the elements in the intersection.

Example Problems

Problem 1

• If X and Y are two sets, $|X| = 17$, $|Y| = 23$, and $|X \cup Y| = 38$, find $|X \cap Y|$.

• Using the formula:

  • $38 = 17 + 23 - |X \cap Y|$

  • $|X \cap Y| = 17 + 23 - 38 = 2$

Problem 2

• Given a universal set U with $|U| = 700$, $|A| = 200$, $|B| = 300$, and $|A \cap B| = 100$, find $|A' \cap B'|$.

• Using De Morgan's Law:

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

• $|A \cup B| = |A| + |B| - |A \cap B| = 200 + 300 - 100 = 400$

• $|(A \cup B)'| = |U| - |A \cup B| = 700 - 400 = 300$

Problem 3

• In a school with 727 students, 600 offer mathematics, and 173 offer both mathematics and physics. How many students are enrolled in physics? How many students are enrolled in physics only?

• Given:

  • $|M \cup P| = 727$

  • $|M| = 600$

  • $|M \cap P| = 173$

• Number of students in physics:

  • $|M \cup P| = |M| + |P| - |M \cap P|$

  • $727 = 600 + |P| - 173$

  • $|P| = 727 + 173 - 600 = 300$

• Number of students in physics only:

  • $|P| - |M \cap P| = 300 - 173 = 127$

Problem 4

• Out of 20 members in a family, 12 like tea, 15 like coffee. Assume that each one likes at least one of the two. How many like only tea, not coffee? How many like only coffee, not tea? How many like both coffee and tea?

• Given:

  • $|T \cup C| = 20$

  • $|T| = 12$

  • $|C| = 15$

• Number of people who like both coffee and tea:

  • $|T \cup C| = |T| + |C| - |T \cap C|$

  • $20 = 12 + 15 - |T \cap C|$

  • $|T \cap C| = 12 + 15 - 20 = 7$

• Number of people who like only tea, not coffee:

  • $|T| - |T \cap C| = 12 - 7 = 5$

• Number of people who like only coffee, not tea:

  • $|C| - |T \cap C| = 15 - 7 = 8$

Ordered Pair

• Definition: A pair of elements in a specific order, denoted by small braces $(a, b)$.

• Key Point: The order matters. $(1, 3)$ is not the same as $(3, 1)$.

• Equality of Two Ordered Pairs: Two ordered pairs $(a, b)$ and $(c, d)$ are equal if and only if $a = c$ and $b = d$.

Cartesian Product

• Definition: Given two non-empty sets A and B, the Cartesian product of A and B (denoted as $A \times B$) is the set of all ordered pairs $(a, b)$ where $a$ belongs to A and $b$ belongs to B.

• Formula of Cartesian product: $A \times B = {(a, b) \mid a \in A, b \in B}$

• Example:

  • If $A = {1, 2, 3}$ and $B = {x, y}$, then

    • $A \times B = {(1, x), (2, x), (3, x), (1, y), (2, y), (3, y)}$

• Number of Elements in Cartesian Product:

  • If $|A| = m$ and $|B| = n$, then $|A \times B| = m \times n$

  • Example: If $|A| = 3$ and $|B| = 2$, then $|A \times B| = 3 \times 2 = 6$