Aby wyrażać własności jakichś obiektów używając formuł logiki, musimy wiedzieć jakich znaczków możemy używać. Na przykład gdy mówimy o arytmetyce liczb rzeczywistych, używamy znaczków 0,1, + , − , * , / , a gdy o jakimś porządku liniowym, używamy tylko znaczku \(\leq\). Intuicyjnie, wszystkie znaczki jakie mają być dostępne nazywamy sygnaturą. Ściślej, sygnatura to lista symboli, z których o każdym wiadomo co ma znaczyć (czy konkretną liczbę jak 0, czy funkcję jak + , czy relację jak \(\leq\)).
Przykład sygnatury:
Sygnatura liczb naturalnych z dodawaniem i porządkiem:
- 0 oznaczające element - stałą,
- + oznaczające dwuargumentową funkcję (czyli funkcję zależną od dwóch elementów),
- \(\leq\) oznaczające relację dwuargumentową (czyli relację która może zachodzić lub nie, pomiędzy parami elementów).
Sama sygnatura w żaden sposób nie określa faktycznego znaczenia symboli. Może na przykład być tak, że ktoś postanowi znaczkiem + oznaczać potęgowanie czy dzielenie. Sygnatura mówi jedynie jakie znaczki mają być dostępne, jakiego mają być typu: stałą, funkcją czy relacją i ile dana funkcja czy relacja ma mieć argumentów.
Struktura
Gdy już wiemy czym są sygnatury, możemy definiować światy w których dostępne są odpowiednie znaczki.
Struktura nad sygnaturą Σ składa się z następujących składników:
- ustalony zbiór nazywany nośnikiem struktury,
- pewne wyróżnione elementy nośnika nazywane stałymi, po jednym dla każdej stałej w Σ,
- pewne relacje, które mówią coś o własnościach elementów struktury, po jednej dla każdej relacji w Σ,
- funkcje przypisujące elementom nośnika inne elementy, po jednej dla każdej funkcji w Σ,
Zazwyczaj struktury oznacza się (na przykład) < A,a,b,f,R > , gdzie pierwszy znaczek po < to zbiór będący nośnikiem (tutaj A), a potem wymienione są stałe, funkcje i relacje dostępne w danej strukturze. Na przykład \(<\mathbb N, 7, \leq>\) oznacza strukturę liczb naturalnych z porządkiem i stałą 7.
Oczywiście liczby argumentów odpowiednich funkcji i relacji muszą się zgadzać z opisem z sygnatury.
Na przykład dla sygnatury z poprzedniego przykładu, jedną ze struktur nad tą sygnaturą są liczby naturalne \(\mathbb N\), ze stałą 0 oznaczającą liczbę \(0\in \mathbb N\), relacją \(\leq\) oznaczającą normalny porządek na liczbach i funkcją + przypisującą \(n,m\in\mathbb N\) wartość n + m.
Ale można rozpatrzyć inną strukturę nad tamtą sygnaturą. Na przykład strukturę gdzie nośnik to {7,9}, stała 0 (jako symbol z sygnatury) jest równa 7, relacja \(\leq\) nie zachodzi dla żadnych elementów i funkcja oznaczana + zawsze przyjmuje wartość 9.
Dla ustalonej sygnatury, możemy formułować różne własności jakich wymagamy, pisząc formuły logiki zawierające znaczki z sygnatury. Formuły takie będą prawdziwe w pewnych strukturach nad tą sygnaturą, a w innych nie.
Ważne jest by pamiętać, że w formułach logiki korzystać możemy tylko z symboli w sygnaturze. Czyli nawet jak wiemy, że elementy struktury to liczby naturalne, nie możemy w formułę logiczną wstawić konkretnej liczby (np. 1986), bo nie ma takiej stałej w sygnaturze. Nie możemy też napisać w formule \(x\cdot y=z\), bo mnożenie nie występuje na liście dostępnych operacji. Możemy więc korzystać tylko z dostarczonych stałych, relacji i funkcji.
Z drugiej strony, czasami niektóre symbole których nie ma w sygnaturze, mogą zostać zdefiniowane. Na przykład w przypadku liczb naturalnych z porządkiem stała 0 nie jest potrzebna, bowiem można napisać prostą formułę definiującą 0:
- \(\psi(x)\equiv \forall_y x\leq y\) (dla każdego y, y jest większy równy x).
Czyli ψ(x) nie używa stałej 0 i jest prawdą tylko wtedy gdy x = 0.
Troszkę bardziej skomplikowany przykład, to formuła \(\varphi(x)\), prawdziwa w liczbach naturalnych wtedy i tylko wtedy, gdy x = 3. Wygląda ona następująco:
- \(\varphi(x)\equiv\exists_a\exists_b a\leq b\leq x\wedge 0\neq a\neq b\neq x \wedge \forall_y (y\leq x)\Rightarrow y\in\{0,a,b,c\}\).
Formuła ta mówi, że istnieją liczby a,b (intuicyjnie równe odpowiednio 1,2), które są nie większe niż x, różne od siebie, od 0 i x i jeśli weźmiemy dowolną liczbę nie większą niż x, to jest ona równa 0,a,b, lub x.
Czyli, jakkolwiek możemy korzystać tylko z symboli określonych w sygnaturze, to gdy wiemy nad jaką strukturą pracujemy, możemy czasem zdefiniować nowe stałe i własności.
Jednym z działów współczesnej logiki jest Teoria Modeli, badająca jakie własności można zdefiniować korzystając z określonych konstrukcji logiki, a jakich zdefiniować się nie da.
Intuicja
Wyobraźmy sobie sygnaturę w której dostępne są relacje jedno-argumentowe (predykaty) oznaczone O,S.
Wyobraźmy sobie teraz, że rozpatrywane struktury to będą domy. Elementy takiej struktury to wszystkie pomieszczenia danego domu, predykat O(x) zachodzi jeśli w pomieszczeniu x jest okno, a S(x) jeśli w danym pomieszczeniu jest sauna.
Na przykład mieszkanie Karola to struktura:
- {przedpokoj,lazienka,kuchnia,gabinet,sypialnia},
- gdzie zachodzi O(gabinet),O(sypialnia) i dla pozostałych pomieszczeń nie zachodzi O(x),
- dla żadnego pomieszczenia x nie zachodzi S(x), bo Karol nie ma sauny.
Możemy teraz formułować różne własności mieszkań korzystając z logiki. Na przykład zdanie
- \(\exists_x S(x)\)
mówi że w rozpatrywanym domu istnieje pomieszczenie w którym jest sauna.
W każdym ustalonym domu dane zdanie albo jest spełnione, albo nie jest spełnione. Na przykład powyższe zdanie nie jest prawdą w mieszkaniu Karola, ale jest prawdą w rezydencji państwa Igrekińskich.
Przykład ten jest bardzo uproszczony, ale tak można na to patrzeć. Struktura to pewien konkretny, ustalony obiekt, o którego własnościach mogą się wypowiadać zdania logiki, korzystając z symboli z sygnatury.
Prawda w strukturze - model
Gdy mamy ustaloną strukturę S nad sygnaturą Σ i dowolne zdanie logiki \(\varphi\) nad tą samą sygnaturą, możemy pytać czy to zdanie jest prawdą w S. Czasami trudno jest to sprawdzić, ale zawsze istnieje odpowiedź na to pytanie, czyli dane zdanie w konkretnej strukturze jest albo spełnione, albo nie spełnione. Sytuację gdy zdanie jest spełnione oznaczamy \(S\models \varphi\). Mówimy wtedy że S jest modelem dla zdania \(\varphi\). Na przykład:
- \(<\mathbb N, \leq>\models \exists_x \forall_y x\leq y\),
czyli w strukturze liczb naturalnych z porządkiem prawdziwe jest zdanie mówiące, że istnieje element najmniejszy. Istotnie, tym elementem jest 0.
Oczywiście dla danego zdania może istnieć wiele modeli. Na przykład w każdej strukturze S, zachodzi \(S\models \top\), czyli każda struktura jest modelem dla \(\top\).
Z tego punktu widzenia, przy ustalonej strukturze, każde zdanie jest prawdziwe, albo nie jest prawdziwe. Czyli gdyby ustalić jedną strukturę w której pracujemy, wtedy każde zdanie było by albo prawdziwe, albo nieprawdziwe. Okazuje się jednak, że jest bardzo trudno ustalić jednoznacznie strukturę dla całej matematyki. Opisane jest to bardziej szczegółowo w dalszych punktach.
Ważnym rozszerzeniem powyższej notacji jest oznaczenie \(S\models\Phi\), gdzie S to pewna struktura nad sygnaturą Σ, a Φ to zbiór zdań logicznych nad tą sygnaturą. Zapis ten oznacza, że każde z tych zdań jest prawdziwe w S. Mówimy wtedy, że struktura S jest modelem dla zbioru zdań Φ.
Operacje Th,Mod
W tej sekcji zakładamy że ustalona jest pewna sygnatura Σ i wszystkie struktury i zdania są nad tą sygnaturą.
Korzystając z relacji \(\models\), możemy zdefiniować dwie abstrakcyjne operacje:
- Dla danej rodziny zdań Φ, zapytajmy o wszystkie modele Φ. Oznaczamy to \(Mod(\Phi)=\mathcal M\), gdzie \(\mathcal M\) zawiera wszystkie struktury S, dla których \(S\models\Phi\).
- Dla danej klasy struktur \(\mathcal M\), można spytać o wszystkie możliwe zdania, prawdziwe jednocześnie we wszystkich tych strukturach. Oznaczamy to \(Th(\mathcal M)=\Phi\), gdzie Φ zawiera wszystkie takie zdania φ, które są prawdziwe w każdej strukturze z rodziny \(\mathcal M\). Zbiór tych wszystkich zdań nazywamy teorią rodziny \(\mathcal M\).
Poniżej kilka własności tych operacji:
- Ponieważ \(\bot\) (czyli fałsz), nie jest spełniony w żadnej strukturze, więc jeśli \(\bot\in\Phi\), to \(Mod(\Phi)=\emptyset\).
- Ponieważ w każdej strukturze spełniona jest prawda, to zawsze \(\top\in Th(\mathcal M)\).
- Weźmy dowolną klasę struktur \(\mathcal M\) i rozważmy ich teorię \(Th(\mathcal M)\), a następnie zdefiniujmy \(\mathcal M'=Mod(Th(\mathcal M))\). Oczywiście jeśli \(S\in\mathcal M\), to w S spełnione są wszystkie zdania z teorii \(\mathcal M\), więc \(S\in\mathcal M'\). Czyli zawsze \(\mathcal M\subseteq\mathcal M'\). Są przykłady, że \(\mathcal M'\), może zawierać więcej modeli niż \(\mathcal M\), więc nie musi być \(\mathcal M=\mathcal M'\)
- Weźmy dowolny zbiór zdań Φ i rozważmy klasę jego modeli Mod(Φ), a następnie zdefiniujmy Φ' = Th(Mod(Φ)). Wtedy jeśli \(\phi\in\Phi\), to φ jest spełnione w każdej strukturze z Mod(Φ), więc należy do zbioru Φ'. Czyli \(\Phi\subseteq \Phi'\). Na przykład, zawsze \(\top\in\Phi'\), nawet jeśli \(\top\notin\Phi\). Więc może być \(\Phi\neq\Phi'\).