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:

Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle \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 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 Nelze pochopit (MathML, alternativně SVG nebo PNG (doporučeno pro moderní prohlížeče a kompenzační pomůcky): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „https://en.wikipedia.org/api/rest_v1/“:): {\displaystyle |B(T)|\geq2<math> neboť <math>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 neboT\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_{{\mathcal {L}}(P)}^{n}}}$ 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_{{\mathcal {L}}(P)}^{n}}}$ 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_{{\mathcal {L}}(P)}^{n}}}$ 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 Morleyovy věty.

Odkazy

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ů