Math 1070Q - Introduction to Sets

Introduction to Sets - Math 1070Q

Chapter 4: Sets and Probability Overview

• This chapter is divided into two main parts:
  • The language of sets (Sections 4.1-4.3)
  • Probability (Sections 4.4-4.7)

A Silly Example: Misinterpretation of Facts

• Consider two statements from the same fact:
  • "My Math 1070 class is online asynchronous."
  • "I don’t need to be present for my Math 1070 class."
• While both stem from the same underlying fact, the second statement is misleading.
• This illustrates Ronald Coase's quote: "If you torture the data long enough, it will confess," highlighting how data can be manipulated to support a desired conclusion.

Introduction to Sets: A Puzzle

• Scenario: $200$ students at UConn, with preferences for fast food:
  • $142$ like Burger King (BK)
  • $95$ like Chick-fil-A (CFA)
  • $65$ like McDonald's (McD)
  • $70$ like both BK and CFA
  • $50$ like both BK and McD
  • $30$ like both CFA and McD
  • $20$ like all three
• Initial Observation: Summing the individual preferences ($142 + 95 + 65 = 302$) yields a total greater than the $200$ students, which seems absurd.
• Explanation: This apparent absurdity arises because students who like multiple brands are counted multiple times in the individual sums (a redundancy).
• Puzzle Question: How many students only like Burger King but not the other two?
• Solution: The number of students who only like Burger King is calculated as $142 - (70 + 50 - 20) = 42$ students. (This type of problem is typically solved using Venn diagrams, which are covered in Section 4.2).

Sets: Definition and Examples

• Definition: A set is a collection of distinct items. These items are called members or elements of the set.
• A set is fundamentally defined by its elements, which can be either listed explicitly or described by a property.
• Example 1: Colors on the USA flag
  • This set has $3$ elements: Red, White, and Blue.
• Example 2: UConn campuses
  • This includes Storrs, Avery Point, Hartford, Stamford, Waterbury, Law, and Health.
• Example 3: Whole numbers (integers)
  • This set has infinitely many elements: $0, ext{ } \pm 1, ext{ } \pm 2, ext{ } \pm 3, \dots$

Set Notations

• Naming Sets: Capital letters (e.g., $A, B, C$) are used to denote the names of sets.
• Set Roster Notation: Elements are explicitly listed within curly brackets.
  • Example: ${\text{red, white, blue}}$ is the set of colors of the USA flag.
• Set Builder Notation: Elements are described by a variable and a property, using the syntax ${x \text{ } | \text{ } x \text{ is } \langle \text{property} \rangle }$.
  • The vertical bar ($|$) is read as "such that."
  • Example: ${x \text{ } | \text{ } x \text{ is a color on the USA flag}}$ reads as "the set of variables $x$ such that $x$ is a color of the USA flag."
• Assigning Names: The equals sign ($=$) is used to assign a name to a set.
  • Example: $A = {x \text{ } | \text{ } x \text{ is a color on the USA flag}}$ reads as "$A$ is the set of elements $x$ such that $x$ is a color on the USA flag."

Key Properties of Sets

• Sets are defined solely by their elements.
• The order in which elements are listed does not matter.
• Repetition of elements does not matter (each element is considered only once).
• Example: If $A = {x \text{ } | \text{ } x \text{ is a color on the USA flag}}$ and $B = {\text{red, white, blue}}$, then $A$ and $B$ represent the same set. This is denoted as $A = B$, meaning the two sets have the exact same elements.
• Repetition: $B = {\text{red, red, white, blue, blue, blue}}$ is considered the same set as $B = {\text{red, white, blue}}$.

Set Membership Notations

• $x \in A$: Means "element $x$ is in set $A$" or "element $x$ is an element of set $A$".
• $A \ni x$: Means "set $A$ contains element $x$" (equivalent to $x \in A$).
• $x \notin A$: Means "element $x$ is not in set $A$" or "element $x$ is not an element of set $A$".
• $A \not\ni x$: Means "set $A$ does not contain element $x$" (equivalent to $x \notin A$).
• Examples:
  • $\text{blue} \in A$
  • $\text{green} \notin A$
