Set Basics & Operations

Overview

The Language of Collections

A set is the most fundamental concept in mathematics - it is simply a well-defined collection of distinct objects. Sets are used to define numbers, functions, relations, and virtually every other mathematical structure. In computer science, sets appear as data structures, database relations, and type systems.

Definition

Set

A set is an unordered collection of distinct objects called elements (or members). We write sets using curly braces: A = {1, 2, 3}.

Notation: • a ∈ A means "a is an element of A" • a ∉ A means "a is not an element of A"

Example: If A = {1, 2, 3}, then 2 ∈ A and 5 ∉ A.

Definition

Common Sets & Notation

Standard number sets: • ℕ = {0, 1, 2, 3, ...} - natural numbers • ℤ = {..., -2, -1, 0, 1, 2, ...} - integers • ℚ = {a/b : a, b ∈ ℤ, b ≠ 0} - rational numbers • ℝ - real numbers • ∅ or {} - the empty set (contains no elements)

Set-builder notation: {x ∈ S | condition on x} Example: {x ∈ ℤ | x > 0} = {1, 2, 3, ...}

Definition

Subsets and Equality

A ⊆ B (A is a subset of B) means every element of A is also in B. A ⊂ B (A is a proper subset of B) means A ⊆ B and A ≠ B. A = B means A ⊆ B and B ⊆ A (they have exactly the same elements).

Important: ∅ ⊆ A for every set A. Every set is a subset of itself: A ⊆ A.

Definition

Set Operations

Union: A ∪ B = {x | x ∈ A or x ∈ B} Intersection: A ∩ B = {x | x ∈ A and x ∈ B} Difference: A - B = {x | x ∈ A and x ∉ B} Complement: Aᶜ = {x ∈ U | x ∉ A} (where U is the universal set) Symmetric Difference: A △ B = (A - B) ∪ (B - A)

Example

Set Operations in Action

Let A = {1, 2, 3, 4} and B = {3, 4, 5, 6}.

A ∪ B = {1, 2, 3, 4, 5, 6} A ∩ B = {3, 4} A - B = {1, 2} B - A = {5, 6} A △ B = {1, 2, 5, 6}

Definition

Power Set & Cardinality

The cardinality of a set A, written |A|, is the number of elements in A. Example: |{a, b, c}| = 3.

The power set of A, written P(A) or 2ᴬ, is the set of all subsets of A. Example: P({1, 2}) = {∅, {1}, {2}, {1, 2}}.

Key fact: If |A| = n, then |P(A)| = 2ⁿ.

Example

Power Set Example

A = {a, b, c} P(A) = {∅, {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c}} |P(A)| = 2³ = 8 subsets.