Język (logika)
Język – pewien zbiór symboli, przy użyciu których można tworzyć bardziej złożone wyrażenia (na przykład formuły, zdania matematyczne) według ściśle określonych reguł syntaktycznych. Przyjmuje się, że w danym języku L mogą występować (w dowolnej liczbie) symbole funkcyjne, relacyjne oraz symbole stałych. Zdania napisane przy użyciu języków tego typu wystarczają do opisu większości własności dowolnych struktur matematycznych oraz do wyrażenia twierdzeń mówiących o tych strukturach.
Język a syntaktyka
edytujWyrażenia języka L to termy oraz formuły. Są to ciągi symboli, które powstają według ściśle określonych reguł z symboli języka L, symboli logicznych (takich jak spójnik koniunkcji czy alternatywy), zmiennych oraz kwantyfikatorów.
Zbiór termów języka L to najmniejszy zbiór T o własnościach:
- stałe z języka L należą do T
- zmienne (na przykład x0, y5, z, v) należą do T
- jeśli t1, ... ,tn należą do T, zaś f jest symbolem funkcji n-argumentowej z języka L, to f(t1, ... ,tn) również należy do T.
Zbiór formuł języka L to najmniejszy zbiór F o własnościach:
- jeśli t1, t2 są termami języka L, to wyrażenie t1 = t2 należy do F
- jeśli t1, ... ,tn są termami języka L, zaś P symbolem relacji n-arnej z języka L, to wyrażenie P(t1, ... ,tn) należy do F
- jeśli f1, f2 należą do F, to wyrażenia "f1 i f2", "f1 lub f2" i "nieprawda, że f1" również należą do F
- jeśli x jest zmienną, zaś f należy do F, to wyrażenia "dla każdego x f" oraz "istnieje takie x, że f" należą do F.
Zdanie to formuła języka L, w której nie występują zmienne wolne. Ze zdań możemy budować teorie, a następnie badać różne własności tych teorii (na przykład takie jak zupełność, rozstrzygalność czy kategoryczność).
Język a semantyka
edytujMówimy, że M jest strukturą (modelem) dla języka L, jeśli M jest zbiorem, w którym zinterpretowane zostały wszystkie symbole z języka L. Oznacza to, że:
- jeśli f jest symbolem funkcji n-argumentowej z języka L, to istnieje funkcja f(M) z n-tej potęgi kartezjańskiej zbioru M w zbiór M, która jest interpretacją f w modelu M
- jeśli P jest symbolem relacji n-argumentowej z języka L, to istnieje relacja n-arna P(M) na zbiorze M (czyli po prostu pewien podzbiór n-tej potęgi kartezjańskiej zbioru M), która jest interpretacją P w modelu M
- jeśli c jest stałą z języka L, to w M istnieje element c(M), który jest interpretacją c w modelu M.
Jeśli M jest modelem dla języka L, to możemy określić, które zdania napisane w języku L są prawdziwe w modelu M lub – inaczej mówiąc – spełniane przez model M. Definicję spełniania zdania przez model jako pierwszy podał polski logik i matematyk Alfred Tarski, powszechnie uważany za twórcę semantyki logicznej (utożsamianej zwykle z teorią modeli).
Zbiór tych wszystkich zdań napisanych w języku L, które są prawdziwe w modelu M dla języka L, tworzy teorię modelu M w języku L. Teoria ta jest teorią zupełną. Badanie zależności między modelami i ich teoriami to główny przedmiot badań obszernego działu logiki matematycznej jakim jest teoria modeli.