Математическа логика - тема 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$).
Доказателство:

Теорема: Нека $X$ е множество от формули. Тогава$Th(x)$ е теория, която съдържа $X$ и е най-малката по включване с това свойство.
Доказателство:

Нека разгледаме множеството $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\}$
Доказателство:

Теорема (Критерий за противоречивост): Една теория $\Gamma + \alpha$ е противоречива тогава и само тогава, когато $\lnot \alpha \in \Gamma$.
Доказателство:

Лема 4: Нека $X$ е множество от формули и $X \mapsto \alpha$. Тогава всеки модел на $X$ е модел и на $\alpha$.
Доказателство:

Теорема: Нека $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$ е максимална.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License