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 (syntaktická chyba): {\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 (syntaktická chyba): {\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 Nelze pochopit (Chyba konverze. Server („https://en.wikipedia.org/api/rest_“) hlásí: „Cannot get mml. Server problem.“): {\displaystyle 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$, 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 -} ,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 \textbf{0}} a 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 \textbf{1}} jako v Konstrukci výše a zvolíme 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 T=Th(\mathfrak{A})} získáme Booleovu algebru, jež značíme 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 \mathcal{L}_n(P,\mathfrak{A})} .

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

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

Algebra 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 \mathbb{B}_n(P,\mathfrak{A})} slouží k definici 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 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ů