Section 2.2: Truth and Models
Structures and Models
A structure
for a given firstorder 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
, 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 onetoone 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 onetoone (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 onetoone 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 quantifierfree. An existential (
) formula is of the form
where
is quantifierfree. 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 nonempty, 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 coNP=NP.