• Important Distinction: Be careful not to confuse an element with a set containing that element.
  • $\text{green}$ is an element.
  • ${\text{green}}$ is a set containing one element, which is $\text{green}$.
  • What is true: $\text{green} \in {\text{green}}$.

Subsets

• Definition 1 (Subset): If all elements of a set $A$ are also in a set $C$, then $A$ is said to be a subset of $C$. This is denoted by $A \subseteq C$ or, equivalently, $C \supseteq A$ (read as "$C$ contains $A$ as a subset").
  • Example: If $C$ is the set of all colors and $A = {\text{red, white, blue}}$, then $A \subseteq C$.
• Definition 2 (Not a Subset): If there is at least one element of set $A$ that is not an element of set $C$, then $A$ is not a subset of $C$. This is denoted by $A \not\subseteq C$.
  • Example: If $D$ is the set of all numbers and $A = {\text{red, white, blue}}$, then $A \not\subseteq D$.
• Crucial Distinction: Do not confuse $A \in C$ with $A \subseteq C$.
  • $A \in C$ means the set $A$ itself is an element of the set $C$. (It is possible for a set to contain other sets as its elements).
  • $A \subseteq C$ means all individual elements of $A$ are also individual elements of $C$.

Proper Subsets

• Definition: If $A$ is a subset of $C$ ($A \subseteq C$) but $C$ is not a subset of $A$ ($C \not\subseteq A$), meaning $C$ contains all elements of $A$ plus at least one additional element not found in $A$, then $A$ is said to be a proper subset of $C$. This is denoted by $A \subsetneq C$
  • Note: Do not confuse $A \subsetneq C$ with $A \not\subseteq C$.
• Self-Subset Property: Every set is a subset of itself ($A \subseteq A$), but no set is a proper subset of itself ($A \not\subsetneq A$).

Two Special Sets

• Empty Set (Null Set):
  • Definition: The set of no elements.
  • Notation: Denoted by $\emptyset$ or ${}$.
  • Property: The empty set is a subset of every set ($\emptyset \subseteq A$ for any set $A$).
• Universal Set:
  • Definition: The set that contains all elements within a specific scope or context.
  • Notation: Denoted by $U$ (often a cursive U).
  • Example: In the context of UConn's people, $U$ would contain all students and staff at UConn.
  • Importance of Scope: The concept of a universal set is always defined within a specific scope. The "set of everything" is not a valid set, as demonstrated by Russell's Paradox, which highlights logical contradictions that arise if one attempts to define a set without a clear scope.

Worked Example: Set $S = {1, {\,1\,}\, 3}$

Let's analyze the properties of set $S$:

1. True or False: $1 \in S$?
   • Answer: True. $1$ is directly listed as an element of $S$.
2. True or False: ${\,1\,} \subseteq S$?
   • Answer: True. Since $1$ is an element of $S$, the set containing only the element $1$ (${\,1\,}$) is a subset of $S$.
3. True or False: ${\,1\,} \in S$?
   • Answer: True. The item ${\,1\,}$ (which is itself a set) is directly listed as one of the three elements of $S$.
4. True or False: ${\,3\,} \in S$?
   • Answer: False. The element $3$ is in $S$, but the set ${\,3\,}$ is not listed as an element within $S$. The true statements regarding $3$ are $3 \in S$ and ${\,3\,} \subseteq S$.
5. How many elements does $S$ have?
   • Answer: Three. The elements are $1$, ${\,1\,}$, and $3$.
6. True or False: $\emptyset \in S$?
   • Answer: False. The empty set $\emptyset$ is not listed as an element within $S$. However, it is always true that $\emptyset \subseteq S$ for any set $S$.
