Pillay - Lecture notes on Model theory (2002).pdf - Logic - Mathematics2014

Lecture notes - Model Theory (Math 411)

Autumn 2002.

Anand Pillay

December 9, 2002

1 Notation and review.

Let me begin by briey discussing many-sorted structures. Although in most

of the course I will be working with the traditional 1-sorted structures, ev-

erything is valid in the more general context.

By a many-sorted language L (or rather a language for many-sorted struc-

tures), we mean a set S of \sorts", a set R of sorted relation symbols, and

a set F of sorted function symbols. What this means is that each R 2 R

comes together with a certain nite sequence (S 1 ;::;S n ) of sorts where n 1,

and each f 2F comes together with a sequence (S 1 ;::;S n ;S) of sorts where

n 0. By the cardinality jLj of L we mean jSj + jRj + jF.

By an L-structure M we mean a family (S(M) : S 2S) of nonempty sets,

together with, for each R 2R of sort (S 1 ;::;S n ) a subset R(M) of S 1 (M)

::: S n (M), and for each f 2 F of sort (S 1 ;::;S n ;S) a function f(M) :

S 1 (M) ::S n (M) ! S(M). So an L-structure is just an interpretation of

the formal language L. The S(M) are the sorts of the structure, the R(M)

the basic relations of the structure and the f(M) the basic functions of the

structure. By the cardinality jMj of M we mean the sum of the cardinalities

of the sets S(M).

A one-sorted language is a (many-sorted) language with only one sort,

that is S is a singleton, say fSg. In that case the sort of a relation symbol is

just a natural number n 1 and likewise for the sort of a function symbol. If

M is an L-structure then S(M) is called the underlying set (or universe) of

M and we often notationally identify it with M (just as we often notationally

identify a group G with its underlying set) if there is no ambiguity.

The many-sorted point of view is quite natural, because a whole \cat-

egory" of objects can be now viewed as a single structure. An example is

the category of \algebraic varieties over Q". By an algebraic variety over Q

we mean (for now) a subset X of some C n which is the common zero-set of

a nite number of polynomials P i (x 1 ;::;x n ) in Q[x 1 ;::;x n ]. By a morphism

(over Q) between X C n and Y C m , we mean a map f : X ! Y given

by m polynomials Q 1 (x 1 ;::;x n );:::;Q m (x 1 ;::;x n ) over Q. The many-sorted

structure V ar Q has as sorts the algebraic varieties over Q, as basic relations

the algebraic subvarieties (over Q) of products of the sorts, and as basic

functions morphisms from products of sorts to sorts.

Of course there is another natural associated one-sorted structure, the

structure (C; +;;; 0; 1). This is the structure with universe C, two basic

2-ary functions, addition and multiplication, one basic unary function ()

and two basic 0-ary functions (or constants), 0 and 1.

Note that V ar Q and (C; +;;; 0; 1) are not only dierent structures, but

structures for dierent languages. But we hope later to explain a sense in

which they are the \same". (They are \bi-interpretable".)

Given a many-sorted language L we build up in the usual manner terms

and rst order formulas of L from the relation and function symbols of L

together with ^, _, :, !, 8, 9 and a countable set of variables for each sort

S 2 S, as well as the symbol = S for each S 2 S. Note that every variable

comes equipped with a sort. If is an L-formula we may write (x 1 ;::;x n )

to mean that the free variables in are among x 1 ;::;x n . An L-sentence is

an L-formula with no free variables. If (x 1 ;::;x n ) is an L-formula where x i

is of sort S i , M is an L-structure and a i 2 S i (M) for i = 1;::;n we dene

(inductively)

M j= [x 1 =a 1 ;::;x n =a n ]

