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:

$ [\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} $

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 $.[1]

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 Konstrukci 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 $.[2]

$ \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 $ volných 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}) $.[3]

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

Odkazy

Reference

  1. Radek Honzík, Boolean Algebras, Lecture Notes, Winter 2013
  2. Handbook of Boolean Algebras: Volume 1, North-Holland 1989, Theorem 9.10
  3. A Shorten Model Theory, Wilfred Hodges, Cambridge UP, April 1997

Použitá literatura

  • Radek Honzík, Boolean Algebras, Lecture Notes, Winter 2013
  • Radek honzík, Introduction to Model Theory, Lecture Notes, Winter 2012
  • A Shorten Model Theory, Wilfred Hodges, Cambridge UP, April 1997
  • Thomas Jech, Set Theory - The 3rd Millenium Edition revised and expanded, Springer, 2006

Související články

Booleova algebra
Forcing
Teorie modelů