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.