Mid-term test 2011/2012

Problem 1A

Let signature $$\Sigma=\{+, s, f, 0\}$$ consist only of function symbols, and let + be binary, $$s$$ and $$f$$ unary, 0 constant. In the algebra $$\mathfrak{A}=\langle A, +^\mathfrak{A}, s^\mathfrak{A},f^\mathfrak{A}, 0^\mathfrak{A}\rangle$$ the function $$f^\mathfrak{A}$$ is said to be periodic, if there exists$$k \in A$$, $$k \not =0^\mathfrak{A}$$ such tha tfor every $$x\in A$$ holds $$f^\mathfrak{A}(x+k)=f^\mathfrak{A}(x)$$.
$$f^\mathfrak{A}$$ is standard periodic, if there exists $$k=s^\mathfrak{A}(\ldots s^\mathfrak{A}(0^\mathfrak{A})\ldots)$$ such that for each $$x\in A$$ holds $$f^\mathfrak{A}(x+k)=f^\mathfrak{A}(x)$$.

For each of the following classes of structures determine, if it is
i) axiomatisable by a single sentence
ii) axiomatisable by a set of sentences, but not by a single sentence
iii) is not axiomatisable by any set of sentences

1. The class of structures $$\mathfrak{A}=\langle A, +^\mathfrak{A}, s^\mathfrak{A}, f^\mathfrak{A}, 0^\mathfrak{A}\rangle$$ over $$\Sigma$$, in which $$f^\mathfrak{A}$$ is periodic

2. The class of structures $$\mathfrak{A}=\langle A, +^\mathfrak{A}, s^\mathfrak{A}, f^\mathfrak{A}, 0^\mathfrak{A}\rangle$$ over $$\Sigma$$, in which $$f^\mathfrak{A}$$ is standard periodic

3. The class of structures $$\mathfrak{A}=\langle A, +^\mathfrak{A}, s^\mathfrak{A}, f^\mathfrak{A}, 0^\mathfrak{A}\rangle$$ over $$\Sigma$$, in which $$f^\mathfrak{A}$$ is not standard periodic

Problem 2A

We work with the class of directed graphs (self-loops are permitted). Give an example of two such graphs $$\mathfrak{G}_1$$ and $$\mathfrak{G}_2$$ such that:

1. For each graph $$\mathfrak{H}$$ with at most 7 vertices, $$\mathfrak{G}_1$$ contains an induced subgraph isomorphic to $$\mathfrak{H}$$ if and only if $$\mathfrak{G}_2$$ contains an induced subgraph isomorphic to $$\mathfrak{H}$$.
2. Player I has a winning strategy in the game $$G_7(\mathfrak{G}_1,\mathfrak{G}_2).$$

Problem 3A
We consider the structure
$$\mathfrak{P}=\langle \mathbb{R}^3,B^\mathfrak{P}\rangle$$, where the relation $$B^\mathfrak{P}$$ is 3-ary and defined as follows:

$$B^\mathfrak{P}(a,b,c)$$ holds if and only if $$a,b,c$$ are all different and collinear, and moreover $$b$$ belongs to the line segment connecting $$a$$ and $$c$$.

Write a first-order formula $$\varphi$$ such that

$$(\mathfrak{P},x_1:a_1,x_2:a_2,x_3:a_3,x_4:a_4)\models\varphi$$ if and only of the points $$a_1,a_2,a_3,a_4$$ lay on a common plane.