Informatyka MIMUW

Monoid to struktura $\mathfrak{M}=\langle M,\circ,e\rangle$, w której
dwuargumentowa operacja $\circ$ jest łączna, a stała $e$ jest jej
elementem neutralnym.

Monoid $\mathfrak{M}$ jest skończenie generowany, jeśli istnieje
skończenie wiele elementów $a_1,\ldots,a_n\in M$ takich, że każde
$a\in M$ można wyrazić za pomocą $\circ$ stosowanej do tych
elementów. Na przykład monoid $\langle A^*,\cdot,\varepsilon\rangle$ słów nad alfabetem $A$ z konkatenacją i
słowem pustym jest skończenie generowany wtedy i tylko wtedy, gdy $A$
jest skończony.

Monoid $\mathfrak M=\langle M,\circ,e\rangle$ jest definiowany w
$\mathfrak{N}$ formułami $\mu(x), \ \nu(x,y,z)$ i $\epsilon(x)$ nad
sygnaturą arytmetyki, jeśli
$M=\{a\in\mathbb{N}~|~(\mathfrak{N},x:a)\models\mu\}$, dla
dowolnych $a,b,c\in M$ zachodzi: $a\circ b=c$ wtedy i tylko wtedy, gdy
$(\mathfrak{N},x:a,y:b,z:c)\models\ \nu$ oraz $e$ jest jedynym elementem
$M$ dla którego $(\mathfrak{N},x:e)\models\epsilon.$

Zad. 1

Wykaż, ze klasa monoidów skończenie generowanych nie jest
aksjomatyzowalna żadnym zbiorem zdań.

Zad. 2

Dla danych $\mu(x),\ \nu(x,y,z)$ i $\epsilon(x)$ nad sygnaturą arytmetyki, które
definiują monoid w $\mathfrak{N}$, napisz zdanie $\gamma$ nad sygnaturą
arytmetyki, używające ich jako podformuł, takie że

$\mathfrak{N}\models \gamma$ wtedy i tylko wtedy, gdy monoid definiowany
przez $\mu,\ \nu$ i $\epsilon$ jest skończnie generowany.

Zad. 3

Rozważamy dwa grafy $\mathfrak{T}_1=\langle T_1,E_1\rangle$ i
$\mathfrak{T}_2=\langle T_2,E_2\rangle$ określone jak następuje:

$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\}$

Napisz zdanie o minimalnej randze kwantyfikatorowej, które rozróżnia
$\mathfrak{T}_1$ i $\mathfrak{T}_2$. Należy uzasadnić poprawność
zdania, można nie uzasadniać jego minimalności.