1.5 KiB
1.5 KiB
Sets: Basics and Operations
Source: MIT 6.1200J Lecture 01
What is a Set?
A set is a collection of objects.
Properties
- No duplicates: {1, 2, 2, 3} = {1, 2, 3}
- Order doesn't matter: {1, 2, 3} = {3, 1, 2}
- Can be infinite: ℕ = {0, 1, 2, ...}
- Can contain other sets: B = {2, {3, 4}, ∅}
Basic Notation
Membership
- ∈ (element of): 6 ∈ A means "6 is in set A"
- ∉ (not element of): {1, 2} ∉ A
Subset
- ⊆ (subset): S ⊆ T means all elements of S are also in T
- Example: {1, 2} ⊆ {0, 1, 2, 6}
Common Sets
- ℕ (Natural numbers): {0, 1, 2, ...}
- ℤ (Integers): {..., -2, -1, 0, 1, 2, ...}
- ∅ or {} (Empty set): The set with no elements
Set-Builder Notation
Used to define sets with predicates:
{n ∈ ℕ | isPrime(n)} = {2, 3, 5, 7, 11, ...}
Reads as: "The set of all n in ℕ such that isPrime(n) is true"
Can also use colon instead of vertical bar: {n ∈ ℕ : isPrime(n)}
Set Operations
Intersection (∩)
A ∩ B = {elements in both A and B}
Union (∪)
A ∪ B = {elements in A or B (or both)}
Difference (\ or −)
A \ B = {elements in A that are not in B}
Ordered Tuples
When order matters, use parentheses (not braces):
- (6, 1, 2, 0) ≠ (2, 1, 6, 0)
- Duplicates allowed: (1, 2, 2, 3) is valid
- Set operations (∩, ∪, etc.) don't apply to tuples