These notes cover in some more detail what the textbook discusses in Chapter 5. Some details of my presentation will be different in irrelevant ways from the details in the book. I will be somewhat terse in terms of examples. Let me know if you feel that they are sorely needed, and I’ll amend the notes accordingly.

Predicate logic extends propositional logic in that we now allow the presence of quantifiers, and therefore we also allow the presence of statements that depend on variables. This complicates the definition of semantics, and also introduces additional complications at the syntactic level. On the other hand, this new flexibility allows us to code in straightforward ways many theories actually used in practice. Set theory is but on example of a theory that can be formalized in this context, and we will see others.

**1. Syntax **

These notes cover in some more detail what the textbook discusses in Chapter 5. Some details of my presentation will be different in irrelevant ways from the details in the book.

Predicate logic extends propositional logic in that we now allow the presence of quantifiers, and therefore we also allow the presence of statements that depend on variables. This complicates the definition of semantics, and also introduces additional complications at the syntactic level. On the other hand, this new flexibility allows us to code in straightforward ways many theories actually used in practice. Set theory is but on example of a theory that can be formalized in this context, and we will see others.

We begin by defining the syntax. As before, we have several options we can use. What matters is that the choice we make should allow us to prove a unique readability theorem, so we can argue by induction on (parsing sequences of) formulas, and give definitions by recursion.

The vocabulary we use to form formulas has two components, a `logical’ and a `non-logical’ one. The logical component is always the same.

Definition 1The logical symbols of the language are (connectives), (quantifier), (parentheses), (comma), (equality), and for (variables).

The non-logical part varies depending on the situation under consideration:

Definition 2A language consists of a set of constant symbols, a set of relational symbols, and a set of function symbols, together with arity functions and

One usually refers to the elements of as *non-logical* symbols. The sets are assumed disjoint, and disjoint from the set of logical symbols. They may be empty or finite, or have any infinite size; of course, we have not yet developed the theory of infinite sizes, so this extra generality won’t be too useful to us for a while. The idea is that if then represents a binary relation symbol, and if then is a ternary function symbol.

In our intended interpretation, we will fix a “universe of discourse,” and the variables will range over this universe. Before we define formulas, we describe the *terms* of the language. Just as the variables, the terms represent elements of the universe of discourse.

Definition 3Given a language the -terms are finite strings of symbols from the vocabulary, defined recursively as follows:

- Each variable and each constant symbol are terms.
- If is a function symbol of arity (i.e., ), and are (not necessarily distinct) terms, then is a term.

In item (2), I mean the sequence

One proves a unique readability lemma asserting that if the string is a term, then it is either a variable, or a constant, or there is exactly one of some arity and exactly one sequence of terms such that The argument is very similar to the argument for unique readability of formulas in propositional logic, so I will skip it. Similarly, we will need unique readability results for the definitions below. I will also skip these.

Now that we have terms we can define formulas. For this, we first define *atomic* formulas (that may be thought of as playing the role of propositional variables).

Definition 4The atomic formulas of an -language are defined as follows:

- If and are terms, then is atomic.
- For any if and are terms, then is atomic.

Now we combine the formulas as in propositional logic. We allow also for the possibility of quantifiers.

Definition 5The formulas of an -language are defined recursively as follows:

- Atomic formulas are formulas.
- If are formulas, then so are and
- If is a variable and is a formula, then is a formula.

Just as we did with propositional variables, we follow standard practice and (informally) omit or add parenthesis if it helps us “read” what the formulas say. Formally, we assume that only strings as described above are formulas. We also use abbreviations, such as for and similarly for We also use for

Additional common abbreviations and conventions described when discussing propositional logic apply here as well. Other common abbreviations are

for

for

The quantifier is an inverted and read “for all.” We refer to it as the *universal* quantifier. The quantifier is an inverted and read “there is” or “there exists.” We refer to it as the *existential* quantifier.

A common abbreviation that is sometimes useful is

for “there is a *unique* such that ”, formally the formula

Here, is some variable not present in and is defined by replacing each appearance of in with .\footnote{This notion of does not coincide with the notion described in the set of notes on completeness, but it turns out to be equivalent to it since I am requiring that does not appear anywhere in }

Other conventions typical of set theory will be introduced later.

We will typically talk about formulas without mentioning the language, with the understanding that some such language has been fixed beforehand, and the notion of formula refers to formulas in this specific language.

