Математическа логика - тема 6
Теории в съждителното смятане, критерий за противоречивост, максимални, пълни и дизюнктивни теории.
страницата се нуждае от дописване/преглеждане
Теории в съждителното смятане
Дефиниция: Едно множество от формули $\Gamma$ наричаме теория в съждителното смятане, ако са изпълнени следните условия:
1. $\Gamma$ съдържа всички теореми на съждителното смятане.
2. $\Gamma$ е затворено множество относно MP. Тоест, ако $\alpha \in \Gamma$ и $\alpha \Rightarrow \beta \in \Gamma$, то $\beta \in \Gamma$.
Примери:
1. Множеството от всички теореми е най-малката по включване теория.
2. Множеството от всички формули е теория - тривиалната теория.
Нема $X$ е множество от формули. Означаваме $Th(X) = \{ \alpha | X \mapsto \alpha\}$. Наричаме $Th(X)$ теория породена от $X$.
Лема 1: Нека $X \subseteq Y$. Тогава $Th(X) \subseteq Th(Y)$ (монотонност).
Доказателство: Нека $\alpha \in Th(X)$. Тогава $X \mapsto \alpha$. От монотонността на синтактичното следване получаваме $Y \mapsto \alpha$. Следователно $\alpha \in Th(Y)$.
Лема 2: Нека $X$ е множество от формули. Тогава $X \subseteq Th(X)$.
Доказателство: Нека $\alpha \in X$. Редицата $\alpha$ е доказателство на $\alpha$ от $X$, следователно $X \mapsto \alpha$, следователно $\alpha \in Th(X)$. Следователно $X \subseteq Th(X)$.
Лема 3: Нека $\Gamma$ е теория. Тогава $Th(\Gamma) = \Gamma$ (теориите са неподвижни точки относно $Th$).
Доказателство:
От Лема 2 следва, че $\Gamma \subseteq Th(\Gamma)$. Остава да покажем, че $Th(\Gamma) \subseteq \Gamma$.
Нека $\alpha \in Th(\Gamma)$. Тогава $\Gamma \mapsto \alpha$.
Нека $\alpha_1, \alpha_2, \dots, \alpha_n=\alpha$ е доказателство на $\alpha$ от $\Gamma$. С индукция ще покажем, че за $i = 1, 2, \dots, n$, $\quad \alpha_i \in \Gamma$.
База: $i = 1$ Разглеждаме двата възможни случая за $\alpha_1$:
1) $\alpha_1$ е аксиома: тогава $\alpha_1$ е теорема, следователно $\alpha_1 \in \Gamma$.
2) $\alpha_1 \in \Gamma$.
Индукционно предположение: Нека за $i = 1,2,\dots,k$ е изпълнено $\alpha_i \in \Gamma$
Индукционна стъпка: Разглеждаме $\alpha_{k+1}$. Има 3 случая:
1) $\alpha_{k+1}$ е аксиома, следователно (както в базата на индукцията) $\alpha_{k+1} \in \Gamma$
2) $\alpha_{k+1} \in \Gamma$
3. $\alpha_{k+1}$ се получава от $\alpha_l$ и $\alpha_m$ по правилото MP, където $l$ и $m$ са числа по-малки от $k+1$. Нека например $\alpha_m = \alpha_l \Rightarrow \alpha_{k+1}$ (другият случай е симетричен). От ИП следва, че $\alpha_l, \alpha_m \in \Gamma$, следователно (понеже теориите са затворени относно MP) $\alpha_{k+1} \in \Gamma$.
Така показахме, че $Th(\Gamma) \subseteq \Gamma$, следователно $Th(\Gamma) = \Gamma$.
Теорема: Нека $X$ е множество от формули. Тогава$Th(x)$ е теория, която съдържа $X$ и е най-малката по включване с това свойство.
Доказателство:
От Лема 2 следва, че $X \subseteq Th(X)$. Остава да покажем, че $Th(X)$ е теория, и че е минимална по включване.
Нека $\alpha$ е теорема на съждителното смятане. Тогава $\emptyset \mapsto \alpha$, следователно (понеже $\emptyset \subseteq X$) $\quad X \mapsto \alpha$. Следователно $\alpha \in Th(X)$. Следователно $Th(X)$ съдържа всички теореми на съждителното смятане.
Нека $\alpha \in Th(X)$ и $\alpha \Rightarrow \beta \in Th(X)$. Тогава $X \mapsto \alpha$ и $X \mapsto \alpha \Rightarrow \beta$. Следователно $X \mapsto \beta$, тоест $\beta \in \Gamma$. Следователно $Th(X)$ е затворена относно MP.
Нека $\Gamma$ е теория и $X \subseteq \Gamma$. Ще докажем, че $Th(X) \subseteq \Gamma$ (тоест, че $Th(X)$ е минималната по включване теория, съдържаща $\Gamma$).
Нека $\alpha \in Th(X)$. Тогава $X \mapsto \alpha$ и от монотонността на синтактичното следване имаме $\Gamma \mapsto \alpha$. Следователно $\alpha \in Th(\Gamma)$. Но $\Gamma$ е теория, следователно (Лема 3) $Th(\Gamma) = \Gamma$, следователно $\alpha \in \Gamma$. Следователно $Th(X) \subseteq \Gamma$.
Нека разгледаме множеството $Th(\{\alpha \land \lnot \alpha\})$. За всяка формула $\beta$ е изпълнено $\alpha \land \lnot \alpha \mapsto \beta$, следователно $Th(\{\alpha \land \lnot \alpha\})$ е тривиалната теория.
По-общо, ако $X \mapsto p \land \lnot p$, то $Th(X)$ е тривиалната теория.
Дефиниция: Теорията $\Gamma$ наричаме противоречива, ако съвържа формула от вида $p \land \lnot p$.
Теорема: Една теория $\Gamma$ е противоречива тогава и само тогава, когато съдържа всички формули (доказателството не е дадено, но е тривиално).
Дефиниция: Нека $\alpha$ е формула, а $\Gamma$ е теория. Означаваме $\Gamma + \alpha = Th(\Gamma \cup \{\alpha\})$.
Теорема: $\Gamma + \alpha = \{\beta | a \Rightarrow \beta \in \Gamma\}$
Доказателство:
Нека $\beta \in \Gamma + \alpha$. Тогава
$\beta \in Th(\Gamma \cup \{\alpha\})$
$\Gamma, \alpha \mapsto \beta$
$\Gamma \mapsto \alpha \Rightarrow \beta$ (от Теорема за дедукцията)
$\alpha \Rightarrow \beta \in Th(\Gamma)$
$\alpha \Rightarrow \beta \in \Gamma$ (от Лема 3)
Нека $\beta \in \{ \beta | \alpha \Rightarrow \beta \in \Gamma\}$. Тогава $\alpha \Rightarrow \beta \in \Gamma$. Но $\alpha \in \Gamma \cup \{\alpha\}$. Следователно (Лема 1) $\alpha \in Th(\Gamma \cup \{\alpha\})$. Също $\alpha \Rightarrow \beta \in Th(\Gamma \cup \{\alpha\})$. Понеже $Th(\Gamma \cup \alpha)$ е теория, то тя е затворена относно MP. Следователно $\beta \in Th(\Gamma \cup \{\alpha\})$, тоест $\beta \in \Gamma + \alpha$.
Теорема (Критерий за противоречивост): Една теория $\Gamma + \alpha$ е противоречива тогава и само тогава, когато $\lnot \alpha \in \Gamma$.
Доказателство:
Нека $\Gamma + \alpha$ е противоречива. Тогава $\Gamma, \alpha \mapsto p \land \lnot p$ и от правилото за привеждане към абсурд получаваме $\Gamma \mapsto \lnot \alpha$. Следователно $\lnot \alpha \in \mathrm{Th}(\Gamma)$ и от лема 3 $\not \alpha \in \Gamma$.
Нека $\lnot \alpha \in \Gamma$. От монотонността получаваме $\lnot \alpha \in \Gamma + \alpha$. Имаме също $\alpha \in \Gamma + \alpha$, следователно $\alpha \land \lnot \alpha \in \Gamma + \alpha$, тоест $\Gamma + \alpha$ е противоречива.
Лема 4: Нека $X$ е множество от формули и $X \mapsto \alpha$. Тогава всеки модел на $X$ е модел и на $\alpha$.
Доказателство:
Нека $v$ е произволен модел на $X$ (тоест, за всяка формула $\beta \in X$ е изпълнено $v(\beta) = 1$). Нека редицата $\alpha_1, \alpha_2, \dots, \alpha_n = \alpha$ е доказателство на $\alpha$ от $X$. Ще видим, че за $i = 1, 2, \dots, n$ е изпълнено $v(\alpha_i) =1$. Индукция по $i$:
База: за $\alpha_1$ знаем, че или е аксиома или е от $X$. И в двата случая $v(\alpha_1)=1$.
ИП: Нека за $i = 1,2 \dots , k$ е изпълнено $v(\alpha_i)=1$.
ИС: Разглеждаме $\alpha_{k+1}$. Имаме три случая:
1. $\alpha_{k+1}$ е аксиома
2. $\alpha_{k+1} \in X$
3. $\alpha_{k+1}$ се получава от два предходни члена на редицата по MP
За 1. и 2. е очевидно, че $v(\alpha_{k+1})=1$.
За 3. имаме, че има два предходни члена — нека това са $\alpha_m$ и $\alpha_l$ — такива че (например) $\alpha_m = \alpha_l \Rightarrow \alpha_{k+1}$. Понеже $m < k+1, l<k+1$ от ИП имаме $v(\alpha_m) = v(\alpha_l) =1$. Тоест $v(\alpha_l \Rightarrow \alpha_{k+1}) =1$. Да допуснем, че $v(\alpha_{k+1})=0$. Тогава от дефиницията за семантика на $\Rightarrow$ получаваме, че $v(\alpha_l)=0$, което е противоречие. Следователно $v(\alpha_{k+1})=1$.
Теорема: Нека $X$ е множество от формули. Ако $X$ има модел, то $Th(X)$ е непротиворечива.
Доказателство: Нека $v$ е модел на $X$. Да допуснем, че $\mathrm{Th}(X)$ е противоречива. Тогава $p \land \lnot p \in \mathrm{Th}(X)$ и от лема 4 получаваме, че $v(p \land \lnot p) =1$, което е абсурд. Следователно $\mathrm{Th}(X)$ е непротиворечива.
Дефиниция: Една теория $\Gamma$ наричаме:
1. Пълна, ако е непротиворечива и за всяка формула $\alpha$ е изпълнено или $\alpha \in \Gamma$ или $\lnot \alpha \in \Gamma$.
2. Дизюнктивна, ако е непротиворечива и от $\alpha \lor \beta \in \Gamma$ следва, че или $\alpha \in \Gamma$ или $\beta \in \Gamma$.
3. Максимална, ако е непротиворечива и за всяка непротиворечива теория $\Delta$ е в сила: ако $\Gamma \subseteq\Delta$ и $\Delta$ е непротиворечива, то $\Gamma = \Delta$.
Теорема: Нека $\Gamma$ е теория. Следните три твърдения са еквивалентни:
1. $\Gamma$ е пълна.
2. $\Gamma$ е дизюнктивна.
3. $\Gamma$ е максимална.