7. List all subsets of $S$.
   • Answer: The subsets are:
     • The empty set: $\emptyset$
     • Single-element subsets: ${\,1\,}$, ${{\,1\,}}$, ${\,3\,}$
     • Two-element subsets: ${\,1, {\,1\,}}$, ${\,1, 3}$, ${{\,1\,}, 3}$
     • The set itself: $S = {\,1, {\,1\,}, 3}$
   • Total: $8$ subsets.
   • General Rule: If a set $S$ has $n$ elements, then it has $2^n$ subsets. In this case, $n = 3$, so $2^3 = 8$ subsets.

Recap of Set Notations

• Equality of Sets: If $A \subseteq B$ and $B \subseteq A$, then $A = B$. This means two sets are equal if and only if they contain the exact same elements.

Venn Diagrams

• Purpose: Venn diagrams are visual tools that help us understand and illustrate relations between sets.
• Components:
  • A rectangle typically represents the universal set ($U$).
  • An ellipse or circle represents an individual set (e.g., $A$).
  • A dot or point inside a circle represents an element that belongs to that set (e.g., $x \in A$).
  • A dot or point outside a circle represents an element that does not belong to that set (e.g., $y \notin A$).

Venn Diagram of Subsets

• When $A \subseteq B$, the circle representing set $A$ is drawn completely within the circle representing set $B$. This visually shows that all elements of $A$ are also elements of $B$.

Complement of a Set

• Definition: The complement of a set $A$, denoted by $A^c$, is the set of all elements in the universal set $U$ that are not in $A$.
  • Expressed in set builder notation: $A^c = {x \text{ } | \text{ } x \in U, x \notin A}$.
• Venn Diagram: The region outside the circle for set $A$ but within the universal rectangle $U$ represents $A^c$.
• Example: Given $U = {\,1, 2, 3, 4, 5}\,$ and $A = {\,2, 3, 5}\,$, then $A^c = {\,1, 4}\,$.

Complement Rules

• If $U$ is the universal set:
  • The complement of the universal set is the empty set: $U^c = \emptyset$.
  • The complement of the empty set is the universal set: $\emptyset^c = U$.
• Double Complement Rule: If $A$ is a subset of the universal set $U$, then the complement of the complement of $A$ is $A$ itself: $(A^c)^c = A$.

Union of Two Sets

• Definition: Given a universal set $U$ and two sets $A$ and $B$, the union of $A$ and $B$, denoted by $A \cup B$, is the set of all elements in $U$ that are either in $A$, or in $B$, or in both.
  • Expressed in set builder notation: $A \cup B = {x \text{ } | \text{ } x \in U, x \in A \text{ or } x \in B}$.
• Note: In set theory, when we say "$A$ or $B$", it always means "$A$, or $B$, or both" (inclusive OR).
• Venn Diagram: The entire shaded region encompassing both circles $A$ and $B$ (including their overlap) represents $A \cup B$.

Observations for Union

• $A \cup A = A$
• $A \cup \emptyset = A$
• $A \cup U = U$
• $A \cup A^c = U$

Intersection of Two Sets

• Definition: The intersection of two sets $A$ and $B$, denoted by $A \cap B$, is the set of all elements that are in both $A$ and $B$.
  • Expressed in set builder notation: $A \cap B = {x \text{ } | \text{ } x \in A \text{ and } x \in B}$.
• If an element $x$ fails to be in at least one of the sets, then $x$ is not in their intersection $A \cap B$.
• Venn Diagram: The region where the circles for $A$ and $B$ overlap represents $A \cap B$.

Disjoint Sets

• Definition: Two sets $A$ and $B$ are disjoint if they have no elements in common. This means their intersection is the empty set: $A \cap B = \emptyset$.
• Venn Diagram: For disjoint sets, the circles representing $A$ and $B$ do not overlap.

Observations for Intersection

• $A \cap A = A$
• $A \cap \emptyset = \emptyset$
• $A \cap U = A$
• $A \cap A^c = \emptyset$

Worked Example: Set Operations

