Sets and Set Theory - Comprehensive Notes

Sets

• A set is a group or collection of objects. The objects are called elements or members of the set.
• Notation:
  • Roster (intensional): list elements inside braces. Example: the set of the four seasons S = {spring, summer, fall, winter}.
  • Word description: describe the set in words.
• Order does not matter in a set: S = {winter, spring, fall, summer} is the same as S = {spring, summer, fall, winter}.

Basic Number Sets

• Natural numbers (counting numbers):

  • $\mathbb{N} = {1, 2, 3, 4, 5, \dots}$

• Whole numbers (includes 0):

  • $\mathbb{W} = {0, 1, 2, 3, 4, 5, \dots}$

• Integers (all positive, negative, and zero):

  • $\mathbb{Z} = {\dots, -4, -3, -2, -1, 0, 1, 2, 3, 4, \dots}$

• Rational numbers: all numbers that can be written as a fraction $\dfrac{p}{q}$ with $p, q \in \mathbb{Z}, q \neq 0$.

  • Example: $\dfrac{1}{2}, \ -\dfrac{3}{4}, 0, 7, 5.25,\dots$ (terminating or repeating decimals).
  • Rational numbers can be written as $\dfrac{p}{q}$ with integer p and q ≠ 0.

• Irrational numbers: nonterminating, nonrepeating decimals (not representable as a ratio of integers). Example: decimal expansion like 0.101001000100001… (not repeating).

• Real numbers: $\mathbb{R} = \mathbb{Q} \cup \mathbb{I}$, the set of all rational or irrational numbers.

• Decimal representations:

  • If a decimal terminates or repeats a block of digits, the number is rational.
  • A decimal that neither terminates nor repeats is irrational. Example: $0.35335333533335\dots$
  • The bar notation (e.g., $\overline{27}$) indicates repeating block; here, 27 repeats indefinitely.

• Well-defined sets (Definition):

  • A set is well defined if it is possible to determine whether a given item is an element of the set.
  • Example: the set of letters of the English alphabet is well defined. The set of great songs is not well defined (no standard criterion).

Notation for Elementhood

• Elementhood: 4 ∈ N means 4 is an element of the natural numbers.
• Not an element: -3 ∉ N (since natural numbers are 1, 2, 3, …).
• Common symbols:
  • $a \in A$ read as “a is an element of A.”
  • $a \notin A$ read as “a is not an element of A.”

Example 4 – Apply Definitions Regarding Sets

• True/false checks:

  • a) 4 ∈ A? (true if 4 is in the defined set A)
  • b) There are no negative natural numbers ⇒ false (naturals start at 1)
  • c) 2.5 ∈ ?? (depends on the set; if the set is integers, true; if not, adjust accordingly)
  • d) “nice” is not precise ⇒ not well defined as a set membership predicate.

• The empty set: the empty set is denoted by ∅ or { }. It contains no elements. It is a subset of every set.

• Set-builder notation: useful for infinite sets. Example: {x ∈ \mathbb{N} | x > 7} reads as “the set of all x in \mathbb{N} such that x > 7.”

• For instance: the set of natural numbers greater than 7 written in set-builder form is:

  • {x \in \mathbb{N} \mid x > 7}

Subsets and Subset Relationships

• Subset: A ⊆ B means every element of A is also an element of B.

• Not a subset: A ⊄ B if there exists an element in A not in B.

• Set examples:

  • The set of vowels {a, e, i, o, u} is a subset of the set of letters in the alphabet.

• Subset examples (truth values):

  • {5, 10, 15, 20} ⊆ {0, 5, 10, 15, 20, 25, 30} is true.
  • \mathbb{W} ⊆ \mathbb{N} is false in strict form if N excludes 0 in this convention; depends on convention.
  • {2, 4, 6} ⊆ {2, 4, 6} is true (a set is a subset of itself).
  • ∅ ⊆ A is true for any A.

• Venn diagrams: universal set U; subsets are drawn as ovals inside the rectangle for U.

Proper Subsets

• Proper subset: A ⊂ B means A ⊆ B and A ≠ B (A is contained in B but not equal to B).
• Example: {a, e, i, o, u} ⊂ {a, b, c, d, e, i, o, u, x} is a proper subset if there are elements in B not in A.
• If A and B are equal, A ⊂ B is false (not a proper subset).
• Natural numbers N are a subset of integers Z, and proper since Z contains elements not in N (e.g., -3).

Venn Diagrams and Subsets

• Venn diagrams illustrate equality and subset relations for two and three sets.
• Regions in a Venn diagram correspond to combinations of membership in the sets A, B, C.
• Basic rule: In expressions, “and” corresponds to intersection, and “or” corresponds to union.
• Examples:
  • A ∪ B corresponds to the union region(s).
  • A ∩ B corresponds to the intersection region(s).

De Morgan’s Laws (Venn Diagrams and Equality of Sets)

• De Morgan’s laws relate complements with unions and intersections:
  • $(A \cup B)^c = A^c \cap B^c$
  • $(A \cap B)^c = A^c \cup B^c$
• These laws hold for any sets A and B within the universal set U.

Venn Diagrams Involving Three Sets

• With three sets A, B, C inside a universal set U, there are eight regions representing all combinations of membership.
• Regions are labeled i through viii in typical diagrams, representing all possible memberships (in A, B, C, in various intersections, or in none).
• The diagrams are used to verify equalities and compute unions/intersections across three sets.

Applications: Blood Groups and Blood Types

