We now return to logic. In Section 1.5, we proved that propositional logic is both sound and complete (Theorems 1.5.9 and 1.5.15). We now do the same for first-order logic. We have an added complication in that this logic involves formulas with variables. Sometimes the variables are all bound resulting in a sentence (Definition 2.2.14), but other times the formula will have free occurrences. We need additional machinery to handle this. Throughout this chapter, let A be a first-order alphabet and S its set of theory symbols. We start with the fundamental definition (compare Definition 4.1.1).

images DEFINITION 7.1.1

The pair images = (A, images) is an S-structure if A ≠ ∅ and images is a function with domain S such that

  • images(c) is an element of A for every constant c ∈ S,
  • images(R) is an n-ary relation on A for every n-ary relation symbol R ∈ S,
  • (f) is an n-ary function on A for ...

Get A First Course in Mathematical Logic and Set Theory now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.