Equality as a logical primitive — axioms and Leibniz's rule.
Normal forms — Prenex (PNF), Skolem, CNF / DNF.
Quantifier rules of inference (UI, UG, EI, EG).
Standard theorems with full proofs.
Translation patterns and counter-examples.
Bibliography.
References: Rosen, Discrete Mathematics and Its Applications, 8e, §1.4–1.5; Velleman, How To Prove It, 3e, ch. 2; Mendelson, Introduction to Mathematical Logic, 6e, ch. 2; Cori & Lascar, Mathematical Logic, vol. 1; Lalement, Logique, réduction, résolution.
2 / 32
1.1 Predicates — formal definition
Let $D$ be a non-empty set. A predicate (or propositional function) of arity $n \in \mathbb{N}$ on $D$ is a map
$$P : D^n \;\longrightarrow\; \{\,\mathtt{T},\,\mathtt{F}\,\}.$$
For each tuple $(a_1,\dots,a_n)\in D^n$, the value $P(a_1,\dots,a_n)$ is a proposition (a truth value).
Notation we will use throughout: $P(x)$, $Q(x,y)$, $R(x_1,\dots,x_n)$. The variables $x,y,x_i$ are placeholders, replaced by elements of $D$ to obtain a proposition.
On $D = \mathbb{Z}$, let $P(x) := (x > 0)$. Then $P(3)=\mathtt T$, $P(-1)=\mathtt F$, while the formula $P(x)$ alone has no truth value — it is a function, not a proposition.
Rosen 8e, §1.4, p. 39; Mendelson 6e, §2.1.
3 / 32
1.2 Arity of a predicate
The arity of a predicate $P$ is the number $n$ of arguments it takes. We speak of $0$-ary, unary ($n=1$), binary ($n=2$), ternary ($n=3$), and in general $n$-ary predicates.
Arity
Form
Example on $\mathbb{Z}$
$0$-ary
$P$
$P := (1+1=2)$ — a plain proposition.
Unary
$P(x)$
$\mathrm{Even}(x) := (\exists k\;x=2k)$.
Binary
$R(x,y)$
$x \mid y$ — "$x$ divides $y$".
Ternary
$T(x,y,z)$
$x + y = z$.
$n$-ary
$P(x_1,\dots,x_n)$
$x_1 + x_2 + \dots + x_n = 0$.
Cori & Lascar, vol. 1, §3.1; Rosen 8e, p. 40.
4 / 32
1.3 Domain of discourse (universe $U$)
The domain of discourse (or universe) of a quantified statement is the set $U$ over which the bound variables range. The truth value of $\forall x\,P(x)$ and $\exists x\,P(x)$ is computed only against this $U$.
The same predicate can become true or false depending on $U$:
Formula
$U=\mathbb{N}$
$U=\mathbb{Z}$
$\forall x\,(x \geq 0)$
True
False
$\exists x\,(x + 1 = 0)$
False
True
$\forall x\,\exists y\,(y < x)$
False ($x=0$)
True
A quantified statement is incomplete without its universe. Always declare $U$ explicitly — e.g. "for all $x \in \mathbb{R}$".
Rosen 8e, §1.4, p. 41; Velleman 3e, §2.2.
5 / 32
1.4 Terms, atomic formulas, well-formed formulas
A first-order language $\mathcal{L}$ consists of: variables $x,y,z,\dots$, constants $c,d,\dots$, function symbols $f,g,\dots$ (each of fixed arity), and predicate symbols $P,Q,R,\dots$ (each of fixed arity). The grammar is inductive.
Terms
Every variable is a term.
Every constant is a term.
If $f$ is an $n$-ary function symbol and $t_1,\dots,t_n$ are terms, then $f(t_1,\dots,t_n)$ is a term.
Atomic formulas
If $P$ is an $n$-ary predicate symbol and $t_1,\dots,t_n$ are terms, then $P(t_1,\dots,t_n)$ is an atomic formula. Equality $t_1 = t_2$ is also atomic.
Well-formed formulas (wff)
Every atomic formula is a wff.
If $\varphi,\psi$ are wff, so are $\neg\varphi$, $(\varphi \wedge \psi)$, $(\varphi \vee \psi)$, $(\varphi \to \psi)$, $(\varphi \leftrightarrow \psi)$.
If $\varphi$ is a wff and $x$ a variable, then $\forall x\,\varphi$ and $\exists x\,\varphi$ are wff.
Mendelson 6e, §2.1; Cori & Lascar, vol. 1, §3.2.
6 / 32
1.5 Free variables, bound variables, scope
In a formula $Q x\,\varphi$ (where $Q \in \{\forall, \exists\}$), the variable $x$ is bound by the quantifier $Q$ and the scope of that quantifier is the subformula $\varphi$. Every occurrence of $x$ inside $\varphi$ that is not rebound by an inner quantifier is bound by this outer $Q$. An occurrence of a variable that is not in the scope of any quantifier binding it is free.
Scope of $\exists x$ : the subformula $P(x) \wedge Q(x,y)$.
Both occurrences of $x$ are bound.
The single occurrence of $y$ is free — its value comes from the context.
In $\forall x\,P(x) \wedge Q(x)$, by precedence the scope of $\forall x$ is just $P(x)$; the $x$ in $Q(x)$ is free. Writing $\forall x\,\bigl(P(x) \wedge Q(x)\bigr)$ binds both.
Mendelson 6e, §2.1, p. 51; Lalement, ch. 4.
7 / 32
1.6 Closed vs open formulas
A formula with no free variables is called closed, or a sentence. A formula with at least one free variable is open.
A sentence has a truth value in every interpretation; an open formula has a truth value only once its free variables are assigned values.
Formula
Free variables
Type
$\forall x\,(x^2 \geq 0)$
—
sentence (closed)
$x^2 \geq 0$
$x$
open
$\exists x\,(x < y)$
$y$
open
$\forall x\,\exists y\,(x < y)$
—
sentence
Cori & Lascar, vol. 1, §3.2.
8 / 32
1.7 Substitution and capture-avoidance
Let $\varphi$ be a formula, $x$ a variable and $t$ a term. The substitution $\varphi[t/x]$ replaces every free occurrence of $x$ in $\varphi$ by $t$. The substitution is said to be capture-avoiding when no variable of $t$ becomes bound by a quantifier of $\varphi$ after replacement.
Take $\varphi := \exists y\,(x < y)$ on $\mathbb{Z}$.
Naïve substitution of $t = y+1$ for $x$ gives $\exists y\,(y+1 < y)$ — false, because the new $y$ in $t$ has been captured by the existing $\exists y$.
The intended meaning ("for $x = y+1$ there is something larger") is recovered by first α-renaming the bound variable: $\varphi \equiv \exists z\,(x < z)$, then $\varphi[(y+1)/x] = \exists z\,(y+1 < z)$, which is true.
α-renaming. A bound variable may be replaced everywhere in its scope by a fresh variable without changing the meaning of the formula:
$$Q x\,\varphi(x) \;\equiv\; Q z\,\varphi(z) \qquad (z \text{ not occurring in } \varphi).$$
Lalement, ch. 4; Mendelson 6e, §2.4.
9 / 32
1.8 Interpretation, structure, model
An interpretation (or structure) of a first-order language $\mathcal{L}$ is a pair $\mathcal{M} = (U,\,\cdot^{\mathcal{M}})$ where
$U$ is a non-empty set — the universe of $\mathcal{M}$,
$\cdot^{\mathcal{M}}$ assigns to every constant $c$ an element $c^{\mathcal{M}} \in U$, to every $n$-ary function symbol $f$ a map $f^{\mathcal{M}} : U^n \to U$, and to every $n$-ary predicate symbol $P$ a relation $P^{\mathcal{M}} \subseteq U^n$.
For a sentence $\varphi$, we write $\mathcal{M} \models \varphi$ ("$\mathcal{M}$ is a model of $\varphi$") to mean $\varphi$ is true under this interpretation.
Language with one binary symbol $<$. Two interpretations:
$\mathcal{M}_1 = (\mathbb{Q}, <)$ : $\mathcal{M}_1 \models \forall x\,\forall y\,(x < y \to \exists z\,(x < z \wedge z < y))$ — density of $\mathbb{Q}$.
$\mathcal{M}_2 = (\mathbb{Z}, <)$ : $\mathcal{M}_2 \not\models$ the same sentence (no integer strictly between $0$ and $1$).
Universal: $\forall x\,P(x)$ is true in $\mathcal{M}$ iff $P(a)$ is true for every $a \in U$. Existential: $\exists x\,P(x)$ is true in $\mathcal{M}$ iff $P(a)$ is true for at least one $a \in U$.
On a finite universe $U = \{a_1,\dots,a_n\}$ the quantifiers reduce to long conjunctions and disjunctions:
$\exists!\,x\,P(x)$ — "there exists a unique $x$ such that $P(x)$" — is a derived notion:
$$\exists!\,x\,P(x) \;\;\Longleftrightarrow\;\; \exists x\,\Bigl(P(x) \;\wedge\; \forall y\,\bigl(P(y) \to y = x\bigr)\Bigr).$$
$\exists!\,x\,P(x)$ is equivalent to: some $x$ satisfies $P$, and any $y$ satisfying $P$ equals that $x$.
(⇒) Assume $\exists!\,x\,P(x)$. By the informal meaning, fix the unique witness $a$. Then $P(a)$ holds. If $P(b)$ also held with $b \neq a$, there would be two distinct witnesses, contradicting uniqueness. Hence $\forall y(P(y)\to y=a)$. Therefore $\exists x\bigl(P(x) \wedge \forall y(P(y)\to y=x)\bigr)$. (⇐) Suppose $\exists x\bigl(P(x) \wedge \forall y(P(y)\to y=x)\bigr)$; let $a$ be such an $x$. Then $P(a)$ holds, so $\exists x\,P(x)$. If $P(b)$ and $P(c)$ both hold, then $b = a$ and $c = a$, so $b = c$ — only one element satisfies $P$. Hence $\exists!\,x\,P(x)$. $\square$
Velleman 3e, §2.4; Rosen 8e, p. 45.
12 / 32
2.4 De Morgan's laws for quantifiers
For every formula $P(x)$:
$$\neg\,\forall x\,P(x) \;\equiv\; \exists x\,\neg P(x), \qquad \neg\,\exists x\,P(x) \;\equiv\; \forall x\,\neg P(x).$$
"$\neg\forall x\,P(x)$" means: not every $x$ satisfies $P$, i.e. at least one $x$ does not, i.e. $\exists x\,\neg P(x)$. The second equivalence is its dual (replace $P$ by $\neg P$ and take negations). $\square$
Negations can be pushed through any string of quantifiers, alternating $\forall \leftrightarrow \exists$:
When we want to restrict quantification to a subset $A \subseteq U$, we write:
$$\forall x \in A\;P(x) \;:=\; \forall x\,\bigl(x \in A \to P(x)\bigr),$$
$$\exists x \in A\;P(x) \;:=\; \exists x\,\bigl(x \in A \wedge P(x)\bigr).$$
Why different connectives?
For $\forall$, the bound $x \in A$ acts as a hypothesis: we ask "for every $x$, if $x \in A$ then $P(x)$". An implication is true whenever the hypothesis is false, so elements outside $A$ are correctly ignored.
For $\exists$, we want a witness inside $A$ and satisfying $P$. A conjunction is the right connective: an element outside $A$ would never satisfy "$x \in A$".
"Every prime $>2$ is odd" : $\;\forall p \in \mathbb{P}\,(p > 2 \to \mathrm{Odd}(p))$.
"Some integer in $[10,20]$ is prime" : $\;\exists n \in \mathbb{Z}\,(10 \leq n \leq 20 \wedge \mathrm{Prime}(n))$ — witness $n = 11$.
Rosen 8e, §1.4, pp. 43–44.
15 / 32
2.9 Vacuous truth
If the universe is empty, $U = \varnothing$, then for every predicate $P$:
$$\forall x\,P(x) \;\text{ is True},\qquad \exists x\,P(x) \;\text{ is False}.$$
$\forall x\,P(x)$ asserts $P(a)$ for every $a \in U$. The statement "for every $a$ in an empty set, $\ldots$" has no possible counter-example, so it holds vacuously. Dually, $\exists x\,P(x)$ requires a witness $a \in U$; with $U = \varnothing$ none exists, so it is false. $\square$
The same effect appears with bounded quantifiers when the bound set is empty:
"All unicorns can fly." Formally $\forall x \in \mathrm{Unicorns}\;\mathrm{Flies}(x) \equiv \forall x(x \in \mathrm{Unicorns} \to \mathrm{Flies}(x))$. If $\mathrm{Unicorns} = \varnothing$, the implication is vacuously true for every $x$. Mathematicians use this regularly: "every element of $\varnothing$ has property $P$" is true.
Velleman 3e, §2.3; Rosen 8e, p. 41.
16 / 32
2.6 / 2.10 Nested quantifiers and quantifier order
Suppose $\exists y\,\forall x\,P(x,y)$; pick a witness $b$ with $\forall x\,P(x,b)$. For an arbitrary $a$ we have $P(a,b)$, so $\exists y\,P(a,y)$, namely $y = b$. Hence $\forall x\,\exists y\,P(x,y)$. $\square$
The converse is false. On $U = \mathbb{Z}$ let $P(x,y) := (y = x+1)$.
$\forall x\,\exists y\,P(x,y)$ is true: for each $x$, choose $y = x+1$.
$\exists y\,\forall x\,P(x,y)$ is false: no single $y$ equals $x+1$ for every integer $x$.
Pattern
Meaning
$\forall x\,\forall y\,P(x,y)$
$P$ holds on the whole grid.
$\exists x\,\exists y\,P(x,y)$
At least one pair satisfies $P$.
$\forall x\,\exists y\,P(x,y)$
Each $x$ has its own $y$ (the choice of $y$ depends on $x$).
$\exists y\,\forall x\,P(x,y)$
One $y$ works for all $x$ (a uniform witness).
Rosen 8e, §1.5, pp. 60–65.
17 / 32
2.11 Validity, satisfiability, contingency
Let $\varphi$ be a sentence. Valid: $\varphi$ is true in every interpretation. Notation: $\models \varphi$. Satisfiable: there exists at least one interpretation in which $\varphi$ is true. Contingent: $\varphi$ is true in some interpretations and false in others (i.e. satisfiable and not valid). Unsatisfiable (contradictory): $\varphi$ is true in no interpretation.
Two formulas $\varphi$ and $\psi$ (with the same free variables) are logically equivalent, written $\varphi \equiv \psi$, if for every interpretation $\mathcal{M}$ and every assignment of free variables, $\varphi$ and $\psi$ receive the same truth value. Equivalently: $\models \varphi \leftrightarrow \psi$.
"True in some interpretation" is satisfiability — a much weaker notion. "True in every interpretation, equivalent to $\psi$" is logical equivalence.
Example: $\forall x\,P(x) \leftrightarrow P(c)$ is satisfiable (pick a model where $c$ is the only element), but not a logical equivalence — pick a two-element model where $P$ holds only at $c$.
Equivalence is preserved by substitution and by replacement of subformulas: if $\varphi \equiv \psi$, then $\chi[\varphi] \equiv \chi[\psi]$.
Mendelson 6e, §2.2; Velleman 3e, §2.3.
19 / 32
3.1–3.2 Equality $=$ as a logical primitive
Equality $=$ is treated in first-order logic as a built-in binary predicate symbol. Its meaning in every interpretation $\mathcal{M}$ is fixed: $a =^{\mathcal{M}} b$ iff $a$ and $b$ are the same element of $U$.
Axioms of equality. For all $x, y, z$:
Reflexivity: $\;x = x$.
Symmetry: $\;x = y \to y = x$.
Transitivity: $\;(x = y \wedge y = z) \to x = z$.
These three axioms make $=$ an equivalence relation; together with Leibniz's rule (next slide) they characterise equality up to logical equivalence.
Mendelson 6e, §2.5; Cori & Lascar, vol. 1, §3.4.
20 / 32
3.3 Leibniz's rule — substitutability
Leibniz / Indiscernibility of identicals. For every predicate $P$:
$$(x = y) \;\to\; \bigl(P(x) \leftrightarrow P(y)\bigr).$$
Read: equal objects satisfy exactly the same predicates. This is what justifies "replacing equals by equals" in proofs.
Let $P(x) := (x^2 = 9)$ on $\mathbb{Z}$. Suppose $a = -3$. By Leibniz, $P(a) \leftrightarrow P(-3)$, that is $a^2 = 9 \leftrightarrow (-3)^2 = 9$, which is True $\leftrightarrow$ True. So once we know $a = -3$, we may freely substitute $a$ for $-3$ in any computation.
Mendelson 6e, §2.5; Cori & Lascar, vol. 1, §3.4.
21 / 32
4.1 Prenex normal form (PNF)
A formula is in Prenex Normal Form if it has the shape
$$Q_1 x_1\,Q_2 x_2\,\dots\,Q_n x_n\;M(x_1,\dots,x_n),$$
where each $Q_i \in \{\forall, \exists\}$ and $M$ is a quantifier-free formula (the matrix).
Every first-order formula is logically equivalent to a formula in PNF.
The standard algorithm:
Rename bound variables so that all are distinct from each other and from any free variable (α-renaming).
Eliminate $\to$ and $\leftrightarrow$ in favour of $\neg, \wedge, \vee$.
Push $\neg$ inward using De Morgan (for connectives and for quantifiers).
Pull quantifiers out using the equivalences:
$$Q x\,\varphi(x) \;\bullet\; \psi \;\equiv\; Q x\,(\varphi(x) \bullet \psi) \qquad (x \text{ not free in } \psi),$$
for $\bullet \in \{\wedge,\vee\}$.
Mendelson 6e, §2.6; Lalement, ch. 5.
22 / 32
4.2 PNF — worked example
Convert $\;\bigl(\forall x\,P(x)\bigr) \;\to\; \bigl(\exists y\,Q(y)\bigr)\;$ to PNF.
Pull quantifiers out (each variable is free in only one side):
$$\exists x\,\Bigl(\,\neg P(x) \;\vee\; \exists y\,Q(y)\,\Bigr) \;\equiv\; \exists x\,\exists y\,\bigl(\neg P(x) \vee Q(y)\bigr).$$
Result in PNF: $\;\exists x\,\exists y\,\bigl(\neg P(x) \vee Q(y)\bigr)$.
Note how "$\forall x\,P(x) \to \cdots$" became "$\exists x\,\neg P(x) \vee \cdots$" — the quantifier flips when it crosses an implication's antecedent. This is a common source of mistakes.
Lalement, ch. 5; Mendelson 6e, §2.6, p. 91.
23 / 32
4.3 Skolemization
Let $\varphi$ be in PNF: $\;Q_1 x_1\dots Q_n x_n\,M$. To Skolemize $\varphi$ we replace each existential quantifier by a fresh function (or constant) symbol depending on the universally quantified variables that precede it. For instance:
$$\forall x_1\,\forall x_2\,\exists y\;P(x_1,x_2,y) \;\rightsquigarrow\; \forall x_1\,\forall x_2\;P\bigl(x_1,x_2,\,f(x_1,x_2)\bigr).$$
When no $\forall$ precedes the $\exists$, the existential is replaced by a fresh Skolem constant: $\exists y\,P(y) \rightsquigarrow P(c)$.
Skolemization preserves satisfiability (not, in general, logical equivalence): $\varphi$ is satisfiable iff its Skolem form is satisfiable.
$\forall x\,\exists y\,P(x,y) \;\rightsquigarrow\; \forall x\,P(x,f(x))$. Reading: instead of saying "for every $x$ there exists some $y$", we name the choice function $f$ that picks the witness for each $x$.
Mendelson 6e, §2.7; Lalement, ch. 6.
24 / 32
4.4 CNF / DNF in first-order logic
After putting a formula in PNF, the matrix $M$ is propositional in the atomic formulas. Distributing $\wedge,\vee$ gives:
Conjunctive Normal Form (CNF): $M$ is a conjunction of disjunctions of literals (atom or its negation).
Disjunctive Normal Form (DNF): $M$ is a disjunction of conjunctions of literals.
A first-order formula is in prenex CNF (resp. prenex DNF) when it is in PNF and its matrix is in CNF (resp. DNF).
5. Quantifier rules of inference (preview of Lesson 5)
5.1 Universal Instantiation (UI)
$\dfrac{\forall x\,P(x)}{P(c)}\;$ for any element $c$ of the universe.
From $\forall x \in \mathbb{R}\,(x^2 \geq 0)$ we infer $(-7)^2 \geq 0$.
5.2 Universal Generalization (UG)
$\dfrac{P(c)}{\forall x\,P(x)}\;$ provided $c$ is arbitrary: it must not appear in any hypothesis nor be a name fixed elsewhere in the proof. This is the rule behind every proof that begins "Let $c$ be an arbitrary element of $U$…".
5.3 Existential Instantiation (EI)
$\dfrac{\exists x\,P(x)}{P(c)}\;$ where $c$ is a fresh constant — one not occurring anywhere else in the proof so far. The named $c$ is a chosen witness; we are not allowed to assume anything else about it.
5.4 Existential Generalization (EG)
$\dfrac{P(c)}{\exists x\,P(x)}\;$ for any constant $c$ — once we have an example, existence follows. Example: from $7^2 + 24^2 = 25^2$ we conclude $\exists x\,\exists y\,\exists z\,(x^2 + y^2 = z^2)$.
Rosen 8e, §1.6; Velleman 3e, §3.3.
26 / 32
6.1 / 6.2 Two basic theorems with proofs
6.1. $\forall x \in \mathbb{R}\;(x^2 \geq 0)$.
Let $x \in \mathbb{R}$ be arbitrary. By the trichotomy of $\mathbb{R}$, either $x \geq 0$ or $x < 0$.
Case 1 ($x \geq 0$): $x \cdot x \geq 0 \cdot x = 0$ by the order axiom (product of non-negatives).
Case 2 ($x < 0$): then $-x > 0$, so $(-x)(-x) \geq 0$ by case 1; but $(-x)(-x) = x^2$. Hence $x^2 \geq 0$.
By UG, $\forall x \in \mathbb{R}\,(x^2 \geq 0)$. $\square$
(⇒) Direct. Suppose $n = 2k$ for some $k \in \mathbb{Z}$. Then $n^2 = 4k^2 = 2(2k^2)$, which is even. (⇐) Contrapositive. Suppose $n$ is odd: $n = 2k+1$. Then $n^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$, which is odd. So $n^2$ even implies $n$ even. $\square$
Rosen 8e, §1.7; Velleman 3e, §3.4.
27 / 32
6.3 / 6.4 Existence of $\sqrt{2}$ — and no negative square in $\mathbb{Z}$
6.3. $\exists x \in \mathbb{R}\;(x^2 = 2)$.
Take $x = \sqrt{2}$. The set $\{r \in \mathbb{Q} : r > 0,\; r^2 < 2\}$ is non-empty (contains $1$) and bounded above (by $2$). By the least-upper-bound property of $\mathbb{R}$, its supremum $s$ exists and $s \in \mathbb{R}$. A standard $\varepsilon$-argument (or Dedekind cut) shows that $s^2 = 2$. Setting $x := s$ gives a witness in $\mathbb{R}$ with $x^2 = 2$. By EG, $\exists x \in \mathbb{R}\,(x^2 = 2)$. $\square$
6.4. $\neg\,\exists x \in \mathbb{Z}\;(x^2 < 0)$.
Equivalent (De Morgan) to $\forall x \in \mathbb{Z}\,(x^2 \geq 0)$, which is Theorem 6.1 restricted to $\mathbb{Z} \subseteq \mathbb{R}$. $\square$
Velleman 3e, §3.5; Rosen 8e, §1.7.
28 / 32
6.5 $\varepsilon$–$\delta$ continuity as a quantifier sentence
A function $f : \mathbb{R} \to \mathbb{R}$ is continuous at $a \in \mathbb{R}$ iff
$$\forall \varepsilon > 0\;\,\exists \delta > 0\;\,\forall x \in \mathbb{R}\;\,\bigl(|x - a| < \delta \;\to\; |f(x) - f(a)| < \varepsilon\bigr).$$
Notice the alternation $\forall \exists \forall$ — the choice of $\delta$ may depend on $\varepsilon$ (and on $a$), but must work for all $x$.
$f(x) = 2x$ is continuous at $a = 1$.
Let $\varepsilon > 0$. Choose $\delta := \varepsilon / 2$. If $|x - 1| < \delta$, then
$|f(x) - f(1)| = |2x - 2| = 2|x - 1| < 2\delta = \varepsilon.$ $\square$
6.6 (Cantor). There is no surjection $f : \mathbb{N} \to \mathcal{P}(\mathbb{N})$.
Suppose, for contradiction, that $f$ is surjective. Define the diagonal set
$$D \;:=\; \{\,n \in \mathbb{N} \,:\, n \notin f(n)\,\} \;\subseteq\; \mathbb{N}.$$
By surjectivity there exists $m \in \mathbb{N}$ with $f(m) = D$. Now ask whether $m \in D$:
$$m \in D \;\Longleftrightarrow\; m \notin f(m) \;\Longleftrightarrow\; m \notin D.$$
This is a contradiction. Hence no such surjection exists. $\square$
6.7 (Russell). The "collection" $R = \{\,x \mid x \notin x\,\}$ cannot be a set.
Asking $R \in R$: by definition of $R$, $R \in R \Leftrightarrow R \notin R$ — a contradiction. So unrestricted comprehension (allowing $\{x \mid \varphi(x)\}$ for arbitrary $\varphi$) is inconsistent. Modern set theory uses restricted comprehension: $\{x \in A \mid \varphi(x)\}$ for a previously given set $A$. $\square$
$\neg\,\exists s \in S\,\forall \ell \in L\,\neg A(s,\ell)\;\equiv\;\forall s\,\exists \ell\,A(s,\ell)$
7.6
Between any two distinct rationals there is a rational. density of $\mathbb{Q}$
$\forall x \in \mathbb{Q}\,\forall y \in \mathbb{Q}\,(x < y \to \exists z \in \mathbb{Q}\,(x < z \wedge z < y))$
7.7
$\mathbb{Z}$ has no upper bound.
$\neg\,\exists M \in \mathbb{Z}\,\forall n \in \mathbb{Z}\,(n \leq M)\;\equiv\;\forall M\,\exists n\,(n > M)$
7.8
Every prime greater than 2 is odd.
$\forall p \in \mathbb{P}\,(p > 2 \to \mathrm{Odd}(p))$
Counter-examples (§8)
8.1 $\forall x(P(x)\vee Q(x)) \not\equiv \forall x\,P(x) \vee \forall x\,Q(x)$.
On $\mathbb{Z}$, $P(x) := (x \geq 0)$, $Q(x) := (x \leq 0)$. The left side is true (every integer is $\geq 0$ or $\leq 0$); the right side is false (neither $\forall x\,P(x)$ nor $\forall x\,Q(x)$ holds).
8.2 $\exists x(P(x)\wedge Q(x)) \not\equiv \exists x\,P(x) \wedge \exists x\,Q(x)$.
On $\mathbb{Z}$, $P(x) := (x > 0)$, $Q(x) := (x < 0)$. Right side is true (witnesses $1$ and $-1$); left side is false (no integer is both).
8.3 $\forall x\,\exists y\,P(x,y) \not\equiv \exists y\,\forall x\,P(x,y)$.
On $\mathbb{Z}$ take $P(x,y) := (y = x+1)$. Left is true; right is false (no $y$ equals $x+1$ for every $x$).
A predicate of arity $n$ is a map $D^n \to \{\mathtt T, \mathtt F\}$; a wff is built from atomic formulas by $\neg, \wedge, \vee, \to, \leftrightarrow, \forall, \exists$.
Free vs bound variables, scope and capture-avoiding substitution determine the meaning of a formula.
Truth is defined relative to an interpretation $\mathcal{M} = (U, \cdot^{\mathcal{M}})$.
$\exists!$ is the unique-existence quantifier; bounded quantifiers desugar to $\to$ for $\forall$ and $\wedge$ for $\exists$.
Equality is a primitive binary predicate with axioms of reflexivity, symmetry, transitivity and Leibniz's substitutability.
Every formula has a PNF; PNF + matrix-CNF / DNF + Skolemization power automatic reasoning.
UI, UG, EI, EG are the four quantifier inference rules used in proofs (more in Lesson 5).
Wolfram → Python quick reference
Wolfram Language
Python equivalent
ForAll[x, P[x]]
z3.ForAll([x], P(x))
Exists[x, P[x]]
z3.Exists([x], P(x))
Resolve[Exists[x, x^2 == 2], Reals]
Solver(); s.add(x*x == 2); s.check()
FullSimplify[expr]
sympy.simplify(expr)
Element[x, Integers]
x = z3.Int('x')
Implies[p, q]
sympy.Implies(p, q) / z3.Implies(p, q)
Bibliography
K. H. Rosen. Discrete Mathematics and Its Applications, 8th ed., McGraw-Hill, 2019 — §§1.4–1.7.
D. J. Velleman. How To Prove It: A Structured Approach, 3rd ed., Cambridge UP, 2019 — ch. 2 & 3.
E. Mendelson. Introduction to Mathematical Logic, 6th ed., CRC Press, 2015 — ch. 2.
R. Cori & D. Lascar. Mathematical Logic, vol. 1, Oxford UP, 2000 — ch. 3.
R. Lalement. Logique, réduction, résolution, Masson, 1990 — ch. 4–6.