Lindenbaumova algebra

Lindenbaumova algebra (také Lindenbaum-Tarského algebra) je pojem z oblasti matematické logiky. Slouží k vyjádření struktury množiny formulí co se týče jejich dokazatelnosti v nějaké formální teorii.

Definice

Lindenbaumovy algebry teorie

Nechť T je bezesporná teorie v jazyce L a m je přirozené číslo. Pro formule $\varphi, \psi$ jazyka L mající právě m volných proměnných definujeme $\varphi \sim \psi$, pokud v T je dokazatelné $\varphi \leftrightarrow \psi$. Označíme $F^m_T$ množinu všech tříd ekvivalence $\sim$. m-tá Lindenbaumova algebra teorie T je Booleova algebra s nosnou množinou $F^m_T$ a operacemi definovanými následovně:

• $[\varphi]_\sim \and [\psi]_\sim = [\varphi \and \psi]_\sim$
• $[\varphi]_\sim \vee [\psi]_\sim = [\varphi \vee \psi]_\sim$
• $-[\varphi]_\sim = [\neg\varphi]_\sim$
• $0 = [\varphi \and \neg\varphi]_\sim$ , kde $\varphi$ je nějaká formule s m-volnými proměnnými.
• $1 = [\varphi \vee \neg\varphi]_\sim$ , kde $\varphi$ je nějaká formule s m-volnými proměnnými.

Lindenbaumovy algebry jazyka

m-tou Lindenbaumovu algebru jazyka L definujeme jako m-tou Lindenbaumovu algebru teorie v jazyce L, která nemá žádné vlastní (tj. mimologické) axiomy.

Vlastnosti

• 0-tá Lindenbaumova algebra teorie T je dvouprvková, právě když je T úplná teorie.
• Formule $\varphi$ je nedokazatelná v T, právě když $\varphi\not\in 1$.
• Formule $\varphi$ je nevyvratitelná v T, právě když $\varphi\not\in 0$.

Související články

• Booleova algebra
• Definovatelná množina
• Typ