Overview
This lecture introduces counting techniques for sets, focusing on key formulas for determining set sizes using set operations, and the application of De Morgan's Laws.
Counting Elements in Sets
- Counting is the focus of the first part of the course, emphasizing different methods to determine set size.
- n(A) denotes the number of elements in set A.
- Example: n({Mouse, Cat, Dog}) = 3; n({50 US states}) = 50; n(∅) = 0 (empty set).
- Sometimes, direct listing is not possible or practical due to size or data availability.
- Counting may involve breaking down complex sets using set operations like union, intersection, and complement.
Core Set Counting Formulas
- n(A ∪ B) = n(A) + n(B) − n(A ∩ B) (number in union of A and B).
- n(A ∩ B) = n(A) + n(B) − n(A ∪ B) (number in intersection).
- n(A^c) = n(U) − n(A) (number in complement: universal set minus set A).
- n(A) = n(A ∩ B) + n(A ∩ B^c) (elements in A either also in B, or not in B).
De Morgan's Laws and Set Relationships
- De Morgan's Law 1: (A ∩ B)^c = A^c ∪ B^c.
- De Morgan's Law 2: (A ∪ B)^c = A^c ∩ B^c.
- These laws help switch between different forms of set expressions to simplify counting.
Example Application
- To find n(A^c ∪ B^c): Rewrite using De Morgan’s Law as n((A ∩ B)^c).
- Use complement formula: n(U) − n(A ∩ B).
- Calculate intersection using known values: n(A ∩ B) = n(A) + n(B) − n(A ∪ B).
- Substitute values to solve for the required set size.
Key Terms & Definitions
- n(A) — number of elements in set A.
- Union (A ∪ B) — set containing all elements from A or B.
- Intersection (A ∩ B) — set containing elements common to both A and B.
- Complement (A^c) — elements in universal set not in A.
- Universal set (U) — set containing all elements under consideration.
- De Morgan’s Laws — rules relating complement, union, and intersection.
Action Items / Next Steps
- Memorize the four core counting formulas and De Morgan’s Laws.
- Practice applying these formulas to word problems involving sets.
- Prepare for exercises that involve translating descriptions into set notation and solving for set sizes.