Formal Logic/Predicate Logic/Models

← Informal Conventions ↑ Predicate Logic Satisfaction →



ModelsEdit

InterpretationsEdit

We said earlier that the formal semantics for a formal language such as   (and now  ) goes in two parts.

  • Rules for specifying an interpretation. An interpretation assigns semantic values to the non-logical symbols of a formal syntax. Just as a valuation was an interpretation for a sentential language, a model is an interpretation for a predicate language.
  • Rules for assigning semantic values to larger expressions of the language. All formulae of the sentential language   are sentences. This enabled rules for assigning truth values directly to larger formulae. For the predicate language  , the situation is more complex. Not all formulae of   are sentences. We will need to define the auxiliary notion satisfaction and use that when assigning truth values.

ModelsEdit

A model is an interpretation for a predicate language. It consists of two parts: a domain and interpretation function. Along the way, we will progressively specify an example model  .

DomainEdit

  • A domain is a non-empty set.

Intuitively, the domain contains all the objects under current consideration. It contains all of the objects over which the quantifiers range.   is then interpreted as 'for any object   in the domain …';   is interpreted as 'there exists at least one object   in the domain such that …'. Our predicate logic requires that the domain be non-empty, i.e., that it contains at least one object.

The domain of our example model  , written  , is {0, 1, 2}.

Interpretation functionEdit

  • An interpretation function is an assignment of semantic value to each operation letter and predicate letter.

The interpretation function for model   is  .

Operation lettersEdit

  • To each constant symbol (i.e., zero-place operation letter) is assigned a member of the domain.

Intuitively, the constant symbol names the object, a member of the domain. If the domain is   above and   is assigned 0, then we think of   naming 0 just as the name 'Socrates' names the man Socrates or the numeral '0' names the number 0. The assignment of 0 to   can be expressed as:

 
  • To each n-place operation letter with n greater than zero is assigned an n+1 place function taking ordered n-tuples of objects (members of the domain) as its arguments and objects (members of the domain) as its values. The function must be defined on all n-tuples of members of the domain.

Suppose the domain is   above and we have a 2-place operation letter  . The function assigned to   must then be defined on each ordered pair from the domain. For example, it can be the function   such that:

 
 
 

The assignment to the operation letter is written as:

 

Suppose that   is assigned 0 as above and also that   is assigned 1. Then we can intuitively think of the informally written   as naming (referring to, having the value) 1. This is analogous to 'the most famous student of Socrates' naming (or referring to) Plato or '2 + 3' naming (having the value) 5.

Predicate lettersEdit

  • To each sentence letter (i.e., zero-place predicate letter) is assigned a truth value. For   a sentence letter, either
 

or

 

This is the same treatment sentence letters received in sentential logic. Intuitively, the sentence is true or false accordingly as the sentence letter is assigned the value 'True' or 'False'.

  • To each n-place predicate letter with n greater than zero is assigned an n-place relation (a set of ordered n-tuples) of members of the domain.

Intuitively, the predicate is true of each n-tuple in the assigned set. Let the domain be   above and assume the assignment

 

Suppose that   is assigned 0,   is assigned 1, and   is assigned 2. Then intuitively  ,  , and   should each be true. However,  , among others, should be false. This is analogous to 'is snub-nosed' being true of Socrates and 'is greater than' being true of  .

SummaryEdit

The definition is interspersed with examples and so rather spread out. Here is a more compact summary. A model consists of two parts: a domain and interpretation function.

  • A domain is a non-empty set.
  • An interpretation function is an assignment of semantic value to each operation letter and predicate letter. This assignment proceeds as follows:
  • To each constant symbol (i.e., zero-place operation letter) is assigned a member of the domain.
  • To each n-place operation letter with n greater than zero is assigned an n+1 place function taking ordered n-tuples of objects (members of the domain) as its arguments and objects (members of the domain) as its values.
  • To each sentence letter (i.e., zero-place predicate letter) is assigned a truth value.
  • To each n-place predicate letter with n greater than zero is assigned an n-place relation (a set of ordered n-tuples) of members of the domain.

ExamplesEdit

A finite modelEdit

An example model was specified in bits and pieces above. These pieces, collected together under the name  , are:

 
 
 
 
 
 
 
 

We have not yet defined the rules for generating the semantic values of larger expressions. However, we can see some simple results we want that definition to achieve. A few such results have already been described:

 
 
 

Some more desired results can be added:

 
 
 
 

We can temporarily pretend that the numerals '0', '1', and '2' are added to   and assign then the numbers 0, 1, and 2 respectively. We then want:

 
 

Because of (1), we will want as a result:

 

Because of (2), we will want as a result:

 

An infinite modelEdit

The domain   had finitely many members; 3 to be exact. Domains can have infinitely many members. Below is an example model   with an infinitely large domain.

The domain   is the set of natural numbers:

 

The assignments to individual constant symbols can be as before:

 
 
 

The 2-place operation letter   can be assigned, for example, the addition function:

 

The 2-place predicate letter   can be assigned, for example, the less than relation:

 

Some results that should be produced by the specification of an extended model:

 
 
 

For every x, there is a y such that x < y. Thus we want as a result:

 

There is no y such that y < 0 (remember, we are restricting ourselves to the domain which has no number less than 0). So it is not the case that, for every x, there is a y such that y < x. Thus we want as a result: