Opis zajęć
W latach 70' Ronald Fagin udowodnił, że klasyczna logika pierwszego rzędu (FO) spełnia prawo zero-jedynkowe (ang. 0-1 law), czyli każde jej zdanie sygnatury czysto relacyjnej jest prawie na pewno prawdziwe albo prawie na pewno fałszywe. Co jednak oznacza to prawie na pewno? Tego dokładniej dowiecie się w trakcie warsztatów — na razie wystarczy wyjaśnić, że będzie nam chodziło o badanie granicy ciągu liczbowego, którego elementy określają częstotliwość, z jaką ustalone zdanie $\sigma$ jest prawdziwe w coraz liczniejszych strukturach skończonych. Stąd też mówi się również o zdaniach asymptotycznie prawdziwych (dla granicy równej 1) albo asymptotycznie fałszywych (dla granicy równej 0). Przykładem rozszerzenia logiki FO, które nie spełnia prawa ”0-1”, jest język z kwantyfikatorami Henkina.
W latach 50' Andrzej Mostowski wprowadził pojęcie kwantyfikatorów uogólnionych, których semantykę określają rodziny podzbiorów uniwersum. Zbadamy na okoliczność prawa "0-1" systemy logiczne m.in. z takimi kwantyfikatorami.
Program
- $logika = syntaktyka + semantyka$, czyli od alfabetu, poprzez język i znaczenie do systemu logicznego
- wprowadzenie do teorii modeli
- co to są te struktury i sygnatury
- Tarskiego definicja prawdy
- prawie na pewno i prawo "0-1"
- FO jako przykład pozytywny — tw. Fagina
- dołączanie kwantyfikatorów i kwantyfikatory uogólnione
- prawo "0-1" w językach z dołączonymi kwantyfikatorami
- kwantyfikatory topologiczne a zliczanie topologii na zbiorach skończonych
Wymagania
- znajomość logiki zerowego rzędu czyli klasycznego rachunku zdań
- podstawy matematyki
- zbiory, rodziny zbiorów, zbiór potęgowy…
- relacje i funkcje
- topologia jako rodzina zbiorów otwartych
Literatura
- …
Kwalifikacja
Przepraszam, że tak późno zadania się pojawiają. Przepraszam także wszystkich, którzy liczyli na postawienie przed nimi bardziej ambitnych problemów, ale z powodu małej ilości czasu, jaki pozostał na rozwiązanie zadań (patrz poprzednie przeprosiny), wolałem nie przekombinować. Na rozwiązania czeka adres moc.liamg|kaiwecolk#moc.liamg|kaiwecolk.
Część syntaktyczna
- $\forall x (P_1(x) \wedge \exists y P_2(x,y))$
- $\forall x P_1(x) \wedge \exists y P_2(x,y)$
- $\forall x \exists y (y = x) \vee \exists x \forall y \neg (y = x)$
- Udowodnij, że powyższe ciągi znaków są poprawnie zbudowanymi formułami elementarnego języka pierwszego rzędu (FO).
- Wskaż wśród nich zdania (formuły bez zmiennych wolnych), a dla formuł nie będących zdaniami podaj zbiór zmiennych wolnych.
Część semantyczna
- Rozważmy strukturę $(\left\{1,\dots,n\right\},V)$, gdzie $V$ jest relacją dwuargumentową. Niech $P$ oznacza predykat będący w języku symbolem tej relacji. Wyraź w logice pierwszego rzędu, że rozważana struktura jest grafem zawierającym trójkąt (klikę liczności 3).