Week 2 Predicate Logic and Proof Patterns

Sources covered

Lecture 4 (predicate logic: quantifiers, scope, interpretations, equivalences, worked interpretations; end of the logic part of Ch. 2) and Lecture 5 (proof patterns, Script §2.6 complete). Script: §2.4.3–2.4.8, §2.5, §2.6.1–2.6.10. Material only in the script is marked (script only); reconstructions or additions of mine are marked (added). Next week: Chapter 3 (sets, relations, functions), starting with a formal definition of the natural numbers.

---

1. Executive Overview & Core Objectives

Lecture 4 finishes the informal introduction to predicate logic (Prädikatenlogik). Quantified formulas over a universe are general formulas whose truth depends on an interpretation, or, once the universe and the meaning of the predicates are fixed, they become statements. The lecture covers scope of quantifiers, pushing negations through quantifiers, which quantifier rules are equivalences and which are only one-way consequences, and how to formalize concepts such as “prime”, “infinitely many primes”, “sibling” or “transitive”.

Lecture 5 introduces the standard proof patterns of §2.6. Each pattern is justified by a logical consequence of propositional logic: composition of implications, direct proof, indirect proof (contraposition), modus ponens, case distinction, proof by contradiction, existence and counterexample proofs, the pigeonhole principle, and induction. The exception is induction, which rests on a Peano axiom.

Learning objectives. After this week you should be able to:

• name and use the building blocks of predicate logic: universe, predicates, functions, constants, operators, quantifiers;
• determine the scope of a quantifier and distinguish free and bound variables;
• evaluate quantified formulas under a given interpretation ($\mathbb{N}$, $\mathbb{Z}$, $\mathbb{R}$, people);
• push negations through quantifiers ($\neg \forall \equiv \exists \neg$, $\neg \exists \equiv \forall \neg$) and know which quantifier laws are $\equiv$ and which only $\models$ (with counterexamples);
• formalize definitions (prime, sibling, grandparent, inverse, transitivity, symmetry) as predicate-logic formulas;
• state each proof pattern of §2.6, its justifying lemma (2.5–2.11), and carry it out on examples ($\sqrt{2}$, $\sqrt{x}$, squares, $n^4\mathrm{mod}5$, primes, pigeonhole, induction);
• recognize the classic errors: proving $\neg S⟹\neg T$ instead of $\neg T⟹\neg S$, using "$\exists$" where "$\forall$" is needed, confusing an indirect proof with a proof by contradiction, and claiming irreversible proof steps are reversible.

---

2. Core Concepts & Formal Definitions

2.1 Building blocks of predicate logic (recap and refinements, Lecture 4)

Building block	Notation	Input → Output	Remarks
universe (Universum)	$U$	the domain of values	a non-empty set (script)
predicates (Prädikate)	$P,Q,R,\dots$	fixed number $k$ of elements of $U$ → truth value	replace the propositional symbols; a 0-ary predicate is just a truth value, like a symbol $A$
functions (Funktionen)	$f,g,h$	fixed number $k\ge 0$ of elements of $U$ → element of $U$	e.g. squaring, $\text{add}$, $\text{mult}$
constants (Konstanten)	$a,b,c$; e.g. $0,2,\pi$	fixed elements of $U$	can be seen as 0-ary functions; kept separate only for convenience
operators	$\neg ,\wedge ,\vee ,\to ,\leftrightarrow$	truth values → truth value	as in propositional logic
quantifiers (Quantoren)	$\forall x$, $\exists x$	formula → formula	”for all $x\in U$”, “there exists $x\in U$”

Infix notation. Binary predicates and functions are usually written between their arguments. In $0\le x$, the symbol $\le$ is a binary predicate, $0$ a constant and $x$ a variable. In $x=y\cdot z$, the symbol $=$ is a binary predicate and $\cdot$ a binary function ($\text{mult}(y,z)$).

Definition 2.11 (Quantifiers)

For a universe $U$ and a predicate $P(x)$:

• $\forall xP(x)$ stands for: $P(x)$ is true for all $x$ in $U$.
• $\exists xP(x)$ stands for: $P(x)$ is true for some $x$ in $U$, i.e. there exists at least one $x\in U$ for which $P(x)$ is true.

More generally, for a formula $F$ in which $x$ occurs, $\forall xF$ is true iff $F$ is true for every value of $x$ in $U$, and $\exists xF$ is true iff $F$ is true for at least one value of $x$ in $U$. (Also written $\forall x:P(x)$ or $\forall x.P(x)$.)

Source note (Lecture 4)

When explaining $\exists x(F\wedge G)$ and its tree, the lecturer twice said that the $\exists x$-node evaluates to true if the subformula is true “for all values of $x$”. That is the semantics of $\forall$. Correct: $\exists xF$ is true iff $F$ is true for at least one $x\in U$.

Restricted quantifiers (script §2.4.3). ”$x^2\ge 25$ whenever $x\ge 5$” is written

$$\forall x((x\ge 5)\to (x^2\ge 25)),\text{also written }\forall x\ge 5:(x^2\ge 25).$$

The variable name is irrelevant: $\exists x(x+5=3)\equiv \exists y(y+5=3)$.

2.2 Scope, free and bound variables (Lecture 4)

Scope convention (lecture and script)

A quantifier $\forall x$ or $\exists x$ binds the variable $x$ in the subformula that follows it. The binding lasts until the parenthesis enclosing that subformula closes, or until an inner quantifier on the same variable takes over (“overwrites”) for its own subformula.

• An occurrence of $x$ inside the scope of a quantifier on $x$ is bound (gebunden).
• An occurrence outside every such scope is free (frei).
• A formula with a free variable cannot be evaluated even under an interpretation, because $x$ has no value. A formula without free variables is closed (geschlossen).

Parentheses change the meaning ( $U=\mathbb{N}$, usual $\le$)

$(\exists x(x\le 2))\wedge (\exists x(x\ge 3))\text{is true: two different witnesses, e.g. }x=0\text{ and }x=3.$
$\exists x((x\le 2)\wedge (x\ge 3))\text{is false: no single }x\text{ is both}\le 2\text{ and }\ge 3.$
The trees differ:

• first formula: root $\wedge$, with an $\exists x$ under each branch;
• second formula: root $\exists x$, with $\wedge$ below it.

You cannot “factor out” the quantifier like a common factor in arithmetic, which is what the student asked about.

Inner quantifier overriding the outer one (reconstructed)

In $\forall x(\exists x(x\ge 3))$, the inner $\exists x$ re-binds $x$, so the outer $\forall x$ has nothing left to bind. The inner formula is true under $U=\mathbb{N}$, hence the whole formula is true. Dropping the inner quantifier gives $\forall x(x\ge 3)$, which is false. In general, if $x$ is not free in $G$:
$\forall xG\equiv G\text{and}\exists xG\equiv G,$
e.g. $\forall x\exists xF\equiv \exists xF$. The lecturer stressed that this was a syntax demonstration, not a sensible formula. Use fresh variable names in practice.

Intuition

Bound variables are like loop variables or function parameters in programming. $\forall x$ is a loop over $U$ that checks “every iteration is true”, and $\exists x$ checks “some iteration is true”. An inner $\exists x$ declares a new local variable that shadows the outer one.

2.3 General formulas vs. interpretations (Script §2.4.5–2.4.7, §2.5)

Interpretation (informal, Script §2.4.5)

A predicate-logic formula has “free parts”: the universe and the meaning of the predicate and function symbols. An interpretation fixes:

• the universe $U$ (non-empty);
• a concrete $k$-ary predicate $U^k\to \{0,1\}$ for each predicate symbol;
• a concrete function for each function symbol;
• an element for each constant.

The precise definition follows in Chapter 6.

Example: $\forall x(P(x)\to Q(x))$ with $U=\mathbb{N}$ and $P(x)$ = ”$x$ divisible by 4”:

• $Q(x)$ = ”$x$ is odd”: false ($x=4$).
• $Q(x)$ = ”$x$ is even”: true.

Satisfiable, tautology, equivalence, consequence (informal, Script §2.4.6–2.4.7)

• $F$ is satisfiable if some interpretation makes $F$ true.
• $F$ is a tautology / valid if every interpretation (every universe, every meaning of the symbols) makes $F$ true.
• $F\equiv G$ if $F$ and $G$ have the same truth value under every interpretation.
• $F\models G$ if every interpretation that makes $F$ true also makes $G$ true.

Compared with propositional logic, “for every truth assignment of the symbols” is replaced by “for every interpretation”, which is a much richer notion.

The lecturer distinguished two “worlds” on the board:

• General (allgemein): statements about formulas that hold for all interpretations, such as $\neg \exists xF\equiv \forall x\neg F$. Only few such laws exist, because interpretations can be arbitrary.
• Special (eine Interpretation): a fixed universe and fixed meanings ($U=\mathbb{N}$ with $\le$, $\cdot$, $=$; or $U$ = people). Here a closed formula is simply true or false.

Formulas as statements (Script §2.5)

A formula is in general not a mathematical statement. If the interpretation is fixed (universe, predicates, functions), a closed formula is a statement that is either true or false. Only then may it be used as a statement, e.g. in a chain of proof steps, and only then is it meaningful to say “the formula is true”.

Example 2.25 (script only): for $U=\mathbb{N}$, $\exists n(n<4\wedge n>5)$ is false and $\forall n(n>0\to \exists m(m<n))$ is true.

Convention used in lecture and script: under a fixed interpretation, "$F\equiv G$" is sometimes used loosely to mean ”$F$ and $G$ have the same truth value (both true or both false)”. That is weaker than equivalence for all interpretations.

Lemma 2.4 (script only)

For any formulas $F$ and $G$: if $F\models G$, then the statement ”$F$ is valid $⟹$ $G$ is valid” is true. The converse is generally false.

Proof. $F\models G$ says that for every interpretation, if $F$ is true then $G$ is true. If $F$ is true for every interpretation, then so is $G$. $\square$

2.4 Laws for quantifiers (Lecture 4; Script §2.4.7–2.4.8)

Law	Type	Reason or counterexample
$\neg \forall xF\equiv \exists x\neg F$	equivalence	”not all” means “at least one exception”
$\neg \exists xF\equiv \forall x\neg F$	equivalence	”none” means “all fail”
$\forall xF\wedge \forall xG\equiv \forall x(F\wedge G)$	equivalence	both directions are clear
$\exists x(F\wedge G)\models \exists xF\wedge \exists xG$	consequence only	the same witness works for both
$\exists xF\wedge \exists xG/\models \exists x(F\wedge G)$	fails	$U=\mathbb{N}$, $F:x\le 2$, $G:x\ge 3$
$\forall x(F\to G)\models \forall xF\to \forall xG$	consequence only	proof in §3.1
$\forall xF\to \forall xG/\models \forall x(F\to G)$	fails	$U=\mathbb{N}$, $F$ = even, $G$ = odd (§3.1)
$\exists x\exists yP(x,y)\equiv \exists y\exists xP(x,y)$	equivalence	identical quantifiers commute
$\forall x\forall yP(x,y)\equiv \forall y\forall xP(x,y)$	equivalence	identical quantifiers commute
$\exists y\forall xP(x,y)\models \forall x\exists yP(x,y)$	consequence only	one $y$ for all $x$ serves each $x$
$\forall x\exists yP(x,y)/\models \exists y\forall xP(x,y)$	fails	$U=\mathbb{N}$, $P(x,y):x<y$
$\forall xF\models \exists xF$	consequence	needs $U\ne \varnothing$
$\forall xG\equiv G$ if $x$ not free in $G$	equivalence	the quantifier is vacuous

Exam Trap: order of mixed quantifiers

$\forall x\exists y$ lets $y$ depend on $x$. $\exists y\forall x$ demands one $y$ that works for all $x$. Under $U=\mathbb{N}$, $P(x,y)=(x<y)$:

• $\forall x\exists y(x<y)$ is true (take $y=x+1$);
• $\exists y\forall x(x<y)$ is false: for any $y$, choosing $x=y$ gives $\neg (y<y)$.

Swapping different quantifiers is never an automatic equivalence.

Source note: empty universe (Lecture 4 Q&A)

A student asked whether $U=\varnothing$ is allowed. The lecturer was unsure (“I have to check”). Script §2.4.1: $U$ is a non-empty set. This matters: $\forall xP(x)\models \exists xP(x)$ fails on an empty universe, where every $\forall$-formula is vacuously true and every $\exists$-formula false.

2.5 Properties of binary predicates (Lecture 4; preview of Ch. 3)

Transitivity and symmetry (as formulas)

A binary predicate $P$ (later: a relation) is

• transitive (transitiv) if $\forall x\forall y\forall z((P(x,y)\wedge P(y,z))\to P(x,z))$ is true under the interpretation;
• symmetric (symmetrisch) if $\forall x\forall y(P(x,y)\to P(y,x))$ is true under the interpretation.

Examples on $\mathbb{N}$: $\le$ and $<$ are transitive, not symmetric; $=$ is transitive and symmetric.

Source note (Lecture 4)

The lecturer first called the transitivity formula a “tautology” and then corrected himself: it is not valid (it fails for interpretations where $P$ is not transitive). We only know it is true for a particular interpretation, and that is exactly what “this $P$ is transitive” means. Transitivity, symmetry and reflexivity define equivalence relations in Chapter 3.

---

3. Step-by-Step Derivations & Mathematical Proofs

3.1 Predicate-logic consequences, proved informally (Lecture 4)

(a) $\exists x(F\wedge G)\models \exists xF\wedge \exists xG$.

1. Fix an interpretation that makes the left side true.
2. Then some $a\in U$ makes $F\wedge G$ true, so $a$ makes $F$ true and $a$ makes $G$ true.
3. So $\exists xF$ is true (witness $a$) and $\exists xG$ is true (witness $a$). The right side is true. $\square$

The converse fails: $U=\mathbb{N}$, $F=(x\le 2)$, $G=(x\ge 3)$. The right side has witnesses $0$ and $3$; the left side needs a single $x$ with $x\le 2$ and $x\ge 3$, which does not exist.

(b) $\forall x(F\to G)\models (\forall xF)\to (\forall xG)$.

1. Fix an interpretation in which $\forall x(F\to G)$ is true. Show that $\forall xF\to \forall xG$ is true.
2. Case 1: $\forall xF$ is false. Then the implication is true (false premise).
3. Case 2: $\forall xF$ is true. Take any $a\in U$. Then $F(a)$ is true, and $F(a)\to G(a)$ is true by assumption, so $G(a)$ is true (modus ponens). As $a$ was arbitrary, $\forall xG$ is true, and the implication is true. $\square$

The student’s route in the lecture: rewrite $F\to G$ as $\neg F\vee G$ and $\forall xF\to \forall xG$ as $\neg \forall xF\vee \forall xG\equiv \exists x\neg F\vee \forall xG$, then argue by cases exactly as above.

Converse fails: $U=\mathbb{N}$, $F(x)$ = ”$x$ even”, $G(x)$ = ”$x$ odd”.

• $\forall xF$ is false, so $\forall xF\to \forall xG$ is true.
• $\forall x(F\to G)$ is false ($x=0$: even, not odd).

(c) $\forall x(P(x)\to \neg P(x))\equiv \forall x\neg P(x)$. For every fixed $x$, $P(x)\to \neg P(x)\equiv \neg P(x)\vee \neg P(x)\equiv \neg P(x)$ (idempotence). Equivalent bodies under $\forall x$ give equivalent formulas.

Intuition: if some $x$ had $P(x)$, it would also have $\neg P(x)$, a contradiction. So $P$ holds for no $x$.

