Day 13 — Sets, Set Operations & Cartesian Products

Updated

July 30, 2025

Day 13 — Sets, Set Operations & Cartesian Products

Day 35 — Sets

Stage IV · concept day
Goal: Use roster and set-builder notation; master $\in$, $\subseteq$, $\subsetneq$; work with the empty set and ambient universes; know Russell’s paradox at awareness level; prove set equality by double inclusion.

Why this matters

Sets are the noun phrases of discrete mathematics: types as collections of values, databases as sets of rows, configs as sets of flags, graphs as vertex/edge sets. Stage IV builds relations and functions on top of sets. Equality by double inclusion is the same muscle as “two specs describe the same states.”

Theory

What is a set? (naive view)

A set is a collection of distinct objects, called elements (or members). We write $x \in A$ for “$x$ is an element of $A$” and $x \notin A$ otherwise.

Naive set theory is enough for CS mathematics at this level; avoid unrestricted “set of all sets.”

Roster notation

List elements in braces: $A = \{1,2,3\}$, $B = \{\mathrm{red},\mathrm{blue}\}$.
Order does not matter: $\{1,2\}=\{2,1\}$.
Repetition does not matter: $\{1,1,2\}=\{1,2\}$.

Set-builder notation

\[\{ x \in U : P(x) \}\]
means the set of all $x$ in universe $U$ such that predicate $P(x)$ holds.
Also written $\{ x \in U \mid P(x) \}$.

Examples: $\{ n \in \mathbb{Z} : n > 0 \} = \mathbb{Z}^+$ (or $\mathbb{N}$ depending on convention); $\{ n \in \mathbb{Z} : 2\mid n \}$ even integers.

Equality of sets

\[A = B \;\overset{\mathrm{def}}{\Longleftrightarrow}\; \forall x\, (x\in A \leftrightarrow x\in B).\]

Double inclusion theorem. $A = B$ iff $A \subseteq B$ and $B \subseteq A$.

Proof. If $A=B$, membership agrees so each is subset of the other. Conversely, if both inclusions hold, then $x\in A \Rightarrow x\in B$ and $x\in B \Rightarrow x\in A$, so $x\in A \leftrightarrow x\in B$. $\square$

Subset and proper subset

\[A \subseteq B \;\overset{\mathrm{def}}{\Longleftrightarrow}\; \forall x\, (x\in A \rightarrow x\in B).\]

$A$ is a proper subset of $B$, written $A \subsetneq B$ (or $A \subset B$ in texts that use $\subset$ for proper), when $A \subseteq B$ and $A \neq B$.

Always $A \subseteq A$. If $A \subseteq B$ and $B \subseteq C$ then $A \subseteq C$ (transitivity—direct element chase).

Empty set

The empty set $\emptyset = \{\}$ has no elements.
$\forall x\, (x \notin \emptyset)$.
$\emptyset \subseteq A$ for every set $A$ (vacuous implication $x\in\emptyset \rightarrow x\in A$).
$\emptyset \neq \{\emptyset\}$: the latter has one element (the empty set).

Universe of discourse

Often all sets under discussion are subsets of a fixed universe $U$ (e.g. $\mathbb{Z}$, all strings, all users). Complements (Day 36) need $U$.

Standard number sets (notation)

$\mathbb{N}$ (naturals—confirm if $0$ included), $\mathbb{Z}$, $\mathbb{Q}$, $\mathbb{R}$, $\mathbb{C}$.
Finite sets: $|A|=n$ means $n$ elements (cardinality; deeper Days 41–43).

Russell’s paradox (awareness, one paragraph)

If unrestricted comprehension allowed $R = \{ x : x \notin x \}$, then $R\in R \leftrightarrow R\notin R$, contradiction. Naive “any property defines a set” is inconsistent. Modern foundations restrict set formation (types, ZFC axioms). Practice: only form $\{x \in U : P(x)\}$ from an already given $U$, or use known set constructors. You will not need formal ZFC here—just do not form “the set of all sets” or “the set of all sets that do not contain themselves.”

Proving $A \subseteq B$

Element chase: Let $x \in A$ be arbitrary. … show $x \in B$. Conclude $A\subseteq B$.

Proving $A \neq B$

Exhibit a witness element in one set but not the other.

Singleton and pairing

$\{a\}$ has one element. $\{a,b\}$ has two if $a\neq b$, else one.

Sets of sets

$\{\emptyset, \{1\}, \{1,2\}\}$ is a set whose elements are sets. Common in power sets (Day 36) and inductively defined structures.

Worked examples

Example 1 — Roster equality

$\{1,2,3\} = \{3,1,2,1\}$ because same members.

Example 2 — Builder

$\{ n \in \mathbb{N} : n < 4 \} = \{0,1,2,3\}$ if $0\in\mathbb{N}$, else $\{1,2,3\}$.

Example 3 — Subset proof

$A = \{2,4\}$, $B = \{n\in\mathbb{Z}: 2\mid n\}$.
Let $x\in A$. Then $x=2$ or $x=4$, both even, so $x\in B$. Thus $A\subseteq B$.

Example 4 — Proper subset

$A \subsetneq B$ because $6\in B$ but $6\notin A$.

Example 5 — Double inclusion

Let $E = \{ n\in\mathbb{Z}: 2\mid n \}$, $F = \{ n\in\mathbb{Z}: n=2k\text{ for some }k\in\mathbb{Z} \}$.
Same definition essentially—show $E\subseteq F$ and $F\subseteq E$ by unpacking $2\mid n$.

Example 6 — Empty subset

$\emptyset \subseteq \{1\}$: there is no counterexample element in $\emptyset$ outside $\{1\}$.

Example 7 — Inequality

$\emptyset \neq \{\emptyset\}$ because $\emptyset \in \{\emptyset\}$ but $\emptyset \notin \emptyset$.

Example 8 — Not subset

$\{1,2\} \nsubseteq \{1,3\}$ witness $2$.

Example 9 — Builder with two variables (preview)

$\{ (x,y) \in \mathbb{Z}^2 : x+y=0 \}$ is a set of pairs (Day 37 products).

Example 10 — Vacuous

Is $\{ n\in\mathbb{Z}: n^2 < 0 \} = \emptyset$? Yes, no integer has negative square.

Example 11 — Transitivity

If $A\subseteq B\subseteq C$ and $x\in A$ then $x\in B$ then $x\in C$.

Example 12 — Spec as set

Valid ports $= \{ p\in\mathbb{Z}: 1\le p \le 65535 \}$. Membership tests are predicate checks.

Example 13 — Equality failure one side

$A\subseteq B$ but not $B\subseteq A$ ⇒ not equal; still useful (subtype / subset of states).

Example 14 — Set of even primes

$\{ p : p\text{ prime and }2\mid p \} = \{2\}$ under standard primes.

Exercises

Rewrite $\{2,4,6,8\}$ in set-builder form as a subset of $\mathbb{Z}$.
List $\{ n\in\mathbb{Z}: 0 \le n < 5 \}$ in roster form.
Prove $\{1,2\} \subseteq \{1,2,3\}$.
Prove $\{1,2,3\} \nsubseteq \{1,2\}$ with a witness.
Prove $\emptyset \subseteq A$ for arbitrary $A$.
Prove $A \subseteq A$.
Determine true/false: $1 \in \{1\}$, $\{1\} \in \{1\}$, $\{1\} \subseteq \{1\}$, $1 \subseteq \{1\}$.
True/false: $\emptyset \in \emptyset$, $\emptyset \subseteq \emptyset$, $\emptyset \in \{\emptyset\}$, $\emptyset \subseteq \{\emptyset\}$.
Prove by double inclusion: $\{ n\in\mathbb{Z}: 6\mid n \} = \{ n\in\mathbb{Z}: 2\mid n \text{ and } 3\mid n \}$.
Show $\{0,1\} \neq \{0,1,0\}$. Wait—actually equal; explain.
Let $A=\{x\in\mathbb{R}: x^2 = 2\}$. Describe $A$.
Prove if $A\subseteq B$ and $B\subseteq A$ then $A=B$ (quote theorem).
Find all subsets of $\{a,b\}$ (roster of the power set preview).
Is $\{ n\in\mathbb{N}: n < 0 \}$ empty? Depends on $\mathbb{N}$—state convention.
Prove transitivity of $\subseteq$.
Give three different roster notations for the same set of two elements.
Translate to builder: “all strings of length $3$ over $\{0,1\}$.”
Witness: show $\{ n : n^2 = n \} \neq \emptyset$ in $\mathbb{Z}$.
Explain in your own words why Russell’s paradox blocks unrestricted comprehension.
Prove $\{\emptyset\} \neq \emptyset$.
If $A = B$ and $x\in A$, prove $x\in B$.
CS: express “set of all failed test names” in builder notation.
Decide $ {1,2} { {1,2} } $ — true or false?
Prove that if $A\subseteq\emptyset$ then $A=\emptyset$.
Double inclusion practice: $\{ n\in\mathbb{Z}: n\mid 6 \} = \{\pm1,\pm2,\pm3,\pm6\}$—prove carefully.

CS connection

Types ≈ sets of values (Day 44).
Database tables ≈ sets/bags of tuples; WHERE is set-builder.
Permissions = sets of actions; inheritance ≈ subsets.
Test coverage: set of covered lines $\subseteq$ set of lines.
Config feature flags as subsets of a universe of flags.
JSON objects are not pure sets, but key sets are.

Common pitfalls

Pitfall	What to do instead
Confusing $\in$ and $\subseteq$	Element vs set of elements
$\{a\} = a$	Rarely; $a$ may not be a set the same way
Order matters in sets	It does not
Forgetting vacuous $\emptyset\subseteq A$	Empty has no counterexample
Proving equality with one inclusion	Need both
Unrestricted comprehension	Always build from a known $U$
$\subset$ ambiguity	Prefer $\subseteq$ and $\subsetneq$

Checkpoint

Roster and builder fluency
Define $\in$, $\subseteq$, $=$
Prove equality by double inclusion once
Prove $\emptyset\subseteq A$
Distinguish $\emptyset$ and $\{\emptyset\}$
Russell awareness paragraph in own words
Exercises done or logged

Two takeaways:

Deep dive — comprehension discipline

Safe pattern: $\{ x \in U : P(x) \}$ with $U$ already a set.
Unsafe pattern: $\{ x : P(x) \}$ with $x$ ranging over “everything,” including sets that might create Russell-like trouble. In discrete math practice, $U$ is $\mathbb{Z}$, $\mathbb{R}$, $V$, strings, etc.

Element-chase templates

Show $A\subseteq B$:
Let $x\in A$. [unpack $A$]. … [pack $B$]. Thus $x\in B$. Since $x$ arbitrary, $A\subseteq B$.

Show $A=B$:
Show $A\subseteq B$ and $B\subseteq A$, then cite double inclusion.

Show $A\nsubseteq B$:
Produce concrete $x\in A\setminus B$.

Sets in specifications

Invariants are often “the set of open handles $\subseteq$ the set of allocated handles.”
Equality of sets of states is the strongest observational equivalence at that abstraction.

More worked examples

Example 15 — Builder equality
$\{ n\in\mathbb{Z}: n^2=1 \} = \{-1,1\}$ by solving.

Example 16 — Nested braces
$\{1\} \in \{\{1\}\}$ true; $\{1\} \subseteq \{\{1\}\}$ false.

Example 17 — Infinite builder
$\{ n\in\mathbb{N}: n\text{ even} \}$ cannot list fully—use builder or “$2\mathbb{N}$.”

Example 18 — Spec
Ports in use $= \{ p : \exists \text{socket bound to } p \}$ as a set comprehension over port universe.

Additional exercises

Prove if $A\subseteq B\subseteq A$ then $A=B$.
How many elements does $\{\emptyset, \{\emptyset\}, \{\emptyset,\{\emptyset\}\}\}$ have?
Write $\{0,1\}^n$ vs $\mathcal{P}([n])$—not equal as sets, but equinumerous.
Prove $A\subseteq B$ and $C\subseteq D$ need not imply $A\cup C \subseteq B\cap D$—counterexample.
Formalize “set of failed tests $\subseteq$ set of run tests.”

Extended practice workshop

Membership true/false battery

For $A=\{1,\{1\},\emptyset\}$, evaluate:

$1\in A$
$\{1\}\in A$
$\{1\}\subseteq A$
$\emptyset\in A$
$\emptyset\subseteq A$
$\{\emptyset\}\subseteq A$
$\{\emptyset\}\in A$
$A\in A$ (naive—should be false here)

Proof battery