Let $U = {\,1, 2, 3, 4, 5, 6, 7, 8}\,$, $A = {\,1, 3, 5, 7}\,$, $B = {\,1, 2, 3, 4}\,$.

1. Find $A^c$.
   • $A^c$ contains elements in $U$ but not in $A$. So, $A^c = {\,2, 4, 6, 8}\,$.
2. Find $A \cap B$.
   • $A \cap B$ contains elements common to both $A$ and $B$. So, $A \cap B = {\,1, 3}\,$.
3. Find $A \cup B$.
   • $A \cup B$ contains all elements that are in $A$ or $B$ (or both). So, $A \cup B = {\,1, 2, 3, 4, 5, 7}\,$.
4. Find $A^c \cup B^c$.
   • First, find $B^c$: Elements in $U$ but not in $B$. So, $B^c = {\,5, 6, 7, 8}\,$.
   • Then, $A^c \cup B^c$: All elements in $A^c$ or $B^c$. So, $A^c \cup B^c = {\,2, 4, 5, 6, 7, 8}\,$.

More Set Operations: Established Rules

• While Venn diagrams are powerful for visualization, knowing established rules (identities) regarding set operations can save time, especially on tests.
• It is crucial to understand what these rules mean, even if memorization is not strictly required.

De Morgan's Theorem

• This theorem provides rules for distributing the complement over unions and intersections:
  1. The complement of the intersection of two sets is the union of their complements: $(A \cap B)^c = A^c \cup B^c$
  2. The complement of the union of two sets is the intersection of their complements: $(A \cup B)^c = A^c \cap B^c$
• Proof (Demonstration for first rule using Venn Diagram):
  • Start with $A \cap B$, which is the overlap of A and B.
  • $(A \cap B)^c$ is everything outside this overlap.
  • $A^c$ is everything outside A. $B^c$ is everything outside B.
  • $A^c \cup B^c$ is the union of everything outside A and everything outside B. This region is identical to everything outside the overlap of A and B. Thus, $(A \cap B)^c = A^c \cup B^c$.
  • The second statement ($(A \cup B)^c = A^c \cap B^c$) can be demonstrated similarly.

List of Established Rules

1. Commutative Rules:
   • $A \cap B = B \cap A$
   • $A \cup B = B \cup A$
2. Associative Rules:
   • $(A \cap B) \cap C = A \cap (B \cap C)$
   • $(A \cup B) \cup C = A \cup (B \cup C)$
3. Distributive Rules:
   • $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$
   • $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$
4. De Morgan’s Rules:
   • $(A \cap B)^c = A^c \cup B^c$
   • $(A \cup B)^c = A^c \cap B^c$

More Worked Examples

Example 1: Identify $(A \cap B)^c \cup C$ on a Venn Diagram

• Given a Venn diagram with universal set $U$ and sets $A, B, C$.
• Step 1: Identify $A \cap B$: This is the region where circles A and B overlap.
• Step 2: Identify $(A \cap B)^c$: This is everything outside the overlap of A and B.
• Step 3: Identify $C$: This is the entire circle C.
• Step 4: Identify $(A \cap B)^c \cup C$: This is the union of the region outside $(A \cap B)$ and the entire region of $C$. It visually represents all areas except the part of $(A \cap B)$ that is not in $C$.

Example 2: Explain $A^c \cap B$ in words

• Given Definitions:
  • $U = {x \text{ } | \text{ } x \text{ is a UConn student}}$
  • $A = {x \text{ } | \text{ } x \in U \text{ and } x \text{ is from Connecticut}}$
  • $B = {x \text{ } | \text{ } x \in U \text{ and } x \text{ is a student-athlete}}$
• Solution:
  • Set $A$ represents UConn students who are from Connecticut.
  • Its complement, $A^c$, represents UConn students who are not from Connecticut.
  • Set $B$ represents all UConn student-athletes.
  • Therefore, the intersection $A^c \cap B$ is the set of UConn student-athletes who are not from Connecticut.