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.