-
Niech A=⟨ω∖{0},nwdA⟩ będzie algebrą, gdzie nwd∈ΣF2, przy czym dla wszystkich m,n∈ω
nwdA(m,n)=najwi"ekszy wsp"olny dzielnik m i n.m i n.
Napisać formułę φ(x) nad Σ definiującą własność ,,być liczbą pierwszą”, tj., taką, że dla wszystkich wartościowań v:X→ω
X⊨φ[v] wtw v(x) jest liczb"a pierwsz"a.v(x) jest liczbą pierwszą.
-
Niech Y=⟨ω,SY,βY,≤Y⟩ będzie strukturą nad sygnaturą Σ, która składa się z symboli S∈ΣF1, β∈ΣF3 oraz ≤∈ΣR2, przy czym dla każdych n,t,p,i∈ω
SY(n)=n+1 S Y n = + n 1 βY(t,p,i)=β(t,p,i),β t p i β Y t p i = β t p i
gdzie β to funkcja beta Gödla, znana z wykładu, zaś ≤Y to zwykła nierówność.
Napisać formułę φ(x,y,z) nad Σ definiującą dodawanie, tj., taką, że dla wszystkich wartościowań v:X→ω
Y⊨φ[v] wtw v(x)+v(y)=v(z).
-
Wykazać, że jeśli klasa A struktur pewnej ustalonej sygnatury Σ nie jest aksjomatyzowalna, to klasa Mod(Σ)∖A, złożona z wszystkich tych struktur sygnatury Σ, które nie należą do A, nie jest definiowalna.
Podać taki przykład aksjomatyzowalnej klasy A nad sygnaturą Σ (którą też można sobie wybrać), że Mod(Σ)∖A nie jest aksjomatyzowalna.
-
Przypuśćmy, że Δ jest zbiorem zdań nad sygnaturą Σ, który ma model nieskończony, oraz, że każde dwa przeliczalne modele Δ są izomorficzne (o takich Δ mówi się, że są ℵ0-kategoryczne). Udowodnić, że dla każdego zdania φ nad Σ, albo Δ⊨φ albo Δ⊨¬φ (innymi słowy, Δ jest zupełny).
-
Równość s=t nazywamy normalną, gdy FV(s)=FV(t), tj., w s i t występują dokładnie te same zmienne.
Przypuśćmy, że E jest zbiorem równości normalnych, oraz że E⊢eqs=t. Udowodnić, że s=t też jest równością normalną.
-
Niech φ będzie zdaniem
∀x∀y(y=f(g(x))→(∃u(u=f(x)∧y=g(u))))
oraz niech ψ będzie zdaniem
∀x[f(g(f(x)))=g(f(f(x)))].
Czy {ψ}⊨φ?
-
Udowodnić, że klasa wszystkich struktur A=⟨A,EA⟩ nad sygnaturą składającą się z jednego dwuargumentowego symbolu relacyjnego E i takich, że EA jest relacją równoważności, która ma wyłącznie klasy abstrakcji parzystej mocy, nie jest definiowalna.
-
Niech A będzie algebrą wolną ze zbiorem wolnych generatorów G, w pewnej klasie A. Udowodnić, że dla każdej relacji równoważności r⊆G×G istnieje kongruencja ˉr⊆A×A taka, że ˉr∩(G×G)=r. (Można to wyrazić stwierdzeniem, że r roszerza się do kongruencji w A.)
Wykorzystując przestrzenie liniowe nad ciałem R jako przykład, udowodnić, że może istnieć wiele różnych kongruencji ˉr, rozszerzających daną relację równoważności r w G.
- Opisać wszystkie kongruencje algebry A=⟨{0,1,2,3},min gdzie \min,\max\in\Sigma^{F}_{2}, a \min^{\mathbb{A}},\max^{\mathbb{A}} są odpowiednio operacjami maksimum i minimum.
-
Niech \mathbb{P}=\langle\mathcal{P}(\omega),\cap^{\mathbb{P}},\cup^{\mathbb{P}}\rangle będzie kratą podzbiorów \omega ze zwykłymi działaniami teoriomnogościowymi. Udowodnić, że \mathbb{P}\times\mathbb{P}\cong\mathbb{P}.