Processing math: 97%

egzamin

  1. Niech A=ω{0},nwdA,1A będzie algebrą, gdzie nwdΣF2 oraz 1ΣF0, przy czym dla wszystkich m,nω

    nwdA(m,n)=najwi"ekszy wsp"olny dzielnik m i n,m i n,

    zaś 1A to zwykła jedynka.

    Napisać formułę φ(x) nad Σ definiującą własność ,,być kwadratem liczby pierwszej”, tj., taką, że dla wszystkich wartościowań v:Xω

    Xφ[v]  wtw  v(x) jest kwadratem liczby pierwszej.v(x) jest kwadratem liczby pierwszej.

  2. Niech X=ω,+X,betaX,0X,1X będzie strukturą nad sygnaturą Σ, która składa się z symboli 0,1ΣF0 i +,βΣF2, przy czym dla każdych t,pω

    βX(t,p)=β(t,p),

    gdzie β to funkcja beta Gödla, znana z wykładu, zaś +X,0X,1X to zwykłe dodawanie, 0 i 1.

    Napisać formułę φ(x,y,z) nad Σ definiującą mnożenie, tj., taką, że dla wszystkich wartościowań v:Xω

    Xφ[v]  wtw  v(x)v(y)=v(z).

  3. Niech Y=ω,SY,βY będzie strukturą nad sygnaturą Σ, która składa się z dwóch symboli SΣF1 i βΣF2, przy czym dla każdych n,t,pω

    SY(n)=n+1 ⁢ S Y n = + n 1 βY(t,p)=β(t,p),β t p ⁢ β Y t p = ⁢ β t p

    gdzie β to funkcja beta Gödla, znana z wykładu.

    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).

  4. Niech P=P(ω),P,P będzie kratą podzbiorów ω ze zwykłymi działaniami teoriomnogościowymi. Udowodnić, że P×PP.
  5. Niech Σ będzie zwykłą sygnaturą ciał, wzbogaconą o jeden jednoargumentowy symbol relacyjny A. Rozpatrujemy struktury postaci RA=R,+R,R,R,0R,1R,A, gdzie R to zbiór liczb rzeczywistych, wszystkie operacje mają zwykłe interpretacje, zaś AR jest dowolny.

    Napisać zdanie pierwszego rzędu φ nad Σ takie, że RAφ wtw A jest zbiorem domkniętym.

  6. 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.

  7. 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).
  8. 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 Eeqs=t. Udowodnić, że s=t też jest równością normalną.

  9. Niech φ będzie zdaniem

    xy(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 {ψ}φ?

  10. Rozważmy algebrę A=ω,fA,, gdzie fΣF2 oraz

    fA(m,n)=m(modn)=reszta z dzielenia m przez n,m przez n

    przy czym przyjmujemy, że m(mod0)=m dla każdego m.
    Udowodnić, że w tej algebrze są tylko dwie kongruencje.
    [Szkic dowodu: Niech będzie kongruencją.
    (*) Jeśli mn dla pewnych 0<m<n, to wtedy m=m(modn)n(modn)=0, więc m,n są kongruentne z 0.
    (**) Jeśli m0 dla pewnego m>0, to dla każdego 0<i<m mamy i=(m+i)(modm)m+i(mod0)=m+i, więc i0 na mocy (*).
    (***) Jeśli m0 dla pewnego m>0, to dla każdego n>m mamy n=n(mod0)n(modm)<m<n, więc n0 na mocy (*).
    (****) Jeśli teraz mn dla pewnych mn, to albo jedno z m,n jest zerem i na mocy (**) i (***) wszystkie liczby są kongruentne z 0, albo m,n są niezerowe, ale wtedy na mocy (*) m0 i znowu jesteśmy w przypadku poprzednim.
    Szkoda by mi było wyrzucić to zadanie, ale chyba jest za trudne.]

  11. Opisać wszystkie kongruencje grupy Z4.
  12. 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.
  13. 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 rG×G istnieje kongruencja ˉrA×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 Pˉr, rozszerzających daną relację równoważności r w G.

  14. 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.
  15. 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ć. Osoby złapane na ściąganiu będziemy usuwać z egzaminu.
    Wszystkie zadania są oceniane w skali 0-1-2 punkty. Na piątkę wystarcza 7 punktów, na czwórkę 5 punktów, a na trójkę 4 punkty. Każdej osobie, kó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, podpianej imieniem, nazwiskiem i numerem indeksu.
    Oceny z egzaminu zostaną wpisane tylko tym studentom, którzy dostarczą indeks z wpisanym zaliczeniem z ćwiczeń.