Informatyka MIMUW

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.