From Logic to Sets: Building the Foundation of Computer Science
• Tables are sets of records
• SQL queries use set operations
• JOIN = Cartesian product
• UNION, INTERSECT, EXCEPT
• Collections: Set, HashSet, TreeSet
• Unique elements
• Fast membership testing
• Remove duplicates
• Graph vertices and edges
• State spaces in AI
• Visited nodes tracking
• User permissions
• Resource access lists
• Group memberships
Throughout this module, we'll use a consistent example that you can relate to:
All Students (Universe U):
U = {Alice, Bob, Charlie, Diana, Eve, Frank, Grace, Henry}
MA2011 (Discrete Maths):
CS = {Alice, Bob, Charlie, Diana}
MA1000 (Calculus):
Math = {Bob, Diana, Eve, Frank}
CP1000 (Physics):
Physics = {Charlie, Frank, Grace, Henry}
CP2001 (Data Structures):
DataSci = {Alice, Bob, Eve, Grace}
We'll use this example to understand every concept in set theory!
A set is a well-defined, unordered collection of distinct objects.
The objects in a set are called its elements or members.
{Alice, Bob, Charlie}
is the same as
{Charlie, Bob, Alice}
Order doesn't matter!
{Alice, Bob, Bob, Alice}
is the same as
{Alice, Bob}
Duplicates are automatically removed!
Students enrolled in MA2011:
CS = {Alice, Bob, Charlie, Diana}
This is a set because each student appears exactly once, and the order we list them doesn't matter.
List all elements between curly braces:
A = {Alice, Bob, Charlie, Diana}
Best for: Small, finite sets where you know all elements
Describe the property that elements must satisfy:
A = {x | x is enrolled in MA2011}
Read as: "A is the set of all x such that x is enrolled in MA2011"
Best for: Large sets or sets defined by a rule
| Symbol | Meaning | Example |
|---|---|---|
| ℕ | Natural numbers | {0, 1, 2, 3, ...} |
| ℤ | Integers | {..., -2, -1, 0, 1, 2, ...} |
| ℝ | Real numbers | All numbers on number line |
| ∅ or {} | Empty set | Set with no elements |
Let's express the same set in all three ways:
A = {Bob, Diana}
A = {x | x ∈ CS AND x ∈ Math}
or equivalently:
A = {x ∈ U | (x enrolled in MA2011) ∧ (x enrolled in MA1000)}
A = CS ∩ Math
Write the set of students enrolled in Physics in both list form and predicate form.
x ∈ A means "x is an element of A" or "x belongs to A"
x ∉ A means "x is NOT an element of A"
Recall: CS = {Alice, Bob, Charlie, Diana}
Alice ∈ CS is TRUE
Eve ∈ CS is FALSE
Eve ∉ CS is TRUE
Bob ∈ Math is TRUE
Grace ∈ Physics is TRUE
For a given element c and set A, "c ∈ A" is a proposition!
It can be either TRUE or FALSE.
If x is a variable, then "x ∈ A" is a predicate!
The cardinality of a set A, written |A|, is the number of elements in A.
A set is finite if it has a finite number of elements.
|CS| = |{Alice, Bob, Charlie, Diana}| = 4
|Math| = |{Bob, Diana, Eve, Frank}| = 4
|Physics| = |{Charlie, Frank, Grace, Henry}| = 4
|DataSci| = |{Alice, Bob, Eve, Grace}| = 4
|U| = 8 (total students)
|∅| = 0
The empty set has no elements
|{Alice}| = 1
A set with exactly one element
What is |{1, 1, 2, 2, 3}|? Remember: sets have no duplicates!
A set B is a subset of a set A, written B ⊆ A, if every element of B is also an element of A.
Formally: B ⊆ A means ∀x (x ∈ B → x ∈ A)
Let BothCourses = {Bob, Diana} (students in both CS and Math)
BothCourses ⊆ CS is TRUE
because both Bob and Diana are in CS
BothCourses ⊆ Math is also TRUE
because both Bob and Diana are in Math
✓ {Alice, Bob} ⊆ CS
✓ {Bob} ⊆ CS
✓ ∅ ⊆ CS (empty set is subset of every set!)
✓ CS ⊆ CS (every set is subset of itself!)
✓ CS ⊆ U (every set is subset of the universe)
✗ {Alice, Eve} ⊆ CS
Why? Eve ∈ {Alice, Eve} but Eve ∉ CS
✗ Math ⊆ CS
Why? Eve ∈ Math but Eve ∉ CS
B ⊄ A means B is NOT a subset of A
Formally: ∃x (x ∈ B ∧ x ∉ A)
There exists at least one element in B that is not in A
A set B is a proper subset of a set A, written B ⊂ A, if:
In other words: B ⊂ A means B ⊆ A but B ≠ A
✓ {Alice, Bob} ⊂ CS
✓ ∅ ⊂ CS
✓ CS ⊂ U
✗ CS ⊂ CS
CS = CS, so not proper
Some textbooks use ⊂ to mean ⊆ (subset)
Some textbooks use ⊂ to mean proper subset (like <)
Always check which convention is being used!
Think: ⊆ is like ≤, and ⊂ is like <
Two sets A and B are equal, written A = B, if they have exactly the same elements.
Formally: A = B if and only if A ⊆ B AND B ⊆ A
Using predicates: ∀x (x ∈ A ↔ x ∈ B)
{Alice, Bob, Charlie} = {Charlie, Alice, Bob}
Order doesn't matter!
{Alice, Bob, Bob, Alice} = {Alice, Bob}
Duplicates don't matter!
{Alice, Bob} ≠ {Alice, Bob, Charlie}
Different elements!
Method 1: Show A ⊆ B and B ⊆ A
Method 2: Show every element of A is in B, and every element of B is in A
Method 3: Use set laws and algebra (we'll learn this soon!)
For any set A: ∅ ⊆ A
Why? There's no element in ∅ that fails to be in A!
Vacuous truth: "All unicorns in my room have wings" is true (there are no unicorns!)
For any set A: A ⊆ A
Why? Every element of A is (obviously) in A!
If A ⊆ B and B ⊆ C, then A ⊆ C
Why? Every element of A is in B, and every element of B is in C, so every element of A is in C!
Let CSMajors = {Alice, Charlie}
Then: CSMajors ⊆ CS ⊆ U
Therefore: CSMajors ⊆ U
The union of sets A and B, written A ∪ B, is the set of all elements that are in A OR in B (or in both).
Formally:
A ∪ B = {x | x ∈ A ∨ x ∈ B}
Union (∪) corresponds to OR (∨)
Think: "in A or in B"
CS = {Alice, Bob, Charlie, Diana}
Math = {Bob, Diana, Eve, Frank}
CS ∪ Math = {Alice, Bob, Charlie, Diana, Eve, Frank}
Students taking at least one of these courses
# Define sets using Python's set type
CS = {'Alice', 'Bob', 'Charlie', 'Diana'}
Math = {'Bob', 'Diana', 'Eve', 'Frank'}
# Method 1: Using the | operator
union1 = CS | Math
print(union1)
# Output: {'Alice', 'Bob', 'Charlie', 'Diana', 'Eve', 'Frank'}
# Method 2: Using the union() method
union2 = CS.union(Math)
print(union2)
# Output: {'Alice', 'Bob', 'Charlie', 'Diana', 'Eve', 'Frank'}
# Both methods give the same result!
print(union1 == union2) # Output: True
Commutative:
A ∪ B = B ∪ A
Associative:
(A ∪ B) ∪ C = A ∪ (B ∪ C)
Identity:
A ∪ ∅ = A
Idempotent:
A ∪ A = A
What is Physics ∪ DataSci?
Physics = {Charlie, Frank, Grace, Henry}, DataSci = {Alice, Bob, Eve, Grace}
The intersection of sets A and B, written A ∩ B, is the set of all elements that are in BOTH A AND B.
Formally:
A ∩ B = {x | x ∈ A ∧ x ∈ B}
Intersection (∩) corresponds to AND (∧)
Think: "in A and in B"
CS = {Alice, Bob, Charlie, Diana}
Math = {Bob, Diana, Eve, Frank}
CS ∩ Math = {Bob, Diana}
Students taking both courses
# Define sets
CS = {'Alice', 'Bob', 'Charlie', 'Diana'}
Math = {'Bob', 'Diana', 'Eve', 'Frank'}
# Method 1: Using the & operator
intersection1 = CS & Math
print(intersection1)
# Output: {'Bob', 'Diana'}
# Method 2: Using the intersection() method
intersection2 = CS.intersection(Math)
print(intersection2)
# Output: {'Bob', 'Diana'}
# Find students in all three courses
Physics = {'Charlie', 'Frank', 'Grace', 'Henry'}
all_three = CS & Math & Physics
print(all_three)
# Output: set() (empty set - no student in all three)
Commutative:
A ∩ B = B ∩ A
Associative:
(A ∩ B) ∩ C = A ∩ (B ∩ C)
Identity:
A ∩ U = A
Annihilator:
A ∩ ∅ = ∅
Two sets A and B are disjoint if they have no elements in common.
Formally: A and B are disjoint if A ∩ B = ∅
Using predicates: ¬∃x (x ∈ A ∧ x ∈ B)
Let CSOnly = {Alice, Charlie} (students only in CS, not in Math)
Let MathOnly = {Eve, Frank} (students only in Math, not in CS)
CSOnly ∩ MathOnly = ∅
These sets are disjoint!
# Check if sets are disjoint
CSOnly = {'Alice', 'Charlie'}
MathOnly = {'Eve', 'Frank'}
print(CSOnly.isdisjoint(MathOnly)) # Output: True
print(CS.isdisjoint(Math)) # Output: False (they share Bob and Diana)
The difference of sets A and B, written A \ B or A - B, is the set of elements that are in A but NOT in B.
Formally:
A \ B = {x | x ∈ A ∧ x ∉ B}
A \ B ≠ B \ A
Difference is NOT commutative!
CS = {Alice, Bob, Charlie, Diana}
Math = {Bob, Diana, Eve, Frank}
CS \ Math = {Alice, Charlie}
Students taking CS but not Math
Math \ CS = {Eve, Frank}
Students taking Math but not CS
# Define sets
CS = {'Alice', 'Bob', 'Charlie', 'Diana'}
Math = {'Bob', 'Diana', 'Eve', 'Frank'}
# Method 1: Using the - operator
cs_only = CS - Math
print(cs_only)
# Output: {'Alice', 'Charlie'}
# Method 2: Using the difference() method
math_only = Math.difference(CS)
print(math_only)
# Output: {'Eve', 'Frank'}
# Demonstrate non-commutativity
print(CS - Math) # {'Alice', 'Charlie'}
print(Math - CS) # {'Eve', 'Frank'}
print((CS - Math) == (Math - CS)) # False!
# Students taking exactly one course (not both)
cs_exclusive = CS - Math # Only CS
math_exclusive = Math - CS # Only Math
one_course_only = cs_exclusive | math_exclusive
print(one_course_only)
# Output: {'Alice', 'Charlie', 'Eve', 'Frank'}
# This is called "symmetric difference" (we'll see this soon!)
What is U \ CS (students not taking CS)?
The complement of set A, written A' or Ā or Ac, is the set of all elements in the universe U that are NOT in A.
Formally:
A' = U \ A = {x ∈ U | x ∉ A}
Complement (') corresponds to NOT (¬)
Think: "not in A"
U = {Alice, Bob, Charlie, Diana, Eve, Frank, Grace, Henry}
CS = {Alice, Bob, Charlie, Diana}
CS' = {Eve, Frank, Grace, Henry}
Students NOT taking CS
# Define universe and sets
U = {'Alice', 'Bob', 'Charlie', 'Diana', 'Eve', 'Frank', 'Grace', 'Henry'}
CS = {'Alice', 'Bob', 'Charlie', 'Diana'}
# Complement: elements in U but not in CS
CS_complement = U - CS
print(CS_complement)
# Output: {'Eve', 'Frank', 'Grace', 'Henry'}
# Verify important properties
print(CS | CS_complement) # Should equal U
# Output: {'Alice', 'Bob', ..., 'Henry'} (all 8 students)
print(CS & CS_complement) # Should be empty
# Output: set() (empty set)
Union with Complement:
A ∪ A' = U
Intersection with Complement:
A ∩ A' = ∅
Double Complement:
(A')' = A
Universe & Empty Set:
U' = ∅
∅' = U
If Math = {Bob, Diana, Eve, Frank}, what is Math'?
| Operation | Symbol | Definition | Logic Connection | Python |
|---|---|---|---|---|
| Union | A ∪ B | Elements in A OR B | ∨ (OR) | A | B |
| Intersection | A ∩ B | Elements in A AND B | ∧ (AND) | A & B |
| Difference | A \ B | Elements in A but NOT in B | ∧ ¬ | A - B |
| Complement | A' | Elements NOT in A | ¬ (NOT) | U - A |
CS = {Alice, Bob, Charlie, Diana}
Math = {Bob, Diana, Eve, Frank}
CS ∪ Math = {Alice, Bob, Charlie, Diana, Eve, Frank}
CS ∩ Math = {Bob, Diana}
CS \ Math = {Alice, Charlie}
CS' = {Eve, Frank, Grace, Henry}
Remember the laws of logic from Weeks 1-2? Set theory has parallel laws!
| Law Name | Logic Law | Set Law |
|---|---|---|
| Commutative | p ∨ q ≡ q ∨ p p ∧ q ≡ q ∧ p |
A ∪ B = B ∪ A A ∩ B = B ∩ A |
| Associative | (p ∨ q) ∨ r ≡ p ∨ (q ∨ r) (p ∧ q) ∧ r ≡ p ∧ (q ∧ r) |
(A ∪ B) ∪ C = A ∪ (B ∪ C) (A ∩ B) ∩ C = A ∩ (B ∩ C) |
| Distributive | p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) | A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) |
| De Morgan's | ¬(p ∨ q) ≡ ¬p ∧ ¬q ¬(p ∧ q) ≡ ¬p ∨ ¬q |
(A ∪ B)' = A' ∩ B' (A ∩ B)' = A' ∪ B' |
Because sets are defined using predicates!
A ∪ B = {x | x ∈ A ∨ x ∈ B}
The ∨ in the predicate becomes ∪ in the set!
Law 1: (A ∪ B)' = A' ∩ B'
The complement of a union is the intersection of complements
Law 2: (A ∩ B)' = A' ∪ B'
The complement of an intersection is the union of complements
CS = {Alice, Bob, Charlie, Diana}
Math = {Bob, Diana, Eve, Frank}
CS ∪ Math = {Alice, Bob, Charlie, Diana, Eve, Frank}
Using Law 1:
(CS ∪ Math)' = {Grace, Henry}
Students not taking CS or Math
CS' ∩ Math' = {Eve, Frank, Grace, Henry} ∩ {Alice, Charlie, Grace, Henry}
= {Grace, Henry} ✓
"Not (in CS or Math)" = "Not in CS AND not in Math"
"Not (in CS and Math)" = "Not in CS OR not in Math"
Show A ⊆ B and B ⊆ A
Show that x ∈ A ⟺ x ∈ B for all x
Use logical equivalences to transform the predicate for A into the predicate for B
Apply known set laws to transform one side into the other
(Like algebraic manipulation, but with sets!)
Let's see an example of each method...
Method 2: Using Predicates
(A ∪ B)' = {x | x ∉ (A ∪ B)}
Definition of complement
= {x | ¬(x ∈ (A ∪ B))}
Rewrite ∉ as ¬∈
= {x | ¬(x ∈ A ∨ x ∈ B)}
Definition of union
= {x | ¬(x ∈ A) ∧ ¬(x ∈ B)}
De Morgan's law of logic!
= {x | x ∉ A ∧ x ∉ B}
Rewrite ¬∈ as ∉
= {x | x ∈ A' ∧ x ∈ B'}
Definition of complement
= A' ∩ B'
Definition of intersection
Therefore, (A ∪ B)' = A' ∩ B' ✓
| Law Name | Set Law |
|---|---|
| Identity Laws | A ∪ ∅ = A A ∩ U = A |
| Domination Laws | A ∪ U = U A ∩ ∅ = ∅ |
| Idempotent Laws | A ∪ A = A A ∩ A = A |
| Complement Laws | A ∪ A' = U A ∩ A' = ∅ (A')' = A |
| Commutative Laws | A ∪ B = B ∪ A A ∩ B = B ∩ A |
| Associative Laws | (A ∪ B) ∪ C = A ∪ (B ∪ C) (A ∩ B) ∩ C = A ∩ (B ∩ C) |
| Distributive Laws | A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) |
| De Morgan's Laws | (A ∪ B)' = A' ∩ B' (A ∩ B)' = A' ∪ B' |
| Absorption Laws | A ∪ (A ∩ B) = A A ∩ (A ∪ B) = A |
The power set of a set A, written P(A) or 2A, is the set of all subsets of A.
Formally: P(A) = {B | B ⊆ A}
Let A = {1, 2}
The subsets of A are:
P(A) = {∅, {1}, {2}, {1, 2}}
Notice: |A| = 2, but |P(A)| = 4 = 2²
Elements of P(A) are SETS, not individual elements!
1 ∈ A but 1 ∉ P(A)
{1} ∈ P(A) but {1} ∉ A
If A is a finite set with |A| = n, then:
|P(A)| = 2n
Think of building a subset: for each element, we have 2 choices:
For n elements: 2 × 2 × 2 × ... × 2 (n times) = 2n subsets
Let Small = {Alice, Bob, Charlie}
|Small| = 3, so |P(Small)| = 2³ = 8
P(Small) = {
∅,
{Alice}, {Bob}, {Charlie},
{Alice, Bob}, {Alice, Charlie}, {Bob, Charlie},
{Alice, Bob, Charlie}
}
The Cartesian product of sets A and B, written A × B, is the set of all ordered pairs (a, b) where a ∈ A and b ∈ B.
Formally: A × B = {(a, b) | a ∈ A ∧ b ∈ B}
Order matters! (a, b) ≠ (b, a) unless a = b
A × B ≠ B × A in general
Let Courses = {CS, Math}
Let Students = {Alice, Bob}
Courses × Students = {
(CS, Alice), (CS, Bob),
(Math, Alice), (Math, Bob)
}
This represents all possible course-student pairings!
(Think: enrollment possibilities)
If |A| = m and |B| = n, then:
|A × B| = m × n
JOIN operations compute Cartesian products
Students × Courses = all possible enrollments
ℝ² = ℝ × ℝ
All points (x, y) in the plane
# Python implementation
from itertools import product
courses = {'CS', 'Math'}
students = {'Alice', 'Bob'}
# Cartesian product
pairings = set(product(courses, students))
print(pairings)
# Output: {('CS', 'Alice'), ('CS', 'Bob'),
# ('Math', 'Alice'), ('Math', 'Bob')}
print(len(pairings)) # 2 × 2 = 4
If |A| = 3 and |B| = 4, what is |A × B|?
For any finite sets A and B:
|A ∪ B| = |A| + |B| - |A ∩ B|
CS = {Alice, Bob, Charlie, Diana}, so |CS| = 4
Math = {Bob, Diana, Eve, Frank}, so |Math| = 4
CS ∩ Math = {Bob, Diana}, so |CS ∩ Math| = 2
Calculate |CS ∪ Math|:
|CS ∪ Math| = 4 + 4 - 2 = 6
Verify:
CS ∪ Math = {Alice, Bob, Charlie, Diana, Eve, Frank}
Count: 6 students ✓
U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
A = {2, 4, 6, 8, 10} (even numbers)
B = {1, 2, 3, 5, 7} (primes and 1)
C = {3, 6, 9} (multiples of 3)
1. A ∪ B = {1, 2, 3, 4, 5, 6, 7, 8, 10}
2. A ∩ B = {2}
3. A \ B = {4, 6, 8, 10}
4. B' = {4, 6, 8, 9, 10}
5. A ∪ C = {2, 3, 4, 6, 8, 9, 10}
(A ∪ C)' = {1, 5, 7}
6. B ∪ C = {1, 2, 3, 5, 6, 7, 9}
A ∩ (B ∪ C) = {2, 6}
7. |A| = 5, |C| = 3
|A × C| = 5 × 3 = 15
8. |A| = 5, |B| = 5, |A ∩ B| = 1
|A ∪ B| = 5 + 5 - 1 = 9
Count elements: 9 ✓
(Distributive Law for Sets)
Show: A ∩ (B ∪ C) ⊆ (A ∩ B) ∪ (A ∩ C) and (A ∩ B) ∪ (A ∩ C) ⊆ A ∩ (B ∪ C)
Show the predicates are logically equivalent
Hint: Start with x ∈ A ∩ (B ∪ C) and transform using definitions and logic laws
x ∈ A ∩ (B ∪ C)
⟺ x ∈ A ∧ x ∈ (B ∪ C)
Definition of ∩
⟺ x ∈ A ∧ (x ∈ B ∨ x ∈ C)
Definition of ∪
⟺ (x ∈ A ∧ x ∈ B) ∨ (x ∈ A ∧ x ∈ C)
Distributive law of logic!
⟺ x ∈ (A ∩ B) ∨ x ∈ (A ∩ C)
Definition of ∩
⟺ x ∈ (A ∩ B) ∪ (A ∩ C)
Definition of ∪
Therefore, A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) ✓
Consider a database table with student enrollments:
| Student | Course |
|---|---|
| Alice | MA2011 |
| Bob | MA2011 |
| Bob | MA1000 |
| Charlie | MA2011 |
| Diana | MA2011 |
| Diana | MA1000 |
-- SQL UNION: Students in MA2011 OR MA1000 SELECT Student FROM Enrollments WHERE Course = 'MA2011' UNION SELECT Student FROM Enrollments WHERE Course = 'MA1000'; -- Result: Alice, Bob, Charlie, Diana, Eve, Frank -- SQL INTERSECT: Students in MA2011 AND MA1000 SELECT Student FROM Enrollments WHERE Course = 'MA2011' INTERSECT SELECT Student FROM Enrollments WHERE Course = 'MA1000'; -- Result: Bob, Diana -- SQL EXCEPT: Students in MA2011 but NOT MA1000 SELECT Student FROM Enrollments WHERE Course = 'MA2011' EXCEPT SELECT Student FROM Enrollments WHERE Course = 'MA1000'; -- Result: Alice, Charlie
Set theory is the foundation of SQL!
# Define user groups (sets)
admins = {'alice', 'bob'}
editors = {'bob', 'charlie', 'diana'}
viewers = {'diana', 'eve', 'frank'}
# Users who can edit OR view
can_access = editors | viewers
print(f"Can access: {can_access}")
# {bob, charlie, diana, eve, frank}
# Users who are both editors AND viewers
power_users = editors & viewers
print(f"Power users: {power_users}")
# {diana}
# Users who can edit but NOT admin
editors_only = editors - admins
print(f"Editors only: {editors_only}")
# {charlie, diana}
# Check specific permissions
def has_permission(user, required_groups):
"""Check if user is in any of the required groups"""
user_groups = set()
if user in admins: user_groups.add('admin')
if user in editors: user_groups.add('editor')
if user in viewers: user_groups.add('viewer')
return bool(user_groups & required_groups)
print(has_permission('bob', {'admin', 'editor'})) # True
print(has_permission('eve', {'admin', 'editor'})) # False
1 ∈ {1, 2, 3} ✓ (1 is an element)
1 ⊆ {1, 2, 3} ✗ (1 is not a set!)
{1} ⊆ {1, 2, 3} ✓ ({1} is a subset)
{1} ∈ {1, 2, 3} ✗ ({1} is not an element!)
{1, 2} = {2, 1} ✓ (sets are unordered)
(1, 2) = (2, 1) ✗ (ordered pairs are ordered!)
∅ is the empty set (no elements)
{∅} is a set containing one element (the empty set!)
|∅| = 0 but |{∅}| = 1
If A and B overlap, you can't just add: |A ∪ B| ≠ |A| + |B|
Use inclusion-exclusion: |A ∪ B| = |A| + |B| - |A ∩ B|
Visual representations help understand operations and prove identities
Every set law has a corresponding logic law:
∪ ↔ ∨, ∩ ↔ ∧, ' ↔ ¬
Use small sets to verify laws before proving them generally
Show every step, state which law or definition you're using
# Verify De Morgan's Law
A = {1, 2, 3}
B = {3, 4, 5}
U = {1, 2, 3, 4, 5, 6}
left = U - (A | B)
right = (U - A) & (U - B)
print(left == right) # Should be True
The practice problems cover all major concepts and proof techniques
Set theory is the foundation of computer science!
Databases, algorithms, data structures all use set operations
Functions are special types of relations (subsets of Cartesian products)
f: A → B is a subset of A × B
Binary relations are subsets of A × A
Equivalence relations partition sets into disjoint subsets
Counting subsets, permutations, combinations
Inclusion-exclusion for complex counting problems
Graphs are sets of vertices and edges
G = (V, E) where V is a set and E ⊆ V × V
Set theory is the language of discrete mathematics. Master it now!
Remember: Sets are the foundation!
Master them now, everything else builds on this.