2.1: Syntax and Semantics

• 2.1.1: Introduction

  In order to develop the theory and metatheory of first-order logic, we must first define the syntax and semantics of its expressions.

• 2.1.2: First-Order Languages

  Expressions of first-order logic are built up from a basic vocabulary containing variables, constant symbols, predicate symbols and sometimes function symbols. From them, together with logical connectives, quantifiers, and punctuation symbols such as parentheses and commas, terms and formulas are formed.

• 2.1.3: Terms and Formulas

  Once a first-order language \(\mathcal L\) is given, we can define expressions built up from the basic vocabulary of \(\mathcal L\). These include in particular terms and formulas.

• 2.1.4: Unique Readability

  The way we defined formulas guarantees that every formula has a unique reading, i.e., there is essentially only one way of constructing it according to our formation rules for formulas and only one way of “interpreting” it.

• 2.1.5: Main operator of a Formula

  It is often useful to talk about the last operator used in constructing a formula \(A\). This operator is called the main operator of \(A\).

• 2.1.6: Subformulas

  It is often useful to talk about the formulas that “make up” a given formula. We call these its subformulas.

• 2.1.7: Free Variables and Sentences

  If a variable occurs in the scope of a quantifier it is considered bound, otherwise free. Formulas without free variable occurrences are called sentences.

• 2.1.8: Substitution

  If \(A\) is a formula, \(x\) is a variable, and \(t\) is a term free for \(x\) in \(A\), then \({A}[t/x]\) is the result of substituting \(t\) for all free occurrences of \(x\) in \(A\).

• 2.1.9: Structures for First-order Languages

  First-order languages are, by themselves, uninterpreted: the constant symbols, function symbols, and predicate symbols have no specific meaning attached to them. Meanings are given by specifying structure.

• 2.1.10: Covered Structures for First-order Languages

  A structure is covered if every element of the domain is the value of some closed term.

• 2.1.11: Satisfaction of a Formula in a Structure

  A formula is satisfied in a structure if the interpretation given to the predicates makes the formula true in the domain of the structure.

• 2.1.12: Variable Assignments

  The value of a term \(t\), and whether or not a formula \(A\) is satisfied in a structure with respect to \(s\), only depend on the assignments \(s\) makes to the variables in \(t\) and the free variables of \(A\).

• 2.1.13: Extensionality

  Extensionality, sometimes called relevance, can be expressed informally as follows: the only factors that bears upon the satisfaction of formula \(A\) in a structure \(M\) relative to a variable assignment \(s\), are the size of the domain and the assignments made by \(M\) and \(s\) to the elements of the language that actually appear in \(A\).

• 2.1.14: Semantic Notions

  The satisfaction relation is the basis for all semantic notions.

• 2.1.15: Summary