Source note (Lecture 4)

The lecturer wrote $\models$ for (c). A student pointed out that $\equiv$ holds. The lecturer agreed (“logische Äquivalenz gilt sogar”) but left $\models$ on the board, which is also correct, just weaker.

3.2 Composition of implications (Script §2.6.1)

Definition 2.12 (Composition of implications)

If $S⟹T$ and $T⟹U$ are both true, conclude that $S⟹U$ is true.

Lemma 2.5

$(A\to B)\wedge (B\to C)\models A\to C.$

Proof. Compare the truth tables of the two formulas. Equivalently (as in Week 1): $A\to C=0$ forces $A=1,C=0$. Then $B=0$ makes $A\to B=0$, and $B=1$ makes $B\to C=0$. So the left side is $0$ whenever the right side is $0$. $\square$

Variant (Lecture 5). Find $R_1,R_2$ with $S⟹R_1$, $S⟹R_2$ and ”$R_1$ and $R_2$” $⟹T$. Justification (added):

$(A\to B)\wedge (A\to C)\wedge ((B\wedge C)\to D)\models A\to D.$

Exam Trap: this variant is not a case distinction

A student asked whether this is a case distinction. No. Here we need $R_1$ and $R_2$; both are proved and both are needed. A case distinction needs a proof that at least one case holds ($R_1$ or $R_2$), plus “each case implies $S$“.

3.3 Direct proof (Script §2.6.2)

Definition 2.13 (Direct proof of an implication)

A direct proof (direkter Beweis) of $S⟹T$ assumes $S$ and then proves $T$ under this assumption.

Example (Lecture 5; Script Example 2.3): if $a$ and $b$ are squares, then $ab$ is a square. Here $n$ is a square if $n=m\cdot m$ for some integer $m$, $S$ is ”$a$ and $b$ are squares”, and $T$ is ”$ab$ is a square”.

$$\begin{array}{rlrl}S& \stackrel{\cdot }{⟹}\exists u\exists v(a=u\cdot u\wedge b=v\cdot v)& & \text{(def. of square; uses assumption }S)\\ & \stackrel{\cdot }{⟹}\exists u\exists v(a\cdot b=(u\cdot u)\cdot (v\cdot v))& & \text{(substitute)}\\ & \stackrel{\cdot }{⟹}\exists u\exists v(a\cdot b=u\cdot ((u\cdot v)\cdot v))& & \text{(associativity, used twice)}\\ & \stackrel{\cdot }{⟹}\exists u\exists v(a\cdot b=u\cdot (v\cdot (u\cdot v)))& & \text{(commutativity on }(u\cdot v)\cdot v)\\ & \stackrel{\cdot }{⟹}\exists u\exists v(a\cdot b=(u\cdot v)\cdot (u\cdot v))& & \text{(associativity)}\\ & \stackrel{\cdot }{⟹}\exists w(a\cdot b=w\cdot w)& & (w:=u\cdot v)\\ & \stackrel{\cdot }{⟹}T& & \text{(def. of square)}\end{array}$$

Why these steps. The left side must be rearranged into the form $w\cdot w$. Associativity re-parenthesizes, and commutativity swaps the two operands of one single multiplication. If we “know nothing about multiplication”, every regrouping must be justified, which is the lecturer’s “bureaucratic” point. The lecturer bundled several re-bracketings per step (“associativity four times in total”); the exact bookkeeping does not matter as long as each step uses an allowed law.

Clicker question (Lecture 5): which step is not reversible?

Steps 3–7 are reversible (equalities and regrouping; for step 6 backwards, take $u:=w$, $v:=1$). The step from ”$a=u\cdot u$ and $b=v\cdot v$” to "$a\cdot b=(u\cdot u)\cdot (v\cdot v)$" is not reversible: from $ab$ being a square of that form we cannot recover that $a$ and $b$ individually are squares. If all steps were equivalences, the lemma’s converse would hold: ”$ab$ square $⟹$ $a$ and $b$ squares”. That is false: $9=3\cdot 3$ is a square, but $3$ is not.

3.4 Indirect proof (contraposition) (Script §2.6.3)

Definition 2.14 (Indirect proof of an implication)

An indirect proof (indirekter Beweis) of $S⟹T$ assumes that $T$ is false and proves, under this assumption, that $S$ is false. That is, it proves the contrapositive (Kontraposition) $\neg T⟹\neg S$.

Lemma 2.6

$\neg B\to \neg A\models A\to B.$ In fact $\neg B\to \neg A\equiv A\to B$, since both have table $1,1,0,1$.

Proof by truth table:

$A$	$B$	$\neg B$	$\neg A$	$\neg B\to \neg A$	$A\to B$
0	0	1	1	1	1
0	1	0	1	1	1
1	0	1	0	0	0
1	1	0	0	1	1

The last two columns are identical.

Exam Trap: flip and negate

Proving $\neg S⟹\neg T$ does not prove $S⟹T$. $\neg A\to \neg B\equiv B\to A$ is the converse, not the contrapositive. Counterexample row: $A=0,B=1$ makes $\neg A\to \neg B=1\to 0=0$, while $A\to B=1$. Both sides must be negated and swapped.

Exam Trap: indirect proof ≠ proof by contradiction

An indirect proof applies to an implication $S⟹T$ and proves $\neg T⟹\neg S$. A proof by contradiction (§3.7) proves an arbitrary statement $S$ by deriving something false from $\neg S$. They are related, but not the same pattern. The lecture said so explicitly.

Example 2.26 (Lecture 5). Claim: if $x>0$ is irrational, then $\sqrt{x}$ is irrational. Here $S$: ”$x$ is irrational”, $T$: ”$\sqrt{x}$ is irrational”; a real number is rational iff it equals $m/n$ for integers $m,n$ with $n\ne 0$.

A direct proof would be awkward: we would have to argue all the time that a certain representation does not exist. So we prove $\neg T⟹\neg S$:

$$\begin{array}{rlrl}\neg T& \stackrel{\cdot }{⟺}\sqrt{x}\text{ is rational}& & \\ & \stackrel{\cdot }{⟹}\exists m\exists n(m,n\in \mathbb{Z}\wedge n\ne 0\wedge \sqrt{x}=m/n)& & \text{(def. of rational)}\\ & \stackrel{\cdot }{⟹}\exists m\exists n(x=m^2/n^2\wedge n^2\ne 0)& & \text{(square both sides)}\\ & \stackrel{\cdot }{⟹}\exists m^{\prime }\exists n^{\prime }(x=m^{\prime }/n^{\prime }\wedge n^{\prime }\ne 0)& & (m^{\prime }:=m^2,n^{\prime }:=n^2)\\ & \stackrel{\cdot }{⟺}x\text{ is rational}\stackrel{\cdot }{⟺}\neg S.& & \end{array}$$

By Lemma 2.6, $S⟹T$. $\square$ A student remarked that $n\ne 0$ is needed; the lecturer had suppressed it for simplicity. It is included above.

3.5 Modus ponens (Script §2.6.4)

Definition 2.15 (Modus ponens)

To prove $S$: (1) find a suitable statement $R$; (2) prove $R$; (3) prove $R⟹S$.

Lemma 2.7

$A\wedge (A\to B)\models B.$

The proof is by truth table (Week 1, §3.6). The formula symbols are “translated” to statements: $A$ becomes ”$R$ is true”, $B$ becomes ”$S$ is true”, $\wedge$ becomes “and”, $\to$ becomes $⟹$.

Example (Lecture 5). $T$: $3001\mid 2^{3000}-1$.

Computing $2^{3000}-1$ directly is hopeless. Even computing $2^{3000}\mathrm{mod}3001$ by repeated squaring needs about ${\log }_{2}3000\approx 12$ squarings with large intermediate numbers. Modus ponens with $S$: “3001 is prime”:

