Hedman. A First Course in Logic, 2004 (Oxford)

these symbols. Since first-order formulas are constructed from atomic formulas using rules (R1), (R2), and (R3), there are three possibilities for ϕ.

•If ϕ has the form ¬ψ, then M |= ϕ if and only if M does not model ψ.

•If ϕ has the form ψ θ, then M |= ϕ if and only if both M |= ψ and M |= θ.

The third possibility is that ϕ has the form xψ. If x is not a free variable of ψ then M |= ϕ if and only if M |= ψ. Otherwise, let ψ(x) be a formula having x as a free variable. Before defining M |= ϕ in this case, we introduce the notion of expansion.

Definition 2.19 Let V be a vocabulary. An expansion of V is a vocabulary containing V as a subset.

Definition 2.20 Let M be a V-structure. A structure M is an expansion of M if M has the same universe as M and interprets the symbols of V in the same way as M .

If M is an expansion of M , then, reversing our point of view, we say that M is a reduct of M .

If M is an expansion of M , then the vocabulary of M is necessarily an expansion of the vocabulary of M .

Example 2.21 The structure M = (R|+, −, ·, <, 0, 1) is an expansion of M = (R|+, ·, <, 0) where each of these structures interpret the symbols in the usual way (see Example 2.16).

Example 2.22 Any structure is (trivially) an expansion of itself.

Our immediate interest is the expansion of a V-structure M obtained by adding a new constant to the vocabulary for each element of the universe UM of M . Let V(M ) denote the vocabulary V {cm|m UM } where each cm is a constant. Let MC denote the unique expansion of M to a V(M )-structure that interprets each cm as the element m.

•If ϕ has the form xψ(x), then M |= ϕ if and only if MC |= ψ(c) for some constant c of V(M ).

We have now defined M |= ϕ for any sentence ϕ that does not use , →, ↔, or . Since each of these symbols is defined in terms of ¬, , and , the definition of M |= ϕ can be extended to all sentences in a natural way. Suppose that, for some sentence ϕ , M |= ϕ has been defined. Suppose further that ϕ has a subformula of the form ¬(¬ψ ¬θ). Let ϕ be the sentence obtained by replacing an occurrence of the subformula ¬(¬ψ ¬θ) in ϕ with (ψ θ). We

(ψ ← θ) (θ ← ψ), or ¬ x¬ψ(x) with xψ(x) then, as definition, M |= ϕ if and only if M |= ϕ .

We have now defined what it means for a V-structure M to be a model of a V-sentence ϕ. We further extend the definition to apply to all V(M )-sentences. Recall that V(M ) is the expansion of V obtained by adding a new constant for each element in the universe of M . There is a natural expansion of M to a V(M )- structure denoted by MC . For any V(M )-sentence ϕ, we define M |= ϕ to mean MC |= ϕ. For any V-structure M , we refer to the constants of V(M ) that are not in V as parameters.

Example 2.23 Let V< be the vocabulary consisting of a single binary relation <. Let R< be the V<-structure having underlying set R which interprets < in the usual way. Then R< models

x y z((y < x) (x < z)),

x y((x < y) → z((x < z) (z < y)))

(3 < 5) (−2 < 0), and

¬ x((x < −2) (5 < x)).

The first two are V<-sentences. The other two are V<(R<)-sentences that are not V<-sentences. We regard −2, 0, 3, and 5 as parameters.

Note that we have not defined the concept of “models” for formulas that are not sentences. Conventionally, when one says that a structure M models a formula ϕ(x1, . . . , xn), what is meant is that M models the sentencex1 . . . xnϕ(x1, . . . , xn). Of course, the formula ϕ(x1, . . . , xn) may be true for some values of x1, . . . , xn and not for others. The set of n-tuples for which the formula holds is called the set defined by ϕ.

Definition 2.24 Let ϕ(x1, . . . , xn) be a V-formula. Let M be a V-structure having underlying set UM . The set of all n-tuples (b1, . . . , bn) (UM )n for which M |= ϕ(b1, . . . , bn) is denoted by ϕ(M ). The set ϕ(M ) is called a V-definable subset of M (although it is actually a subset of (UM )n).

Typically, most subsets of a structure’s universe are not definable (as we will see in Section 2.5). The definable subsets are special subsets and play a central role in model theory (Chapters 4–6). The V-definable subsets are the subsets that the vocabulary V is capable of describing. For the sake of model theory, the notion of a first-order structure can be defined without reference to the syntax of

