śr., 10/03/2012 - 12:27 — fmurlak
### Ex. 1

### Ex. 2

Solution

### Ex. 3

### Ex. 4

### Ex. 5

### Ex. 6

### Ex. 7

### Ex. 8

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.

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})\)?

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.

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.

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.

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.

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.

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

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)\)?

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.