Lindenbaum-Tarského algebry

Lindenbaum - Tarského algebra je speciální Booleova algebra na množině formulí klasické predikátové logiky

Konstrukce

Uvažme $\varphi, \psi \in \mathit{Form_L}$, kde $\mathit{Form_L}$ je množina všech prvořádových formulí predikátové logiky v jazyce L, a teorii $T\subseteq\mathit{Form_L}$. Pro každou takovouto teorii můžeme definovat ekvivalenci $\equiv_T$ následovně: $$ \varphi\equiv_T\psi \Leftrightarrow T\vdash \varphi\leftrightarrow\psi $$ Označme nyní $[\varphi]_{\equiv_T}$ ekvivalenční třídu pro $\varphi$ a uvažme $B(T)=\{[\varphi]_{\equiv_T}| \varphi \in \mathit{Form_L}\}$ na níž definujme operace $\wedge$ (průsek), $\vee$ (sjednocení), $-$ (komplement) a prvky $\textbf{1}$ (maximální prvek), $\textbf{0}$ (minimální prvek) takto: \begin{align*} [\varphi]_{\equiv_T} \wedge [\psi]_{\equiv_T} &= [\varphi \& \psi]_{\equiv_T}\\ [\varphi]_{\equiv_T} \vee [\psi]_{\equiv_T} &= [\varphi \vee \psi]_{\equiv_T}\\ -[\varphi]_{\equiv_T} &= [\neg\varphi]\\ \textbf{1} &= [\varphi \vee \neg\varphi]_{\equiv_T}\\ \textbf{0} &= [\varphi \& \neg\varphi]_{\equiv_T} \end{align*}

Potom $\mathbb{B}(T)=<B(T),\wedge,\vee,-,\textbf{0},\textbf{1}>$ je Booleova algebra.\\

Omezíme-li se nyní pouze na sentence tj. místo $B(T)$ definujeme operace na $LT(T)=\{[\varphi]_{\equiv_T}| \varphi \in \mathit{Sent_L}\}$ kde $\mathit{Sent_L}\subseteq\mathit{Form_L}$ je množina sentencí, získáme Lindenbaum-Tarského algebru pro teorii $T$.

Spočetný průsek a sjednocení

Je rozumné klást otázku na význam spočetného průseku a sjednocení v $\mathbb{B}(T)$. Intuitivně bychom se mohli pokusit definovat nekonečný průsek množiny $M\subseteq B(T)$ jako nekonečnou konjunkci formulí z $M$, obdobně nekonečné sjednocení množiny $M$ jako nekonečnou disjunkci formulí z $M$ avšak protože formule mohou mít pouze konečnou délku nebyl by výsledek prvkem $B(T)$. Pro některé množiny formulí však nekonečný průsek a sjednocení definovat můžeme:\\ Nechť $\varphi \in\mathit{Form_L}$ potom pro $M_\varphi=\{[\varphi(t,x_0,\cdots)]|t~je~term~jazyka~L\}$ definujme $$\bigvee M_\varphi=[(\exists x)(\varphi(x,x_0,\cdots)]~a~\bigwedge M_\varphi=[(\forall x)(\varphi(x,x_0,\cdots)]$$

Uspořádání na B(T)

Jako jakoukoli jinou Booleovu algebru můžeme i $B(T)$ chápat jako uspořádanou množinu pomocí relace $\leq$ : $$[\varphi]\leq[\psi] \Leftrightarrow [\varphi]=[\varphi]\wedge[\psi]$$ neboť $[\varphi]=[\varphi]\wedge[\psi]$ v $\mathbb{B}(T)$ vlastně znamená $T \vdash \varphi \leftrightarrow \varphi \wedge \psi$ což je ekvivalentní s $T \vdash \varphi \rightarrow \psi$ dostáváme: $$[\varphi]\leq[\psi] \Leftrightarrow T \vdash \varphi \rightarrow \psi$$~.\\ Stojí za povšimnutí, že uspořádání na $\mathbb{B}(T)$ lze interpretovat jako "čím blíže je $[\varphi]$ k $\textbf{0}$ tím silnějším je tvrzením" (blízkost nule může odpovídat snadnosti falsifikace, $\textbf{0}$ je falsisikovaná vždy naopak $\textbf{1}$ není falsifikovatelná nikdy).Mimo jiné tato interpretace plyne i z triviálního faktu, že čím blíže je $[\varphi]$ k $\textbf{0}$ tím větší (co do inkluze) je množina následníků tj. čím silnější předpoklad učiníme, tím více závěrů jsme schopni udělat. S touto interpretací se můžeme setkat například ve forcingu, kde $p\leq q$ interpretujeme jako "$p$ je silnější podmínka než $q$".

Definice

Nechť $T$ je teorie prvořádové predikátové logiky a $L$ její jazyk, potom $\mathbb{LT}(T)=<LT(T),\wedge,\vee,-,\textbf{0},\textbf{1}>$ kde $LT(T)=\{[\varphi]_{\equiv_T}| \varphi \in \mathit{Sent_L}\}$ a $\equiv_T$, $\wedge$, $\vee$, $-$,$\textbf{0}$ a $\textbf{1}$ jsou definovány jako v Konstrkukce výše, nazveme Lindenbaum-Tarského algebrou pro teorii $T$.

Vlastnosti

• Je-li $T$ sporná, potom $\forall \varphi,\psi \in \mathit{Form_L} : T\vdash \varphi\leftrightarrow\psi$ a tedy $|B(T)|=1$ a tedy i $|L(T)|=1$.\\
• Je-li $T$ bezesporná, je $|B(T)|\geq2$ neboť $T \vdash \neg(\varphi \vee \neg\varphi \leftrightarrow \varphi \& \neg\varphi)$ a proto $[\varphi \vee \neg\varphi]_{\equiv_T}~\neq~[\varphi \& \neg\varphi]_{\equiv_T}$.\\
• Je-li $T$ bezesporná a navíc úplná dostáváme $|L(T)|=2$ neboť z úplnosti $T$ plyne, že $\forall \sigma \in \mathit{Sent_L} : T \vdash \sigma nebo T \vdash \neg\sigma$ a tedy $T \vdash \sigma \leftrightarrow \top$ nebo $T \vdash \sigma \leftrightarrow \bot$ z čehož plyne, že $[\sigma]_{\equiv_T} \in [\varphi \vee \neg\varphi]_{\equiv_T}$ nebo $[\sigma]_{\equiv_T} \in [\varphi \& \neg\varphi]_{\equiv_T}$ a tedy $L(T)=\{[\varphi \vee \neg\varphi]_{\equiv_T},[\varphi \& \neg\varphi]_{\equiv_T}\}$\\
• Je-li $T$ bezesporná a neúplná potom $|L(T)|\geq 4$ neboť existuje sentence $\sigma$ t.ž. $T \nvdash \sigma$ a $T \nvdash\neg\sigma$ a tudíž $\sigma \notin [\top]_{\equiv_T}$, $\sigma \notin [\bot]_{\equiv_T}$ a proto jsou $[\top]_{\equiv_T},[\bot]_{\equiv_T},[\sigma]_{\equiv_T},[\neg\sigma]_{\equiv_T}$ čtyři navzájem různé prvky $L(T)$.
• Každá Booleova algebra je izomorfní Lindenbaum-Tarského algebře $LT(T)$ pro vhodné $T$.

$\mathcal{L}_n(P,\mathfrak{A})

Definice: Nechť $\mathfrak{A}$ je struktura s nosičem $A$ a $P\subseteq A$, potom $\mathcal{L}(P)$ je jazyk obsahující pouze parametry z $P$ a $\mathit{Form^n_{\mathcal{L}(P)}}$ množina formulí $\varphi$ v jazyce $\mathcal{L}(P)$ kde $\varphi$ má právě $n$ proměnných.

Na množině $\mathit{Form^n_{\mathcal{L}(P)}}$ můžeme opět zavést ekvivalenci $\equiv_T$ jako výše v Konstrukci. Zadefinujeme-li také $\equiv_T$, $\wedge$, $\vee$, $-$,$\textbf{0}$ a $\textbf{1}$ jako v Konstrukci výše a zvolíme $T=Th(\mathfrak{A})$ získáme Booleovu algebru, jež značíme $\mathcal{L}_n(P,\mathfrak{A})$.

Definice: Nechť $\mathfrak{A}$ je struktura s nosičem $A$ a $P\subseteq A$, řekneme, že množina $X \subseteq A^n$ je $P$-definovatelná pokud existuje $\varphi \in \mathit{Form^n_{\mathcal{L}(P)}}$ taková, že $\varphi$ definuje $X$. Soubor všech $P$-definovatelných množin na $A$ označíme $B_n(P,\mathfrak{A})$

Význam: Vzhledem k tomu, že každá $[\varphi]_{\equiv_T}$ z $\mathcal{L}_n(P,\mathfrak{A})$ definuje právě jednu $P$-definovatelnou množinu v $A^n$ nepřekvapí nás, že platí:$$\mathcal{L}_n(P,\mathfrak{A})\cong\mathbb{B}_n(P,\mathfrak{A})$$ kde $\mathbb{B}_n(P,\mathfrak{A}$ je algebra množin s nosičem $B_n(P,\mathfrak{A})$.

Algebra $\mathbb{B}_n(P,\mathfrak{A})$ slouží k definici $n$-typu v Teorii modelů a důkazu Morleyho věty.

Odkazy

Související články

Booleova algebra
Forcing
Teorie modelů