1. Prove $S$: it suffices to check that no prime $\le \sqrt{3001}\approx 54.8$ divides 3001, i.e. the primes $2,3,5,\dots ,53$. None does, so 3001 is prime.
2. Prove $S⟹T$ using the lemma (Fermat’s little theorem for base 2, proved later in the number theory and algebra chapters): if $p$ is a prime with $p>2$, then $2^{p-1}{\equiv }_{p}1$. With $p=3001$: $2^{3000}{\equiv }_{3001}1$, i.e. $3001\mid 2^{3000}-1$.

Both steps hold, so $T$ follows. (Checked by computer: $2^{3000}\mathrm{mod}3001=1$.)

Source note (Lecture 5)

The lecturer said ”$2^{p-1}$ congruent 1 modulo K”. He meant modulo $p$: $2^{p-1}{\equiv }_{p}1$.

Exam Trap: ${\equiv }_p$ vs. $\equiv$

The symbol is overloaded. $a{\equiv }_{p}b$ between numbers (with a subscript) means ”$a$ and $b$ have the same remainder modulo $p$”, i.e. $p\mid a-b$ (Chapter 4). $F\equiv G$ between formulas means logical equivalence. Same glyph, unrelated meanings.

3.6 Case distinction (Script §2.6.5)

Definition 2.16 (Case distinction)

To prove $S$ by case distinction (Fallunterscheidung):

1. Find a finite list $R_1,\dots ,R_k$ of statements (the cases).
2. Prove that at least one $R_i$ is true (at least one case occurs).
3. Prove $R_i⟹S$ for every $i=1,\dots ,k$.

Steps 2 and 3 can be done in either order. For $k=1$ this is exactly modus ponens.

Lemma 2.8

For every $k$:
$(A_1\vee \cdots \vee A_k)\wedge (A_1\to B)\wedge \cdots \wedge (A_k\to B)\models B.$

The lecturer’s point: for each fixed $k$ this can be checked with a truth table ($2^{k+1}$ rows). But “for every $k$” is an infinite family of statements, and checking tables one $k$ at a time never finishes. We need induction for that (script remark).

Proof sketch by induction on $k$ (added, following the script’s remark):

• Base $k=1$: $A_1\wedge (A_1\to B)\models B$ is Lemma 2.7.

• Step $k\to k+1$: take an assignment making the left side for $k+1$ true. Then $A_1\vee \cdots \vee A_{k+1}$ is true.

  • If $A_1\vee \cdots \vee A_k$ is true, the left side for $k$ is true (all $A_i\to B$ for $i\le k$ are among the conjuncts), so $B$ is true by the induction hypothesis.
  • Otherwise $A_{k+1}$ must be true, and $A_{k+1}\to B$ gives $B$.

  Either way $B$ is true. $\square$

Example (Lecture 5): $P(4)=1$ for the chessboard. On a $4\times 4$ board, the marked square is a corner, an edge (non-corner) square, or an interior square. Up to rotation and reflection, these three cases cover all 16 positions. Give a tiling for each case. (The counting criterion $3\mid k^2-1$ is necessary but does not prove existence.)

Example 2.27 (script only). Claim: for every $n\in \mathbb{N}$ not divisible by 5, $n^4$ is one more than a multiple of 5.

1. Write $n=5k+c$ with $1\le c\le 4$ (possible since $5\nmid n$).
2. By the binomial formula $(a+b{)}^4=a^4+4a^{3}b+6a^2{b}^2+4a{b}^3+b^4$:
   $n^4=5^4{k}^4+4\cdot 5^3{k}^{3}c+6\cdot 5^2{k}^2{c}^2+4\cdot 5k{c}^3+c^4.$
3. Every summand except $c^4$ is divisible by 5. So the claim is equivalent to ”$c^4$ is one more than a multiple of 5” for $c\in \{1,2,3,4\}$.
4. Case distinction:

$c$	$c^4$	$c^4-1$
1	1	0 = 5·0
2	16	15 = 5·3
3	81	80 = 5·16
4	256	255 = 5·51

All cases hold. $\square$ (Later this generalizes to every odd prime in place of 5, via Fermat’s little theorem.)

3.7 Proof by contradiction (Script §2.6.6)

Definition 2.17 (Proof by contradiction)

To prove $S$ by contradiction (Widerspruchsbeweis):

1. Find a suitable statement $T$.
2. Prove that $T$ is false.
3. Assume that $S$ is false and prove (from this assumption) that $T$ is true, a contradiction.

In practice the order is often: assume $\neg S$, derive statements until one is visibly false. That one is $T$, and step 2 is then obvious. A contradiction is often marked with $↯$ (lightning); define the symbol if you use it.

Lemma 2.9

$(\neg A\to B)\wedge \neg B\models A.$ Since $\neg A\to B\equiv A\vee B$, equivalently $(A\vee B)\wedge \neg B\models A$: prove ”$S$ or $T$” and ”$T$ is false”.

Check: the right side is $0$ only for $A=0$. Then $\neg A=1$, so the left side needs $B=1$ (for $\neg A\to B$) and $\neg B=1$, i.e. $B=0$. Impossible, so the left side is $0$ whenever $A=0$. $\square$

Example 2.28 (Lecture 5): $\sqrt{2}$ is irrational.

Fact used: a number $a$ is rational iff $a=m/n$ for coprime (teilerfremd) integers $m,n$, i.e. $\gcd (m,n)=1$ (greatest common divisor, ggT; defined formally in §4.2.3). At most one of $m,n$ is then even.

$$\begin{array}{rlrl}S\text{ false}& \stackrel{\cdot }{⟺}\sqrt{2}\text{ is rational}& & \\ & \stackrel{\cdot }{⟺}\exists m\exists n(\sqrt{2}=m/n\wedge \gcd (m,n)=1)& & \\ & \stackrel{\cdot }{⟺}\exists m\exists n(m^2=2n^2\wedge \gcd (m,n)=1)& & \text{(square, multiply by }{n}^2)\end{array}$$

Now consider $m^2=2n^2$ on its own, for arbitrary $m,n$:

$$\begin{array}{rlrl}{m}^2=2n^2& \stackrel{\cdot }{⟹}2\mid m^2(m^2\text{ even})& & \\ & \stackrel{\cdot }{⟹}2\mid m(m\text{ even})& & \\ & \stackrel{\cdot }{⟹}4\mid m^2& & \\ & \stackrel{\cdot }{⟹}4\mid 2n^2& & (\text{using }{m}^2=2n^2)\\ & \stackrel{\cdot }{⟹}2\mid n^2& & \\ & \stackrel{\cdot }{⟹}2\mid n& & \\ & \stackrel{\cdot }{⟹}\gcd (m,n)\ge 2& & (\text{using that }m\text{ is even})\end{array}$$

Plugging this back in:

$$\exists m\exists n(m^2=2n^2\wedge \gcd (m,n)=1)\stackrel{\cdot }{⟹}\underset{T\text{, which is false}}{\underbrace{\exists m\exists n(m^2=2n^2\wedge \underset{\text{false for all }m,n}{\underbrace{\gcd (m,n)\ge 2\wedge \gcd (m,n)=1}})}}.$$

So $\neg S⟹T$ with $T$ false, hence $S$. $\square$ The script notes that the formulas here are only compact notation for statements; the reasoning is ordinary mathematics, not formula manipulation.

Why does $2\mid m^2$ imply $2\mid m$? (student question, Lecture 5)

Indirect proof: if $m$ is odd, $m=2j+1$, then $m^2=4j^2+4j+1=2(2j^2+2j)+1$ is odd. So ”$m$ odd $⟹m^2$ odd”, whose contrapositive is ”$m^2$ even $⟹m$ even”.

Via unique prime factorization (lecturer’s alternative): the exponent of 2 in $m^2$ is twice the exponent in $m$, so it is even. If $2\mid m^2$, that exponent is $\ge 1$, hence $\ge 2$, so the exponent in $m$ is $\ge 1$.

