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.

Informatyka MIMUW