$\emptyset\subseteq A$
$A\subseteq A$
Transitivity of $\subseteq$
Double inclusion $\Rightarrow$ equality
If $A\subseteq\emptyset$ then $A=\emptyset$
$\{n\in\mathbb{Z}:6\mid n\}=\{n:2\mid n\text{ and }3\mid n\}$

Builder practice

Evens as builder.
Primes as builder (no closed form expected).
$\{n: n^2<0\}$ in $\mathbb{R}$ and in $\mathbb{Z}$.
Valid TCP ports builder.

Spec practice

“Failed tests $\subseteq$ run tests” as sets.
“Admins $\subseteq$ users.”
When is equality the right claim vs mere inclusion?

Russell awareness

Restate the paradox in your own words.
Why $\{x\in\mathbb{Z}: P(x)\}$ is safe if $\mathbb{Z}$ is given.

Notation card

Symbol	Read as
$\in$	element of
$\subseteq$	subset of
$\subsetneq$	proper subset
$\emptyset$	empty set
$\{x\in U:P(x)\}$	builder

Synthesis

Sets turn predicates into objects: $\{x\in U:P(x)\}$ packages a property as a value you can pass around, compare, and later transform with $\cup,\cap$ (Day 36). The core proof skill is the element chase: to show $A\subseteq B$, take arbitrary $x\in A$ and derive $x\in B$. Equality is two inclusions—never “they look the same.”

Element-chase templates

Subset.
Let $x\in A$. … reason … Therefore $x\in B$. Since $x$ was arbitrary, $A\subseteq B$.

Equality.
Prove $A\subseteq B$ and $B\subseteq A$ separately; conclude $A=B$.

Inequality.
To show $A\neq B$, exhibit $x$ in one but not the other (or show one inclusion fails).

More worked examples

Example — Empty set is subset of every set.
Let $x\in\emptyset$. The premise is false, so $x\in\emptyset \rightarrow x\in A$ is vacuously true for every $x$. Hence $\emptyset\subseteq A$. (Equivalently: there is no counterexample $x\in\emptyset\setminus A$.)

Example — Builder equality.
$\{n\in\mathbb{Z}: n^2=n\}=\{0,1\}$. Prove $\subseteq$ by solving $n^2-n=0$; prove $\supseteq$ by checking $0,1$.

Example — Proper subset.
$\{1\}\subsetneq\{1,2\}$ because $\subseteq$ holds and $2$ witnesses inequality.

Example — Set vs element confusion.
$\emptyset\neq\{\emptyset\}$: left has no elements; right has one element, namely $\emptyset$. Also $\emptyset\in\{\emptyset\}$ but $\emptyset\notin\emptyset$.

Example — Spec as inclusion.
“Every admin is a user” is $\mathrm{Admins}\subseteq\mathrm{Users}$. “Admins are exactly the users with flag $A$” is equality of two builders.

Extra exercises (synthesis)

Prove: if $A\subseteq B$ and $B\subseteq C$ then $A\subseteq C$ (transitivity) by element chase.
Prove: $A\subseteq\emptyset$ implies $A=\emptyset$.
Disprove: $A\in B$ implies $A\subseteq B$ (give finite counterexample).
Write $\{n\in\mathbb{Z}: 6\mid n\}$ as an intersection of two builders (div by $2$ and by $3$).
Prove $\{n\in\mathbb{Z}: n>0\} = \{n\in\mathbb{Z}: n\ge 1\}$ under standard integer order.
Russell awareness: why unrestricted $\{x: x\notin x\}$ is not admitted as a set in this course’s working foundations.

Common Stage IV carry-forward

Habit	Payoff
Always name ambient $U$ for builders	Avoids “all sets” paradoxes
Double inclusion for equality	Standard in ops/relations proofs
Distinguish $\in$ vs $\subseteq$	Kills $\{\emptyset\}$ bugs
Vacuous truth for $\emptyset\subseteq A$	Matches quantifier Day 26

Roster for finite sets; builder for infinite or rule-defined sets. Tomorrow adds the algebra of combining sets.

Tomorrow

Day 36 — Set operations. $\cup,\cap,\setminus,\triangle$, complement; Venn reasoning; identities with proofs; power set; $|\mathcal{P}(S)|=2^{|S|}$.

Day 36 — Set operations

Stage IV · concept day
Goal: Master union, intersection, difference, symmetric difference, and complement; reason with Venn diagrams carefully; prove set identities; define the power set; prove $|\mathcal{P}(S)|=2^{|S|}$ for finite $S$ by induction or bitstring bijection.

Why this matters

Boolean combinations of sets are boolean combinations of membership predicates—the same algebra as Days 24–25 with $\in$ as the atom. Power sets appear in configuration spaces, subset DP, and “all subsets of permissions.” Counting $2^n$ subsets is a foundational counting fact.

Theory

Definitions (relative to elements)

Fix sets $A,B$ (and universe $U$ when complements appear).

\[ \begin{align*} A \cup B &= \{ x : x\in A \lor x\in B \},\\ A \cap B &= \{ x : x\in A \land x\in B \},\\ A \setminus B &= \{ x : x\in A \land x\notin B \},\\ A \triangle B &= (A\setminus B)\cup(B\setminus A) = (A\cup B)\setminus(A\cap B),\\ A^c &= U\setminus A = \{ x\in U : x\notin A \}. \end{align*} \]

$A$ and $B$ are disjoint when $A\cap B = \emptyset$.

Venn reasoning

Diagrams guide intuition for $2$–$3$ sets. They do not replace element-chase proofs for identities you must justify. For $n$ sets, $2^n$ regions—same explosion as truth tables.

Algebra of sets (selected identities)

\[ \begin{align*} A\cup B &= B\cup A, & A\cap B &= B\cap A,\\ (A\cup B)\cup C &= A\cup(B\cup C), & (A\cap B)\cap C &= A\cap(B\cap C),\\ A\cup(B\cap C) &= (A\cup B)\cap(A\cup C),\\ A\cap(B\cup C) &= (A\cap B)\cup(A\cap C),\\ A\cup\emptyset &= A, & A\cap\emptyset &= \emptyset,\\ A\cup U &= U, & A\cap U &= A,\\ A\cup A &= A, & A\cap A &= A,\\ A\cup A^c &= U, & A\cap A^c &= \emptyset,\\ (A^c)^c &= A,\\ (A\cup B)^c &= A^c \cap B^c, & (A\cap B)^c &= A^c \cup B^c && \text{(De Morgan)}. \end{align*} \]