We need the notion of free and bound variables in order to define *sentences*. Intuitively, a sentence is a formula whose meaning does not depend of the particular way we `interpret’ its variables. Typically, theories consist of sentences. To proceed with the definition, one first needs to verify that given a formula and an occurrence of a in say

for some (possibly empty) strings and there is a unique variable a unique formula and a unique string such that

We call the string lying in between and the *scope* of that instance of the quantifier in

Definition 6Let be a variable and let be a formula. An occurrence of in is bounded iff it lies within the scope of some quantifier. Otherwise, that occurrence of in is free.

Note that it is possible that the same variable occurs sometimes free and sometimes bounded within the same formula For example, if is then the first two occurrences of in are bounded, but the last one is free, while the first occurrence of is free, and its last two occurrences are bounded.

Definition 7A variable is free in a formula iff occurs in and at least one such occurrence is free. We say that is bounded in iff it occurs in and at least one such occurrence is bounded.

Note that in this definition, free and bounded are not complementary notions; the same variable can be free and bounded in

Definition 8A sentence is a formula without free variables. A theory is a set of sentences.

In what follows, I will sometimes use the standard convention that if I write then it is understood that the free variables of are among To avoid cumbersome notation, we allow here the possibility that some of the are not even present in However, I may still write even if there are free variables present in

**2. Semantics **

We want to define here the mathematical notion of truth. This is of course the standard notion we always use, but its formalization in this setting is somewhat cumbersome. First we introduce *structures*, that play the role that valuations did in propositional logic. The word is appropriate, in that structures in our sense are clearly mathematical structures in the standard sense.

Definition 9Let be a language. An -structure is a tuple

where:

- is a set, called the universe of the structure
- where for each We refer to as the interpretation of in We also say that is a constant (while is but a constant symbol).
- where for each relational symbol letting be its arity, the interpretation of is a -ary relation on
- where for each function symbol the interpretation is a function in of the appropriate arity,

Note that, by convention, the universe of a structure is nonempty. Note also that, with a slight change in the original definitions, we could code the same information by referring solely to relational symbols. This is because, of course, we can code a function with its graph, and a constant with a function that always takes the same value. It is standard, however, to divide the collection of symbols as we have done.

The setting above (that comes from what is sometimes called “universal algebra” ) is fairly general, note that it allows us just as well to talk about groups, fields, partial orders, the natural numbers with the standard arithmetic operations, etc. The price to pay for this generality is that the definitions tend to look a bit more abstract than in each specific instance.

Now I proceed to specify how to decide whether a formula is true or false in a given structure. This requires that we first explain how to evaluate terms. For this, we need a notion of assignment (not to be confused with the notion of the same name from propositional logic).

Definition 10Given a structure an assignment is a function

How a term is interpreted is relative to the variables that are present in the term, and depends on assignments.

Definition 11Given a term a structure and an assignment we define the interpretation of in relative to as follows:

- If is a constant symbol then
- If is a variable then
- If where and the are terms, then

Note that and that its value is independent of if there are no variables present in More generally, if and are assignments, and they coincide on the variables present in then

Now that we know how to interpret terms, we can proceed to evaluate formulas.

Definition 12Let be a formula, let be a structure, and let be an assignment. We define when is true in of in symbols or , as follows:

- If is for some terms then iff it is the case that
- It is where and are terms, then iff
- If has been defined, then iff it is not the case that which we can also write as
- If and have been defined, then iff either or else
- If has been defined for all assignments then iff for any assignment that coincides with on all variables except (possibly) we have

It may take some reflection to realize that this definition is just spelling out the “obvious” notion of truth that one actually works with. An easy induction shows that given a structure and two assignments and such that for then

Because of this, we write

for whenever for some (any) assignment such that for Again, we should think of this as saying that the tuple has property in This may help clarify the definition of Given we are saying that

iff for any we have

note that the free variables of are among regardless of whether is free or not in Note also that if is a sentence, then whether is actually independent of and we simply write in that case.

Definition 13If is a theory and is a structure (in the language of ), we say that is a model of in symbols iff for all We say that iff all models of are models of

The notation is the usual one. For example, a group is simply a model of the theory of groups, which we could state in the language as the set of axioms asserting the usual properties, and it is a good way of checking that one has understood the definitions to see that this is indeed the case.

*Typeset using LaTeX2WP. Here is a printable version of this post.*