Lindenbaumova algebra

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

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[editovat | editovat zdroj]

Lindenbaumovy algebry teorie[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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

Vlastnosti[editovat | editovat zdroj]

  • 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[editovat | editovat zdroj]