## Mid-term test 2012/2013

A {\em monoid} is a structure $$\mathfrak{M}=\langle M,\circ,e\rangle$$,
where binary operation $$\circ$$ is associative and constant $$e$$ is its
neutral element.

Monoid $$\mathfrak{M}$$ is finitely generated, if there exist
finitely many elements $$a_1,\ldots,a_n\in M$$ such that every $$a\in M$$ can be
expressed using those elements and $$\circ$$. For example, the monoid
$$\langle A^*,\cdot,\varepsilon\rangle$$ of words over an alphabet $$A$$ with
concatenation and empty word is a finitely generated iff $$A$$ is finite.

Monoid $$\mathfrak M=\langle M,\circ,e\rangle$$ is defined in
$$\mathfrak N$$ by formulas $$\mu(x),\ \nu(x,y,z)$$ and $$\epsilon(x)$$
over the
signature of arithmetics, if
$$M=\{a\in\mathbb{N}~|~(\mathfrak{N},x:a)\models\mu\}$$, for every
$$a,b,c\in M$$ the equality $$a\circ b=c$$ holds if and only if
$$(\mathfrak{N},x:a,y:b,z:c)\models\nu$$ and $$e$$ is the only element of
$$M$$ such that $$(\mathfrak{N},x:e)\models\epsilon.$$

Problem 1

Prove that the class of finitely generated monoids is not
axiomatizable by any set od sentences of FO.

Problem 2

For given $$\mu(x),\ \nu(x,y,z)$$ and $$\epsilon(x)$$ over the signature
of arithmetics, which define a monoid in $$\mathfrak{N}$$, write a
sentence $$\gamma$$ over the signature of arithmetics, which may use
them as subformulas, and such that

$$\mathfrak{N}\models \gamma$$ if and only if the monoid defined by
$$\mu,\ \nu$$ and $$\epsilon$$ is finitely generated.

Problem 3

We consider two graphs $$\mathfrak{T}_1=\langle T_1,E_1\rangle$$ and
$$\mathfrak{T}_2=\langle T_2,E_2\rangle$$ defined as follows:

$$T_1=\{1,2,\ldots,15\},$$ $$E_1=\{\langle n,2n+1\rangle~|~n,2n+1\in T_1\}$$

$$T_2=\{1,2,\ldots,11\},$$ $$E_2=\{\langle n,2n+1\rangle~|~n,2n+1\in T_2\}$$

Write a sentence of minimal possible quantifier rank, which
distinguishes $$\mathfrak{T}_1$$ and $$\mathfrak{T}_2$$. You should prove
the correcntess of your sentence, but you do not have to prove its
minimality.