Set Theory: Sets and Subsets

Section 2.1: Sets and Subsets

What is a Set?

• A set is a well-defined collection of objects.

  • Well-defined: There must be an objective rule determining if an object belongs to the set, not a matter of opinion.

• The objects in a set are called elements.

  • Elements can be numbers, letters, people, animals, cities, colors, etc.

• Notation: Sets are typically denoted by capital letters (e.g., A, B, C).

  • Sometimes, the letter helps remember what the set represents (e.g., M for math students).

Three Ways to Represent a Set

1. Roster Method (Listing)

• Lists all elements that belong to the set.

• Notation: Uses curly brackets to enclose the elements, with $comma$s separating them.

  • Example: A = {1, 2} is read as "set A contains the elements one and two."

• Element Notation: The symbol $\in$ means "is an element of" or "belongs to."

  • Example: $1 \in A$ means "1 is an element of set A."

• Rules for Roster Method:

  • An element may not repeat in a set (each element must be unique).

    • This rule applies within the context of set theory in this chapter; other types of sets (like data sets) may allow repetition.

  • The order of elements does not matter.

    • The set {Wisconsin, Wyoming, West Virginia, Washington} is the same as {Washington, Wyoming, Wisconsin, West Virginia}.

• Example: Let W be the set of US states whose name begins with the letter W.

  • W = {Wisconsin, Wyoming, West Virginia, Washington}.

• Applicability: Useful for small sets; impractical for very large sets.

2. Set-Builder Method (Describing)

• Provides a well-defined rule describing which elements belong to the set.

• Elements must satisfy all conditions of the rule to be included.

• Notation: ${x | \text{rule about x}}$.

  • The vertical bar $|$ is read as "such that."

  • Example: $W = {x | x \text{ is a state in the US whose name begins with the letter W}}$.

  • Read as: "Set W is the set of all elements $x$ such that $x$ is a state in the US whose name begins with the letter W."

• Applicability: Can describe small, large, or infinite sets more efficiently than the roster method.

3. Cardinality (Quantifying)

• Refers to how many elements belong to a set.

• Notation: $n(A)$ represents the cardinal number (or cardinality) of set A.

  • Example: If set F (finite class) has $80$ students, then $n(F) = 80$.

• Applicability: Quantifies finite sets. Infinite sets do not have a cardinal number.

  • $n(\text{Alphabet}) = 26$.

  • $n(\text{US States}) = 50$.

Identifying Sets vs. Non-Sets

• Example 1: A = {2, 3, 4, 5, 1}

  • This is a set. Elements are unique, and order doesn't matter.

• Example 2: B = {2, 3, 4, 5, 1, 2}

  • This is not a set because the element $2$ repeats, violating a roster method rule.

• Example 3: C = {x | x is a prime number}

  • This is a set (an infinite set). "Prime number" is an objective rule.

    • A prime number is any integer greater than $1$ that is only divisible by itself and $1$.

    • Example: $2, 3, 5, 7, 11, ...$ ($4$ is not prime because it's divisible by $2$).

• Example 4: D = {x | x is a small number}

  • This is not a set because "small number" is subjective and not well-defined.

• Example 5: E = {x | x is an integer greater than 0 and less than 5}

  • This is a set. It can be written in roster form as {1, 2, 3, 4}.

Converting Between Set Representations (Examples)

• Problem: Use the roster method to list the elements of A = {x | x is an odd positive integer less than 20}.

  • Conditions: odd, positive, integer, less than $20$.

  • Solution: A = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19}.

• Problem: Use the roster method to list the elements of A = {x | x is a prime number and divisible by 2}.

  • Solution: A = {2}. This is a singleton set (a set with exactly one element), as $2$ is the only prime number divisible by $2$. Other prime numbers are odd.

• Problem: Write set B = {x | x = 2y + 4 \text{ and } y \in I \text{ and } 0 < y < 5} in roster form, where I is the set of integers.

  • Step 1: Identify possible values for $y$. $y$ must be an integer strictly between $0$ and $5$.

    • Possible $y$ values: {1, 2, 3, 4}.

  • Step 2: Substitute each $y$ value into the expression $x = 2y + 4$ to find the $x$ values for set B.

    • If $y = 1$, $x = 2(1) + 4 = 6$.

    • If $y = 2$, $x = 2(2) + 4 = 8$.

    • If $y = 3$, $x = 2(3) + 4 = 10$.

    • If $y = 4$, $x = 2(4) + 4 = 12$.

  • Solution: B = {6, 8, 10, 12}.

Important Set Types

The Empty Set (Null Set)

• Definition: The set containing no elements.

• Notation: $\emptyset$ (an $O$ with a slash through it) or {} (a pair of empty curly brackets).

  • Using {} is often preferred to avoid confusion with the number $0$.

