- Niech \(\Sigma\) będzie sygnaturą składającą się z jednego jednoargumentowego symbolu funkcyjnego \(f.\) Udowodnić, że każda algebra \(\mathbb{A}\) sygnatury \(\Sigma\) o więcej niż jednym elemencie ma nietrywialny (tzn. różny od identyczności) homomorfizm \(h:\mathbb{A}\to\mathbb{A}\).
-
Niech zbiór \(X\) będzie spektrum zdania \(\varphi\) sygnatury \(\Sigma\), tzn., niech \(X=\{ n\in\mathbb{N}~/~\text{istnieje struktura $\mathbb{A}$ nad $\Sigma$ t.że $|A|=n$ i $\mathbb{A}\models\varphi$}\}.\)\(\mathbb{A}\) nad \(\Sigma\) t.że \(|A|=n\) i \(\mathbb{A}\models\varphi\)}.
Udowodnić, że zbiór \(\{ m+n~/~m,n\in X\}\) też jest spektrum pewnego zdania \(\psi\) (w konstrukcji wolno powiększyć sygnaturę o nowe symbole).
-
- Skonstruować algebrę \(\mathbb{A}\) i klasę algebr \(\mathcal{A}\) takie, że \(\mathbb{A}\) jest wolna w \(\mathcal{A}\) nad dwoma różnymi niepustymi zbiorami wolnych generatorów \(G_{1},G_{2}\) takimi, że \(G_{1}\cap G_{2}=\emptyset.\)
- Skonstruować algebrę \(\mathbb{A}\) i klasę algebr \(\mathcal{A}\) takie, że \(\mathbb{A}\) jest wolna w \(\mathcal{A}\) nad dokładnie jednym niepustym zbiorem wolnych generatorów.
-
Niech \(\mathcal{C}\) będzie klasą wszystkich grafów, skończonych i nieskończonych, które są \(n\)-dzielne, dla pewnego \(n\in\mathbb{N}.\) Graf \(\mathbb{G}\) jest \(n\)-dzielny jeśli istnieje podział jego zbioru wierzchołków \(G\) na niepuste i rozłączne podzbiory \(G_{1},\dots,G_{n}\) tak, że każda z podstruktur indukowanych \(\mathbb{G}_{{|G_{i}}}\) nie zawiera żadnych krawędzi. Przykładowo, graf pełny o \(n\) wierzchołkach \(\mathbb{K}_{n}\) jest \(n\)-dzielny, ale nie \(m\)-dzielny dla \(m< n.\)
Udowodnić, że klasa \(\mathcal{C}\) nie jest definiowalna.
-
Niech \(\mathbb{W}=\langle\{ 0,1\}^{+},\circ^{\mathbb{W}},0^{\mathbb{W}},1^{\mathbb{W}},r^{\mathbb{W}}\rangle\) będzie strukturą, w której \(\{ 0,1\}^{+}\) to zbiór wszystkich niepustych skończonych ciągów zerojedynkowych, \(\circ^{\mathbb{W}}\) to operacja konkatenacji ciągów (\(\langle x_{1}\dots x_{n}\rangle\circ^{\mathbb{W}}\langle y_{1}\dots y_{m}\rangle=\langle x_{1}\dots x_{n}y_{1}\dots y_{m}\rangle,\) \(0^{\mathbb{W}}\) i \(1^{\mathbb{W}}\) to ciągi jednoelementowe \(\langle 0\rangle\) i \(\langle 1\rangle\), zaś \(r^{\mathbb{W}}\) jest relacją jednoargumentową określoną przez \(r^{\mathbb{W}}(w)\) wtw. gdy każdy prefiks \(w\) zawiera nie więcej jedynek niż zer, a w całym ciągu \(w\) ilość jednek i zer jest jednakowa.
Udowodnić, że
\(\mathbb{W}\models\forall x([\exists y_{1}\exists y_{2}\exists y_{3}\, x=(y_{1}\circ y_{2})\circ y_{3}]\to\\ .\)
-
Niech \(\mathbb{N}\) będzie standardowym modelem arytmetyki, nad standardową sygnaturą, składającą się z symboli \(+,*,0,1,\leq.\)
Napisać formułę \(\varphi(x)\) nad sygnaturą arytmetyki definiującą relację ,,\(x\) ma nieparzystą ilość cyfr w rozwinięciu dziesiętnym”, tzn. taką, że dla wszystkich wartościowań \(v:X\to\omega\) zachodzi równoważność \(\mathbb{N}\models\varphi[v]\) wtw \(v(x)\) ma nieparzystą ilość cyfr w rozwinięciu dziesiętnym.
-
Niech \(\mathbb{Z}_{{8}}=\langle\{ 0,1,\dots,7\},S^{{\mathbb{Z}_{{8}}}},0^{{\mathbb{Z}_{{8}}}}\rangle,\) gdzie \(S^{{\mathbb{Z}_{{8}}}}\) jest operacją następnika modulo \(8,\) zaś \(0^{{\mathbb{Z}_{{8}}}}\) to \(0.\)
Proszę opisać wszystkie kongruencje algebry \(\mathbb{Z}_{{8}}.\)
-
Niech sygnatura algebraiczna \(\Sigma\) składa się z symboli stałych \(a,b,c\) i nie zawiera innych symboli. Niech \(\mathbb{A}\) i \(\mathbb{B}\) będą dwuelementowymi algebrami sygnatury \(\Sigma\) takimi, że \(a^{\mathbb{A}}=b^{\mathbb{A}}\neq c^{\mathbb{A}},\) zaś \(a^{\mathbb{B}}\neq b^{\mathbb{B}}=c^{\mathbb{B}}.\) Udowodnić, że każda rozmaitość algebr nad \(\Sigma\) zawierająca jednocześnie \(\mathbb{A}\) i \(\mathbb{B}\) zawiera wszystkie algebry nad \(\Sigma.\)
-
Niech \(c,d\) będą dwoma symbolami pewnej sygnatury algebraicznej \(\Sigma,\) która poza tym może zawierać także inne symbole funkcyjne, o różnych ilościach argumentów. Zbiór \(E\) równości nad \(\Sigma\) nazwiemy symetrycznym, gdy każda równość \(t=s\) należy do \(E\) wtedy i tylo wtedy, gdy równość otrzymana z \(t=s\) przez (jednoczesną) zamianę wystąpień \(c\) na \(d\) oraz \(d\) na \(c,\) też należy do \(E.\)
Udowodnić, że jeśli zbiór równości \(E\) nad \(\Sigma\) jest symetryczny, to zbiór\(\{ t=s~/~E\models t=s\}\) też jest symetryczny.
-
PDF wygląda inaczej
Rozstrzygnąć, czy \(\{\varphi _{1},\varphi _{2},\varphi _{3}\}\models\{\psi _{1},\psi _{2}\}.\)
\(\displaystyle \varphi _{1}: ~~~\forall x_{1}\forall x_{2}\, E(x_{1},x_{2})\to E(x_{2},x_{1})\) φ 1 : → ∀ x 1 ∀ x 2 E x 1 x 2 E x 2 x 1 \(\displaystyle \varphi _{2}: ~~~\forall x\,\lnot E(x,x)\) φ 2 : ∀ x ¬ E x x \(\displaystyle \varphi _{3}: ~~~\exists x_{1}\exists x_{2}\exists x_{3}\exists x_{4}\exists x_{5}\,\bigwedge _{{1\leq i< j\leq 5}}x_{i}\neq x_{j}\) φ 3 : ≠ ∃ x 1 ∃ x 2 ∃ x 3 ∃ x 4 ∃ x 5 ⋀ 1 ≤ i < j ≤ 5 x i x j \(\displaystyle \psi _{1}: ~~~\exists x_{1}\exists x_{2}\exists x_{3}\, E(x_{1},x_{2})\land E(x_{2},x_{3})\land E(x_{3},x_{1})\) ψ 1 : ∧ ∃ x 1 ∃ x 2 ∃ x 3 E x 1 x 2 E x 2 x 3 E x 3 x 1 \(\displaystyle \psi _{2}: ~~~\exists x_{1}\exists x_{2}\exists x_{3}\,\lnot(E(x_{1},x_{2})\lor E(x_{2},x_{3})\lor E(x_{3},x_{1}))\) ψ 2 : ∃ x 1 ∃ x 2 ∃ x 3 ¬ ∨ E x 1 x 2 E x 2 x 3 E x 3 x 1