Why a quantified specification needs more than a truth table
The assertion that every vertex has an outgoing neighbor is a single sentence, yet its meaning depends on the graph. It can hold on a directed cycle and fail after deleting one edge. Propositional logic can name the whole assertion as a Boolean variable, but cannot explain how its truth depends on individual vertices. Predicate logic supplies that internal structure: a relation describes the edges, variables stand for vertices, and quantifiers specify which choices must succeed.
This structure matters when turning a specification into a proof or program. A neighbor chosen after seeing a vertex may depend on that vertex. A single neighbor required to serve every vertex must be chosen without that information. Confusing these requirements can turn a correct per-input algorithm into an impossible constant-output promise.
This note develops elementary relational first-order logic. It gives sound reasoning rules and an exact finite evaluator; it does not claim a complete first-order proof calculus.
Structures, assignments and variable scope
Definition 12.2.1
(Relational structures and terms)
Fix a nonempty domain . A relational vocabulary lists predicate symbols with their arities: for instance, a unary symbol and a binary symbol . A structure interprets as a subset of and as a subset of . Equality means actual equality of domain elements. We allow constant symbols, each naming a specified element of , but no function symbols are needed here. A term is a variable or a constant.
Definition 12.2.2
(Assignments and the truth of quantified formulas)
An assignment gives each variable a domain value. The atom is true under exactly when belongs to the interpreted relation. Constants use their fixed interpretations. The connectives combine truth values as in propositional logic. For quantifiers, write for the assignment changed only at :
Definition 12.2.3
(Bound and free variables, sentences)
An occurrence of a variable is bound when it lies in the scope of a quantifier for that variable; otherwise it is free. The innermost such quantifier determines a bound occurrence. Thus in the first is free, the second is bound, and is free. A formula with no free variables is a sentence. Its truth depends on the structure but not the assignment: an induction through the formula shows that only values of free variables can affect its truth.
Common mistake
(Shadowing a variable with a nested quantifier)
Use different names for nested roles whenever possible. The sentence is legal, but the inner quantifier hides the outer variable. It says merely that some element has a loop, because is nonempty. It does not say that every vertex has a loop. Renaming only the inner bound variable gives and makes the lost dependence visible.
Definition 12.2.4
(Truth in a structure, validity and entailment)
A statement is true in a structure after its domain and relations have been fixed. A sentence is valid if it is true in every structure of its vocabulary under our nonempty-domain convention. A set of premises entails a conclusion if every structure and assignment making all premises true also makes true. Testing one graph establishes truth there; it cannot establish validity across all graphs.
Substitution must preserve what a variable means
Definition 12.2.5
(Capture-safe substitution)
Write for replacing the free occurrences of by a term . Bound occurrences of are untouched. Before substituting, rename any bound variables that would capture a variable in . Such renaming changes a bound name consistently inside its scope and uses a fresh name, so it leaves meaning unchanged. Choosing a fresh name is always possible because a finite formula uses only finitely many variable names.
Worked example 12.2.6
(A substitution that accidentally changes the question)
Let and substitute the variable for the free . Direct textual replacement produces , which asks for a loop. First rename the bound variable to , obtaining ; the correct result is , which asks whether the vertex currently assigned to the free has an outgoing neighbor. On the two-vertex graph with only the edge , and assignment , the correct result is true while the captured version is false.
Theorem 12.2.7
(The meaning of capture-safe substitution)
Let be a variable or a constant, and perform the preceding capture-safe substitution. A formula is true under exactly when is true under , where is the value of under the original assignment.
Proof
(Induction on the structure of the formula)
For an atom, the replacement changes precisely the argument positions formerly occupied by free , so both sides test the same tuple. The connective cases follow by combining the induction hypotheses. At a quantifier binding , substitution stops and the quantified truth is independent of the incoming value of . At a quantifier binding another variable , rename first if needed so that it does not occur in . Changing then does not change 's value, and the updates at distinct commute. Apply the induction hypothesis for each and use the same universal or existential condition. This proves the statement by induction on the formula.
The lemma explains why substitution rules have a side condition. They assert that a syntactic change represents a particular change of assignment. Variable capture breaks that correspondence; it is a mathematical error, rather than a matter of preferred notation.
Four quantifier rules and their hypotheses
Universal elimination: from , infer , using capture-safe substitution. The universal statement holds at the value named by , and the substitution lemma identifies the resulting instance.
Existential introduction: from , infer . The value of provides the witness. In both rules, must denote a domain element; an undefined expression is not a legitimate instance.
Universal introduction: introduce a fresh parameter , prove without any extra assumption specific to , and conclude . More precisely, must not occur in the undischarged premises or in the original formula. A parameter here is a new constant whose interpretation is arbitrary.
Existential elimination: suppose the premises imply . Temporarily assume for a fresh parameter , and derive a conclusion . If occurs neither in nor in the other undischarged premises or the original , discharge the temporary assumption and infer .
Proposition 12.2.8
(Soundness of the four quantifier rules)
Each of the four rules, applied under its stated side conditions, is sound: every structure and assignment that satisfies the premises also satisfies the conclusion.
Proof
(Why the freshness conditions give soundness)
For universal elimination, the universal statement holds at the value named by , and the substitution lemma identifies the resulting instance. For existential introduction, the value of provides the witness.
For universal introduction, fix a structure satisfying the premises and any , and interpret as . The premises do not mention , so they still hold, and the proof of then shows that holds at . Since was arbitrary, holds at every element.
For existential elimination, fix a structure satisfying the original premises. Since they imply , choose a witness for it and interpret as that witness, so holds. The temporary derivation proves ; since does not mention , its truth is a conclusion about the original structure.
Proof X-ray
An arbitrary element and an unknown witness have different jobs
For universal introduction, the proof must work for every interpretation of a new name. For existential elimination, the proof uses one interpretation that satisfies the witness property, but its final conclusion must not depend on which name was used. The freshness restrictions are what let these two semantic arguments go through. Writing “let be arbitrary” cannot remove an assumption already restricting .
Worked example 12.2.9
(Moving an existential claim through a universal implication)
Assume and . To prove , temporarily name a witness with . Universal elimination gives , so follows. Existential introduction gives . This conclusion contains no , so existential elimination discharges the temporary witness assumption. We have not identified a predetermined named element satisfying ; we have proved that some element does.
Counterexample mode
A witness does not become a specified constant
Let , let hold only at , and let an existing constant name . Then is true but is false. The inference from an existential claim to a claim about a previously specified element is invalid. Similarly, from a temporary assumption one cannot introduce while that assumption is undischarged: the supposed arbitrary parameter has been restricted.
Negation, restricted domains and witness dependence
Proposition 12.2.10
(Quantifier negation)
For every formula ,
Proof
(Negation through the semantic clauses)
For the first identity, failure at every value is not required: a universal fails precisely when at least one value falsifies its body. The second says that no witness exists precisely when every value fails.
Applying these identities one quantifier at a time gives
Common mistake
(Negating a universal-existential sentence needs a vertex, not an edge)
The right side asks for a vertex with no outgoing edge. It does not ask for one missing edge: a single missing edge only refutes the stronger statement .
Definition 12.2.11
(Restricted quantifiers)
For a subset , restricted quantifiers abbreviate
where means membership in .
Common mistake
(Restricting a universal with a conjunction)
If is empty, the restricted universal is true and the restricted existential false, even though the ambient domain is nonempty. Writing the universal with a conjunction instead is a mistake: requires every domain element to belong to as well as satisfy , so it is false whenever is empty. The implication in the universal restriction is essential.
Proposition 12.2.12
(Exchanging a universal and an existential quantifier)
For every formula , the sentence implies . The converse implication is not valid in general.
Proof
(One witness serves every choice of x)
In , the witness for may depend on ; in , it must work for every . If the second sentence holds with witness , then after any choice of the same witnesses the first sentence.
Counterexample mode
A witness chosen after x need not serve every x
Take the domain and let mean . Then is true: choose . But is false: fails at , and fails at . No single value equals both elements, so the converse implication fails.
For a sentence consisting of a string of quantifiers followed by a quantifier-free formula, each existential choice may depend on earlier choices but not on later universal choices. This is a direct reading of the nested semantic conditions, not permission to guess future information.
Concept lensStructural
Witnesses as functions of earlier choices
On a finite domain, says exactly that there is a function with for every , while says that such a function can be taken constant. In general, each existential variable is witnessed by a function of the universal variables quantified before it, and of none quantified after it. This reading explains why a constant function gives the implication above, and why a table of witnesses indexed by the earlier choices may be much larger than the formula.
An exact algorithm for a finite structure
Suppose is explicitly enumerable with elements. Given a formula and values for its free variables, evaluate atoms in the supplied relations, combine Boolean results recursively, and implement quantifiers as finite loops. For a universal, evaluate the body with assigned each domain value; stop with false at the first false body, or return true after the loop. For an existential, stop with true at the first true body, or return false after the loop. Save and restore the old assignment to when leaving its scope. This is needed when the same variable name also has an outer meaning.
Theorem 12.2.13
(Finite evaluation is correct and terminates)
The recursive evaluator returns the semantic truth value for every formula, every finite structure of this kind and every assignment of its free variables. If the formula has parse-tree size , maximum nested quantifier depth , and unit-cost term evaluation and relation membership, its worst-case time is . Beyond the stored model and read-only formula, a depth-first implementation needs working machine words, assuming a domain index fits one word.
Proof
(Correctness by induction and the cost count)
Correctness follows by induction on the formula. Atoms use exactly their interpretation. Each connective uses the correct truth function on recursively correct results. At a universal, the loop visits every with exactly the assignment required by the semantic clause; an early false value disproves the universal, and an exhausted loop proves every case. The existential argument uses an early witness or the failure of all cases. Assignment restoration prevents one recursive evaluation from changing the meaning of a sibling. The recursion descends to strictly smaller formula nodes, and every loop is finite, proving termination.
For the time bound, each quantifier on a path contributes at most a factor . A particular parse-tree node is therefore evaluated at most times, and there are nodes. Local Boolean work and loop overhead satisfy the same bound. A depth-first traversal stores at most call frames, variable values and loop positions; it need not retain the entire tree of choices. Relation tables, input encoding and the cost of accessing a tuple are separate from the stated unit-cost model.
For a fixed formula, is fixed, so this is a polynomial bound in the domain size under that model. If formulas themselves vary, can grow with the input; the displayed bound is not a uniform polynomial-time guarantee. Nor does a correct finite evaluator decide validity over all finite and infinite structures. It answers one formula on one supplied structure and assignment.
Worked example 12.2.14
(A cycle, a witness table and a failure certificate)
Let and let the edges be exactly , , . To check , the evaluator can record witnesses for respectively. The sentence is true. But is false: for candidate , choose ; for , choose ; for , choose . Each diagonal edge is absent. Delete and the first sentence also becomes false; the counterexample is together with the fact that every fails.
A true universal does not generally have one short witness of the same form as a true existential. Here the true universal-existential sentence uses one witness per vertex. Conversely, falsifying an existential-universal sentence may require one failed universal instance for each proposed existential choice. Keeping that dependence explicit is valuable even when a program only returns a Boolean result.
Practice
Quick check
(Find the free variables of . Rename bound variables so that the free and bound roles cannot be confused.)
Solution · Answer
The free variables are : the free occurs in the left disjunct, and the free in the right. An unambiguous renaming is . The quantifier in the right disjunct binds its occurrences only; it does not reach back into the left disjunct.
Quick check
(Let , and let hold only at . Compare with . What happens if is empty?)
Solution · Answer
The implication-based sentence is true: at its consequent is true, and at its antecedent is false. The conjunction-based sentence is false, since its body already fails at . For empty , every implication is true, while every conjunction is false. Thus the restricted universal is true, but the conjunction-based sentence remains false on this nonempty domain.
Quick check
(Prove . Does replacing both conjunctions by disjunctions give an equivalence?)
Solution · Answer
If every element satisfies both predicates, each predicate holds at every element. Conversely, if both separate universal statements hold, any chosen element satisfies both, proving the conjunction universally. For disjunction, the direction from to holds, but the converse fails. On with true only at and only at , every element satisfies one of them but neither predicate holds universally.
Quick check
(A proposed proof reads: “Assume ; call a witness ; therefore ; therefore .” Identify the invalid step and give a two-element countermodel. Under the additional premise , give a valid conclusion involving .)
Solution · Answer
The universal-introduction step is invalid: is a temporary assumption about an existential witness, so is not unrestricted. Take and . Existence is true but universality false. With the additional universal implication, use the temporary witness to infer , introduce and then discharge the witness assumption. The resulting conclusion does not contain , as existential elimination requires.
Quick check
(On with meaning , evaluate and . Give witness or refutation data for each, and bound the number of atomic membership tests made by the simple nested-loop evaluator for either sentence.)
Solution · Answer
The first sentence is true, with witnesses for and for . The second is false: for either proposed , the universal opponent can choose , making the atom false. Each sentence has at most two outer choices and two inner choices, so at most four membership tests are needed; short-circuiting may reduce that number. One cannot choose after seeing in the second sentence: its existential choice is outside the universal one.