First order logic: Ehrenfeucht-Fraisse games

Ex. 1

Prove that there is no first-order sentence \(\varphi\) such that for every undirected (finite or not) graph \(\mathfrak{G}\) there is
\(\mathfrak{G}\models\varphi\) iff every vertex \(\mathfrak{G}\) belongs to a (finite) cycle in the graph.

Ex. 2

Prove that for any fixed finite graph \(\mathfrak{G}\) (this glyph is the gothic G) and any fixed \(m\in\mathbb{N}\), the following decision problem can be decided by a deterministic Turing machine that, in addition to a read-only input tape, has a working tape of length \(O(\log n)\), where \(n\) is the input size:

Given: an encoding of a finite graph \(\mathfrak{H}\) (gothic H) as an incidende matrix listed by rows.
Question: Does Player II have a winning strategy in the game \(G_m(\mathfrak{G},\mathfrak{H})\)?

Solution

Traverse the E-F game tree using a min-max algorithm. One tree node can be written with at most \(\log n\) bits, as a vertex number in \( \mathfrak{H}\) (written in binary), since \(\mathfrak{G}\) is fixed and the length of the encoding of its vertices is constant. The tree has depth \(2m\), since there are \(m\) rounds with two steps in each.
In a leaf, checking for the winner amounts to testing whether vertex pairs in in tree nodes define a partial isomorphism. This involves counting positions on the input tape, and counters of \(\log n\) bits are enough for this.
Altogether, the algorithm uses \(O(\log n)\) space.

Ex. 3

Prove that the class of all structures \(\mathbb{A}=\langle A,r^{\mathbb{A}}\rangle,\) where \(r\in\Sigma^{R}_{1}\) such that \(|r^{\mathbb{A}}|=|A\setminus r^{\mathbb{A}}|\) is not axiomatizable.

Ex. 4

Prove that the class of all structures \(\mathbb{A}=\langle A,E^{\mathbb{A}}\rangle\) over a signature that contains a single binary relation symbol \(E\), such that \(|\{(a,b)\in A\times A~/~(a,b)\in E^{\mathbb{A}}\}|< |\{(a,b)\in A\times A~/~(a,b)\notin E^{\mathbb{A}}\}|,\), is not axiomatizable.

Ex. 5

Prove that the class of all structures \(\mathbb{A}=\langle A,E^{\mathbb{A}}\rangle\) over a signature that contains a single binary relation symbol \(E\), such that \(E^{\mathbb{A}}\) is finite, is not definable.

Ex. 6

Prove that the class of all equivalence relations with finitely many equivalence classes is not axiomatizable.

Ex. 7

Let \(\mathfrak{H}^n\) be a structure whose carrier is the hypercube \(\{0,1\}^n\), where the only binary relation \(E^{\mathfrak{H}^n}\) is defined by:
\(E^{\mathfrak{H}^n}(x,y)\) iff \(x\) and \(y\) differ on exactly one position.

What is the largest \(m\) such that Player II has a winning strategy in the Ehrenfeucht-Fraisse game
\(G_m(\mathfrak{H}^4,\mathfrak{H}^3)\)?

Ex. 8

Prove that ther is no first-order sentence \(\varphi\) such that the every finite graph \(\mathfrak{G}\) there is \(\mathfrak{G}\models\varphi\) iff \(\mathfrak{G}\) has an Euler cycle.