Models and countermodels

Quantified formulas have been called true and false for two lessons without anything saying what those words mean once a domain is involved.

For propositional logic the answer was a row of a table, and there were finitely many rows. Here there is no such list: a domain may hold any number of things, including infinitely many, and there are infinitely many domains to consider. So the truth table method is gone, and with it the guarantee that any question can be settled by grinding. What replaces it is the notion of a model, which makes truth precise, and the practice of building countermodels, which is how invalidity gets shown in practice.

What an interpretation supplies

An interpretation, also called a structure or a model, has three parts.

A domain: a non-empty set of objects the quantifiers range over. Non-empty is a stipulation rather than a discovery, made so that $\forall x F x \to \exists x F x$ comes out valid, and it is worth knowing it is a convention that could have gone the other way.

An object for each name: the constant $s$ picks out one member of the domain. Two names may pick out the same object, and an object may have no name at all.

An extension for each predicate: for a one-place predicate, the set of domain members it is true of; for a two-place one, the set of ordered pairs. The extension is all there is to a predicate. $F$ does not mean "is a fish" in an interpretation; it just is a set, and calling it fishhood is a comment for the reader.

That is deliberately spare, and the spareness is the point. Logic is checking whether the conclusion follows under every way of filling those slots, so it must not care what the slots are filled with.

Truth in a model

With an interpretation fixed, every sentence gets a truth value by a recursion that runs through its structure.

An atomic sentence $F a$ is true when the object named by $a$ is in the extension of $F$ , and $R a b$ is true when the pair of objects named sits in the extension of $R$ . The connectives behave exactly as in the truth tables of the third lesson, so $φ \land ψ$ is true when both parts are, and so on for the rest.

The quantifiers are the new part. $\forall x φ$ is true when $φ$ holds of every member of the domain, and $\exists x φ$ is true when it holds of at least one, where "holds of an object" means the object is temporarily treated as the value of $x$ . Over a finite domain this is a finite check, and over an infinite one it is a definition rather than a procedure: it says what truth is without saying how to establish it.

Take a domain of three people, ${1, 2, 3}$ , with $L x y$ for " $x$ likes $y$ " whose extension is the pairs $(1, 2)$ , $(2, 3)$ and $(3, 1)$ , and $H x$ true of 1 and 2 only. Then $\exists x \neg H x$ is true, witnessed by 3. $\forall x \exists y L x y$ is true, since each person likes one other. $\exists y \forall x L x y$ is false, since being liked by everyone would need three incoming arrows and each person has exactly one. Nothing here required inspiration; each answer was read off the extensions.

Countermodels

The eighth lesson's definition of validity carries over word for word, with interpretations in place of rows: an argument is valid when no interpretation makes every premise true and the conclusion false. So to show an argument invalid, produce one such interpretation. It is called a countermodel, and it settles the question permanently, the way a single counterexample destroys a universal claim.

This is the workhorse skill of predicate logic, and it has a method rather than requiring inspiration.

Start with the smallest domain that could work, usually one or two objects. Write down what the conclusion being false requires. Write down what each premise being true requires. Fill in the extensions to satisfy all of it, adding objects only when forced. Then check every premise and the conclusion against the finished interpretation, because a countermodel that does not actually work is worse than none.

Example. Show that $\forall x (F x \to G x)$ and $\exists x G x$ do not entail $\exists x F x$ .

The conclusion is false when nothing is $F$ , so try an empty extension for $F$ . The first premise is then vacuously true, since no object has to pass the test. The second premise needs something in $G$ . So take the domain ${1}$ , the extension of $F$ empty, the extension of $G$ containing 1.

Check: $\forall x (F x \to G x)$ holds because $F 1$ is false, making the conditional true. $\exists x G x$ holds because $G 1$ is true. $\exists x F x$ fails because $F$ is empty. One object settles it. Reading it in English: every fish is a mammal is true when there are no fish, something is a mammal is true, and nothing is a fish.

Now you. Show that $\forall x (F x \to G x)$ and $\forall x (H x \to G x)$ do not entail $\forall x (F x \to H x)$ .

Answer

Take the domain ${1}$ , with $F$ and $G$ both true of 1 and $H$ empty. The first premise holds since $G 1$ is true, the second holds vacuously since $H$ is empty, and the conclusion fails since $F 1$ is true and $H 1$ is false. A one-object domain is enough, and the English version is that all cats are mammals and all dogs are mammals do not make all cats dogs.

Countermodels with relations

Relations need slightly larger domains, and the quantifier order of the previous lesson is where they are needed most.

