Algebrai logika előadás 2002, tavasz



Irodalom
Linkek
Csak a feladatok
Az egész honlap tömörítve


1. ea., feb. 19. Történeti áttekintés, motiváció, vö. ezzel. Boole-algebrák, vö. [henkhalo] 1-6 o., [uab4AL].
2. ea., feb. 26. Stone-Birkhoff tétel, alapvető összefüggések Boole-algebrákkal és disztributív hálókkal kapcsolatban, nulladrendű logika (ítéletkalkulus) fogalma (vö. [ans], 7/1)
  • 1. feladat Bizonyítsuk be, hogy egy háló pontosan akkor disztributív, ha rendelkezik a kongruenciakiterjesztési tulajdonsággal (CEP)!
  • 2. feladat Bizonyítsuk be, hogy egy U halmaz feletti (azaz a hatványhalmazán értelmezett) f lezárási operátor pontosan akkor teljesen additív, ha van U-n olyan unér algebra, ahol a ,,részalgebra-generálás'' operátor éppen f!

    • 3. ea., márc. 5. Lezárási operátorok, Galois-kapcsolat (vö. [fried], 115-117 o.). Mod, Th: az ,,érvényesség'' reláció generálta Galois-kapcsolat formulahalmazok és struktúrahalmazok között. A nulladrendű logika kompaktsági tétele. Hilbert típusú kalkulus fogalma (vö. [ans], Def. 33).
    4. ea., márc. 11. A nulladrendű logika teljességi tétele (vö. [akns], Thm. 3.2.3, [ans], 7/1). Az implicit és az explicit definíció fogalma, Beth tétele nullandrendű logikára (epimorfizmus vs. szürjektivitás; BA-ban epimorfizmusok szürjektívek)(vö. [ans], Thm. 58(i), 7/1, [hoo]). Hogyan algebraizáljuk az elsőrendű logikát? Cilindrifikációk, diagonális konstansok. Probléma: atomi formulák képzése.
  • 3. feladat Mutassuk meg, hogy nem létezik megszámlálhatóan végtelen szigma-teljes Boole-algebra!
  • 4. feladat Bizonyítsuk be, hogy van adekvát Hilbert típusú kalkulus a következő logikai rendszerekhez:
    a) negációmentes nulladrendű logika;
    b) negáció-, 0- és 1-mentes nulladrendű logika;
    c) csoportok logikája!
  • 5. feladat Mutassuk meg, hogy a negációmentes nulladrendű logika esetén nem érvényes Beth tétele (azaz ha alkalmas Q kijelentésváltozó-halmazt kiegészítünk néhány (alkalmas sok) további pi kijelentésváltozóval, akkor található olyan formulahalmaz, mely implicite definiálja a pi-k jelentését Q-ból, de explicite nem)!

    • 5. ea., márc. 18. Hogyan algebraizáljuk az elsőrendű logikát? (folyt.) -- a választott megoldás (egyebek: kvázipoliadikus, ill. poliadikus algebrák helyett): cilindrikus algebrák segítségével. Ennek eldöntése után már lehetséges a nulladrendűéhez hasonló stílusban definiálni az elsőrendű logikát (véges, ill. végtelen sok változós verziók). Vegyük észre a hozzávetőleges analógiát az adott logikai rendszer érvényes formulasémái és a struktúrák definiálásánál használt algebrák azonosságelmélete, ill. érvényes levezetési szabályok és az algebrák kváziazonosság-elmélete között! Kérdés tehát: az algebrák által generált varietás, ill. kvázivarietás leírása.
  • 6. feladat Rajzoljunk minél szebben négy általános helyzetű halmazt!
  • 7. feladat Mutassuk meg, hogy véges relációs típus esetén, ha veszünk egy olyan struktúrát, ahol a relációjelek interpretáltjai is végesek, abban minden automorfizmus-invariáns reláció elsőrendű formulával kifejezhető!

    • 6. ea., ápr. 16. Kvázivarietások modellelméleti jellemzése: $\mbox{\large${\sf ModQeq} = {\bf SPUp}$}$ (vö. [bs], V./Thm. 2.23 [az előadáson elhangzott verzió], ill. [uab4AL], Thm. 2.3.11). Birkhoff típusú tételek ( $\sf ModEq = \bf HSP$ : [uab4AL], Thm. 2.3.10, ill. [bs], II./11.; axiomatizálhatóság, végesen axiomatizálhatóság, univerzálisan/egzisztenciálisan axiomatizálhatóság: [csirmi] 8.17, 9.13, 9.14 Tételek, [csirmish]; axiomatizálhatóság + $\bf H$-zártság ugyanaz, mint pozitív formulákkal axiomatizálhatóság: [chk], Thm. 3.2.4; ${\sf ModQeq} = {\bf SP}$: [uab4AL], Lemma 2.3.13; kategóriaelméleti egységes tárgyalás: [ns] ). Cilindrikus halmazműveletek, reprezentálható cilindrikus algebrák ( $\mbox{\large${\sf RCA}_\alpha$}$): varietást alkotnak. Ebből beláttuk: ha $\mbox{\large$n< \omega$}$, az $\mbox{\large$n$}$ dimenziós kockán reprezentálható $\mbox{\large$\sf CA$}$-k univerzálisan axiomatizálható osztályt alkotnak (ez egy ún. pszeudoaxiomatizáció segítségével látható), így $\mbox{\large${\sf RCA}_n$}$ kvázivarietás. (vö. [ans], Thm. 17, Lemma 5, Thm. 18)
  • 8. feladat Bizonyítsuk be, hogy $\mbox{\large$\alpha\geq \omega$}$-ra az $\mbox{\large$\alpha$}$ dimenziós kockán reprezentálható $\mbox{\large$\sf CA$}$-k osztálya nem axiomatizálható!
  • 9. feladat Az $\mbox{\large$x_1, x_2, \dots$}$ elemekkel generált szabad Boole-algebrát $\mbox{\large${\sf CA}_\omega$}$ típusú algebrává bővítjük a következőképp: legyen $\mbox{\large${\sf d}_{ij} = x_i \otimes x_j$}$, ill. $\mbox{\large${\sf c}_i$}$ hasson úgy az $\mbox{\large$x_1, x_2, \dots$}$ változók egy adott $\mbox{\large$k$}$ Boole-kifejezésén, hogy $\mbox{\large$x_i$}$ valamely előfordulását 1-re cseréli, ha ezen előfordulás $\mbox{\large$k$}$-beli negációmélysége páros, és 0-ra, ha páratlan (ahol az előfordulás $\mbox{\large$k$}$-beli negációmélységén $\mbox{\large$k$}$ azon részkifejezéseinek számát értjük, melyek tartalmazzák az előfordulást és komplementációval kezdődnek)(ez jóldefiniált lesz). Keressünk olyan elsőrendű struktúrát, aminek épp az így kapott algebra a jelentésalgebrája!

    • 7. ea., ápr. 23. $\mbox{\large$n< \omega$}$ esetén $\mbox{\large${\sf RCA}_n$}$ varietás (folyt.): a diszkriminátor-függvény, diszkriminátor-varietások (vö. [bs] IV/9.), ,,diszkriminátor-kvázivarietások'' (tétel: utóbbi uaz., mint előbbi: [uab4AL], Thm. 2.4.3; Jónsson-lemma: [bs], IV/6.8 tétel) . A cilindrikus halmazalgebráknak ( $\mbox{\large${\sf Cs}_n$}$) van diszkriminátoruk, így $\mbox{\large${\sf RCA}_n$}$ diszkriminátor-varietás ([ans] Thm. 17/(i)). A cilindrikus halmazműveletek alaptulajdonságai. Ezeknek eleget tevő (absztrakt) algebrák: a cilindrikus algebrák ( $\mbox{\large${\sf CA}_\alpha$}$). $\mbox{\large${\sf RCA}_\alpha$}$ vs. $\mbox{\large${\sf CA}_\alpha$}$: $\mbox{\large${\sf RCA}_1 = {\sf CA}_1\dots$}$
  • 10. feladat Mutassunk példát elsőrendű struktúrák pszeudoaxiomatizálható, de egzisztenciális másodrendű formulákkal nem axiomatizálható osztályára!
  • 11. feladat Tekintsük a következő logikai rendszert: a Boole-konnektívák mellé felvesszük még az $\mbox{\large$\alpha$}$, $\mbox{\large$\alpha^*$}$ unér konnektívákat. A formulák ezekbol képződnek a szokásos módon. Egy modellhez először is megadandó egy $\mbox{\large$\< U, A, A^*\csname rangle\endcsname $}$ hármas, ahol $\mbox{\large$U$}$ nemüres halmaz, $\mbox{\large$A$}$ egy binér reláció $\mbox{\large$U$}$-n, $\mbox{\large$A^*$}$ pedig $\mbox{\large$A$}$ reflexív-tranzitív lezártja. $\mbox{\large$\mathscript P(U)$}$-n ekkor adódik egy, a mi konnektíváinkat használó extra-Boole algebrai struktúra: $\mbox{\large$X\subseteq U$}$ esetén $\mbox{\large$\alpha(X) = \{u\in U: \exists v\in X\ \ \< u,v\csname rangle\endcsname \in A\}$}$, ill. hasonlóképp $\mbox{\large$\alpha^*$}$ és $\mbox{\large$A^*$}$ viszonylatában. Ezután a modell megadása abból áll, hogy a kijelentésváltozókhoz hozzárendeljük valahogy $\mbox{\large$U$}$ némely részhalmazát. A modell jelentésfüggvénye ezen hozzárendelésnek a formulaalgebrára való homomorf kiterjesztéseként adódik, és persze egy formula érvényes a modellben, ha jelentése $\mbox{\large$U$}$. Mutassuk meg, hogy ez a logikai rendszer nem kompakt (van végtelen kielégíthetetlen formulahalmaz, aminek minden véges része kielégíthető)!
  • 12. feladat
    a) Legyenek $\mbox{\large$f$}$ és $\mbox{\large$g$}$ egyváltozós függvények egy Boole-algebrán, úgy, hogy ún. konjugált párt alkotnak, azaz $\mbox{\large$x\land f(y)= 0\iff g(x)\land y= 0$}$. Mutassuk meg, hogy ekkor $\mbox{\large$f$}$ és $\mbox{\large$g$}$ additívak (azaz pl. $\mbox{\large$f(x\lor y)= f(x) \lor f(y)$}$)!
    b) Tegyük fel, hogy egy Boole-algebrán $\mbox{\large$c$}$ egy unér extenzív függvény ( $\mbox{\large$x\leq c(x)$}$). Bizonyítsuk be, hogy ekkor a kövtkezők ekvivalensek:
      (i) $\mbox{\large$c$}$ idempotens, additív, komplementált ( $\mbox{\large$c(x)= c(c(x))$}$, $\mbox{\large$c(x\lor y)= c(x)\lor c(y)$}$, $\mbox{\large$c(-c(x))= -c(x)$}$);
      (ii) $\mbox{\large$c(0)=0$}$, $\mbox{\large$c(x\land c(y))= c(x)\land c(y)$}$.
  • 13. feladat Mutassunk nem egyszeresen összefüggő véges topologikus teret! Keressük meg univerzális fedőterét is!

    • 8. ea., ápr. 30. A diszkriminátor alaptulajdonságai(Foster-Pixley tétel: ld. [bs] IV/10.8). Operátoros Boole-algebrák (BAO-k) (ld. [uab4AL] 4.). Elsőrendű struktúrák komplexusalgebrái, normális BAO-k atomstruktúrái (kiteljesítés) (vö. [hmt1] 2.7). Stone-dualitás: Boole-algebrák és Boole-terek (ld. [bs] IV/4.). Cilindrikus algebrák atomstruktúrái: a projekció operátor...
  • 14. feladat Ágyazzuk be a megszámlálhatóan végtelen sok elemmel generált szabad Boole-algebra Boole-terét a valós számok terébe!

    • 9. ea., máj. 7. Normál BAO-k kongruenciáinak megfelelő ideálok. BAO-k kiteljesítése (folytatás). Kiteljesítés megőrzi a pozitív kifejezéseket (azaz additív operátorok összetételét).
  • 15. feladat Legyen $\mbox{\large$\bf B$}$ Boole-algebra, $\mbox{\large$f: {\bf B}^n \longrightarrow {\bf B}$}$ additív normális függvény, $\mbox{\large$R$}$ a neki megfelelő atomreláció (ha $\mbox{\large$\langle U_1,\dots U_n, V \rangle$}$ ultraszűrők $\mbox{\large$n+1$}$-ese, $\mbox{\large$\langle U_1,\dots U_n, V \rangle \in R$}$, ha $\mbox{\large$f^\supset(U_1, \dots, U_n)\subseteq V$}$). Legyen $\mbox{\large$x\in B$}$. Mutassuk meg, hogy ha
    a) $\mbox{\large$n=1$}$, akkor $\mbox{\large$R^{-1}(\overset\~x)$}$ zárt!;
    b) $\mbox{\large$n\geq 2$}$, akkor alkalmasan választott $\mbox{\large$\bf B$}$, $\mbox{\large$f$}$, $\mbox{\large$x$}$ mellett $\mbox{\large$R^{-1}(\overset\~x)$}$ nem zárt!

    • 10. ea., máj. 14. Kiteljesítés megőrzi pozitív azonosságokat. Atomstruktúrák diszjunkt úniója: komplexusalgebráik direkt szorzata. Atomstruktúrák elsőrendű elméletének és komplexusalgebráik azonosságelméletének kapcsolata. Extra-nulladrendű logikák: BAO-s séma. Ami kell még ahhoz, hogy a cilindirkus algebrákat belepásszítsuk e keretbe: cilindrikus algebrák atomstruktúrái (folytatás). Ortocilindrikus algebrák.
    11. ea., máj. 22. Cilindrikus, ortoclindrikus algebrák atomstruktúrái (folytatás): reláció-, tégla- és kocka atomstruktúrák, pszeudo verziók. Diagonálismentes esetben (reláció- és tégla atomstruktúráknál) pszeudoság megszüntethető ([hcs] Lemma 1.9). Reláción reprezentálható diagonálismentes ortocilindrikus algebrák axiomatizálása (vö. [hcs] Thm 3.3). Halmazon reprezentálható diagonálismentes ortocilindrikus algebrák ( $\mbox{\large${\bf I}{\sf Dfs}^\perp_n$}$) axiomatizálása (vö. [hcs] Thm. 3.6). A konszonancia-azonosságok.
  • 16. feladat Mutassuk meg, hogy kettőnél nagyobb dimenzióban az orto-cilindrifikációk felcserélhetőségéből nem következik a konszonancia! (Van $\mbox{\large$R$}$ háromváltozós reláció és $\mbox{\large${\bf A} \leq \langle R, c_0^\perp, c_1^\perp, c_2^\perp\rangle$}$, hogy $\mbox{\large$\bf A$}$-ban felcserélhetők az orto-cilindrifikációk, de $\mbox{\large$\bf A$}$ nem konszonáns.)

    • 12. ea., máj. 24. Reprezentálható diagonálismentes ortocilindrikus algebrák ( $\mbox{\large${\sf RDf}^\perp_n$}$) axiomatizálása (alapvető azonosságok + konszonancia)(vö. [hcs] Thm.3.18). Ebből: kétdimeziós reprezentálható diagonálismentes cilindrikus algebrák ( $\mbox{\large${\sf RDf}_2$}$) axiomatizálása: $\mbox{\large${\sf RDf}_2 = {\sf Df}_2$}$. Aztán ebből: kétdimeziós reprezentálható cilindrikus algebrák ( $\mbox{\large${\sf RCA}_2$}$) axiomatizálása: $\mbox{\large${\sf RCA}_2$}$-t leírják a $\mbox{\large${\sf CA}_2$}$-axiómák + két kiegészítő azonosság ([ans] Thm. 17/(iii) -- bizonyítás nélkül; [hmt2] 79-84 o., ezen belül: Thm 3.2.65. -- ronda bizonyítás, szép ábra), ill. Jónsson módszere univerzális (kvantormentes formulákkal axiomatizálható) osztályok végesen-nem-axiomatizálhatóságának megmutatására, sőt: annak megmutatására, hogy véges sok változót használó kvantormentes formulával nem axiomatizálható az adott osztály (,,nincs véges séma-axiomatizáció''). Azaz: a $\mbox{\large$K$}$ osztályhoz és adott $\mbox{\large$n$}$-hez mutatunk $\mbox{\large${\bf A}\notin K$}$-t, hogy $\mbox{\large$n$}$ elemmel generált részei $\mbox{\large$K$}$-ban vannak. Jónsson módszere $\mbox{\large$K = {\sf RCA}_\omega$}$ esetben ([ans] Thm. 19 vagy [and1] Thm. 1. -- ez utóbbi hely a $\mbox{\large$K = {\sf RCA}_n$}$, $\mbox{\large$n \leq 3 < \omega$}$ esetre is kitér).

    Kiegészítő feladatok
  • 17. feladat Legyen t az az algebrai típus, amely egyetlen kétváltozós függvényjelből áll. Mutassunk olyan t típusú varietást, amely nem axiomatizálható véges sok változót használó kvantormentes formulahalmazzal!
  • 18. feladat Mutassuk meg, hogy $\mbox{\large$n < \omega$}$ esetén az $\mbox{\large${\bf S} \{ \langle R, {\sf c}_0^\perp,\dots {\sf c}_{n-1}^\perp \rangle: R\ n \mbox{ v\'altoz\'os rel\'aci\'o} \} $}$ varietás nem diszkriminátorvarietás, de generálják a benne levő diszkriminátoros algebrák!
  • 19. feladat Bizonyítsuk be, hogy egy struktúraosztály pontosan akkor zárt a részstruktúra-képzésre, ha axiomatizálható kvantormentes végtelen formulákkal (esetleg osztálynyi sokkal)! (Végtelen formulán a következőt értjük: rögzítjük változók egy $\mbox{\large$\{x_\xi: \xi \mbox{ rendsz\'am}\} $}$ osztályát, és ezek használatával képzünk olyan formulákat, melyekben az elsőrendű konnektívákon túl szerepelhet végtelen (halmaznyi méretű) konjunkció és diszjunkció is.)
  • 20. feladat Egy teljes relációalgebra nem más, mint valamely $\mbox{\large$U$}$ halmaz mellett a $\mbox{\large${\bf P}(U\times U)$}$ Boole-algebra kiegészítése a binér relációkompozíció és unér reláció-inverz műveletekkel, ill. a diagonális konstanssal. A halmaz-relációalgebrák pedig a teljes relációalgebrák részalgebrái. A reprezentálható relációalgbrák pedig a halmaz-relációlagebrák osztályának $\mbox{\large$\bf {SP}$}$-lezártjának elemei.
    a) Jellemezzük a halmaz-, ill. a reprezentálható relációalgebrák atomstruktúráit!
    b) Mutassuk meg, hogy a reprezentálható relációalgebrák varietást alkotnak, s hogy e varietásnak rekurzíve felsoroható az azonosságelmélete!




    Levél az előadónak (Henk Csaba)

    Vissza
    Vissza a főoldalra