Math 2.0

Mathematical logic and foundations Definition

Lindenbaum–Tarski algebra

Builds on Propositional logicEquivalence relationQuotient setBoolean algebra

Definition

Let PP be a set of propositional variables. Let FF be the set of formulas of classical propositional logic over PP built with ∧\wedge, ∨\vee, ¬\neg, ⊤\top and ⊥\bot. Let T⊆FT \subseteq F be a theory. For φ,ψ∈F\varphi, \psi \in F, put φ∼Tψ\varphi \sim_T \psi if T⊢φ↔ψT \vdash \varphi \leftrightarrow \psi. This is an equivalence relation on FF; write [φ][\varphi] for the class of φ\varphi. The Lindenbaum–Tarski algebra of TT is the quotient set F/∼TF / {\sim_T} with the operations [φ]∧[ψ]=[φ∧ψ],[φ]∨[ψ]=[φ∨ψ],¬[φ]=[¬φ],[\varphi] \wedge [\psi] = [\varphi \wedge \psi], \quad [\varphi] \vee [\psi] = [\varphi \vee \psi], \quad \neg [\varphi] = [\neg \varphi], and the constants 0=[⊥]0 = [\bot] and 1=[⊤]1 = [\top].

Remarks

The operations are well defined because provable equivalence is compatible with the connectives, and the result is a Boolean algebra. Its order is given by [φ]≤[ψ][\varphi] \le [\psi] if and only if T⊢φ→ψT \vdash \varphi \to \psi.

Example: for P={p}P = \set{p} and T=∅T = \emptyset, every formula is equivalent to one of ⊥\bot, pp, ¬p\neg p, ⊤\top, and no two of these are equivalent, as their truth tables differ. So the algebra is the four-element Boolean algebra with atoms [p][p] and [¬p][\neg p].

Non-example: identify formulas only when they are equal as strings. Then the classes [p∧q][p \wedge q] and [q∧p][q \wedge p] differ, so ∧\wedge is not commutative and the result is not a Boolean algebra.

The same construction for intuitionistic logic gives a Heyting algebra. A theory TT is consistent if and only if 0≠10 \ne 1 in its algebra.

Reading path

To understand this page from the ground up, read these 11 pages in order. The foundations come first.

Show the path as a graph
Boolean algebra, concept, no evidence levelBoolean algebraconceptEquivalence relation, concept, no evidence levelEquivalence relationconceptProposition, concept, no evidence levelPropositionconceptQuotient set, concept, no evidence levelQuotient setconceptConjunction, definition, no evidence levelConjunctiondefinitionDisjunction, definition, no evidence levelDisjunctiondefinitionImplication, definition, no evidence levelImplicationdefinitionNegation, definition, no evidence levelNegationdefinitionBiconditional, definition, no evidence levelBiconditionaldefinitionPropositional logic, concept, no evidence levelPropositional logicconceptLindenbaum–Tarski algebra, definition, no evidence levelLindenbaum–Tarski alg…definition
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Boolean algebra concept
  2. Equivalence relation concept
  3. Proposition concept
  4. Quotient set concept
  5. Conjunction definition
  6. Disjunction definition
  7. Implication definition
  8. Negation definition
  9. Biconditional definition
  10. Propositional logic concept
  11. Lindenbaum–Tarski algebra definition

Further reading

  1. Web https://en.wikipedia.org/wiki/Lindenbaum–Tarski_algebra
About this page
TagMGCVQXXQJH
URIm2://MGCVQXXQJH
Kinddefinition
WritingW0 stub
MSC03G05, 03B05
DefinesLindenbaum–Tarski algebra
UsesPropositional logic, Equivalence relation, Quotient set, Boolean algebra
Changed2 November 2026

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • an inventory row: the row of the inventory that the node accounts for (0 of 1)
  • a source with a locator (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.