Section 2.2: Truth and Models
A structure for a given first-order language is a function on the set of parameters that assigns
- to a nonempty set called the universe or domain of .
- to every -place predicate symbol an -ary relation on .
- to every constant symbol a member of .
- 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 for every
everywhere except for
- 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.
A set of wffs logically implies a wff , , iff implies , for every structure for the language and every .
are logically equivalent iff
- iff .
is called valid,
- 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.
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.
-ary relation on
, 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, .
and are elementarily equivalent, , iff for any sentence , iff .
Isomorphic structures are elementarily equivalent:
- 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 .
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 .
- In all decidable relations are definable, but there are many others (see Section 3.5).
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 .
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 .
is elementarily closed (
) iff with any structure,
also contains all elementarily equivalent structures.
- is elementarily closed iff is a union of classes.
- 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.