Informatyka MIMUW

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.