Day 26 — Predicates & quantifiers

Day 26 — Predicates & quantifiers

Stage III · concept day
Goal: Work with predicates and a universe of discourse; use \(\forall\) and \(\exists\) correctly; distinguish free and bound variables; translate English carefully; negate quantified statements with \(\neg\forall \equiv \exists\neg\) and \(\neg\exists \equiv \forall\neg\); handle multiple variables at a single quantifier nesting depth.

Why this matters

Propositional logic cannot say “every user has a role” or “there exists a free port.” Specifications, type constraints, database integrity, and algorithm pre/postconditions are quantified. Negating “all tests pass” incorrectly is how false confidence survives in reviews. Master single-level quantifiers today; nesting order is Day 27.

Theory

Predicates and open sentences

A predicate \(P(x)\) is a statement template that becomes a proposition when \(x\) is fixed in a domain. Examples: \(E(n)\): “\(n\) is even”; \(R(u)\): “user \(u\) is registered.”

• \(E(4)\) is a proposition (true).
  
• \(E(n)\) with free \(n\) is not yet a proposition.

Predicates may take several arguments: \(L(x,y)\): “\(x < y\)”; \(T(u,r)\): “user \(u\) has role \(r\).”

Universe of discourse

The universe (domain) \(U\) is the set of values variables range over. Truth of quantified claims depends on \(U\).

• \(\forall x\, (x > 0)\) is false in \(\mathbb{Z}\), true if \(U = \{1,2,3\}\).
  
• Always state or inherit the universe.

Common universes: \(\mathbb{N},\mathbb{Z},\mathbb{R}\), finite sets of IDs, strings, nodes in a graph.

Universal quantifier \(\forall\)

\(\forall x\, P(x)\) means: for every \(x \in U\), \(P(x)\) is true.

• False if at least one counterexample \(c\in U\) has \(\neg P(c)\).
  
• True on empty universe? Vacuously true (every element—of which there are none—satisfies \(P\)). Rare in casual speech; remember for empty sets later.

Existential quantifier \(\exists\)

\(\exists x\, P(x)\) means: there exists at least one \(x \in U\) such that \(P(x)\).

• True if a witness \(c\) with \(P(c)\) exists.
  
• False if \(P(x)\) fails for all \(x\in U\).
  
• On empty universe: false (no witness).

Restricted quantifiers

\[\forall x \in S\, P(x) \quad\text{means}\quad \forall x\, \bigl(x\in S \rightarrow P(x)\bigr).\]

\[\exists x \in S\, P(x) \quad\text{means}\quad \exists x\, \bigl(x\in S \wedge P(x)\bigr).\]

Do not swap \(\rightarrow\) and \(\wedge\). “Every even integer is divisible by \(2\)” is \(\forall n\,(E(n)\rightarrow D(n))\), not \(\forall n\,(E(n)\wedge D(n))\) (the latter claims every integer is even).

Free and bound variables

An occurrence of \(x\) is bound if it is in the scope of a quantifier on \(x\); otherwise free.

• In \(\forall x\, (P(x) \rightarrow Q(y))\), \(x\) is bound, \(y\) is free.
  
• The formula is a predicate in \(y\), not a closed proposition, until \(y\) is fixed or quantified.

Alpha renaming: \(\forall x\, P(x)\) is the same claim as \(\forall t\, P(t)\) if \(t\) is fresh. Bound names are dummy.

Scope and parentheses

\(\forall x\, P(x) \wedge Q(x)\) is ambiguous in prose. Prefer:

• \((\forall x\, P(x)) \wedge Q(x)\) — \(x\) free in \(Q\), or
  
• \(\forall x\, \bigl(P(x) \wedge Q(x)\bigr)\) — both bound.

Write quantifier scope explicitly.

Multiple variables, single “layer”

\(\forall x \forall y\, P(x,y)\) means for every pair \((x,y)\), \(P\) holds. Same layer of “for all.”
\(\exists x \exists y\, P(x,y)\) means some pair works.

When quantifiers are the same kind, order can be swapped:

\[\forall x \forall y\, P(x,y) \equiv \forall y \forall x\, P(x,y), \qquad \exists x \exists y\, P(x,y) \equiv \exists y \exists x\, P(x,y).\]

Mixed \(\forall\exists\) vs \(\exists\forall\) is Day 27—order matters.

Negation rules (critical)

\[ \begin{align*} \neg \forall x\, P(x) &\equiv \exists x\, \neg P(x),\\ \neg \exists x\, P(x) &\equiv \forall x\, \neg P(x). \end{align*} \]

