Prawo zero-jedynkowe w logice a języki z dołączonymi kwantyfikatorami

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)$
  1. Udowodnij, że powyższe ciągi znaków są poprawnie zbudowanymi formułami elementarnego języka pierwszego rzędu (FO).
  2. 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

  1. 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).
O ile nie zaznaczono inaczej, treść tej strony objęta jest licencją Creative Commons Attribution-ShareAlike 3.0 License