Absorption: $A\cup(A\cap B)=A$, $A\cap(A\cup B)=A$.

These mirror Boolean algebra with $\cup\leftrightarrow\vee$, $\cap\leftrightarrow\wedge$, $^c\leftrightarrow\neg$.

Proving identities

Element chase: $x\in$ LHS iff (logic) iff $x\in$ RHS.
Double inclusion: LHS $\subseteq$ RHS and converse.
Algebraic rewrite using known identities (name them).
Characteristic vectors / indicator functions: $1_{A\cup B} = \max(1_A,1_B)$ or boolean or, etc.

Power set

\[\mathcal{P}(S) = \{ A : A \subseteq S \}\]
the set of all subsets of $S$. Always $\emptyset \in \mathcal{P}(S)$ and $S \in \mathcal{P}(S)$.

Cardinality of the power set (finite)

Theorem. If $|S|=n < \infty$, then $|\mathcal{P}(S)| = 2^n$.

Proof 1 (bitstrings). Fix enumeration $S=\{s_1,\ldots,s_n\}$. Map $A\subseteq S$ to $(b_1,\ldots,b_n)\in\{0,1\}^n$ with $b_i=1$ iff $s_i\in A$. This is a bijection. $|\{0,1\}^n|=2^n$. $\square$

Proof 2 (induction on $n$).
$n=0$: $\mathcal{P}(\emptyset)=\{\emptyset\}$, size $1=2^0$.
Assume true for $|S|=k$. Let $|T|=k+1$, pick $a\in T$, $S=T\setminus\{a\}$.
Subsets of $T$ partition into those not containing $a$ ($\mathcal{P}(S)$) and those containing $a$ ($\{ B\cup\{a\} : B\subseteq S \}$).
Sizes $2^k + 2^k = 2^{k+1}$. $\square$

Disjoint union (awareness)

Sometimes $A \sqcup B$ means disjoint union (tagged): copy sets to force disjointness. Distinct from $A\cup B$ when they overlap. Day 37 contrasts with products.

Inclusion indicators

$x\in A\cap B$ iff both memberships; truth table of $\wedge$. Set identities $\leftrightarrow$ propositional tautologies about membership.

Worked examples

Example 1 — Compute

$A=\{1,2,3\}$, $B=\{3,4\}$:
$A\cup B=\{1,2,3,4\}$, $A\cap B=\{3\}$, $A\setminus B=\{1,2\}$, $A\triangle B=\{1,2,4\}$.

Example 2 — De Morgan proof sketch

$x\in (A\cup B)^c \Leftrightarrow x\notin A\cup B \Leftrightarrow x\notin A \wedge x\notin B \Leftrightarrow x\in A^c \cap B^c$.

Example 3 — Distributivity element chase

$x\in A\cap(B\cup C) \Leftrightarrow x\in A \wedge (x\in B\vee x\in C) \Leftrightarrow \cdots \Leftrightarrow x\in (A\cap B)\cup(A\cap C)$.

Example 4 — Symmetric difference

$A\triangle A = \emptyset$, $A\triangle\emptyset = A$, $A\triangle B = B\triangle A$.

Example 5 — Power set small

$S=\{1,2\}$: $\mathcal{P}(S)=\{\emptyset,\{1\},\{2\},\{1,2\}\}$, size $4=2^2$.

Example 6 — Bitstring

$S=\{a,b,c\}$, subset $\{a,c\}$ ↔︎ $101$.

Example 7 — Complement depends on $U$

If $U=\mathbb{Z}$ and $A=$ evens, $A^c=$ odds. If $U=$ evens, $A^c=\emptyset$ when $A=U$.

Example 8 — Identity

$A\setminus B = A \cap B^c$ (prove by element chase).

Example 9 — Counting

$|A\cup B| = |A|+|B|-|A\cap B|$ for finite sets (inclusion-exclusion lite; Stage V deepens).

Example 10 — Partition via characteristic

For fixed $A$, universe splits into $A$ and $A^c$.

Example 11 — Prove $A\subseteq B \Leftrightarrow A\cup B = B$

⇒: if $A\subseteq B$, $A\cup B\subseteq B\cup B=B$, and $B\subseteq A\cup B$.
⇐: if $A\cup B=B$ then $A\subseteq A\cup B=B$.

Example 12 — $\mathcal{P}$ monotonic

If $A\subseteq B$ then $\mathcal{P}(A)\subseteq\mathcal{P}(B)$.

Example 13 — Not true

$\mathcal{P}(A\cup B) = \mathcal{P}(A)\cup\mathcal{P}(B)$ is false generally. Counterexample: $A=\{1\},B=\{2\}$, $\{1,2\}$ in left not in right.

Example 14 — Config space

$n$ independent boolean flags: $2^n$ configurations $=|\mathcal{P}([n])|$ if each subset is “enabled set.”

Exercises

Compute all of $\cup,\cap,\setminus,\triangle$ for $A=\{0,1,2\}$, $B=\{1,2,3\}$.
Prove $A\setminus B = A \cap B^c$.
Prove De Morgan $(A\cap B)^c = A^c \cup B^c$.
Prove distributivity $A\cup(B\cap C)=(A\cup B)\cap(A\cup C)$.
Prove $A\subseteq B \Leftrightarrow A\cap B = A$.
Prove $A\triangle B = (A\cup B)\setminus(A\cap B)$.
List $\mathcal{P}(\{1\})$ and $\mathcal{P}(\{\emptyset\})$.
Prove by induction $|\mathcal{P}(S)|=2^{|S|}$ for finite $S$.
Give the bitstring bijection proof in your own words.
Counterexample: $\mathcal{P}(A\cap B)=\mathcal{P}(A)\cap\mathcal{P}(B)$—is this true? Prove or disprove.
True or false: $\mathcal{P}(A\cup B)=\mathcal{P}(A)\cup\mathcal{P}(B)$.
Prove $(A^c)^c=A$.
If $A,B$ finite, prove $|A\setminus B| = |A|-|A\cap B|$.
Show $A$ and $A^c$ disjoint and union $U$.
Simplify $(A\cup B)\cap(A\cup B^c)$ .
Prove absorption $A\cup(A\cap B)=A$.
Venn: shade $(A\cap B)\setminus C$; describe in words.
How many subsets of an $n$-set contain a fixed element $a$?
How many subsets have even cardinality? (Binomial; state $\sum \binom{n}{2k}=2^{n-1}$ awareness.)
Prove $A\setminus(B\cup C)=(A\setminus B)\cap(A\setminus C)$.
CS: express active users as $Registered \setminus Banned$.
Prove $A\triangle B = \emptyset \Leftrightarrow A=B$.
If $|\mathcal{P}(S)|=32$, what is $|S|$?
Show there is no bijection between $S$ and $\mathcal{P}(S)$ for any set $S$ (Cantor; outline diagonal)—preview Day 43.
Prove $A\cap(B\setminus A)=\emptyset$.

