[HD] EECS3342 F26 - 2026-09-24 (Thursday) - Lecture 5

Overview

Jackie Wang develops the set-theory foundations for relations: subset and set-difference rules lead to power sets, Cartesian products, and a formal definition of relations. Examples show how to enumerate subsets and relations, calculate power-set size as either a sum of binomial coefficients or 2^|S|, and represent all relations from S to T as the power set of S × T.

Key takeaways

To prove S₁ is a proper subset of S₂, establish S₁ ⊆ S₂ and provide a witness x ∈ S₂ with x ∉ S₁.
If S₁ ⊆ S₂, then S₁ = S₂ exactly when S₂ \ S₁ is empty.
A set with n elements has 2ⁿ subsets because each element independently can be included or excluded; equivalently, the count is the sum of n choose k for k = 0 through n.
A Cartesian product S × T contains every valid ordered pair with its first element from S and second from T.
Relations from S to T are precisely the subsets of S × T, so their total number is 2^(|S|·|T|); the empty relation and S × T are the minimum and maximum cases.

Chapters

0:00 Lab 1 Follow-Up and the October 7 Rodin Programming Test

Jackie Wang says the Lab 1 solution will be released that night or the next day, with TA lab time and office hours available for questions.
The programming test is scheduled for October 7; a PDF guide and a past-year test will be shared before then.
Students should practice Rodin syntax and tool use, and can type the PDF solution into Rodin as extra practice.

1:40 Subset Definition and Set Comprehension Notation

S₁ ⊆ S₂ means every x in S₁ is also in S₂; elements outside S₁ do not affect whether the implication holds.
Subset inclusion allows S₁ and S₂ to be equal, unlike proper subset inclusion.
Set comprehension is introduced as a way to define sets implicitly, including relational operators covered later.

4:20 Set Difference and a Test for Set Equality

S₁ \ S₂ contains elements that are in S₁ and not in S₂; reversing the operands changes the result.
If S₁ ⊆ S₂ and S₂ \ S₁ = ∅, then S₁ = S₂.
A Venn-diagram interpretation identifies S₂ \ S₁ as the region inside S₂ but outside S₁.

9:00 Proper Subsets and Witness Elements

S₁ ⊂ S₂ requires S₁ ⊆ S₂ and at least one element x in S₂ that is not in S₁.
The witness x demonstrates that the sets are not equal while preserving containment.
Jackie Wang emphasizes this containment-plus-witness pattern as useful for later refinement arguments.

13:00 Big-O Classes as Sets of Functions

O(n) is treated as a set of functions whose growth is asymptotically bounded by n, including constants, logarithmic functions, and linear functions such as 2n.
O(n) is a proper subset of O(n²), since functions such as n² or n log n belong to O(n²) but not O(n).
The example illustrates why proper-subset notation conveys more information than ordinary subset notation.

19:00 Subset Laws, Set Equality, and Noncommutative Difference

The empty set is a subset of every set, and every set is a subset of itself; no set is a proper subset of itself.
The empty set is a proper subset of S exactly when S is nonempty.
Set equality can be proved by showing S ⊆ T and T ⊆ S; set difference is generally noncommutative because S₁ \ S₂ and S₂ \ S₁ select opposite regions.

27:00 Power Set Definition: A Set Whose Members Are Sets

The power set P(S) contains every subset X of S, so each member of a power set is itself a set.
For S = {1, 2, 3}, the smallest member is ∅ and the largest member is S itself.
The definition uses ordinary subset inclusion, ensuring that both ∅ and S are included.

31:00 Enumerating P({1, 2, 3}) by Cardinality

Group the subsets of {1, 2, 3} by size: one subset of cardinality 0, three of cardinality 1, three of cardinality 2, and one of cardinality 3.
The rows correspond to the binomial counts 3 choose 0, 3 choose 1, 3 choose 2, and 3 choose 3.
Their total, 1 + 3 + 3 + 1 = 8, gives the cardinality of P({1, 2, 3}); sets with different element orderings are not counted as distinct.

38:00 Power-Set Cardinality as a Sum of Binomial Coefficients

For a set S with n elements, count subsets separately by cardinality k, from 0 through n.
The total number of subsets is the sum of the counts n choose k for all k from 0 to n.
Although binomial counts are symmetric, calculating half and doubling requires care when the middle cardinality is not paired with a distinct row.

42:00 Why a Set of n Elements Has 2ⁿ Subsets

Each element independently has two choices when constructing a subset: include it or exclude it.
For S = {A, B, C}, three binary choices produce 2³ = 8 subsets, including ∅ and S.
The formula |P(S)| = 2^|S| is an efficient alternative to summing the binomial coefficients.

46:00 Cartesian Products Build Tuples from Multiple Sets

A Cartesian product S₁ × … × Sₙ contains n-tuples whose ith element is drawn from Sᵢ.
For {A, B} × {2, 4} × {$, %}, each tuple has three components and there are 2 × 2 × 2 = 8 tuples.
A branching tree enumerates the tuples systematically: each root-to-leaf path corresponds to one tuple.

53:00 Relations as Sets of Ordered Pairs

A relation from source S to target T is a set of ordered pairs (x, y), where x ∈ S and y ∈ T.
For S = {1, 2, 3} and T = {A, B}, the pair (1, A) is valid, but the bare pair is not itself a relation until enclosed in a set.
The pair (B, 2) is invalid for this source and target because its first component is not in S and its second is not in T.

59:00 Empty and Maximum Relations from S to T

The empty relation ∅ is the minimum relation because it contains no ordered pairs.
The maximum relation is S × T, which includes every valid source-target pair.
For S = {1, 2, 3} and T = {A, B}, the maximum relation contains six pairs; relation order does not matter because a relation is a set.

1:04:00 All Relations Are Subsets of the Cartesian Product

For S = {A, B} and T = {2, 4}, the maximum relation S × T has four pairs: (A, 2), (A, 4), (B, 2), and (B, 4).
Every relation is a subset of that maximum relation; relations of cardinality k are counted by choosing k of its four pairs.
Thus the set of all relations from S to T is P(S × T), and there are 2^(|S|·|T|) such relations.

Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Jackie Wang.