The lecture skipped this justification; a complete proof needs it.

3.8 Existence proofs and counterexamples (Script §2.6.7, §2.6.9)

Definition 2.18 (Existence proof)

Consider a universe $X$ of parameters and, for each $x\in X$, a statement $S_x$. An existence proof (Existenzbeweis) proves that $S_x$ is true for at least one $x\in X$, i.e. $\exists x{S}_x$.

• It is constructive if it exhibits a concrete $a$ with $S_a$ true.
• Otherwise it is non-constructive.

Definition 2.19 (Proof by counterexample)

A proof by counterexample (Beweis durch Gegenbeispiel) proves that $S_x$ is not true for all $x\in X$, i.e. $\neg \forall x{S}_x$, by exhibiting an $a$ (the counterexample) with $S_a$ false. Since $\neg \forall x{S}_x\equiv \exists x\neg S_x$, it is a constructive existence proof of a counterexample.

Examples:

• Example 2.29 (constructive): $\exists n(\text{prime}(n)\wedge \text{prime}(n-10)\wedge \text{prime}(n+10))$. Witness $n=13$: $3,13,23$ are all prime.
• Example 2.30 (non-constructive; infinitely many primes, $\forall m\exists p(\text{prime}(p)\wedge p>m)$):
  1. Fix $m$ and consider $m!+1$.
  2. No $k$ with $2\le k\le m$ divides $m!+1$, because $k\mid m!$ and so $m!+1$ leaves remainder 1.
  3. Every $n\ge 2$ has a prime divisor, so $m!+1$ has a prime divisor $p$, and $p>m$ by step 2.
  4. $p$ exists, but we don’t know it explicitly. In general $p\ne m!+1$.
• Example 2.34: "$\forall n\text{prime}(n^2-n+41)$" holds for $n=1,\dots ,40$, but $n=41$ gives $41^2$, which is not prime. Counterexample, so the claim is false. (Checked by computer: $n=41,42,45$ are the first failures.)
• Example 2.35: “every $n\ge 10$ is a sum of at most three squares”, i.e. $\forall n(n\ge 10\to \exists x\exists y\exists z(n=x^2+y^2+z^2))$. Counterexample $n=15$: only $0,1,4,9$ are squares $\le 15$, and no three of them sum to 15.

Exam Trap

A single example never proves a $\forall$-statement, but a single counterexample disproves it. Symmetrically, one witness proves an $\exists$-statement. “It works for $n=1,\dots ,40$” (Example 2.34) is not a proof.

3.9 The pigeonhole principle (Script §2.6.8)

Partition

A partition (Partition) of a set $S$ into $S_1,\dots ,S_k$ is a family of subsets with

• $S_i\cap S_j=\varnothing$ for all $i\ne j$ (pairwise disjoint), and
• $S_1\cup \cdots \cup S_k=S$ (together they cover $S$).

Hence $|S|=|S_1|+\cdots +|S_k|$.

Theorem 2.10 (Pigeonhole principle, Schubfachprinzip)

If a set of $n$ objects is partitioned into $k<n$ sets, then at least one of these sets contains at least $\lceil n/k\rceil$ objects.

Proof (by contradiction).

1. Suppose every part has at most $\lceil n/k\rceil -1$ objects.
2. Since the parts are disjoint and cover the set, the total is
   $n={\sum }_{i=1}^k|S_i|\le k(\lceil \frac{n}{k}\rceil -1)<k\left(\right(\frac{n}{k}+1)-1)=k\cdot \frac{n}{k}=n.$
   The strict inequality uses $\lceil n/k\rceil <n/k+1$, which holds because rounding up adds less than 1.
3. So $n<n$, a contradiction. $\square$

The lecturer called this an indirect proof: the theorem is an implication, and we derive “not a partition of $n$ objects” from the negated conclusion. The script calls it a proof by contradiction. Both descriptions fit.

Name: more pigeons than pigeonholes forces some hole to contain at least 2 pigeons. Since $k<n$, $\lceil n/k\rceil \ge 2$, which gives the classical version (footnote 41). The theorem is the quantitative strengthening.

Source note (Lecture 5)

1. The lecturer stated “there exists $i$ with $|S_i|$ greater than $\lceil n/k\rceil$”. That is wrong. Counterexample: $n=4$, $k=2$, parts of size $2,2$, and $\lceil 4/2\rceil =2$, so no part is $>2$. Correct: $\ge \lceil n/k\rceil$ (script, and also what the proof above shows).
2. When defining a partition he wrote ”$S_i\cap S_j=\varnothing$ for all $i,j$”. It must be for all $i\ne j$, since $S_i\cap S_i=S_i$.

Examples (script only):

• Example 2.31: among 100 people, at least 9 share a birth month: $n=100$, $k=12$, $\lceil 100/12\rceil =\lceil 8.33\rceil =9$.

• Example 2.32: every $A\subseteq \{1,\dots ,2n\}$ with $|A|=n+1$ contains distinct $a,b$ with $a\mid b$.

  1. Write each $a\in A$ as $a=2^{e}u$ with $u$ odd.
  2. There are only $n$ possible odd parts $u\in \{1,3,\dots ,2n-1\}$ (the holes) but $n+1$ numbers (the pigeons), so two numbers share the same $u$.
  3. The one with fewer factors of 2 divides the other.

  This is tight: $A=\{n,\dots ,2n-1\}$ has size $n$ and no such pair (e.g. $\{2,3,5,7,9,10\}$ contains $3\mid 9$).

• Example 2.33 (Erdős–Szekeres): every sequence of $m^2+1$ distinct numbers has a strictly increasing or strictly decreasing subsequence of length $m+1$.

  1. To each position $\ell$, assign $(i_{\ell },d_{\ell })$: the lengths of the longest increasing and decreasing subsequences starting at $\ell$.
  2. If the claim were false, all $i_{\ell },d_{\ell }\in \{1,\dots ,m\}$, so there are at most $m^2$ possible pairs for $m^2+1$ positions.
  3. By pigeonhole, some $s<t$ have $(i_s,d_s)=(i_t,d_t)$.
  4. If $a_s<a_t$, putting $a_s$ in front of the longest increasing subsequence from $t$ gives length $i_t+1=i_s+1>i_s$, a contradiction. If $a_s>a_t$, the same with $d$.

3.10 Proof by induction (Script §2.6.10)

Proof by induction (vollständige Induktion)

Goal: $\forall nP(n)$ over $U=\mathbb{N}=\{0,1,2,\dots \}$. In this course $0\in \mathbb{N}$ (convention).

1. Basis step (Induktionsanfang / Verankerung): prove $P(0)$.
2. Induction step (Induktionsschritt): prove that for an arbitrary $n$, $P(n)⟹P(n+1)$. Assume $P(n)$ (the induction hypothesis) and derive $P(n+1)$.

Variants: for $\{1,2,\dots \}$ prove $P(1)$ as the base; for $\{k,k+1,\dots \}$ prove $P(k)$.

Theorem 2.11 (justification of induction)

For the universe $\mathbb{N}$ and an arbitrary unary predicate $P$:
$P(0)\wedge \forall n(P(n)\to P(n+1))⟹\forall nP(n).$

Why this is special (lecturer’s emphasis). $\forall nP(n)$ contains infinitely many statements. Nothing in propositional or predicate logic as developed so far proves that the chain $P(0)\Rightarrow P(1)\Rightarrow P(2)\Rightarrow \cdots$ reaches every natural number. That is a property of $\mathbb{N}$ itself, so it is built into the definition of $\mathbb{N}$: Theorem 2.11 is one of the Peano axioms (Peano-Axiome), i.e. postulated, not proved. Script footnote 44: if one instead defines $\mathbb{N}$ within axiomatic set theory, the Peano axioms become provable theorems (beyond this course). A formal definition of $\mathbb{N}$ comes in the next lectures.