CS connection

SQL UNION, INTERSECT, EXCEPT ≈ $\cup,\cap,\setminus$ (bag semantics caveats).
Permission sets: grant $= A\cup B$, revoke difference.
Feature flags power set of options.
Bitsets implement subsets of a fixed universe; OR/AND/NOT = $\cup/\cap/^c$.
Subset sum / DP over $\mathcal{P}([n])$ for small $n$.
De Morgan in firewall rules: deny all except…

Common pitfalls

Pitfall	What to do instead
Complement without universe	Fix $U$
Trusting Venn alone	Element chase for proofs
$\mathcal{P}(A\cup B)=\mathcal{P}(A)\cup\mathcal{P}(B)$	False; see counterexample
Counting $\mathcal{P}$ as $n$	$2^n$
Confusing $\setminus$ with $-$ on numbers	Set difference
Symmetric difference as intersection	It is XOR of membership

Checkpoint

Define $\cup\cap\setminus\triangle$ and complement
Prove one De Morgan and one distributive law
Define $\mathcal{P}(S)$ and list a small one
Prove $|\mathcal{P}(S)|=2^n$ two ways (sketch both)
Give counterexample for a false power-set identity
Exercises done or logged

Two takeaways:

Deep dive — indicator functions

For $A\subseteq U$, the indicator $1_A: U\to\{0,1\}$ has $1_A(x)=1$ iff $x\in A$. Then:

\[ \begin{align*} 1_{A\cap B} &= 1_A \cdot 1_B,\\ 1_{A\cup B} &= 1_A + 1_B - 1_A 1_B,\\ 1_{A^c} &= 1 - 1_A,\\ 1_{A\triangle B} &= 1_A + 1_B \bmod 2. \end{align*} \]

Set algebra ↔︎ arithmetic on indicators ↔︎ boolean algebra on membership bits. Bitsets in programming are indicators of subsets of a fixed universe.

Counting subsets with structure

Subsets containing fixed $a$: $2^{n-1}$.
Subsets of size $k$: $\binom{n}{k}$ (Stage V).
Even-sized subsets: $2^{n-1}$ for $n\ge 1$.

Power set functoriality

If $f: A\to B$, define $\mathcal{P}(f): \mathcal{P}(A)\to\mathcal{P}(B)$ by $S\mapsto f(S)=\{f(x):x\in S\}$ (direct image). Not to be confused with preimage $f^{-1}(T)$.

More worked examples

Example 15 — Simplify
$(A\cup B)\cap(A\cup B^c)\cap(A^c\cup B)$ stepwise.

Example 16 — Symmetric difference associative
$A\triangle(B\triangle C)=(A\triangle B)\triangle C$ (indicator mod 2).

Example 17 — Power set size
$|\mathcal{P}(\mathcal{P}(\{1\}))|=|\mathcal{P}(\{\emptyset,\{1\}\})|=4$.

Example 18 — Disjointify
$A\setminus B$ and $A\cap B$ partition $A$.

Additional exercises

Prove $A\triangle B = A^c\triangle B^c$.
Prove by induction $|\mathcal{P}(S)|=2^{|S|}$ writing the partition step carefully.
Show $\mathcal{P}(A)\cap\mathcal{P}(B)=\mathcal{P}(A\cap B)$.
Disprove $\mathcal{P}(A)\cup\mathcal{P}(B)=\mathcal{P}(A\cup B)$.
Bitset: express $A\subseteq B$ as a bitwise condition on indicators.

Extended practice workshop

Compute on $A=\{1,2,3\}$, $B=\{2,3,4\}$, $U=\{1,2,3,4,5\}$

$A\cup B$, $A\cap B$, $A\setminus B$, $B\setminus A$, $A\triangle B$
$A^c$, $B^c$
$(A\cup B)^c$ and $A^c\cap B^c$—match
$(A\cap B)^c$ and $A^c\cup B^c$—match

Identity proofs (element chase)

Distributivity $A\cap(B\cup C)$
De Morgan one form
$A\setminus B=A\cap B^c$
$A\subseteq B\Leftrightarrow A\cup B=B$
$A\subseteq B\Leftrightarrow A\cap B=A$
$A\triangle B=\emptyset\Leftrightarrow A=B$

Power set

List $\mathcal{P}(\{a,b\})$
List $\mathcal{P}(\{\emptyset\})$
Induction proof $|\mathcal{P}|=2^n$
Bitstring proof sketch
Counterexample $\mathcal{P}(A\cup B)=\mathcal{P}(A)\cup\mathcal{P}(B)$
Prove $\mathcal{P}(A\cap B)=\mathcal{P}(A)\cap\mathcal{P}(B)$

Counting

Subsets of $n$-set containing a fixed element
$|A\cup B|$ given sizes and intersection
$|\mathcal{P}(\mathcal{P}(\emptyset))|$

CS

Bitwise AND/OR/NOT as $\cap/\cup/^c$ on bitsets.
Feature flags as elements of $\mathcal{P}(F)$.
SQL EXCEPT as $\setminus$.

Indicator cheat sheet

$1_{A\cap B}=1_A 1_B$, $1_{A^c}=1-1_A$, $1_{A\triangle B}\equiv 1_A+1_B\pmod 2$.

Synthesis

Set operations are the boolean algebra of collections: $\cup$ like $\vee$, $\cap$ like $\wedge$, complement like $\neg$. Element-chase proofs of identities are the same muscle as truth-table or algebraic boolean proofs, rephrased with $\in$. Power sets shift attention from elements of $S$ to subsets of $S$—critical for relations ($\mathcal{P}(A\times B)$) and state spaces.

Proof patterns for identities

Element chase both sides of $X=Y$ via double inclusion.
Indicator algebra on a fixed universe: rewrite $1_X$ and compare.
Known laws (De Morgan, distributivity) in a chain with names—like Day 24.

More worked examples

Example — Distributivity chase.
$x\in A\cap(B\cup C)$ iff $x\in A$ and ($x\in B$ or $x\in C$) iff ($x\in A\cap B$ or $x\in A\cap C$) iff $x\in (A\cap B)\cup(A\cap C)$.

Example — Set difference as intersection.
$A\setminus B = A\cap B^c$ by unfolding: $x\in A$ and $x\notin B$.

Example — Subset via union.
$A\subseteq B \Leftrightarrow A\cup B=B$: if subset, union adds nothing; if union equals $B$, every $x\in A$ is in the union hence in $B$.

Example — Power set size.
For $S=\{1,2,3\}$, list $8$ subsets. Inductive idea: subsets of $S\cup\{a\}$ split into those without $a$ ($\mathcal{P}(S)$) and those with $a$ (same count).

Example — Counterexample $\mathcal{P}(A)\cup\mathcal{P}(B)=\mathcal{P}(A\cup B)$.
$A=\{1\}$, $B=\{2\}$: $\{1,2\}\in\mathcal{P}(A\cup B)$ but $\{1,2\}$ is neither a subset of $A$ nor of $B$, so not in the union of power sets.

Extra exercises (synthesis)

Prove $(A\setminus B)\setminus C = A\setminus(B\cup C)$.
Prove $A\triangle B = (A\cup B)\setminus(A\cap B)$.
Show $A\subseteq B \Leftrightarrow B^c \subseteq A^c$.
Compute $|\mathcal{P}(\mathcal{P}(\{1\}))|$.
If $|A|=n$, how many subsets have even cardinality? (Binomials preview—or compute for $n\le 4$ and conjecture.)
Bitset: explain $A\cap B$ as bitwise AND of characteristic vectors of length $|U|$.

Identity priority list (memorize proofs of)

Identity	Why first
De Morgan (both)	Complements in specs
$A\setminus B=A\cap B^c$	Rewrite tool
Distributivity one direction	Case reasoning
$A\subseteq B\Leftrightarrow A\cap B=A$	Spec refinement
$\|\mathcal{P}(S)\|=2^{\|S\|}$	Counting backbone

Venn diagrams are discovery tools; element chase is the proof. Indicators are a power-user shortcut once membership reasoning is solid.

Tomorrow

Day 37 — Products & tuples. $A\times B$; $n$-tuples; $|A\times B|=|A||B|$; relations as subsets of products (preview); disjoint union vs product.

Day 37 — Products & tuples

Stage IV · concept day
Goal: Define Cartesian products and $n$-tuples; count $|A\times B|=|A||B|$ (finite); see relations as subsets of products; contrast disjoint union with product; connect to records, schemas, and nested loops.

Why this matters

A pair $(user, role)$ lives in a product. Database rows are $n$-tuples; multiple loop indices range over products; graphs’ edge sets are subsets of $V\times V$ (or unordered pairs). Relations and functions (Days 38–42) are specialized subsets of products.

Theory

Ordered pairs

An ordered pair $(a,b)$ satisfies $(a,b)=(c,d)$ iff $a=c$ and $b=d$.
Order matters: $(1,2)\neq(2,1)$.
(Set-theoretic encoding $(a,b)=\{\{a\},\{a,b\}\}$ is optional awareness.)

Cartesian product

\[A \times B = \{ (a,b) : a\in A,\; b\in B \}.\]

If $A=\emptyset$ or $B=\emptyset$ then $A\times B=\emptyset$.

$n$-tuples and $n$-fold products

\[A_1 \times A_2 \times \cdots \times A_n = \{ (a_1,\ldots,a_n) : a_i\in A_i \}.\]

\[A^n = \underbrace{A\times\cdots\times A}_{n\text{ times}}.\]

Associativity up to canonical bijection: $(A\times B)\times C \cong A\times(B\times C)$ via $((a,b),c)\mapsto(a,(b,c))\mapsto(a,b,c)$.

Finite counting

Theorem. If $A,B$ finite, $|A\times B| = |A|\cdot|B|$.

Proof. For each of $|A|$ choices of first coordinate, $|B|$ choices of second. $\square$

More generally $|A_1\times\cdots\times A_n| = \prod_i |A_i|$.
$|A^n| = |A|^n$.

Relations as subsets (preview)

A binary relation from $A$ to $B$ is any $R \subseteq A\times B$.
We write $a\,R\,b$ for $(a,b)\in R$. Day 38 studies properties on $A\times A$.

Graphs (preview)

Directed graph: edge set $E\subseteq V\times V$.
Undirected simple: edges as $2$-subsets, related but not identical to $V\times V$.

Disjoint union vs product

Disjoint union (tagged sum):
\[A \sqcup B = (\{0\}\times A) \cup (\{1\}\times B).\]
Elements are either from $A$ or from $B$ (with tags).
$|A\sqcup B| = |A|+|B|$ if we use this tagging (always disjoint).

Product: elements are both an $A$ and a $B$ coordinate.
$|A\times B|=|A||B|$.

In programming: sum types / enums with payload ≈ disjoint union; structs with two fields ≈ product (Day 44).

Projections

$\pi_1: A\times B \to A$, $\pi_1(a,b)=a$; $\pi_2(a,b)=b$.
Surjective if the other factor is nonempty.

Sections / fibers

For $a\in A$, the fiber $\{b : (a,b)\in R\}$ for $R\subseteq A\times B$.

Nested loops

for a in A:
  for b in B:
    body

runs $|A|\cdot|B|$ times—iteration over $A\times B$.

Worked examples

Example 1 — Small product

$A=\{1,2\}$, $B=\{x,y,z\}$:
$A\times B = \{(1,x),(1,y),(1,z),(2,x),(2,y),(2,z)\}$, size $6$.

Example 2 — Noncommutativity

$A\times B \neq B\times A$ in general as sets of pairs (different coordinate types/order), though equinumerous if finite.

Example 3 — Empty

$\emptyset \times \{1,2\} = \emptyset$.

Example 4 — $A^2$

$\{0,1\}^2 = \{(0,0),(0,1),(1,0),(1,1)\}$.

Example 5 — Relation

$R = \{ (n,m)\in\mathbb{Z}^2 : n < m \} \subseteq \mathbb{Z}\times\mathbb{Z}$.

Example 6 — Count functions preview

Number of functions $A\to B$ is $|B|^{|A|}$ (Day 41–42)—each element of $A$ picks an image in $B$, product of choices.

Example 7 — Schema