Push \(\neg\) through: flip quantifier, negate matrix. For restricted forms:

\[ \begin{align*} \neg \forall x\in S\, P(x) &\equiv \exists x\in S\, \neg P(x),\\ \neg \exists x\in S\, P(x) &\equiv \forall x\in S\, \neg P(x). \end{align*} \]

De Morgan for quantifiers is the infinite analogue of De Morgan for \(\wedge\)/\(\vee\):
\(\forall\) is like a big \(\wedge\) over \(U\); \(\exists\) is like a big \(\vee\).

Translating English carefully

English	Logical form (typical)
All \(P\)s are \(Q\)s	\(\forall x\,(P(x)\rightarrow Q(x))\)
Some \(P\) is a \(Q\)	\(\exists x\,(P(x)\wedge Q(x))\)
No \(P\) is a \(Q\)	\(\forall x\,(P(x)\rightarrow \neg Q(x))\) or \(\neg\exists x\,(P(x)\wedge Q(x))\)
Not all \(P\)s are \(Q\)s	\(\exists x\,(P(x)\wedge \neg Q(x))\)
Only \(P\)s are \(Q\)s	\(\forall x\,(Q(x)\rightarrow P(x))\)

“Any,” “each,” “every” → \(\forall\). “There is,” “at least one,” “some” → \(\exists\). “Unique” → Day 27 \(\exists!\).

Quantifiers and connectives (common valid patterns)

• \(\forall x\,(P(x) \wedge Q(x)) \equiv (\forall x\, P(x)) \wedge (\forall x\, Q(x))\).
  
• \(\exists x\,(P(x) \vee Q(x)) \equiv (\exists x\, P(x)) \vee (\exists x\, Q(x))\).
  
• \(\forall x\,(P(x) \vee Q(x))\) is weaker than \((\forall x\,P)\vee(\forall x\,Q)\)—not equivalent.
  
• \(\exists x\,(P(x) \wedge Q(x))\) is stronger than \((\exists x\,P)\wedge(\exists x\,Q)\)—not equivalent (witnesses may differ).

Proof obligations (preview)

• To prove \(\forall x\, P(x)\): let \(x\) be arbitrary in \(U\); prove \(P(x)\).
  
• To disprove \(\forall x\, P(x)\): exhibit one counterexample.
  
• To prove \(\exists x\, P(x)\): construct/find a witness (or non-constructive existence later).
  
• To disprove \(\exists x\, P(x)\): prove \(\forall x\, \neg P(x)\).

Worked examples

Example 1 — Universe matters

\(U=\mathbb{Z}\): \(\exists n\, (n^2 = 2)\) is false. \(U=\mathbb{R}\): true (\(n=\sqrt{2}\)). Always fix \(U\).

Example 2 — Restricted quantifier expansion

\(\forall n\in\mathbb{Z}\, (2\mid n \rightarrow 2\mid n^2)\) expands to \(\forall n\,(n\in\mathbb{Z} \rightarrow (2\mid n \rightarrow 2\mid n^2))\), or treat \(\mathbb{Z}\) as \(U\) and write \(\forall n\,(2\mid n \rightarrow 2\mid n^2)\).

Example 3 — Negate “all tests pass”

Let \(T(x)\): test \(x\) passes, \(U=\) test suite.
\(\neg \forall x\, T(x) \equiv \exists x\, \neg T(x)\): some test fails.
Not “all tests fail” (\(\forall x\, \neg T(x)\)).

Example 4 — Negate “some server is down”

\(D(s)\): server \(s\) is down.
\(\neg \exists s\, D(s) \equiv \forall s\, \neg D(s)\): every server is up.

Example 5 — Free vs bound

\(P(y): \forall x\, (x+y=y+x)\). Here \(y\) is free; for \(U=\mathbb{Z}\) the statement \(\forall x\,(x+y=y+x)\) is true for each fixed \(y\). Closing: \(\forall y\forall x\,(x+y=y+x)\).

Example 6 — Bad translation

English: “Every user has a password.”
Wrong: \(\forall u\, H(u) \wedge P(u)\) if \(H\) means “is user.”
Right with \(U=\) all users: \(\forall u\, P(u)\).
Right with \(U=\) all entities: \(\forall u\,(User(u)\rightarrow HasPassword(u))\).

Example 7 — Some vs all with and

\((\exists x\, P(x)) \wedge (\exists x\, Q(x))\) allows different witnesses.
\(\exists x\,(P(x)\wedge Q(x))\) needs one \(x\) with both.
\(P=\) “is even”, \(Q=\) “is odd” on \(\mathbb{Z}\): left true, right false.

Example 8 — Distribute \(\forall\) over \(\wedge\)

\(\forall n\,(n\ge 0 \wedge n\le n)\) \(\equiv\) \((\forall n\, n\ge 0)\wedge(\forall n\, n\le n)\)—but on \(\mathbb{Z}\) left is false because \(n\ge 0\) fails. On \(\mathbb{N}\) both sides true. Structure of \(\equiv\) holds regardless.

Example 9 — No \(P\) is \(Q\)

\(\neg \exists x\,(P(x)\wedge Q(x)) \equiv \forall x\, \neg(P(x)\wedge Q(x)) \equiv \forall x\,(\neg P(x)\vee \neg Q(x)) \equiv \forall x\,(P(x)\rightarrow \neg Q(x))\).

Example 10 — Multiple same quantifiers

\(\forall x \forall y\, (x+y=y+x)\) on \(\mathbb{R}\): true. Same as \(\forall y \forall x\).
\(\exists x \exists y\, (x^2+y^2=0)\) on \(\mathbb{R}\): true, witness \((0,0)\).

Example 11 — Vacuous restricted universal

\(\forall x\in\emptyset\, P(x)\) is true for any \(P\) (empty \(\rightarrow\) product).
\(\exists x\in\emptyset\, P(x)\) is false.

Example 12 — Program spec

“For every request \(r\), if \(r\) is authenticated then \(r\) receives \(200\) or \(403\).”
\(\forall r\, \bigl(Auth(r) \rightarrow (Ok(r) \vee Forbidden(r))\bigr)\).

Example 13 — Negate nested same-type carefully

\(\neg \forall x \forall y\, P(x,y) \equiv \exists x\, \neg\forall y\, P(x,y) \equiv \exists x \exists y\, \neg P(x,y)\).
Flip each quantifier as \(\neg\) moves right.

Example 14 — “Only if” with quantifiers

“A file is deleted only if it is marked trash”: \(\forall f\,(Deleted(f)\rightarrow Trash(f))\).

Exercises

1. Let \(U=\mathbb{Z}\). Truth value: \(\forall n\, (n^2 \ge 0)\); \(\exists n\, (n^2 < 0)\); \(\exists n\, (n^2=2)\).
   
2. Translate: “Every prime greater than \(2\) is odd.”
   
3. Translate: “Some integer is both even and divisible by \(3\).”
   
4. Negate and simplify: \(\forall x\, (P(x) \rightarrow Q(x))\).
   
5. Negate: \(\exists x\, (P(x) \wedge \neg Q(x))\).
   
6. Expand \(\exists n\in\mathbb{N}\, (n^2=n)\) with \(\wedge\) form; is it true?
   
7. Identify free/bound: \(\forall x\, (P(x,y) \rightarrow \exists y\, Q(x,y))\). Careful with the two \(y\)s—rewrite with safe names.
   
8. Show by counter-universe or reasoning: \(\forall x\,(P\vee Q) \not\equiv (\forall x\,P)\vee(\forall x\,Q)\) with predicates on a \(2\)-element set.
   
9. Same for \(\exists(P\wedge Q)\) vs \((\exists P)\wedge(\exists Q)\).
   
10. Write “No logged-in user is banned” in two equivalent ways.
    
11. Universe \(U=\{1,2,3\}\). Expand \(\forall x\, P(x)\) as a conjunction; \(\exists x\, P(x)\) as a disjunction.
    
12. Negate \(\forall x\in S\, \exists y\, R(x,y)\) fully (push \(\neg\) all the way)—preview Day 27.
    
13. Translate: “Not every process is runnable.”
    
14. Is \(\forall x\, P(x) \rightarrow \exists x\, P(x)\) always true? Discuss empty universe.
    
15. Formalize: “There is a user with no roles.”
    
16. Formalize: “Every even integer is a sum of two integers” (trivial on \(\mathbb{Z}\))—write it, then specialize.
    
17. Which is stronger on nonempty \(U\): \(\forall x\, P(x)\) or \(\exists x\, P(x)\)?
    
18. Prove or disprove on \(\mathbb{Z}\): \(\exists n\, \forall m\, (n \le m)\).
    
19. Prove or disprove on \(\mathbb{Z}\): \(\forall m\, \exists n\, (n \le m)\). (Order still single insight.)
    
20. Give alpha-renaming of \(\forall x \exists y\, (y > x)\) with variables \(a,b\).
    
21. Translate a DB constraint: “Every order has at least one line item.”
    
22. Negate: \(\exists x\, \forall y\, (x \le y)\) on \(\mathbb{R}\) and state truth of original.
    
23. Write \(\forall x\in A\, P(x)\) and \(\exists x\in A\, P(x)\) using only unrestricted quantifiers and \(\in\).
    
24. English → logic: “Any cache miss causes a fetch.”
    
25. Logic → English: \(\neg\exists u\,(Admin(u)\wedge Banned(u))\).

CS connection

• Preconditions/postconditions: \(\forall\) inputs satisfying pre, post holds; \(\exists\) path that fails is a bug report.
  
• SQL: ALL / EXISTS / NOT EXISTS mirror quantifiers; WHERE NOT EXISTS is often \(\neg\exists\).
  
• Type systems: “for all types \(T\)” in generics/parametric polymorphism (awareness).
  
• Access control: “every request has a principal” as integrity invariant.
  
• Testing: universal claims need counterexample search; existential claims need a witness test.
  
• Configuration: “some replica is primary” (\(\exists\)! often desired—Day 27).

Common pitfalls

Pitfall	What to do instead
\(\forall\) with \(\wedge\) for “all \(P\) are \(Q\)”	Use \(\rightarrow\) for restricted universals
\(\exists\) with \(\rightarrow\)	Use \(\wedge\): \(\exists x\,(P\wedge Q)\)
Negating \(\forall\) to \(\forall\neg\)	\(\neg\forall \equiv \exists\neg\)
Ignoring universe	State \(U\) or \(x\in S\)
Free variables left in “theorems”	Quantify or instantiate
Same witness assumed for two \(\exists\)	Combine into one \(\exists\) only if joint property
Scope ambiguity	Parenthesize quantifier bodies

Checkpoint

• Define predicate, universe, \(\forall\), \(\exists\)
  
• Expand restricted \(\forall\)/\(\exists\) correctly
  
• Mark free vs bound in a mixed formula
  
• Negate \(\forall\) and \(\exists\) statements fluently
  
• Translate “all / some / no / not all”
  
• Know when \(\forall\) distributes over \(\wedge\) and when \(\exists\) over \(\vee\)
  
• Give witness vs counterexample proof obligations
  
• Exercises done or logged

Two takeaways:

1. …
   
2. …

Deep dive — quantifiers as big meet/join

If \(U=\{a_1,\ldots,a_n\}\) is finite,
\[\forall x\, P(x) \;\equiv\; P(a_1)\wedge\cdots\wedge P(a_n), \qquad \exists x\, P(x)\;\equiv\; P(a_1)\vee\cdots\vee P(a_n).\]
De Morgan for quantifiers is then ordinary De Morgan on a long conjunction/disjunction. On infinite \(U\), the same idea holds but the conjunction is infinite—still the right mental model for negation and for restricted quantifiers.

Order of rewriting restricted forms

\[\neg\forall x\in S\, P(x) \equiv \neg\forall x\,(x\in S\rightarrow P(x)) \equiv \exists x\, \neg(x\in S\rightarrow P(x)) \equiv \exists x\,(x\in S \wedge \neg P(x)).\]
Do not “flip \(\in S\).” The restriction stays existential with \(\wedge\).

Common valid/invalid quantifier–connective moves

Claim	Status
\(\forall x(P\wedge Q)\equiv(\forall x P)\wedge(\forall x Q)\)	Valid
\(\exists x(P\vee Q)\equiv(\exists x P)\vee(\exists x Q)\)	Valid
\(\forall x(P\vee Q)\equiv(\forall x P)\vee(\forall x Q)\)	Invalid
\(\exists x(P\wedge Q)\equiv(\exists x P)\wedge(\exists x Q)\)	Invalid
\(\forall x(P\rightarrow Q)\Rightarrow ((\forall x P)\rightarrow(\forall x Q))\)	Valid (careful proof)
converse of previous	Invalid in general

More worked examples

Example 15 — Empty domain
On \(U=\emptyset\): \(\forall x\, P\) true, \(\exists x\, P\) false, for any \(P\).

Example 16 — Translate “only admins can delete”
\(\forall u\,(Delete(u)\rightarrow Admin(u))\).

Example 17 — Negate “every even is sum of two primes” (Goldbach form)
\(\exists n\,(Even(n)\wedge n>2 \wedge \neg\exists p,q\,(Prime(p)\wedge Prime(q)\wedge p+q=n))\)
(status open for all even \(n\)—here only practice negation).

