Math 512: Finite Model Theory Problem Set 3

John Baldwin

February 27, 1997

1. Prove or disprove the 0-1 law for first order sentences about a) directed graphs, b) tournaments. (for constant probability).

2. a) Show that in a language containing one binary relation E which is required to be an equivalence relation, for each k there are sentences in F O^{k+1} which are not equivalent to a sentence in L^{k}. (a strict hierarchy exists).

b) Add a second symbol < to the universe and require < to linearly order the universe. Show that over infinite models this hierarchy remains strict but that over finite models every first order sentence in <, E is equivalent to a sentence in F O^{3}.

3. Find two infinite models which satisfy the same F O^{s} sentences but are not L^{s}- equivalent. (You choose s.)