Row type $Users\times Roles$ vs relation $Assigned \subseteq Users\times Roles$.

Example 8 — Disjoint union size

$|\{a,b\} \sqcup \{b,c\}| = 4$ tagged, while $|\{a,b\}\cup\{b,c\}|=3$.

Example 9 — Triple loop

$|A\times B\times C|=|A||B||C|$.

Example 10 — Diagonal

$\Delta_A = \{(a,a): a\in A\} \subseteq A\times A$ (equality relation).

Example 11 — Bijection reassociation

Map $((a,b),c)\mapsto(a,b,c)$ is bijective between $(A\times B)\times C$ and $A\times B\times C$.

Example 12 — Boolean cube

$\{0,1\}^n$ has $2^n$ points—bitstrings of length $n$.

Example 13 — Grid

Pixel coordinates $\{1,\ldots,W\}\times\{1,\ldots,H\}$.

Example 14 — Subset of product

$\{ (x,y)\in\mathbb{R}^2 : x^2+y^2 = 1 \}$ unit circle—not a full product.

Exercises

List $\{a,b\}\times\{1,2\}$.
Compute $|\mathbb{Z}/5\mathbb{Z} \times \mathbb{Z}/2\mathbb{Z}|$ if $|\mathbb{Z}/n\mathbb{Z}|=n$.
Prove $A\times B = \emptyset \Leftrightarrow A=\emptyset \lor B=\emptyset$.
Show by counterexample $A\times B = B\times A$ can fail.
How many elements in $\{1,2,3\}^4$?
Define $R\subseteq\{1,2,3\}^2$ as $\le$ on numbers; list pairs.
Prove $|A\times B|=|A||B|$ for finite sets carefully (double count).
Give a bijection $(A\times B)\times C \to A\times(B\times C)$.
Express disjoint union of $\{0,1\}$ and $\{0,1\}$ as a $4$-element set of tagged pairs.
Count nested loop iterations: $i\in A$, $j\in B$, $k\in C$.
Is $(A\cup B)\times C = (A\times C)\cup(B\times C)$? Prove.
Is $(A\cap B)\times C = (A\times C)\cap(B\times C)$? Prove.
Disprove $(A\times B)\cup(C\times D) = (A\cup C)\times(B\cup D)$ in general.
Describe $\pi_1^{-1}(\{a\})$ as a subset of $A\times B$.
CS: model HTTP request as product of method set and path set (simplified).
How many directed edges possible on vertex set $V$ (allowing loops)? $|V|^2$.
Without loops: $|V|(|V|-1)$.
Define equality relation on $A$ as a subset of $A\times A$.
If $|A|=n$, how many subsets does $A\times A$ have?
Compare $|A\sqcup A|$ and $|A\times\{0,1\}|$—bijection?
Prove if $A\subseteq C$, $B\subseteq D$ then $A\times B \subseteq C\times D$.
Tuples: when is $(a,b,c)=(d,e,f)$?
Bitmasks: identify $\mathcal{P}([n])$ with $\{0,1\}^n$ again.
Give a real schema with $4$ attributes as a product of domains.
Explain in one paragraph product vs sum types for a “Result” value (preview Day 44).

CS connection

Structs / records = products of field types.
JOIN in databases multiplies row spaces (then filters).
Nested loops iterate products.
Configuration grids hyperparameter products.
Pairing heap keys, coordinates, key-value stores.
Graph adjacency as subset of $V\times V$.

Common pitfalls

Pitfall	What to do instead
Treating pairs as sets $\{a,b\}$	Order and repetition differ
$A\times B=B\times A$ as sets	Only equinumerous in general
Empty product mistakes	Any empty factor empties product
Confusing $\cup$ of products with product of $\cup$	See Exercise 13
Counting undirected edges as $\|V\|^2$	Adjust for order and loops
Forgetting tags in disjoint union	Overlap collapses $\cup$

Checkpoint

Define $A\times B$ and $A^n$
Count finite products
Give relation as subset of product
Contrast $\sqcup$ and $\times$
Prove one distributive law over $\times$
Exercises done or logged

Two takeaways:

Deep dive — currying and exponential (awareness)

Maps $A\times B\to C$ biject with maps $A\to (B\to C)$ (currying) when working with pure total functions:
\[C^{A\times B} \cong (C^B)^A.\]
This is the set-theoretic root of “a function of two arguments is a function returning a function.” Day 44 types will echo this.

Counting recap

Object	Count (finite)
$A\times B$	$\\|A\\|\\|B\\|$
$A^n$	$\\|A\\|^n$
relations on $A$	$2^{n^2}$ if $\\|A\\|=n$
functions $A\to B$	$\\|B\\|^{\\|A\\|}$
subsets of $A\times B$	$2^{\\|A\\|\\|B\\|}$

Distributivity laws (prove by element chase)

\[ \begin{align*} (A\cup B)\times C &= (A\times C)\cup(B\times C),\\ (A\cap B)\times C &= (A\times C)\cap(B\times C),\\ A\times(B\cup C) &= (A\times B)\cup(A\times C). \end{align*} \]

More worked examples

Example 15 — Non-example of product
Unit circle $\neq$ product of two nontrivial intervals in a simple way.

Example 16 — Database
SELECT * FROM A CROSS JOIN B has $|A||B|$ rows before WHERE.

Example 17 — Identity
$A\times\{*\}\cong A$ via $(a,*)\mapsto a$.

Example 18 — Tagging
$A+A \cong A\times\{0,1\}$ as sets.

Additional exercises

Prove the three distributivity identities above.
Count binary relations from a $3$-set to a $4$-set.
Give a bijection $A\times B\to B\times A$.
Show $(A\times B)\times(C\times D)$ equinumerous with $A\times B\times C\times D$.
Model a key-value store state as a function $K\to V$ vs relation $K\times V$.

Extended practice workshop

Listing and counting

List $\{0,1\}\times\{a,b,c\}$.
$|\{1,\ldots,10\}^3|$.
$|A\times B|$ if $|A|=0$.
Number of subsets of $A\times A$ for $|A|=3$.
Number of binary relations on a $4$-set.

Algebra of products

Prove $(A\cup B)\times C=(A\times C)\cup(B\times C)$.
Prove $(A\cap B)\times C=(A\times C)\cap(B\times C)$.
Counterexample for $(A\times B)\cup(C\times D)=(A\cup C)\times(B\cup D)$.
Bijection $(A\times B)\times C\cong A\times B\times C$.
Bijection $A\times B\cong B\times A$.