• Karl Landsteiner identified four major blood groups based on A and B antigens: A, B, AB, O.
  • A: Only A antigens
  • B: Only B antigens
  • AB: Both A and B antigens
  • O: No A or B antigens
• Later, the Rh factor was discovered, giving eight possible blood types when considering ABO and Rh (A+, A−, B+, B−, AB+, AB−, O+, O−).
• Venn diagrams illustrate the relationships among these antigen groups and Rh factor.

Section 2.4 Applications of Sets – Surveys and Inclusion-Exclusion

• Inclusion-Exclusion Principle for counting:
  • For two sets: $|A \cup B| = |A| + |B| - |A \cap B|$
  • 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|$
• Percent form: if p(A) denotes the percent of the population in A, then
  • $p(A \cup B) = p(A) + p(B) - p(A \cap B)$

Example: A music survey

• Given: total students = 495

  • Rap: 320
  • Rock: 395
  • Heavy metal: 295
  • Rap ∩ Rock: 280
  • Rap ∩ HM: 190
  • Rock ∩ HM: 245
  • All three: 160

• Exactly two of the three types: sum of the pairwise intersections not counting all-three:

  • $(|R \cap Ro| - |R \cap Ro \cap HM|) + (|R \cap HM| - |R \cap Ro \cap HM|) + (|Ro \cap HM| - |R \cap Ro \cap HM|)$
  • = (280 - 160) + (190 - 160) + (245 - 160) = 120 + 30 + 85 = 235

• Exactly one type: compute total with at least one type minus those with two or three:

  • At least one: by inclusion-exclusion, $|R \cup Ro \cup HM| = 320 + 395 + 295 - 280 - 190 - 245 + 160 = 455$
  • Exactly one: $455 - (235 + 160) = 60$

• So, 60 students like exactly one type, 235 like exactly two types, and 160 like all three.

• Using the Inclusion-Exclusion principle in practice helps solve survey problems efficiently via counting in Venn diagrams.

The Inclusion-Exclusion Principle – Practical Examples

• An application: Band and choir field trip with overlap 16 students, bands total 65, choir total 30.
  • By inclusion-exclusion: total = 65 + 30 - 16 = 79.
  • Interpreting regions in the Venn diagram confirms the same result.

Infinitely Many Sets

• Cantor’s idea: one-to-one correspondences show what sets are the same size (cardinality).
• Example of a finite-to-infinite idea:
  • Natural numbers N and even numbers E = {2, 4, 6, 8, …}
  • One-to-one correspondence: n ↔ 2n. This shows N and E have the same cardinality (countably infinite).
• Infinite sets: A set is infinite if there is a bijection between the set and one of its proper subsets.
• Examples:
  • N is infinite because N is in bijection with its proper subset E.
  • S = {5, 10, 15, 20, …, 5n, …} is infinite because S ≈ T = {10, 20, 30, …} via the mapping 5n ↔ 10n.
• Cardinality concept: For a finite set A with n elements, the cardinal number is $n(A) = n$. For example, if A = {1, 4, 6, 9}, then $n(A) = 4$.

Subsets, Equal Sets, and Equivalent Sets

• Equal sets: two sets are equal if they contain exactly the same elements.
• Equivalent sets: two sets are equivalent if they have the same cardinality (number of elements), not necessarily the same elements.

Section 2.5 – Infinite Sets (Recap)

• One-to-one correspondences are a foundational tool for proving set equivalence and infinitude.
• Infinite sets can be put in a one-to-one correspondence with one of their proper subsets, which demonstrates infinity.

Connections and Significance

• Sets form the foundation for most of discrete mathematics, logic, and combinatorics.
• Understanding subsets, complements, and unions/intersections is essential for analyzing relationships between groups of objects.
• Venn diagrams provide a visual tool to reason about these relationships and to apply De Morgan’s laws.
• The Inclusion-Exclusion principle is a powerful counting technique used in probability, statistics, and survey design.
• Infinite set concepts (Cantor) underpin important topics in analysis, number theory, and modern mathematics, including the notion of cardinality and countability.

Quick Reference Formulas

• Rational numbers: \mathbb{Q} = \left{\dfrac{p}{q} \;\middle|\; p,q\in\mathbb{Z}, q\neq 0\right}
• Real numbers: $\mathbb{R} = \mathbb{Q} \cup \mathbb{I}$, where $\mathbb{I}$ denotes irrational numbers.
• Terminating or repeating decimals correspond to rationals; nonterminating and nonrepeating decimals are irrational.
• Complement with respect to universal set U:
  • $A' = U \setminus A$ (or $A^c$)
• Universal set and empty set:
  • Complement of U is ∅; complement of ∅ is U.
• Subset relations:
  • $A \subseteq B$ means every element of A is in B.
  • $A \subsetneq B$ (or $A \subset B$) means A is a proper subset of B.
• Cardinality (finite sets):
  • If $A = {a<em>1, a</em>2, \dots, a_n}$, then $n(A) = n$ and the number of all subsets is $2^n$.
  • The number of proper subsets of A is $2^n - 1$ when A has n elements.
• Set operations:
  • Intersection: $A \cap B$
  • Union: $A \cup B$
• De Morgan’s laws:
  • $(A \cup B)^c = A^c \cap B^c$
  • $(A \cap B)^c = A^c \cup B^c$
• Inclusion-Exclusion (two sets):
  • $|A \cup B| = |A| + |B| - |A \cap B|$
• Inclusion-Exclusion (three sets):
  • $|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$
• Percent form of inclusion-exclusion:
  • $p(A \cup B) = p(A) + p(B) - p(A \cap B)$

End of Notes