Notation question (Lecture 5). The lecturer wrote $⟹$ (statement arrow) between the parts, not $\models$ or $\to$, because he reads the formula under a fixed interpretation ($U=\mathbb{N}$, a concrete $P$) as a statement, so the axiom applies to arbitrary statements $P(n)$. Written with $\to$ it would be the formalization of the axiom in some calculus.

Why not over $\mathbb{R}$? (student question) Induction walks through the elements one by one: 0, then 1, then 2, and so on. $\mathbb{R}$ is “larger” than $\mathbb{N}$ (uncountable, §3.7), so no such enumeration reaches all reals, and the base plus successor step cannot cover them.

Example 2.36 (script only). ${\sum }_{i=0}^n{2}^i=2^{n+1}-1$ for all $n$.

• Basis: ${\sum }_{i=0}^0{2}^i=2^0=1=2^1-1$.

• Step: assume ${\sum }_{i=0}^n{2}^i=2^{n+1}-1$. Then
  ${\sum }_{i=0}^{n+1}{2}^i=\left({\sum }_{i=0}^n{2}^i\right)+2^{n+1}\stackrel{\text{IH}}{=}(2^{n+1}-1)+2^{n+1}=2\cdot 2^{n+1}-1=2^{(n+1)+1}-1.$

  We split off the last summand to make the induction hypothesis applicable. $\square$

Example 2.37 (script only). Which postages can be formed from 4-cent and 5-cent stamps?

• $1,2,3,6,7,11$ are impossible.
• $4,5,8,9,10,12,13,14,15$ are possible.
• Claim: every amount $\ge 15$ is possible. Let $P(n)$ = ”$n+15$ is a sum of 4s and 5s”.

  • Basis: $15=5+5+5$.

  • Step (by case distinction): assume a decomposition of $n+15$.

    • Case 1: it contains a 4. Replace one 4 by a 5, which gives $n+16$.
    • Case 2: it contains no 4. Since $n+15\ge 15$, it has at least three 5s. Replace three 5s ($=15$) by four 4s ($=16$), which gives $n+16$.

    Either way $P(n+1)$ holds. $\square$

---

4. Worked Examples & Applications

4.1 Interpretation $U=\mathbb{N}$ (Lecture 4)

Formula	Reading	Truth value
$\forall x(0\le x)$	every natural number is $\ge 0$	true (would be false on $\mathbb{R}$)
$\exists x(x\le 2)$	some number is $\le 2$	true ($x=0,1,2$)
$\exists x(x\le 2)\wedge \exists x(x\ge 3)$	some number $\le 2$ and some (other) number $\ge 3$	true
$\exists x(x\le 2\wedge x\ge 3)$	one number both $\le 2$ and $\ge 3$	false
$\forall x\exists y(x<y)$	there is no largest number	true
$\neg \forall x\exists y(x<y)$	there is a largest number	false

Negation pushed through (student’s solution):

$\neg \forall x\exists y(x<y)\equiv \exists x\neg \exists y(x<y)\equiv \exists x\forall y\neg (x<y)\equiv \exists x\forall y(x\ge y).$

“There is an $x$ that is $\ge$ every $y$”: a maximum exists. It is false on $\mathbb{N}$ but true on a finite universe like $\{0,1,\dots ,100\}$ (take $x=100$). Same formula, different interpretation, different truth value.

4.2 Defining $\text{prime}(x)$ (Lecture 4; Script Example 2.19)

Goal: a formula with free variable $x$ that is true exactly when $x$ is prime, using only $=$, $\cdot$, constants and quantifiers. $:⟺$ (or $\stackrel{\text{def}}{⟺}$) means “the left side is defined as the right side”.

Student’s solution (Lecture 4):

$\text{prime}(x):⟺\forall y\forall z((x=y\cdot z)\to (y=1\vee z=1))\wedge \neg (x=1).$

Script version: $\text{prime}(x)\stackrel{\text{def}}{⟺}x>1\wedge \forall y\forall z((yz=x)\to ((y=1)\vee (z=1)))$.

Step by step:

• $\forall y\forall z(x=y\cdot z\to \dots )$ ranges over every factorization of $x$, and each must be trivial ($1\cdot x$ or $x\cdot 1$).
• Without $\neg (x=1)$, the number $1$ would qualify: its only factorization is $1\cdot 1$.
• $x=0$ is excluded automatically: $0=0\cdot 2$ is a factorization with neither factor 1. The lecturer briefly considered adding $\neg (x=0)$ for safety; it is harmless but not needed. The script’s $x>1$ excludes both $0$ and $1$.

Exam Trap: $\forall$ vs. $\exists$ in definitions

Q (Lecture 4): “Why not $\exists y\exists z$?” With $\exists$, the formula would say that some factorization is trivial. That is true for every $x$ ($x=1\cdot x$), so every number would be “prime”. Q: “Doesn’t $18=1\cdot 18$ make 18 prime?” No. The $\forall$ demands that all factorizations be trivial, and $18=2\cdot 9$ violates it.

4.3 Reading formulas (Lecture 4; Script Examples 2.17–2.23)

• $U=\mathbb{N}$: $\forall m\exists n(n>m\wedge \text{prime}(n))$ says that above every number there is a prime, i.e. there are infinitely many primes (Example 2.21).
• $U=\mathbb{R}$: $\forall x(x=0\vee \exists y(x\cdot y=1))$ says every non-zero real has a multiplicative inverse. True on $\mathbb{R}$; false on $\mathbb{N}$ (e.g. $x=2$) (Example 2.22). Equivalent form (Example 2.24): $\forall x(\neg (x=0)\to \exists y(xy=1))$, since $F\vee G\equiv \neg F\to G$.
• (script only) Example 2.17: on $\mathbb{N}$, $\forall x(x\ge 2)$ is false; $\exists x(x+5=3)$ is false on $\mathbb{N}$ but true on $\mathbb{Z}$ ($x=-2$).
• (script only) Example 2.18: $\forall x\exists y(y<x)$ says there is no smallest element. True on $\mathbb{Z}$ and $\mathbb{R}$, false on $\mathbb{N}$ ($x=0$).
• (script only) Example 2.20, Fermat’s last theorem on $\mathbb{N}\setminus \{0\}$: $\neg \exists x\exists y\exists z\exists n(n\ge 3\wedge x^n+y^n=z^n)$. The script does not abbreviate $\exists x\exists y\exists z$ to $\exists xyz$.
• (script only) Example 2.23: $\forall x\forall y((x<y)\to \exists z(x<z\wedge z<y))$ says between any two distinct elements lies a third (“dense”). True on $\mathbb{Q}$ and $\mathbb{R}$ (take $z=(x+y)/2$); false on $\mathbb{N}$ and $\mathbb{Z}$ ($x=0,y=1$).
• (script only) §2.4.6: $\forall x((P(x)\wedge Q(x))\to (P(x)\vee Q(x)))$ is a tautology: for each $x$, the body is an instance of the propositional tautology $(A\wedge B)\to (A\vee B)$.

4.4 Family relations (Lecture 4)

Interpretation: $U$ = all humans. Simplifying assumptions: humans have always existed and always will, and everyone has parents (no philosophical claim intended). Basic predicate: $\text{par}(x,y)$: ”$x$ is a parent of $y$”.

$\text{child}(x,y):⟺\text{par}(y,x)$

$\text{sibling}(x,y):⟺\neg (x=y)\wedge \exists z(\text{par}(z,x)\wedge \text{par}(z,y))$

$\text{grandparent}(x,y):⟺\exists z(\text{par}(x,z)\wedge \text{par}(z,y))$

• Child: swap the arguments.
• Sibling: a common parent $z$. The student’s first proposal lacked $\neg (x=y)$. Mathematically, everyone would then be their own sibling. The lecture added $\neg (x=y)$ to match everyday language. The transcript does not capture the student’s exact formula, so this version is reconstructed. With one common parent, half-siblings count as siblings.
• Grandparent: $z$ is the parent in the middle.

