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.