• Cardinality: $n(\emptyset) = 0$.

• Nothing vs. Zero: These are distinct concepts.

  • If an equation's solution is $x = 0$, it means $0$ is a valid solution. This is different from the equation having no solution (an empty set of solutions).

  • A blank license plate has $n(\text{plate}) = 0$ characters. A license plate with the number $0$ on it has $n(\text{plate}) = 1$ character.

  • Sets with different cardinalities cannot be equal.

The Universal Set (U)

• Definition: The set that contains everything relevant to a particular problem or discussion.

• It establishes the scope of elements that exist for the purposes of the problem.

• Example: For the set W (US states starting with W), the universal set U was all $50$ US states, not states from other countries like India.

Subsets

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

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

  • The bar under the $\subseteq$ symbol indicates that A and B can be equal.

• Examples:

  • Apples are a subset of fruit.

  • W (states starting with W) is a subset of the universal set of US states.

  • {Wisconsin, Wyoming} is a subset of W.

  • The empty set $\emptyset$ is always a subset of any set.

    • This is true because we always have the option of choosing none of the elements from a set.

• Symbols for Subset Relations: ($\subseteq$ for subset, $\neq$ for not equal, $\not\subseteq$ for not a subset).

  • {1} \subseteq {1, 2} (True)

  • {3, 4, 5} \not\subseteq {3, 5} (False, because $4$ is not in the right set)

  • {7, 9} \subseteq {9, 7} (True, they are also equal because order doesn't matter).

  • $\emptyset \subseteq {0}$ (True. They are not equal because $n(\emptyset) = 0$ and $n({0}) = 1$).

Number of Subsets

• The following two sets are always subsets of any given set:

  1. The empty set ($\emptyset$)

  2. The set itself

• Pattern: When you add an element to a set, the number of possible subsets doubles.

  • Set with $1$ element (e.g., {B}): $2$ subsets ($\emptyset$, {B}).

  • Set with $2$ elements (e.g., {B, C}): $4$ subsets ($\emptyset$, {B}, {C}, {B, C}).

  • Set with $3$ elements (e.g., {B, C, D}): $8$ subsets ($\emptyset$, {B}, {C}, {D}, {B, C}, {B, D}, {C, D}, {B, C, D}).

• Formula: If a set has $n$ elements, there are $2^n$ possible subsets.

  • Example: The alphabet has $26$ letters, so it has $2^{26} = 67,108,864$ possible subsets.

• Applications of the Formula:

  • Problem: Set S has cardinality $5$ ($n(S) = 5$). How many possible subsets can be constructed from S?

    • Solution: $2^5 = 32$ subsets.

  • Problem: How many possible subsets can be constructed from set S that contain at least one element?

    • This means all subsets except the empty set.

    • Solution: $2^n - 1 = 2^5 - 1 = 32 - 1 = 31$ subsets.

  • Problem: How many possible subsets can be constructed from set S that contain at most one element?

    • This means subsets with one element (singleton sets) or zero elements (the empty set).

    • Solution: Number of singleton sets ($n$) + Number of empty sets ($1$) = $n + 1 = 5 + 1 = 6$ subsets.

Complement of a Set

• Definition: Given a universal set U and a set A that is a subset of U, the complement of A (expressed as A') is the set of elements in U that are not in set A.

• Notation: A' (read as "A prime" or "A complement").

• Requirement: The universal set U must be given to find the complement.

• Example: If $U = \{\text{Bart, Brett, Aaron, Sterling}\}$ and $A = \{\text{Aaron, Bart}\}$,

  • Then $A' = \{\text{Brett, Sterling}\}$.

Review Questions (Section 2.1)

• Given U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13}.

• A = {x | x is a multiple of 6}.

• B = {y | y is even}.

• Answer in roster form:

  • A = {6, 12} (from U)

  • A' = {1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 13} (elements in U not in A)

    • Check: $n(A) + n(A') = n(U)$ ($2 + 11 = 13$).

  • B = {2, 4, 6, 8, 10, 12} (from U)

  • B' = {1, 3, 5, 7, 9, 11, 13} (elements in U not in B - all odd numbers)

• True/False Subset Questions:

  • Is A \subseteq B?

    • All elements of A ($6, 12$) are in B ($\{2, 4, 6, 8, 10, 12\}$).

    • True.

  • Is B \subseteq A?

    • Not all elements of B are in A (e.g., $2 \in B$ but $2 \not\in A$).

    • False.

  • Is A' \subseteq B'?

    • Not all elements of A' are in B' (e.g., $2 \in A'$ but $2 \not\in B'$).

    • False.

  • Is B' \subseteq A'?

    • All elements of B' ($\{1, 3, 5, 7, 9, 11, 13\}$) are in A'. (Both contain the same odd numbers).

    • True.