## 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})$$?

### 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.