First-Order Logic

Propositional logic treats "every prime greater than 2 is odd" as one indivisible proposition. It cannot see the structure inside: the objects (numbers), the properties (prime, odd) and the word "every". First-order logic (predicate logic) adds exactly these: variables that range over a domain, predicates that describe properties and relations of objects, and the quantifiers "for all" and "there exists".

First-order logic is the language of mathematical definitions (limits, asymptotic notation, injectivity), of database queries (tuple relational calculus is a fragment of it), and of program specifications. The working skills are translation between English and formulas, the effect of quantifier order, negation of quantified statements, and deciding which formulas are valid.

Over a finite domain $D = \{d_1, \ldots, d_n\}$:

This is the bridge between first-order and propositional reasoning, and a reliable way to test a claim on a small domain.

Domain convention. Domains are always non-empty here (the standard convention). Under it, $\forall x\, P(x) \to \exists x\, P(x)$ is valid; over an empty domain it would fail.

In $\forall x\,(P(x) \to Q(x, y))$, the variable $x$ is bound by $\forall x$, whose scope is the parenthesised formula; $y$ is free. A formula with no free variables is a sentence and has a truth value once the domain and the meaning of the predicates (an interpretation) are fixed.

Precedence: quantifiers bind more tightly than all connectives, so $\forall x\, P(x) \lor Q(x)$ means $(\forall x\, P(x)) \lor Q(x)$, and the second $x$ is free. Write the parentheses explicitly when the scope should extend.

Rule: $\forall$ goes with $\to$; $\exists$ goes with $\land$.

Negation moves inward, flipping each quantifier it passes and finally negating the matrix:

For restricted forms: $\neg \forall x\,(S(x) \to E(x)) \equiv \exists x\,(S(x) \land \neg E(x))$ ("some student is not enrolled"), and $\neg \exists x\,(S(x) \land E(x)) \equiv \forall x\,(S(x) \to \neg E(x))$ ("no student is enrolled").

Quantifiers of the same kind commute: $\forall x\, \forall y \equiv \forall y\, \forall x$ and $\exists x\, \exists y \equiv \exists y\, \exists x$. Quantifiers of different kinds generally do not:

The valid direction is

and the converse is not valid. A single witness $y$ that works for all $x$ certainly provides a $y$ for each $x$, but not the other way round.

Counterexample for the converse of row 3: domain $\{1, 2\}$, $P$ true only at 1, $Q$ true only at 2. Every element satisfies $P \lor Q$, but neither $P$ nor $Q$ holds everywhere.

When $x$ does not occur free in $A$:

The last two need care: moving a quantifier out of the antecedent of an implication flips it. ($\exists x\,(P(x) \to A) \equiv \forall x\, P(x) \to A$ relies on the domain being non-empty.)

A sentence is valid if it is true in every interpretation (every non-empty domain and every meaning of the predicates), satisfiable if true in at least one, and unsatisfiable if true in none. To show a sentence is not valid, give one interpretation that makes it false. To show it is valid, argue for an arbitrary interpretation.

Unlike propositional logic, validity in first-order logic cannot in general be decided by any algorithm (Church and Turing). On short problems, small counter-models are the practical tool.

Universal modus ponens: from $\forall x\,(P(x) \to Q(x))$ and $P(a)$, infer $Q(a)$. Example: "All primes greater than 2 are odd; 7 is a prime greater than 2; so 7 is odd."

Domain: people. $L(x, y)$: "$x$ loves $y$".

Let $D$ be the domain of $f$, with $a$ an accumulation point of $D$. Negate “for every $\varepsilon>0$ there is $\delta>0$ such that for all $x\in D$, $0<|x-a|<\delta\to |f(x)-L|<\varepsilon$”:

This is precisely "the limit of $f$ at $a$ is not $L$" (see Limits). The implication becomes a conjunction, as $\neg(p \to q) \equiv p \land \neg q$.

Claim: $\forall x\, \exists y\, P(x, y) \equiv \exists y\, \forall x\, P(x, y)$.

Domain $\{1, 2\}$, $P(x, y)$ true exactly when $x = y$. Left side: for $x = 1$ choose $y = 1$, for $x = 2$ choose $y = 2$: true. Right side: $y = 1$ fails at $x = 2$, $y = 2$ fails at $x = 1$: false. The claim is false. Over the $2^4 = 16$ possible relations $P$ on $\{1, 2\}$, the left side is true for 9 of them and the right side for 7, and every relation that makes the right side true also makes the left side true.

Is $\exists x\,(P(x) \to Q(x)) \to (\exists x\, P(x) \to \exists x\, Q(x))$ valid?

Try to falsify. Need $\exists x\, P(x)$ true and $\exists x\, Q(x)$ false, so $Q$ is false everywhere; and need $\exists x\,(P(x) \to Q(x))$ true. Domain $\{1, 2\}$, $P(1)$ true, $P(2)$ false, $Q$ false everywhere: at $x = 2$, $P \to Q$ is $F \to F = T$. Antecedent true, consequent false: not valid. Compare with the valid sentence $\forall x\,(P(x) \to Q(x)) \to (\exists x\, P(x) \to \exists x\, Q(x))$.