A formal language for first-order predicate logic

The basic syntax of first-order logic—the signature of a language, terms, atomic formulas, well-formed formulas, free and bound variables, interpreting a language in a structure.

This week’s installment from A Panorama of Logic, an introduction to topics in logic for philosophers, mathematicians, and computer scientists.

For fresh content each week, please consider becoming a free or paid subscriber.

We shall present a formal language for first-order predicate logic. Let us begin by being a little more precise with our semantic notions.

Structures in a given signature

One specifies a mathematical structure by specifying the intended domain of individuals and providing on that domain all the various relations, functions, and constants that are called for by the signature of the structure, which details the number and kinds of these structural features to be included. Order structures such as ⟨ℚ, ⩽ ⟩ or ⟨P(ℕ), ⊆ ⟩, for example, have a signature calling for one binary relation, while a linearly graded order ⟨A, ≼ ,⩽ ⟩, in contrast, has two binary relations, the partial order ≼ and the linear grading preorder ⩽. The signature of the standard model of arithmetic ⟨ℕ, +, ·, 0, 1, <⟩ specifies two binary functions, two constants and one binary relation. Different structures, even extremely different structures, can have the same signature.

In the general case, a signature has a family of relation symbols { R_i | i ∈ I }, a family of function symbols { f_j | j ∈ J }, and a family of constant symbols { c_k | k ∈ K}, each of them possibly empty, and the signature specifies for each relation and function symbol the intended arity. A model or structure ℳ in this signature provides an intended domain and interpretations on that domain for these structural features.

\(ℳ = \left\langle M,R_i^{ℳ},f_j^{ℳ},c_k^{ℳ}\right\rangle_{i ∈ I,\, j ∈ J,\, k ∈ K} \)

Thus, the structure is specified by the following information:

• The intended domain of objects M.

• For each relation symbol R_i, an actual relation R_i^ℳ on the domain M

• For each function symbol f_j, an actual function f_j^ℳ on the domain M

• For each constant symbol c_k, an actual element c_k^ℳ of the domain M

The relations R_i^ℳ and functions f_j^ℳ should have in each case the arity specified by the signature for that relation or function symbol.

In this way, the structure provides interpretations of the various language symbols appearing in the signature. We use superscripts to emphasize that R_i^ℳ is the structure ℳ's interpretation of the relation symbol R_i—another structure may have a different interpretation—and similarly with f_j^ℳ and c_k^ℳ. Later, we shall often omit this heavy notation when the meaning is clear. For example, in the rational order ⟨ℚ,⩽ ⟩ we might use ⩽ ambiguously to denote both the symbol for the relation and for the actual relation itself, which might otherwise be denoted ⩽^ℚ. But also, with the reader's permission I should like to drop the finicky font distinction between the structure ℳ and its domain M, and henceforth for simplicity I shall often simply denote them both by M—the meaning will be clear from context.

The key idea is that the various symbols R_i, f_j, c_k of the signature, which are meaningless on their own, are given an interpretation in the structure and thereby provided with meaning in that structure. This is an instance of the syntax/semantics dichotomy, for we distinguish between the symbols of the language and their interpretation in a structure. We shall presently develop the signature into a full corresponding language capable of expressing truths and meaning in a given structure.

Mathematics overflows with first-order structures—orders of all kinds, graphs, digraphs, groups, rings, fields, categories, diverse algebraic structures of every imaginable sort. Indeed, many mathematical fields of study are identified by the class of mathematical structures that are the principal focus of investigation: graph theory, group theory, order theory, ring theory, category theory and so on. The concept of a mathematical structure itself is extremely general and unifies all these mathematical investigations.

Let me illustrate the enormous range of the structure concept by mentioning the structure of chess, denoted 𝕮h, whose domain consists of…