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.

Definice

Lindenbaumovy algebry teorie

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

• $[\phi {]}_{\sim }\wedge [\psi {]}_{\sim }=[\phi \wedge \psi {]}_{\sim }$
• $[\phi {]}_{\sim }\vee [\psi {]}_{\sim }=[\phi \vee \psi {]}_{\sim }$
• $-[\phi {]}_{\sim }=[\mathrm{\neg }\phi {]}_{\sim }$
• $0=[\phi \wedge \mathrm{\neg }\phi {]}_{\sim }$ , kde $\phi$ je nějaká formule s m-volnými proměnnými.
• $1=[\phi \vee \mathrm{\neg }\phi {]}_{\sim }$ , kde $\phi$ 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. Lindenbaumova algebra teorie T je dvouprvková, právě když je T úplná teorie.
• Formule $\phi$ je nedokazatelná v T, právě když $\phi \in ̸1$.
• Formule $\phi$ je nevyvratitelná v T, právě když $\phi \in ̸0$.

Související články

• Booleova algebra
• Definovatelná množina
• Typ