Exam Trap: no recursive definitions

A student proposed $\text{ancestor}(x,y):⟺\text{par}(x,y)\vee \exists z(\text{par}(x,z)\wedge \text{ancestor}(z,y))$. Not allowed here. A definition may not use the defined predicate itself. Arbitrarily long chains ($\text{par}\vee \text{grandparent}\vee \dots$) cannot be written as a finite formula with our means. Ways around this exist, but they bring back self-reference problems such as “the set of all sets that do not contain themselves” (Chapter 3, Russell). Aside (added): it is a known theorem that “ancestor”, the transitive closure of $\text{par}$, is in general not definable in first-order predicate logic.

4.5 Which steps are reversible? (Lecture 5)

In a chain of $\stackrel{\cdot }{⟹}$ steps, only some steps are equivalences. The script writes $\stackrel{\cdot }{⟺}$ where both directions hold, but $\stackrel{\cdot }{⟹}$ always suffices (footnote 35).

Step	Reversible?
$a=u^2,b=v^2\Rightarrow ab=u^2{v}^2$	no ($9=3\cdot 3$, but $3$ is not a square)
$\sqrt{x}=m/n\Rightarrow x=m^2/n^2$	no in general ($x=2$: $2=2/1$, but $\sqrt{2}$ is not rational)
$m$ even $\Rightarrow 4\mid m^2$	no ($m=2$: fine; but $4\mid m^2$ implies $m$ even, so actually yes)
$\sqrt{2}$ rational $\iff \exists m,n(m^2=2n^2\wedge \gcd =1)$	yes (script uses $\stackrel{\cdot }{⟺}$)

(Row 3: $4\mid m^2\Rightarrow 2\mid m^2\Rightarrow 2\mid m$, so that step happens to be reversible. Always check each direction individually.)

---

5. Intuition & Conceptual Bridges

Every proof pattern is a tautology in disguise

Each pattern of §2.6 is a logical consequence of propositional logic, “translated” so that symbols become statements, $\wedge$ becomes “and”, and $\to$ becomes $⟹$.

Pattern	Justifying consequence
composition	$(A\to B)\wedge (B\to C)\models A\to C$ (L. 2.5)
indirect proof	$\neg B\to \neg A\models A\to B$ (L. 2.6)
modus ponens	$A\wedge (A\to B)\models B$ (L. 2.7)
case distinction	$(A_1\vee \cdots \vee A_k)\wedge {\bigwedge }_i(A_i\to B)\models B$ (L. 2.8)
contradiction	$(\neg A\to B)\wedge \neg B\models A$ (L. 2.9)
counterexample	$\neg \forall xP(x)\equiv \exists x\neg P(x)$
induction	Peano axiom (Thm. 2.11), not a tautology

Induction is the only one that is not a logical law but a property of $\mathbb{N}$. Invalid “patterns” correspond to non-tautologies, e.g. $B\wedge (A\to B)\models A$ fails (Week 1, the "$1<0$" proof).

Quantifiers are big AND and big OR

On a finite universe $U=\{u_1,\dots ,u_m\}$:

• $\forall xF(x)$ is $F(u_1)\wedge \cdots \wedge F(u_m)$;
• $\exists xF(x)$ is $F(u_1)\vee \cdots \vee F(u_m)$.

Then the quantifier laws follow from Lemma 2.1:

• $\neg \forall \equiv \exists \neg$ and $\neg \exists \equiv \forall \neg$ are de Morgan’s rules;
• $\forall (F\wedge G)\equiv \forall F\wedge \forall G$ is just reordering a long conjunction;
• $\exists x(F\wedge G)$ is a disjunction of $F(u_i)\wedge G(u_i)$, while $\exists xF\wedge \exists xG$ is a conjunction of two disjunctions with independent indices. So the second only follows from the first.

On infinite universes the “big” $\wedge /\vee$ become infinite, and that is where truth tables stop working.

Which pattern when? (Lecture 5 Q&A)

There is no ranking. Use what fits.

• Statements of the form “not … exists” or “is irrational/infinite” are often easiest by contradiction or indirectly: you get to assume something concrete ($\sqrt{x}=m/n$).
• “For all $n\in \mathbb{N}$” suggests induction.
• “There exist two … with …” with more objects than categories suggests pigeonhole.
• “For all” claims you suspect false call for a counterexample.

The lecturer admitted to having written unnecessarily long direct proofs in research papers that would have been short by contradiction.

Connections.

• Backwards: Week 1 tautologies ($A\wedge (A\to B)\models B$, transitivity) now justify proof patterns. The doubling theorem of the chessboard (Week 1) is an induction in disguise: base $P(1)$, step $P(2^i)\Rightarrow P(2^{i+1})$. $P(4)=1$ by case distinction is §2.6.5 in action.
• Forward: Chapter 3 (sets, relations, functions) starts next week. Transitivity and symmetry return as properties of relations defining equivalence relations and partial orders. Partitions (pigeonhole) return as equivalence classes. Russell’s paradox explains the ban on self-referential definitions. Countability (§3.7) explains why induction works on $\mathbb{N}$ but not $\mathbb{R}$. Chapter 4 proves the Fermat lemma used in the modus ponens example and defines $\gcd$ and ${\equiv }_m$. Chapter 6 makes interpretations, $\models$ for predicate logic, and proof calculi fully formal.

---

6. Summary & Self-Assessment Questions

Cheat sheet

Concept	Key fact
$\forall xF$	true iff $F$ true for every $x\in U$
$\exists xF$	true iff $F$ true for at least one $x\in U$
Scope	until the closing parenthesis or a re-quantification of the same variable
Free variable	not bound; the formula cannot be evaluated
Universe	non-empty set
Interpretation	fixes $U$ and the meaning of predicates, functions, constants
Valid (predicate logic)	true under all interpretations
Formula as statement	only under a fixed interpretation (§2.5)
Negation	$\neg \forall xF\equiv \exists x\neg F$, $\neg \exists xF\equiv \forall x\neg F$
$\forall$ and $\wedge$	$\forall xF\wedge \forall xG\equiv \forall x(F\wedge G)$
$\exists$ and $\wedge$	$\exists x(F\wedge G)\models \exists xF\wedge \exists xG$ (not $\equiv$)
$\forall$ and $\to$	$\forall x(F\to G)\models \forall xF\to \forall xG$ (not $\equiv$)
Mixed quantifiers	$\exists y\forall xP\models \forall x\exists yP$ (not $\equiv$)
prime$(x)$	$x>1\wedge \forall y\forall z(yz=x\to (y=1\vee z=1))$
Composition	$S\Rightarrow T$, $T\Rightarrow U$, hence $S\Rightarrow U$ (L. 2.5)
Direct proof	assume $S$, derive $T$ (Def. 2.13)
Indirect proof	assume $\neg T$, derive $\neg S$ (Def. 2.14, L. 2.6)
Modus ponens	find $R$, prove $R$, prove $R\Rightarrow S$ (Def. 2.15, L. 2.7)
Case distinction	cases $R_1..R_k$, at least one holds, each implies $S$ (Def. 2.16, L. 2.8)
Contradiction	$\neg S\Rightarrow T$ and $T$ false (Def. 2.17, L. 2.9)
Existence	exhibit a witness (constructive) or show existence otherwise (Def. 2.18)
Counterexample	one $a$ with $\neg S_a$ disproves $\forall x{S}_x$ (Def. 2.19)
Pigeonhole	$n$ objects in $k<n$ parts: some part has $\ge \lceil n/k\rceil$ (Thm. 2.10)
Induction	$P(0)$ and $\forall n(P(n)\Rightarrow P(n+1))$, hence $\forall nP(n)$ (Thm. 2.11, Peano)
$\mathbb{N}$	contains 0 in this course

Source notes: where lecture and correct version differ