in the usual way. (\(a 1 ;:;a n ) satises (x 1 ;::;x n ) in M", or \(x 1 ;::;x n )

is true of (a 1 ;::;a n ) in M".) When there is no ambiguity we just write

M j= [a 1 ;::;a n ]. An important fact is that exactly one of M j= [a 1 ;::;a n ],

M j= (:)[a 1 ;::;a n ] holds.

(By the way the = S symbols are interpreted as equality, namely if x;y

are variables of sort S, M is an L-structure, and a;b 2 S(M) we dene

M j= x = S y[x=a;y=b] to hold if a = b.)

If is an L-sentence we say \M is a model of " for M j= and this is

where the expression \model theory" comes from.

Denition 1.1 Let L be a language and M an L-structure, a set of L-

sentences, and an L-sentence.

(i) We say that M j= (M is a model of ) if M j= for all 2 .

(ii) j= ( logically implies ) means that every model of is a model of

(iii) By an L-theory we mean a set of L-sentences closed under j=. (L-

theories are often debtoed by T.)

(iv) We say that is consistent if has a model.

(v) We say that is complete if is consistent and for every , either 2

or : 2 .

(vi) Let K be a class of L-structures. By Th(K) we mean f : M j= for all

M 2Kg. If K = fMg we write Th(M) in place of Th(K).

(vii) Let K be a class of L-structures. We say that K is an elementary class

if there is a set of L-sentences such that K = fM : M j= g.

(viii) We write M N (M is elementarily equivalent to N)if M and N are

models of the same L-sentences, that is, if Th(M) = Th(N).

(ix) Let T be an L-theory. We say that axiomatizes T if T and j=

for all 2 T.

Exercise 1.2 (i) Let be a set of L-sentences and 0 = f : j= g. Then

0 is a theory.

(ii) Th(M) is a complete theory.

(iii) Let K be a class of L-structures. Then K is an elementary class i

K = fM : M j= Th(K)g.

(iv) T is complete i all models of T are elementarily equivalent

Example 1.3 Let L be the 1-sorted language containing a single binary func-

tion symbol f say, and a single constant sybol e say. Any group can be con-

sidered to be an L-structure.

(i) The class of groups is elementary.

(ii) The class of torsion-free divisible abelian groups is an elementary class.

(iii) (needs compactness theorem) The class of torsion abelian groups is NOT

elementary.

(iv) (needs more) The class of simple nonabelian groups is NOT an elemen-

tary class.

Example 1.4 Let L be the language \of unitary rings" that is L is again

one-sorted, contains two binary function symbolds + and say, one unary

funtion symbol , and two constant symbols 0; 1. Any ring can be naturally

viewed as an L-structure.

(i) The class of nite elds is NOT an elementary class. (Needs compact-

ness.)

(ii) Let K be the class of nite elds. By denition a pseudonite eld is an

innite model of Th(K). Then the class of pseudonite elds IS an elemen-

tary class. (Why?)

We now consider relations between L-structures. Let us x a (many-sorted)

language L. The notion of an isomorphism between two L-structures is pretty

obvious and clearly we are only interested in L-structures up to isomorphism.

We have already dened elementary equvalence of L-structures and it is

important that this is generally weaker than isomorphism. However:

Exercise 1.5 Let M and N be elementarily equivalent L-structures. Sup-

pose that for every sort symbol S of L, S(M) is nite. Then M and N are

isomorphic.

Denition 1.6 (i) Let M, N be L-structures. We say that M is a substruc-

ture of N if for each sort symbol S, S(M) S(N), for each relation symbol

R of L of sort S 1 :::S n , R(M) = R(N)\(S 1 (M):::S n (M)) and for

each function symbol f of L of sort (S 1 ;::;S n ;S), and choice a i 2 S i (M) for

i = 1;::;n, f(M)(a 1 ;:;a n ) = f(N)(a 1 ;::;a n ).

(ii) We say that M is an elementary substructure of N if M is a substruc-

ture of N, and for all L-formulas (x 1 ;:;x n ) and a 1 ;:;a n in the sorts of M

corresponding to variables x 1 ;::;x n respectively, we have M j= [a 1 ;::;a n ] i

N j= [a 1 ;::;a n ].

(iii) An (elementary) embedding of M into N is an isomorphism of M with

a (elementary) substructure of N.

Exercise 1.7 (i) Let L be the language of unitary rings mentioned earlier.

Let F;K be elds. Then F is a subeld of K i F is a substructure of K.

(ii) Let L be 1-sorted and consist of a single unary function symbol. Let

S be the succesor function on Z. Then (Z;S) and N;S) are naturally L-

structures. The rst is a substructure of the second, but not an elementary

substructure.

(iii) Let M be a substructure of N. Then for any quantier-free L-formula

(x 1 ;::;x n ) and a i 2 M of suitable sort, M j= [a 1 ;::;a n ] i N j= [a 1 ;::;a n ].

Exercise 1.8 (Tarski-Vaught test.) Let M be a substructure of N. Then

M is an elementary substructure if M if and only if for each L-formula

(x 1 ;::;x n ;x) and a 1 ;::;a n 2 M (in the appropriate sorts), if N j= (9x())[a 1 ;::;a n ]

then for some b of the appropriate sort in M, N j= [a 1 ;::;a n ;b].

Let us introduce a bit of notation. Let L be a language as usual, and M

an L-structure. Let L M be L together with a set of new (sorted) constant

symbols c m for m ranging over elements of M (i.e. of elements of sorts of

M). Then we can \expand" canonically M to an L M -structure M 0 say by

dening c m (M 0 ) = m. We often write M 0 as (M;m) m2M . For (x 1 ;::;x n ) an

L-formula, and m 1 ;::;m n 2 M of appropriate sorts, let (c m 1 ;::;c m n ) be the

L M -formula which results from substituting c m i for x i in . In this context

we have:

Remark 1.9 (i) M j= [m 1 ;::;m n ] i (M;m) m2M j= (c m 1 ;::;c m n ).

Note that we can do exactly the same thing, if we add constants for a

subset A of M (that is each element of A is in some S(M)), to obtain a

language L A and an \expansion" (M;a) a2A of M to an L A -structure.

With this notation we have:

Lemma 1.10 Let M be a substructure of N. Then M is an elementary

substructure of N i and only if (M;m) m2M and (N;m) m2M are elementarily

equivalent as L M -structures.

Sometimes we completely abuse notation by writing M j= (m 1 ;::;m n )

in place of the equivalent conditions in Remark 1.9.

Here is a useful slight strengthening of 1.8 which we state for convenience

in the 1-sorted context.

Exercise 1.11 (Assume L to be 1-sorted.) Let M be an L-structure, and A

a subset of the underlying set (or universe) of M. Then A is the universe of

an elementary substructure of M if and only if for each L A -formula (x), if

M j= 9x((x)) then there is b 2 A such that M j= (b).

Pillay - Lecture notes on Model theory (2002).pdf

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: