Abstract:In this course, First-order logic is our preferred formalism for representing the meaning of natural language sentences. In the following section we'll review its syntax and semantics. We'll discuss
↗vocabularies,
↗first-order models and
↗first-order languages, merge them to one single complex using what we call the
satisfaction definition, define the key logical concepts of
validity and
logical consequence, and conclude with a short discussion of
equality.
Basic ConceptsThe two central concepts introduced in this section are what we call
↗first-order formula and
↗first-order model. Intuitively, we perceive of first-order formulas as
descriptions of certain
situations. First order models correspond to such situations.
Semantic NotionsGiven a model of appropriate vocabulary, a sentence such as
∀xMORON(x) is either true or false in that model. To put it more formally, there is a relation called
truth which holds, or does not hold, between sentences and models of the same vocabulary. Now, how to verify if a given sentence is true in a given model is obvious in most cases (for example, in order to check the truth of
∀xMORON(x) we simply need to check if every individual in the model is a moron). What is not so clear is how to give a precise definition of this relation for arbitrary sentences. This is going to be the problem this section deals with.
EqualityIn this section we consider a common additional feature to first-order logic as it has been defined above: An
equality symbol can be added to a first-order language to express equality between the objects denoted by terms. In what follows, we shall have a look at the syntactic and semantic consequences of this extension.
Give a (natural language) description of this model.
Give an inductive definition of subformulahood.
We've claimed that when evaluating sentences, it doesn't matter which variable assignment we start with. Formally, this means that given any sentenceϕ and any model M (of the same vocabulary), and any variable assignments g and g′ in M, then M,g⊧ϕ iff M,g′⊧ϕ. Now, we would like you to do two things:
First, show that the above claim is false if ϕ is not a sentence but a formula containing free variables.
Secondly, show that the claim is true if ϕ is a sentence.
This exercise shows that free variables and constants are very similar. In particular, if a free variable x and a constant c denote the same individual, we can even replace the free variable by the constant without affecting satisfiability.
Formally, let M=(D,F) be a model, let g be an assignment in M, and suppose that F(c)=g(x). Let ϕ be any formula, and let ϕ[c∕x] denote the formula obtained by replacing all free occurrences of x in ϕ by c. Then M,g⊧ϕ iff M,g′⊧ϕ[c∕x], where g′ is any x-variant of g.
It follows that when working with exact models, every formula is equivalent to a sentence. Explain why.
This exercise shows that the validity of arbitrary formulae is equivalent to the validity of certain sentences. As a first step, we would like the reader to prove that if ϕ is a formula containing x as a free variable, then ϕ is valid iff ∀xϕ is valid.
It follows that the validity of formulae is reducible to the validity of sentences. Explain why. [Hint: we've just found a way of reducing the number of free variables by one while maintaining validity. Iterate this process.]
The Deduction Theorem for first-order logic states that ϕ1,…,ϕn⊧ψ if and only if ⊧(ϕ1∧⋯∧ϕn)→ψ. (That is, there is a close link between validities and valid arguments.) Prove the Deduction Theorem.