- 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
Czas na rozwiązanie zadań to 3 godziny od chwili ich rozdania. Wolno używać dowolnych notatek i podręczników, natomiast nie wolno ściągać.
Wszystkie zadania są oceniane w skali 0-1-2-3 punkty, przy czym ważne jest uzasadnienie odpowiedzi. Na piątkę trzeba 10 punktów (w tym 4 zadania na co najmniej 2 punkty), na czwórkę 8 punktów (w tym co najmniej 3 zadania na co najmniej 2 punkty), a na trójkę 5 punktów (w tym co najmniej 2 zadania na co najmniej 2 punkty lub jedno zadanie na 3 punkty). Każdej osobie, która odda więcej niż cztery zadania, do wyniku zostaną policzone najsłabsze cztery spośród nich, tak więc nie opłaca się oddawać więcej niż czterech zadań.
Każde zadanie proszę napisać na osobnej kartce, podpisanej imieniem, nazwiskiem i numerem indeksu.