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 φ , ψ {\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 F T m {\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 F T m {\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 }}
  • 0 = [ φ ∧ ¬ φ ] ∼ {\displaystyle 0=[\varphi \land \neg \varphi ]_{\sim }} , kde φ {\displaystyle \varphi } je nějaká formule s m-volnými proměnnými.
  • 1 = [ φ ∨ ¬ φ ] ∼ {\displaystyle 1=[\varphi \vee \neg \varphi ]_{\sim }} , kde φ {\displaystyle \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. Lindenbaumova algebra teorie T je dvouprvková, právě když je T úplná teorie.
  • Formule φ {\displaystyle \varphi } je nedokazatelná v T, právě když φ ∉ 1 {\displaystyle \varphi \not \in 1} .
  • Formule φ {\displaystyle \varphi } je nevyvratitelná v T, právě když φ ∉ 0 {\displaystyle \varphi \not \in 0} .

Související články

  • Booleova algebra
  • Definovatelná množina
  • Typ