Lesson 4: Set Concepts

What Is a Set?

A set is an unordered collection of distinct elements. Sets group objects that share (or are selected by) some property. Sets are the foundational structure of discrete mathematics.

Representing Sets

1. Roster (Tabular) Form

List all elements, separated by commas, enclosed in curly braces.

Examples:

• First six natural numbers: N = {1, 2, 3, 4, 5, 6}
• Vowels: V = {a, e, i, o, u}
• Even numbers less than 9: X = {2, 4, 6, 8}

2. Set-Builder Notation

Describe all elements using a rule or condition.

Examples:

• P = {x | x is a counting number and x > 12}
• A = {x | x is an even number, 4 < x < 16}

3. Cardinality

The cardinality of a set is its size — the number of distinct elements. Written as |A|.

Examples:

• A = {2, 4, 6, 8, 12} → |A| = 5
• B = {1, 2, 3, 3, 4, 6, 8} → |B| = 6 (3 appears twice but counts once)

Set Operations

Union (∪)

All elements belonging to either set A or set B (or both).

A ∪ B = {x | x ∈ A or x ∈ B}

Example: A = {1, 2, 5, 8}, B = {1, 3, 4, 6, 7} A ∪ B = {1, 2, 3, 4, 5, 6, 7, 8}

Intersection (∩)

Only the elements that appear in both A and B.

A ∩ B = {x | x ∈ A and x ∈ B}

Example: A = {1, 2, 3, 4}, B = {2, 4, 6, 8} A ∩ B = {2, 4}

Complement (Aᶜ or A')

All elements in the universal set U that are not in A.

Example: A = {1, 2, 3, 4}, U = {1, 2, 3, 4, 5, 6, 7, 8} A' = {5, 6, 7, 8}

Difference (A − B)

Elements in A that are not in B.

A − B = {x | x ∈ A and x ∉ B}

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

Cartesian Product (A × B)

The set of all ordered pairs (a, b) where a ∈ A and b ∈ B.

|A × B| = |A| × |B|

Example: A = {1, 2}, B = {a, b} A × B = {(1,a), (1,b), (2,a), (2,b)}

De Morgan's Laws for Sets

• (A ∪ B)ᶜ = Aᶜ ∩ Bᶜ
• (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ

These mirror De Morgan's laws for propositional logic.

Inclusion-Exclusion Principle

When counting the union of two sets where some elements overlap:

|A ∪ B| = |A| + |B| − |A ∩ B|

For three sets:

|A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|