A set is a collection of distinct objects. The core proof technique for sets is element-chasing: to show A is a subset of B, pick an arbitrary element x in A and show x must be in B. To show A = B, show each is a subset of the other.
Set notation and membership
Sets are written with curly braces or set-builder notation. Membership is "x in A." The empty set has no elements. Two sets are equal when they have exactly the same elements, regardless of order or repetition.
Scheme
; Sets as sorted lists (no duplicates)
(define A (list 12345))
(define B (list 34567))
(define (member? x s)
(cond ((null? s) #f)
((= x (car s)) #t)
(else (member? x (cdr s)))))
(display "3 in A? ") (display (member? 3 A)) (newline)
(display "6 in A? ") (display (member? 6 A)) (newline)
(display "6 in B? ") (display (member? 6 B))
Subset and equality
A is a subset of B if every element of A is also in B. To prove A = B, prove A is a subset of B and B is a subset of A. This is the standard technique for proving set equality.
Scheme
; Subset: every element of A is in B
(define (member? x s)
(cond ((null? s) #f)
((= x (car s)) #t)
(else (member? x (cdr s)))))
(define (subset? a b)
(cond ((null? a) #t)
((member? (car a) b) (subset? (cdr a) b))
(else#f)))
(define (set-equal? a b)
(and (subset? a b) (subset? b a)))
(define A (list 123))
(define B (list 1234))
(define C (list 321))
(display "A subset B? ") (display (subset? A B)) (newline)
(display "B subset A? ") (display (subset? B A)) (newline)
(display "A = C? ") (display (set-equal? A C))
Union, intersection, complement
Scheme
; Set operations
(define (member? x s)
(cond ((null? s) #f)
((= x (car s)) #t)
(else (member? x (cdr s)))))
(define (union a b)
(cond ((null? a) b)
((member? (car a) b) (union (cdr a) b))
(else (cons (car a) (union (cdr a) b)))))
(define (intersection a b)
(cond ((null? a) (list))
((member? (car a) b) (cons (car a) (intersection (cdr a) b)))
(else (intersection (cdr a) b))))
(define (difference a b)
(cond ((null? a) (list))
((member? (car a) b) (difference (cdr a) b))
(else (cons (car a) (difference (cdr a) b)))))
(define A (list 12345))
(define B (list 34567))
(display "A union B: ") (display (union A B)) (newline)
(display "A intersect B: ") (display (intersection A B)) (newline)
(display "A \\ B: ") (display (difference A B))
Python
# Set operations in Python
A = {1, 2, 3, 4, 5}
B = {3, 4, 5, 6, 7}
print(f"A | B = {sorted(A | B)}")
print(f"A & B = {sorted(A & B)}")
print(f"A - B = {sorted(A - B)}")
print(f"A <= B = {A <= B}")
Power set and Cartesian product
The power set of A is the set of all subsets of A. It has 2^|A| elements. The Cartesian product A x B is the set of all ordered pairs (a, b) with a in A and b in B.
Proof that A intersect (B union C) = (A intersect B) union (A intersect C). Pick x in the left side: x is in A and x is in B union C. Case 1: x is in B, so x is in A intersect B, so x is in the right side. Case 2: x is in C, so x is in A intersect C, so x is in the right side. The other direction is similar.
Scheme
; Verify distributive law: A n (B u C) = (A n B) u (A n C)
(define (member? x s)
(cond ((null? s) #f)
((= x (car s)) #t)
(else (member? x (cdr s)))))
(define (union a b)
(cond ((null? a) b)
((member? (car a) b) (union (cdr a) b))
(else (cons (car a) (union (cdr a) b)))))
(define (intersection a b)
(cond ((null? a) (list))
((member? (car a) b) (cons (car a) (intersection (cdr a) b)))
(else (intersection (cdr a) b))))
(define (set-equal? a b)
(and (null? (difference a b)) (null? (difference b a))))
(define (difference a b)
(cond ((null? a) (list))
((member? (car a) b) (difference (cdr a) b))
(else (cons (car a) (difference (cdr a) b)))))
(define A (list 1234))
(define B (list 235))
(define C (list 346))
(define lhs (intersection A (union B C)))
(define rhs (union (intersection A B) (intersection A C)))
(display "LHS: ") (display lhs) (newline)
(display "RHS: ") (display rhs) (newline)
(display "Equal? ") (display (set-equal? lhs rhs))