first-order logic. In general, a “structure” can be defined as a set with together with special subsets having names. A first-order structure is a structure having names for those sets that are definable by a first-order formula (see Exercises 2.11 and 2.12).

Example 2.25 Let V< and R< be as in the previous example. Consider the V<(R<)-formulas

(x < y) (x > y) (x = y), and

(¬(x < 3) ¬(x = 3) (5 < x)) (x = 5) (x < −2).

Let ϕ(x, y) denote the first formula and let ψ(x) denote the second formula. Then R< |= ϕ(x, y). By this we mean that R< models the sentence x yϕ(x, y). It follows that the set defined by ϕ(x, y) is all of R2. In contrast, the formula ψ(x) does not hold for all x in R. So R< does not model this formula. The set ψ(R<) defined by ψ(x) is (−∞, −2) (3, 5]. Note that R< also does not model the formula ¬ψ(x). The set ¬ψ(R<) is [2, 3] (5, ∞), the complement of ψ(R<) in R.

If M models ϕ, then we say ϕ holds in M , or simply, that ϕ is true in M . A sentence may be true in one structure and not in another. If a V-sentence ϕ holds in every V-structure, then it is valid, (or a tautology). If the sentence ϕ holds in some structure, then it is satisfiable. Otherwise, if there is no structure in which ϕ is true, then ϕ is unsatisfiable (or a contradiction).

We use the same terminology as in propositional logic. We give the analogous definitions for consequence and equivalence. For V-sentences θ and ϕ, “θ is a consequence of ϕ” means that, for every V-structure M , if M |= ϕ then M |= θ. And “θ is equivalent to ϕ” means that θ and ϕ are consequences of each other. Again, we use the following notation:

|= ϕ means that ϕ is a tautology,

ϕ|= ψ means ψ is a consequence of ϕ, and

ϕ≡ θ means ϕ and ψ are equivalent.

The definition of satisfiability can be extended to apply to all formulas of first-order logic (not just sentences). The formula ϕ(x1, . . . , xm) is satisfiable if and only if the sentence x1 . . . xmϕ(x1, . . . , xm) is satisfiable. Therefore, the notions of unsatisfiability, tautology, and consequence also apply to formulas as well as sentences (see Exercise 2.6).

A primary aim of ours is to resolve the following decision problems.

Validity problem: Given formula ϕ, is ϕ valid?

Satisfiability problem: Given formula ϕ, is ϕ satisfiable?

Consequence problem: Given formulas ϕ and ψ, is ψ a consequence of ϕ? Equivalence problem: Given formulas ϕ and ψ, are ϕ and ψ equivalent?

These are, in some sense, variations of the same problem. For this reason we focus on just one of these: the Satisfiability problem. If we could resolve this problem, then we could also resolve the Validity problem (by asking if ¬ϕ is unsatisfiable), the Consequence problem (by asking if ϕ ¬ψ is unsatisfiable), and the Equivalence problem (by asking if ϕ and ψ are consequences of each other).

The question of whether or not a given formula is satisfiable regards the syntax of the formula rather than the semantics. For example, consider the formula (y + 1) < y. If we interpret the vocabulary {+, <, 1} in the usual manner, then this formula cannot be satisfied. The result of adding one to a number cannot be less than the number. Under a di erent interpretation, however, this formula is satisfiable (suppose that we interpret < as “not equal”). For the same reason, 2 + 2 = 4 is not a tautology. For an example of a formula that is not satisfiable, consider xR(x, y) → x¬R(x, y). This formula is unsatisfiable by virtue of its structure. It has the form “p implies not p.” Regardless of how the binary relation R is interpreted, the formula is contradictory.

The Satisfiability problem for first-order logic is decidedly more di cult than the corresponding problem for propositional logic. In propositional logic we could, in theory, compute a truth table to determine whether or not a formula is satisfiable. In first-order logic, we would have to check every structure to do this. We have no systematic way for doing this. So, for now, we have no way of proving that a first-order formula is unsatisfiable. To show that a formula is satisfiable, however, can be easy. We need only to find one structure in which it is true.

Example 2.26 Let ϕ be the sentence x yR(x, y) y x¬R(x, y). To show that this is satisfiable, we must find a structure M that models ϕ.

