ndz., 11/24/2013 - 11:50 — jty

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.