1. L4: $\exists xF$ was described as “true if true for all $x$”. Correct: for at least one $x$.
2. L4: the empty universe was left open. The script requires $U\ne \varnothing$, which is needed for $\forall xP\models \exists xP$.
3. L4: the transitivity formula was briefly called a “tautology”. It is only true under the interpretations where $P$ is transitive.
4. L4: $\forall x(P(x)\to \neg P(x))\models \forall x\neg P(x)$ even holds as $\equiv$.
5. L4: the sibling formula is reconstructed; the transcript drops the student’s exact proposal.
6. L5: ”$2^{p-1}\equiv 1$ modulo $K$” should read modulo $p$.
7. L5: pigeonhole stated with "$>$". Correct: $\ge \lceil n/k\rceil$. Partition disjointness needs $i\ne j$.
8. L5: Lemma 2.8 “cannot be proved yet”. The script proves it by induction on $k$ (sketch in §3.6).

Self-assessment questions

Question 1. Let $U=\mathbb{Z}$ and $P(x,y)$: "$x+y=0$". Determine the truth value of (a) $\forall x\exists yP(x,y)$, (b) $\exists y\forall xP(x,y)$, (c) $\neg \forall x\exists yP(x,y)$ written with the negation pushed all the way inside. (d) Which of (a), (b) changes its truth value when $U=\mathbb{N}$?

Solution to Question 1

(a) True. For each $x$ choose $y=-x\in \mathbb{Z}$. Here $y$ depends on $x$, which $\forall x\exists y$ allows.
(b) False. A single $y$ would need $x+y=0$ for all $x$. But $x=-y$ and $x=-y+1$ cannot both satisfy it.
(c) $\neg \forall x\exists yP(x,y)\equiv \exists x\neg \exists yP(x,y)\equiv \exists x\forall y\neg P(x,y)$, i.e. $\exists x\forall y(x+y\ne 0)$. It is false on $\mathbb{Z}$, consistent with (a) being true.
(d) On $\mathbb{N}$, (a) becomes false: for $x=1$ there is no $y\in \mathbb{N}$ with $1+y=0$. (b) stays false: $y=0$ fails for $x=1$, and any $y\ge 1$ fails for every $x$. So only (a) changes.

Question 2. (a) Show that $\exists xP(x)\wedge \exists xQ(x)/\models \exists x(P(x)\wedge Q(x))$ with a concrete interpretation. (b) Is $\forall x(P(x)\vee Q(x))\equiv \forall xP(x)\vee \forall xQ(x)$? Prove the valid direction and refute the other.

Solution to Question 2

(a) $U=\mathbb{N}$, $P(x)$: ”$x$ even”, $Q(x)$: ”$x$ odd”. The left side is true (witnesses 0 and 1). The right side would need a number that is both even and odd, so it is false. One interpretation where the left is true and the right false refutes $\models$.
(b) Not equivalent; only $\forall xP(x)\vee \forall xQ(x)\models \forall x(P(x)\vee Q(x))$.

• Proof: if $\forall xP(x)$ is true, then every $x$ satisfies $P(x)$, hence $P(x)\vee Q(x)$. The same if $\forall xQ(x)$ is true (case distinction on which disjunct holds).
• Refutation of the converse: even/odd on $\mathbb{N}$ again. Every number is even or odd, so the left side is true. But not all numbers are even and not all are odd, so the right side is false.

This is the dual of the $\exists$/$\wedge$ law: $\forall$ distributes over $\wedge$, $\exists$ over $\vee$, and the mixed cases only give $\models$.

Question 3. Prove by an indirect proof: for every integer $n$, if $n^2$ is odd then $n$ is odd. Then state precisely why proving “if $n^2$ is even then $n$ is even” would not be an indirect proof of the same claim (and what it would prove instead).

Solution to Question 3

Let $S$: ”$n^2$ is odd”, $T$: ”$n$ is odd”. Indirect proof: assume $\neg T$, i.e. $n$ is even, $n=2k$. Then $n^2=4k^2=2(2k^2)$ is even, i.e. $\neg S$. So $\neg T⟹\neg S$, and by Lemma 2.6 ($\neg B\to \neg A\equiv A\to B$), $S⟹T$. $\square$

“If $n^2$ is even then $n$ is even” is $\neg S⟹\neg T$, which corresponds to $\neg A\to \neg B\equiv B\to A$. That is the converse ”$n$ odd $⟹n^2$ odd”, a different statement (true here, but not the claim). Negating without swapping is the classic error.

Question 4. (a) Prove by contradiction that $\sqrt{3}$ is irrational. Name $S$ and $T$ explicitly. (b) Where exactly would the analogous proof break down for $\sqrt{4}$?

Solution to Question 4

(a) $S$: ”$\sqrt{3}$ is irrational”. Assume $\neg S$: $\sqrt{3}=m/n$ with $\gcd (m,n)=1$, $n\ne 0$. Then $m^2=3n^2$.

1. $3\mid m^2$, hence $3\mid m$. (Indirect: if $3\nmid m$, then $m{\equiv }_{3}1$ or $2$, so $m^2{\equiv }_{3}1$, i.e. $3\nmid m^2$.)
2. Write $m=3j$. Then $9j^2=3n^2$, so $n^2=3j^2$, so $3\mid n^2$, hence $3\mid n$.
3. So $3\mid \gcd (m,n)$, i.e. $\gcd (m,n)\ge 3$.

$T$: ”$\exists m,n$ with $m^2=3n^2$, $\gcd (m,n)=1$ and $\gcd (m,n)\ge 3$”, which is false. We showed $\neg S⟹T$ and $T$ false, so $S$ holds (Lemma 2.9). $\square$
(b) For $\sqrt{4}$: $m^2=4n^2$ gives $2\mid m$, $m=2j$, $4j^2=4n^2$, so $j^2=n^2$. Nothing forces $2\mid n$ (e.g. $m=2,n=1$). The step "$4\mid 4n^2\Rightarrow 2\mid n^2$" has no analogue: dividing by 4 leaves no factor 2 behind. No contradiction arises, as it must be, since $\sqrt{4}=2/1$ is rational.

Question 5. (a) Show with the pigeonhole principle that among any 5 points in a unit square (side length 1), two have distance at most $\sqrt{2}/2$. (b) Prove by induction that ${\sum }_{i=1}^n(2i-1)=n^2$ for all $n\ge 1$. State base, hypothesis and step. (c) Why is “it holds for $n=1,\dots ,1000$, I checked by computer” not a proof of (b), and what pattern would a single failing $n$ give?

Solution to Question 5

(a) Split the unit square into 4 sub-squares of side $1/2$ (the “holes”; assign boundary points to any one adjacent sub-square so the parts form a partition). 5 points into $k=4<5$ parts: some part contains at least $\lceil 5/4\rceil =2$ points (Theorem 2.10). Two points in a square of side $1/2$ are at most its diagonal apart: $\sqrt{(1/2{)}^2+(1/2{)}^2}=\sqrt{2}/2$. $\square$
(b) $P(n)$: ${\sum }_{i=1}^n(2i-1)=n^2$, universe $\{1,2,\dots \}$, so the base is $P(1)$.

• Base: ${\sum }_{i=1}^1(2i-1)=1=1^2$.
• Hypothesis: ${\sum }_{i=1}^n(2i-1)=n^2$ for an arbitrary $n\ge 1$.
• Step: ${\sum }_{i=1}^{n+1}(2i-1)={\sum }_{i=1}^n(2i-1)+(2(n+1)-1)\stackrel{\text{IH}}{=}{n}^2+2n+1=(n+1{)}^2$.

By Theorem 2.11 (shifted to start at 1), $\forall n\ge 1P(n)$. $\square$
(c) Finitely many checks only prove $P(1)\wedge \cdots \wedge P(1000)$, not the infinite $\forall n$ (cf. $n^2-n+41$, prime up to $n=40$). One failing $n$ would be a counterexample (Def. 2.19), proving $\neg \forall nP(n)$.