Lesson overview | Previous part | Lesson overview

Sets and Logic: Part 13: Common Mistakes and Misconceptions to 16. Conceptual Bridge

13. Common Mistakes and Misconceptions

---

14. Exercises

Exercise 1: Set Operations (Warm-up)

Given $A = \{1, 2, 3, 4, 5\}$, $B = \{3, 4, 5, 6, 7\}$, $C = \{5, 6, 7, 8, 9\}$, compute:

1. $A \cup B$
2. $A \cap B \cap C$
3. $A - B$
4. $A \triangle B$ (symmetric difference)
5. $(A \cup B) \cap C$
6. $A \cap (B \cup C)$
7. Verify De Morgan's law: $(A \cup B)^c = A^c \cap B^c$ (with $U = \{1,\ldots,9\}$)
8. $\mathcal{P}(\{1,2,3\})$ - list all elements

Exercise 2: Relations

Let $A = \{1, 2, 3, 4\}$ and $R = \{(1,1), (1,2), (2,1), (2,2), (3,3), (4,4), (3,4), (4,3)\}$.

1. Is $R$ reflexive? Symmetric? Transitive?
2. Is $R$ an equivalence relation? If yes, find the equivalence classes.
3. Draw the relation as a directed graph.
4. Write $R$ as a Boolean matrix.

Exercise 3: Partial Orders

Consider the divisibility relation $|$ on the set $S = \{1, 2, 3, 4, 6, 12\}$ ($a \mid b$ iff $a$ divides $b$).

1. Verify that $|$ is a partial order on $S$ (check reflexivity, antisymmetry, transitivity).
2. Draw the Hasse diagram.
3. Find all maximal elements, minimal elements, greatest element, least element.
4. Is $(S, |)$ a total order? Why or why not?
5. Find all chains of maximum length.

Exercise 4: Propositional Logic

1. Construct truth tables for:
   • $(p \to q) \wedge (q \to r) \to (p \to r)$ - is this a tautology?
   • $(p \wedge q) \to p$ - simplification law
   • $\neg(p \to q) \leftrightarrow (p \wedge \neg q)$
2. Prove or disprove: $(p \to q) \equiv (\neg q \to \neg p)$ (using truth tables).
3. Convert to CNF: $p \to (q \vee r)$.
4. Convert to DNF: $\neg(p \wedge q) \vee r$.

Exercise 5: Predicate Logic

Translate to FOL (define your predicates):

1. "Every transformer has at least one attention head."
2. "No model with zero parameters can learn."
3. "There exists a learning rate that makes every batch converge."
4. "For every $\varepsilon > 0$, there exists $N$ such that for all $n > N$, $|a_n - L| < \varepsilon$."
5. Negate statement (3) formally and interpret in English.

Exercise 6: Proof Practice

Prove each of the following using the specified technique:

1. Direct proof: If $n$ is odd, then $n^2$ is odd.
2. Contrapositive: If $n^2$ is divisible by 3, then $n$ is divisible by 3.
3. Contradiction: $\log_2 3$ is irrational.
4. Induction: For all $n \geq 1$: $\sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6}$.
5. Cases: For all integers $n$: $n^3 - n$ is divisible by 6.

Exercise 7: Cardinality

1. Prove that $|(0, 1)| = |\mathbb{R}|$ by constructing an explicit bijection.
2. Prove that $|\mathbb{N} \times \mathbb{N}| = |\mathbb{N}|$ using the Cantor pairing function.
3. Explain why the set of all Python programs is countable.
4. Explain why the set of all functions $\mathbb{N} \to \{0, 1\}$ is uncountable. (Hint: relate to $\mathcal{P}(\mathbb{N})$.)
5. A vocabulary has $|V| = 32{,}000$ tokens. How many distinct prompts of length exactly $n$ exist? Of length at most $n$?

Exercise 8: AI Applications

1. Attention mask logic: A sliding window attention mask allows query $i$ to attend to key $j$ iff $|i - j| \leq w$. A causal mask allows $i$ to attend to $j$ iff $j \leq i$. Write the combined mask as a set: $M = \{(i, j) \mid \ldots\}$. Is $M$ an equivalence relation? A partial order?

2. Tokeniser as equivalence: Define an equivalence relation on $\{a, b, c\}^*$ where two strings are equivalent iff they map to the same token sequence under the BPE merges: $ab \to X$. List the equivalence classes (up to length 3).

3. Loss convergence as FOL: Write the formal statement "SGD converges to a critical point" using quantifiers. Then write its negation and interpret what it means for training to fail.

4. Function composition: A model has: embedding $E: V \to \mathbb{R}^{768}$, encoder $T: \mathbb{R}^{n \times 768} \to \mathbb{R}^{n \times 768}$ (12 layers), and head $H: \mathbb{R}^{768} \to \mathbb{R}^{|V|}$. Write the full model as a composition. Is the composition associative? Does the order matter?

---

15. Why This Matters for AI

15.1 Summary of Connections

16. Conceptual Bridge

16.1 What to Study Next

Now that you have the foundations of sets and logic, the natural next steps are:

1. Functions and Mappings (Chapter 03): Deepens the treatment of functions from 4.5 - injectivity, surjectivity, inverse functions, and their role in defining neural network layers precisely.

2. Linear Algebra (Chapters 02-03): Sets and logic provide the language for defining vector spaces, subspaces, and linear maps rigorously. Every "for all" and "there exists" in a linear algebra textbook uses the predicate logic from 6.

3. Calculus (Chapters 04-05): The $\varepsilon$-$\delta$ definition of continuity ($\forall \varepsilon > 0, \exists \delta > 0, \forall x, |x - a| < \delta \to |f(x) - f(a)| < \varepsilon$) is a nested quantifier statement from 6.5. Optimisation theory builds on this.

4. Probability Theory (Chapters 06-07): Built entirely on measure theory, which is set theory on steroids. Events are sets, probability is a set function, and conditional probability uses set intersection.

5. Information Theory (Chapter 09): Cross-entropy and KL divergence are defined using sets (probability distributions), logarithms (built from real numbers, which are built from sets), and summations (which are disguised quantifiers).

16.2 The Big Picture

     +-----------------------------------------------------+
     |                  THIS CHAPTER                        |
     |                                                      |
     |   Sets ---- Logic ---- Proofs ---- Axioms            |
     |    |          |          |            |               |
     |    v          v          v            v               |
     |  Data      Masks     Theory     Foundations          |
     | structures  & rules   papers     of math             |
     |    |          |          |            |               |
     |    +----------+----------+------------+               |
     |                    |                                  |
     |                    v                                  |
     |          +-----------------+                         |
     |          |    EVERYTHING    |                         |
     |          |   IN MATH/CS    |                         |
     |          |   BUILDS HERE   |                         |
     |          +-----------------+                         |
     +-----------------------------------------------------+

Sets and logic are the lingua franca of mathematics. Every mathematical definition, theorem, and proof uses the language developed in this chapter. When you encounter a statement like:

"For every $\varepsilon > 0$, there exists a neural network $N$ with at most $n(\varepsilon)$ neurons such that $\|N - f\|_\infty < \varepsilon$"

You now know:

• $\forall \varepsilon > 0$ - universal quantifier (6.2)
• $\exists N$ - existential quantifier (6.2)
• $\|N - f\|_\infty < \varepsilon$ - a predicate (6.1)
• The whole statement is a nested $\forall\exists$ claim (6.5)
• It can be proved by construction (7.8) or contradiction (7.4)
• The set of all such networks has a specific cardinality (10)

You can read mathematics now. The rest of this course builds on this foundation.