MLCS-Homework 2 Solved

1. EF-games and (non)-expressibility

Exercise 1.1. Prove using EF-games that the property P = “having domain of finite cardinality” is not finitely expressible in any first-order language over the class of all structures. Is the property finitely expressible over finite structures?

Exercise 1.2. Consider the following two structures G1 and G2 for the language of graphs: Write at least

 

two sentences distinguishing the two structures. Discuss the EF-game played on these structures: for what k can the Duplicator win the k-rounds game? For what k can Spoiler win?

Exercise 1.3. Consider the property of being an Eulerian graph. This is equivalent to the fact that every node has even degree. Use the following structure to prove that the Eulerian (boolean) query is not finitely expressible in the language of graphs over finite graphs:

Gn: The set of vertices is {a1,...,an,v,w}. The only edges are as follows: each ai is connected by an edge to v and to w. Show that for every m ≤ n the Duplicator wins the m-moves game on Gn and Gn+1.

Exercise 1.4. Express the following queries with first-order sentences in the language of graphs:

(1)   G is a complete graph.

(2)   G has two isolated nodes.

(3)   G has degree at least 2.

(4)   G contains a path of length 4.

Exercise 1.5. Consider the following two structures (for the language of graphs):

(1)   G1 is a cycle of length 4n;

(2)   G2 consists of two disjoint cycles of length 2n.

Analyze the EF games on these structures for n = 1,2 and write a sentence of minimal quantifier rank distinguishing the two structures for n = 1,2.

BONUS: Formulate a generalization of your observations and prove that the Connectivity query is notexpressible in the language of graphs over finite graphs, using EF-games.

Exercise 1.6. Consider the following two graphs:

(1)   G1 is a line of length 4n;

(2)   G2 consists of a line of length 2n and a cycle of length 2n (the two components are disjoint).

Analyze the EF games on these structures for n = 1,2 and write a sentence of minimal quantifier rank distinguishing the two structures for n = 1,2.

BONUS: Formulate a generalization of your observations and prove that the Acyclicity query is notexpressible in the language of graphs over finite graphs, EF-using games (a graph is acyclic iff it does not contain a cycle).

1

Exercise 1.7. Consider the proof of the following Theorem in Handout 8: if A and B are finite linear orders of size larger than 2k then A ≡k B in the language L = {min,max,<}.

(1)   Show by an example that the proof can fail if the Duplicator answers a move of the Spoiler without guaranteeing conditions (1) and (2) in the Inductive Hypothesis but only condition (3) (partial isomorphism).

(2)   Does the proof work if A and B are of cardinality exactly 2k and 2k + 1, respectively?

(3)   What can you say about (bounded) elementary equivalence of finite linear orders A and B if they have the same cardinality?

2. Other

Exercise 2.1. Let S be a class of formulas over a finite relational language L. We denote by BC(S) the class of all Boolean Combinations of formulas in S (i.e., the class of all formulas obtained by applying Boolean connectives ¬, ∧, ∨ to formulas in S). A class S of formulas is finite modulo logical equivalence if there exists a finite subset S0 ⊆ S such that for each F ∈ S there exists a G ∈ S0 such that F ≡ G. Show the following two points:

(1)   Let T = BC(S). If two structures A and B satisfy the same formulas in S then they also satisfy the same formulas in T.

(2)   If S is finite modulo logical equivalence then T is finite modulo logical equivalence.

Exercise 2.2. Let L be a finite vocabulary with no constant or function symbols. The atomic formulas in some fixed set of variables x1,...,xn are obviously finitely many. Let A be a structure adequate for L and (a1,...,an) and (b1,...,bn) be two vectors in A. We write (a1,...,an) ≡at (b1,...,bn) iff the two vectors satisfy the same atomic formulas in A. It is easy to observe that in this case they also satisfy the same quantifier-free formulas, a fact we denote by (a1,...,an) ≡qf (b1,...,bn).

Let T be a theory in L. We say that T admits Quantifier Elimination if for all formulas of the form

∃xn+1F(x1,...,xn,xn+1) there exists a quantifier-free formula G(x1,...,xn) that is T-equivalent to it.

We say that T has the Extension Property if the following holds: for all models A of T, for all (a1,...,an) and (b1,...,bn) in An, if (a1,...,an) ≡at (b1,...,bn) then for any an+1 ∈ A there exists a bn+1 ∈ A such that (a1,...,an,an+1) ≡at (b1,...,bn,bn+1).

(1)   Show that for each (a1,...,an) in An there exists a formula H(x1,...,xn) with free variables x1,...,xn such that for all (b1,...,bn) in An

(a1,...,an) ≡at (b1,...,bn) if and only if A |= H(x1,...,xn)[b1,...,bn].

(2)   Show that if T admits Quantifier Elimination then T has the Extension Property.

BONUS: Show that if T has the Extension Property and is semantically complete then T admits Quantifier Elimination.

Exercise 2.3. Show that the theory DLO has the Extension Property (defined in the previous Exercise).

Exercise 2.4. Show that the Random Graph Theory has the Extension Property (defined above).