Let M = (N|R) where N denotes the natural numbers and the binary relation R is interpreted as the successor relation. That is, R(x, y) holds if and only if y = x + 1 (y is the successor of x).

Under this interpretation, ϕ says that every element has a successor and there exists an element that has no predecessor. This is true in M . Every natural number has a successor, but 0 has no predecessor.

So M |= ϕ and ϕ is satisfiable.

It is also easy to see that ϕ is not a tautology. We need only to find one structure that models ¬ϕ. Consider, for example, the structure N = (Z|R)

where Z denotes the set of integers and the binary relation R is interpreted as the successor relation. This structure does not model ϕ since every integer has a predecessor.

Example 2.27 Let VE be the vocabulary {E} consisting of one binary relation. Let M be a VR-structure. The relation E is an equivalence relation on M if and only if M models the three sentences

xE(x, x)

x y(E(x, y) → E(y, x))

x y z((E(x, y) E(y, z) → E(x, z))).

The first sentence, call it ϕ1, says that E is reflexive, the second sentence, ϕ2, says that E is symmetric, and the third sentence ϕ3 says E is transitive.

We have seen equivalence relations before. “Equivalence” was the name we gave to the relation ≡ between formulas of propositional logic. It is easy to see that this relation warrants the name we bestowed it. It clearly satisfies the three conditions of an equivalence relation. That is, the VE -structure (U |E) models each ϕi, where U is the set of all formulas of propositional logic and E is interpreted as ≡.

We can show that these three sentences are not redundant, that all three are needed to define the notion of equivalence relation. To do this, we show that none of these sentences is a consequence of the other two. For example, to show that ϕ2 is not a consequence of ϕ1 and ϕ3, we must find a structure that is a model of ϕ1 ϕ3 ¬ϕ2. That is, we must demonstrate a VE -structure where

Eis reflexive and transitive, but not symmetric. The VE -structure (R|E) where

Eis interpreted as ≤ on the real numbers is such a structure. Likewise, we can show that ϕ1 is not a consequence of ϕ2 and ϕ3, and ϕ3 is not a consequence of ϕ1 and ϕ2. We leave this as Exercise 2.4.

In these examples we are able to show that certain formulas are satisfiable by exhibiting structures in which they hold. Using this same idea, we can show that a given formula is not a tautology, that one formula is not a consequence of another, and that two given formulas are not equivalent. However, we have no way at present to show that a formula is unsatisfiable, or a tautology, or that one formula is a consequence of another. This is the topic of Chapter 3 where we define both formal proofs and resolution for first-order logic.

2.4 Examples of structures

Let us now examine some specific structures. We consider four types of structures that one encounters in mathematics and computer science: number systems, linear orders, databases, and graphs.

2.4.1 Graphs. Graph theory provides examples of mathematical structures that are both accessible and versatile.

Definition 2.28 A graph is a set of points, called vertices, and lines, called edges so that every edge starts at a vertex and ends at a vertex. Two vertices are said to be adjacent if they are connected by an edge.

The following are examples of graphs:

Instead of giving a picture, we can describe a graph by listing its vertices and edges. The following data completely describes a graph.

Vertices: a, b, c, d, e

Edges: ab, ad, ae, bc, cd, ce, de

This graph has five vertices (a, b, c, d, and e) and seven edges (between vertices a and b, a and d, and so forth). Note that both Graphs 2 and 3 fit this description. We regard Graphs 2 and 3 as two depictions of the same graph.

We can view any graph as a structure G as follows. The underlying set U of G is the set of vertices. The vocabulary VG of G consists of a single binary relation R. The structure G interprets R as the edge relation. That is, for elements a and b of U , G |= R(a, b) if and only if the graph has an edge between vertices a and b.

Each of the above graphs model each the following two VG-sentences.

x¬R(x, x)

x y(R(x, y) ↔ R(y, x))

The first of these sentences says that the binary relation R is not reflexive (no vertex is adjacent to itself). The second sentence says that R is symmetric. Henceforth, when we speak of a graph, we mean a VG-structure that models the above

two sentences. Our notion of a “graph” is more accurately described in graph theoretic terms as an “undirected graph with neither multiple edges nor loops.” Graphs 1–4 also model the sentence x yR(x, y) which asserts that each vertex is adjacent to some other vertex. However, this is not true of all graphs.

For example, consider the following graph:

Graph 5

The vertex in the middle of the square is not adjacent to any vertex. Therefore, this graph models x y¬R(x, y) which is equivalent to the negation ofx yR(x, y). Any graph containing more than one vertex that models this negation must not be connected. We now define this terminology.

Definition 2.29 For any vertices a and b of a graph, a path from a to b is a sequence of vertices beginning with a and ending with b such that each vertex other than a is adjacent to the previous vertex in the sequence.

Definition 2.30 A graph is connected if for any two vertices a and b in G, there exists a path from a to b.

Each of the Graphs 1–4 is connected. Since each has more than one vertex, each models x yR(x, y). On the other hand, none of these graphs modelsx yR(x, y). This sentence asserts that there exists a vertex that is adjacent to every vertex. Since no vertex is adjacent to itself, no graph models this sentence (i.e. the negation of x yR(x, y) is a consequence of x¬R(x, x)). However, Graph 1 contains a vertex that is adjacent to every vertex other than itself. This can be expressed in first-order logic as follows:

x y(¬(x = y) → R(x, y)).

Graph 4 also models this sentence.

To distinguish Graph 1 from Graph 4, we can say that Graph 1 contains a unique vertex that is adjacent to every vertex other than itself. This can be expressed as a sentence of first-order logic. To simplify this sentence, let ϕ(x) denote the formula y(¬(x = y) → R(x, y)). For any graph G and any vertex a of G, G |= ϕ(a) if and only if a is adjacent to every vertex of G other than a itself. The following sentence says there is a unique such element:

yϕ(y) z(ϕ(z) → (z = y)).

This sentence distinguishes Graph 1 from Graphs 2–4.

Graph 4, on the other hand, is characterized by the following sentence that says that ϕ(x) holds for every vertex x.

x y(¬(x = y) → R(x, y)).

Any graph that models this sentence is called a clique (or a complete graph). The clique having n vertices is called the n-clique and is denoted by Kn. So Graph 4 is the 8-clique K8. Note that, when n is specified, we use the definite article when referring to the n-clique. This is because any two n-cliques are essentially the same. More precisely, they are isomorphic.

Definition 2.31 Graphs G1 and G2 are said to be isomorphic if there exists a one-to-one correspondence f from the set of vertices of G1 onto the set of vertices of G2 such that for any vertices a and b of G1, a and b are adjacent in G1 if and only f (a) and f (b) are adjacent in G2. Such a function f is called an isomorphism.

Isomorphic graphs are essentially the same.

Example 2.32 Consider the following two graphs.

Graph G:

Vertices: a, b, c, d

Edges: ab, bc, cd, ad.

Graph H:

Vertices: w, x, y, z

Edges: wx, wy, xz, yz.

The function f defined by

f (a) = w, f (b) = x, f (c) = z, and f (d) = y

is an isomorphism from G onto H. Both of these graphs can be depicted as squares. The only di erence between G and H are the letters used to represent the vertices.

We have demonstrated a VG-sentence distinguishing Graph 1 from Graph 4. We can do much better than this. There exists a VG-sentence distinguishing Graph 1 from all graphs that are not isomorphic to Graph 1. That is, there exists a VG-sentence ϕG such that for any graph H, H |= ϕG if and only if H is isomorphic to G. We prove this in Section 2.6 as Proposition 2.81. In this sense, first-order logic is a powerful language for describing finite graphs.

In another sense, however, first-order logic is not a powerful language. Basic graph theoretic properties cannot be expressed using first-order logic. For example, there is no first-order sentence that says a graph has an even number

of vertices. Also, first order logic cannot say that a graph is connected. Recall that the sentence x yR(x, y) holds in any connected graph having more than one vertex. However, just because this sentence holds in a structure does not mean that it is connected. There is no VG-sentence ϕ such that G |= ϕ if and only if G is a connected graph. These and other limitations of first-order logic are discussed in Section 4.7.

2.4.2 Relational databases. Relational databases provide concrete examples of structures. Any collection of data can be viewed as a database, whether it be a phone book, a CD catalog, or a family tree. A relational database is presented as a set of tables. For example, the three tables below form a relational database (Tables 2.1–2.3).

We now describe a structure D representing this relational database. The underlying set of D consists of all items occuring as an entry in some column of a table. So this set contains 13 names and four dates.