Example 18 — Free variable bug
Claim written \(\forall x\, P(x,y)\) as a “theorem” still depends on \(y\) unless quantified.

Additional exercises

26. Expand and negate \(\forall x\in\mathbb{Z}\, (x>0 \rightarrow x^2>0)\).
    
27. Give a universe where \(\forall x(P\vee Q)\) true but \((\forall x P)\vee(\forall x Q)\) false.
    
28. Formalize: “There is exactly one empty string” without \(\exists!\) using length.
    
29. SQL-flavored: negate NOT EXISTS (SELECT 1 FROM t WHERE bad(t)) in logic.
    
30. Prove carefully \(\forall x(P\rightarrow Q)\) and \(\forall x P\) imply \(\forall x Q\).

Synthesis

Single-layer quantifiers are the bridge from propositional logic to real specifications. Everything you do with nested quantifiers (Day 27), proofs (Days 28–32), and set theory (Stage IV) still rests on: fix a universe, expand restricted forms correctly, push negations by flipping quantifiers, and know whether you need a witness or a counterexample.

Translation → negation → proof duty pipeline

1. English → formal. Identify “all / some / no / not all / only.”
   
2. Expand restrictions. \(\forall x\in S\) uses \(\rightarrow\); \(\exists x\in S\) uses \(\wedge\).
   
3. Negate if disproving or writing the dual claim. Flip each quantifier; push \(\neg\) onto the matrix.
   
4. Choose obligation. Prove \(\forall\) by arbitrary \(x\); disprove \(\forall\) by one counterexample; prove \(\exists\) by a witness; disprove \(\exists\) by proving \(\forall\neg\).

More worked examples

Example 19 — “Only \(P\)s are \(Q\)s” vs “all \(P\)s are \(Q\)s.”
Only: \(\forall x\,(Q(x)\rightarrow P(x))\). All: \(\forall x\,(P(x)\rightarrow Q(x))\). These are converses—neither implies the other.
Counter-models: \(U=\{1,2\}\), \(P=\{1\}\), \(Q=\{1,2\}\) makes “all \(P\) are \(Q\)” true and “only \(P\) are \(Q\)” false.

Example 20 — Spec that looks universal but is existential.
“The system has a recovery path” is \(\exists\) path, not \(\forall\) paths. Formalize: \(\exists p\, Recovery(p)\). Negation: every path fails recovery.

Example 21 — Finite expansion as a proof tool.
On \(U=\{a,b,c\}\), \(\forall x\, P(x)\) is \(P(a)\wedge P(b)\wedge P(c)\). To prove it, prove three propositions. To disprove, falsify one. Same discipline scales to infinite \(U\) with an arbitrary-element proof instead of a finite \(\wedge\)-chain.

Example 22 — When \(\forall x(P\rightarrow Q)\) and \((\forall x P)\rightarrow(\forall x Q)\) differ in flavor.
The first is “every individual that is \(P\) is \(Q\).” The second is “if everything is \(P\), then everything is \(Q\).” On a nonempty universe, \(\forall x(P\rightarrow Q)\) implies the second, but the second can hold vacuously when \(\forall x P\) is false even if some \(P\) fails to be \(Q\).

Extra exercises (synthesis)

31. Pipeline practice: translate “No expired token is accepted,” negate it, then state how you would prove the original (arbitrary token that is expired…).
    
32. On \(U=\{0,1\}\), invent predicates making \(\exists x(P\wedge Q)\) false while \((\exists x P)\wedge(\exists x Q)\) true.
    
33. Expand \(\forall n\in\mathbb{N}\, (n\ge 2 \rightarrow \exists p\,(Prime(p)\wedge p\mid n))\) and identify free vs bound names.
    
34. Explain in two sentences why empty-universe \(\forall\) is true and empty-universe \(\exists\) is false.
    
35. Write a four-row “mini truth table” of proof duties: prove/disprove \(\forall\) and \(\exists\).

Self-check before Day 27

• Can you expand and negate restricted \(\forall\)/\(\exists\) without swapping \(\rightarrow\) and \(\wedge\)?
  
• Can you give a \(2\)-element counter-model to illicit distribution of \(\forall\) over \(\vee\)?
  
• Can you mark free and bound variables after \(\alpha\)-renaming collisions?

If any answer is no, rework Examples 3–7 and Exercises 4–9 cold before nesting quantifiers.

Tomorrow

Day 27 — Nested quantifiers. Order matters; \(\forall\exists\) vs \(\exists\forall\); unique existence \(\exists!\); witnesses; sorting and database English.