Relations preview

List $\le$ on $\{1,2,3\}$ as pairs.
Equality $\Delta_A$ as a set.
“$m$ divides $n$” on $\{1,2,3,4\}$ as pairs.

Disjoint union

Write $\{0,1\}\sqcup\{0,1\}$ as tagged pairs.
Compare $|A\cup B|$ vs $|A\sqcup B|$ when overlap.

CS scenarios

Nested loop counts as $|A\times B\times C|$.
Grid coordinates.
Schema as product of domains.
Directed edges $\subseteq V\times V$.
Key-value as function vs as relation $\subseteq K\times V$.

Product vs sum card

	Product $A\times B$	Sum $A\sqcup B$
Element	both	either
Count	multiply	add
Code	struct	enum/variant

Synthesis

Cartesian products are how discrete math packages joint data: pairs, records, grid points, edges as ordered pairs. Counting multiplies; algebra distributes over $\cup$/$\cap$ with care. Relations (tomorrow) are subsets of products—so every product identity you prove today pays rent immediately.

Mental model

$A\times B$: an element is a pair $(a,b)$ with both components.
$A\sqcup B$: an element is a tagged value from $A$ or from $B$ (disjoint union).
$A\to B$ (later): an element is a function—equivalently a special subset of $A\times B$ (functional relation).

More worked examples

Example — Empty product.
$A\times\emptyset=\emptyset$: there is no pair $(a,b)$ with $b\in\emptyset$. Same for $\emptyset\times B$. Counting: $|A|\cdot 0=0$.

Example — Distributivity.
$(A\cup B)\times C = (A\times C)\cup(B\times C)$ by unfolding membership of pairs.
Fails for outer union of products: $(A\times B)\cup(C\times D)$ need not equal $(A\cup C)\times(B\cup D)$—counterexample $A=C=\{1\}$, $B=\{x\}$, $D=\{y\}$: right side contains $(1,y)$ and $(1,x)$ etc. in ways left may miss or… standard counterexample: $A=\{1\},B=\{a\},C=\{2\},D=\{b\}$; $(1,b)$ is in the product of unions but not in either $A\times B$ or $C\times D$.

Example — Counting nested loops.
for a in A: for b in B: for c in C runs $|A||B||C|$ iterations when loops are independent—literal $|A\times B\times C|$.

Example — Bijection swap.
$\varphi:A\times B\to B\times A$, $\varphi(a,b)=(b,a)$ is bijective with inverse the same pattern. So $|A\times B|=|B\times A|$ even though ordered pairs care about order.

Example — Relations as subsets.
On $A=\{1,2,3\}$, the relation $\le$ is the set of pairs $\{(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)\}\subseteq A\times A$. Number of all binary relations on $A$: $2^{|A|^2}=2^9=512$.

Extra exercises (synthesis)

Prove $A\times(B\cap C)=(A\times B)\cap(A\times C)$.
Prove $A\times(B\cup C)=(A\times B)\cup(A\times C)$.
Give a counterexample to $(A\times B)\cap(C\times D)=(A\cap C)\times(B\cap D)$ or prove it (it is true—prove).
Count $|\{0,1\}^n|$ and interpret as bitstrings / subsets via characteristic vectors.
Model a directed multigraph without multi-edges as $E\subseteq V\times V$. When would you want $E\subseteq V\times V\times L$ (labeled edges)?
Compare $|A\cup B|$ and $|A\sqcup B|$ when $A\cap B\neq\emptyset$.

Product algebra priority

Claim	Status
$(A\cup B)\times C=(A\times C)\cup(B\times C)$	True
$(A\cap B)\times C=(A\times C)\cap(B\times C)$	True
$(A\times B)\cup(C\times D)=(A\cup C)\times(B\cup D)$	False in general
$A\times\emptyset=\emptyset$	True
$\|A\times B\|=\|A\|\|B\|$ (finite)	True

Tomorrow: properties of subsets of $A\times A$ (and $A\times B$)—reflexive, symmetric, transitive, and friends.

Tomorrow

Day 38 — Relations. Binary relations; digraph/matrix; reflexive/symmetric/transitive/antisymmetric; closures; composition.

Object	Count (finite)
\(A\times B\)	\(\\|A\\|\\|B\\|\)
\(A^n\)	\(\\|A\\|^n\)
relations on \(A\)	\(2^{n^2}\) if \(\\|A\\|=n\)
functions \(A\to B\)	\(\\|B\\|^{\\|A\\|}\)
subsets of \(A\times B\)	\(2^{\\|A\\|\\|B\\|}\)

Day 13 — Sets, Set Operations & Cartesian Products

Day 35 — Sets

Why this matters

Theory

What is a set? (naive view)

Roster notation

Set-builder notation

Equality of sets

Subset and proper subset

Empty set

Universe of discourse

Standard number sets (notation)

Russell’s paradox (awareness, one paragraph)

Proving \(A \subseteq B\)

Proving \(A \neq B\)

Singleton and pairing

Sets of sets

Worked examples

Exercises

CS connection

Common pitfalls

Checkpoint

Deep dive — comprehension discipline

Element-chase templates

Sets in specifications

More worked examples

Additional exercises

Extended practice workshop

Membership true/false battery

Proof battery

Builder practice

Spec practice

Russell awareness

Notation card

Synthesis

Element-chase templates

More worked examples

Extra exercises (synthesis)

Common Stage IV carry-forward

Tomorrow

Day 36 — Set operations

Why this matters

Theory

Definitions (relative to elements)

Venn reasoning

Algebra of sets (selected identities)

Proving identities

Power set

Cardinality of the power set (finite)

Disjoint union (awareness)

Inclusion indicators

Worked examples

Exercises

CS connection

Common pitfalls

Checkpoint

Deep dive — indicator functions

Counting subsets with structure

Power set functoriality

More worked examples

Additional exercises

Extended practice workshop

Compute on \(A=\{1,2,3\}\), \(B=\{2,3,4\}\), \(U=\{1,2,3,4,5\}\)

Identity proofs (element chase)

Power set

Counting

CS

Indicator cheat sheet

Synthesis

Proof patterns for identities

More worked examples

Extra exercises (synthesis)

Identity priority list (memorize proofs of)

Tomorrow

Day 37 — Products & tuples

Why this matters

Theory

Ordered pairs

Cartesian product

\(n\)-tuples and \(n\)-fold products