Lindenbaumova algebra

Lindenbaumova algebra (také Lindenbaumova–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.

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

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

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

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

• Booleova algebra
• Definovatelná množina
• Typ