Example. Show that $\forall x \exists y R x y$ does not entail $\exists y \forall x R x y$ .

The premise needs every object to relate to something; the conclusion must fail, so no single object may be related to by everything. Two objects suffice. Take the domain ${1, 2}$ with $R$ holding of the pairs $(1, 2)$ and $(2, 1)$ and no others.

Check the premise: 1 relates to 2 and 2 relates to 1, so every object relates to something. Check the conclusion: for it to hold, some object must be related to by both. Object 1 qualifies only if $R 11$ and $R 21$ both hold, and $R 11$ is absent; object 2 qualifies only if $R 12$ and $R 22$ hold, and $R 22$ is absent. So the conclusion is false and the argument is refuted. In English, everyone has a friend does not give that someone is everyone's friend.

Now you. Show that a transitive relation need not be reflexive, by giving a model of $\forall x \forall y \forall z ((R x y \land R y z) \to R x z)$ in which $\forall x R x x$ fails.

Answer

Take the domain ${1, 2}$ with $R$ empty. Transitivity holds vacuously, since no pair is in $R$ at all, and $R 11$ fails. If an empty relation feels like a cheat, use ${1, 2}$ with $R$ holding only of $(1, 2)$ : transitivity still holds because no chain of two steps exists, and $R 11$ still fails. Both are legitimate, and the empty one is quicker.

How big must a countermodel be

Small, usually. Many invalid arguments are refuted by one object, most of the rest by two or three, and a good rule is to try each size in turn rather than starting with something elaborate.

The number of interpretations to check at each size is finite and grows fast: with a domain of $n$ objects, a one-place predicate has $2^{n}$ possible extensions and a two-place one has $2^{n^{2}}$ , so a two-object domain with one binary relation already offers 16 choices and a three-object domain offers 512. That is why the guided method beats enumeration.

There is an honest limit. Not every satisfiable formula has a finite model. Take the conjunction of three sentences: $\forall x \neg R x x$ , saying nothing relates to itself; $\forall x \forall y \forall z ((R x y \land R y z) \to R x z)$ , transitivity; and $\forall x \exists y R x y$ , saying everything relates to something. The positive integers with $R x y$ as $x < y$ satisfy all three. No finite domain can: brute force over all relations on domains of one, two, three and four objects finds zero models, and the reason generalises, since starting anywhere and following the relation gives an endless chain of distinct objects, distinct because a repeat would make something related to itself by transitivity.

So searching for countermodels is not a decision procedure. It is a method that usually works quickly and can fail to terminate, and the theory says that this cannot be repaired.

What cannot be done

Propositional logic was decidable: the table always finished. First-order logic is not. Alonzo Church and Alan Turing showed independently in 1936 that no algorithm decides whether an arbitrary first-order formula is valid, which settled Hilbert's Entscheidungsproblem in the negative and, in Turing's case, produced the machine model of computation on the way to the answer.

What survives is weaker and still useful. Validity is semi-decidable: the derivations can be enumerated mechanically, so a search that tries all of them will find a proof if one exists. If the formula is valid you eventually get a proof; if it is not, the search may run for ever, and no signal tells you which situation you are in. That asymmetry is exactly what makes automated theorem provers behave the way they do.

There is one important special case. Monadic first-order logic, with only one-place predicates and no relations, is decidable, and the categorical syllogisms of the eighth lesson live inside it, which is why the count of valid forms could be computed by exhausting a finite list of possibilities. Adding a single two-place predicate loses the property.

Example. Why is producing a countermodel a complete method for showing invalidity but not for showing validity?

Because invalidity is an existential claim and validity is a universal one. One interpretation with true premises and a false conclusion establishes invalidity outright, and no amount of failing to find one establishes validity, since the interpretations are unbounded in size and number. Establishing validity therefore needs a proof about all interpretations at once, which is what a derivation supplies.

Now you. An argument survives your search through every domain of one, two and three objects. What have you established?

Answer

Nothing decisive, only that any countermodel needs four objects or more, or that none exists. The search is evidence and not proof, and the correct next move is to try to derive the conclusion instead.

Where this leaves things

Truth in a model is now defined, invalidity has a practical test, and the limits of that test are known: countermodels are usually small, sometimes impossible, and searching for one never certifies validity.

That last gap is what the next lesson fills. Derivation was the answer for propositional logic when tables became unwieldy, and it is the answer here for a stronger reason, since the semantic method has stopped being a procedure at all. Four rules for the quantifiers turn out to be enough, and two of them need restrictions that look fussy until you see what happens without them.