Section 2.2: Problem 1 Solution »

Section 2.2: Truth and Models

Structures and Models

A structure for a given first-order language is a function on the set of parameters that assigns
  1. to a nonempty set called the universe or domain of .
  2. to every -place predicate symbol an -ary relation on .
  3. to every constant symbol a member of .
  4. to every -place function symbol an -ary operation on .
Let be a wff, and , where is the set of all variables. Then, is said to satisfy with , , iff
  • First, we extend to defined for all terms as follows: a) for variables, , b) for constants, , c) for functions of terms, .
  • Second, we define satisfaction for all atomic formulas: a) iff , b) iff .
  • Third, we extend the notion of satisfaction to all wffs: a) iff , b) iff or , c) iff for every , where is everywhere except for and .
    • Another way is, given , to define recursively the function as the set of functions such that satisfies with .
Assume that and agree at all variables that occur free in , then iff .
  • Similarly, if structures and agree at all the parameters that occur in , then iff for any .
  • The theorem justifies the following notation: where all free variables of are among .
  • For a sentence either for every , or for every .
is a model of the sentence iff is true in , , meaning for any . Otherwise, is false in . is a model of a set of sentences iff it is a model of every sentence in the set.

Logical Implication

A set of wffs logically implies a wff , , iff implies , for every structure for the language and every .
  • Wffs and are logically equivalent iff and .
    • iff .
  • A wff is called valid, , iff .
    • and are logically equivalent iff is valid.
    • is valid iff is valid.
  • Sentences: iff every model of is also a model of . is valid iff it is true in every structure.

Homomorphisms

is a homomorphism of into iff it preserves predicates and functions (including constants) both ways (that is iff).
  • is an isomorphism (isomorphic embedding) of into iff it is a one-to-one homomorphism.
  • and are said to be isomorphic, , iff there is an isomorphism of onto .
Homomorphism Theorem. If is a homomorphism of into , and , then
(a) For any term , .
(b) For any quantifier- and equality- free formula , iff .
(c) In (b), may contain the equality symbol if is one-to-one (isomorphism), and/or quantifier symbols if is onto.
is a substructure of , or, alternatively, is an extension of , iff and the identity map from into is an isomorphism.
  • The identity map in this case is an isomorphism iff a) for every predicate , is the restriction of to , b) for every constant , , and c) for every function , is the restriction of to .
  • For every structure and function such that , there is a structure such that is a homomorphism of onto .
  • For every structure and one-to-one function such that , there is a unique structure such that is an isomorphism of onto .
  • If is an isomorphic embedding of into , there is a structure such that is a substructure of , and is isomorphic to .
A universal ( ) formula is of the form where is quantifier-free. An existential ( ) formula is of the form where is quantifier-free. In general, a formula is of the form where is an formula. An formula is of the form where is a formula.
  • If is a substructure of , , then if is then implies , and if is then implies .
  • If is a model of an sentence , and the language does not have any function or constant symbols, then there is a finite substructure of that is a model of .
An isomorphism of onto is called an automorphism.
  • The identity map is an automorphism. If there are other automorphisms, is called rigid.
  • If is an -ary relation on definable in , then an automorphism preserves it.
    • This can be used to show that some relations are not definable (see Definability in a Structure below): is not definable in , ; the length is not definable in a vector space via addition and scalar multiplication, .

Elementarily equivalent structures

and are elementarily equivalent, , iff for any sentence , iff .
  • Isomorphic structures are elementarily equivalent: implies .
    • If is finite, implies .
  • and are elementarily equivalent but not isomorphic.
  • and are not elementarily equivalent, but every sentence true in is true in .
An elementary type of a structure is the class of all structures elementarily equivalent to .

Definability in a Structure

A wff defines the -ary relation in iff where the free variables of are among .
  • A -ary relation on is definable in iff there is that defines it.
  • A -ary relation on is definable from points in (a more common name definable from parameters in ) iff it is definable in , where is plus a constant symbol for each element of .
  • Examples.
    • In all decidable relations are definable, but there are many others (see Section 3.5).
    • In a set is definable iff it is a finite union of intervals with algebraic endpoints. A set is definable from points iff it is a finite union of intervals.
      • In there are definable unary relations, definable binary relations, definable ternary relations etc. (see Exercise 14).
    • If , then any non-empty, bounded and definable from points subset of has a least upper bound in .

Definability of a Class of Structures

For a set of sentences let be the class of all models of .
A class of structures for the language is an elementary class ( ) iff for some sentence .
A class of structures for the language is an elementary class in the wider sense ( ) iff for some set of sentences .
  • A class is elementarily closed ( ) iff with any structure, also contains all elementarily equivalent structures.
    • is elementarily closed iff is a union of classes.
  • Examples:
    • Given the language , the class of all directed graphs is an elementary class for the axiom “ ”, but the class of all finite graphs is not an elementary class.
    • Given the language , the class of all groups is , but the class of all infinite groups is but not .
    • Given the language , the class of all fields is , but the class of all fields of characteristic zero is but not .
The spectrum of a sentence is the set of all positive integers such that there is a model of of size . A subset of positive integers in a spectrum if there is such is the spectrum of .
  • The set of even numbers is a spectrum, see Exercise 16. The set of powers of prime numbers is a spectrum (for the field axioms).
  • Whether the complement of a spectrum is a spectrum is an open question, related to the question whether co-NP=NP.