mathematical logic Mathematical logic is the study of formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical properties of formal ...

, the Lindenbaum–Tarski algebra (or Lindenbaum algebra) of a

logical theory In mathematical logic, a theory (also called a formal theory) is a set of sentence (mathematical logic), sentences in a formal language. In most scenarios, a deductive system is first understood from context, after which an element \phi\in T of a d ...

''T'' consists of the equivalence classes of sentences of the theory (i.e., the

quotient In arithmetic, a quotient (from lat, quotiens 'how many times', pronounced ) is a quantity produced by the division of two numbers. The quotient has widespread use throughout mathematics, and is commonly referred to as the integer part of a ...

, under the equivalence relation ~ defined such that ''p'' ~ ''q'' exactly when ''p'' and ''q'' are provably equivalent in ''T''). That is, two sentences are equivalent if the theory ''T'' proves that each implies the other. The Lindenbaum–Tarski algebra is thus the quotient algebra obtained by factoring the algebra of formulas by this congruence relation. The algebra is named for

logician Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the science of deductively valid inferences or of logical truths. It is a formal science investigating how conclusions follow from premises ...

Adolf Lindenbaum Adolf Lindenbaum (12 June 1904 – August 1941) was a Polish-Jewish logician and mathematician best known for Lindenbaum's lemma and Lindenbaum–Tarski algebras. He was born and brought up in Warsaw. He earned a Ph.D. in 1928 under Wac ...

and

Alfred Tarski Alfred Tarski (, born Alfred Teitelbaum;School of Mathematics and Statistics, University of St Andrews ''School of Mathematics and Statistics, University of St Andrews''. January 14, 1901 – October 26, 1983) was a Polish-American logician a ...

. It was first introduced by Tarski in 1935 as a device to establish correspondence between classical

propositional calculus Propositional calculus is a branch of logic. It is also called propositional logic, statement logic, sentential calculus, sentential logic, or sometimes zeroth-order logic. It deals with propositions (which can be true or false) and relations ...

and Boolean algebras. The Lindenbaum–Tarski algebra is considered the origin of the modern algebraic logic.; here: pages 1-2

Operations

The operations in a Lindenbaum–Tarski algebra ''A'' are inherited from those in the underlying theory ''T''. These typically include

conjunction Conjunction may refer to: * Conjunction (grammar), a part of speech * Logical conjunction, a mathematical operator ** Conjunction introduction, a rule of inference of propositional logic * Conjunction (astronomy), in which two astronomical bodies ...

and

disjunction In logic, disjunction is a logical connective typically notated as \lor and read aloud as "or". For instance, the English language sentence "it is raining or it is snowing" can be represented in logic using the disjunctive formula R \lor S ...

, which are

well-defined In mathematics, a well-defined expression or unambiguous expression is an expression whose definition assigns it a unique interpretation or value. Otherwise, the expression is said to be ''not well defined'', ill defined or ''ambiguous''. A func ...

on the equivalence classes. When negation is also present in ''T'', then ''A'' is a

Boolean algebra In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variables are the truth values ''true'' and ''false'', usually denoted 1 and 0, whereas i ...

, provided the logic is classical. If the theory ''T'' consists of the propositional tautologies, the Lindenbaum–Tarski algebra is the

free Boolean algebra In mathematics, a free Boolean algebra is a Boolean algebra with a distinguished set of elements, called ''generators'', such that: #Each element of the Boolean algebra can be expressed as a finite combination of generators, using the Boolean opera ...

generated by the

propositional variable In mathematical logic, a propositional variable (also called a sentential variable or sentential letter) is an input variable (that can either be true or false) of a truth function. Propositional variables are the basic building-blocks of proposit ...

Related algebras

Heyting algebra In mathematics, a Heyting algebra (also known as pseudo-Boolean algebra) is a bounded lattice (with join and meet operations written ∨ and ∧ and with least element 0 and greatest element 1) equipped with a binary operation ''a'' → ''b'' of '' ...

s and

interior algebra In abstract algebra, an interior algebra is a certain type of algebraic structure that encodes the idea of the topological interior of a set. Interior algebras are to topology and the modal logic S4 what Boolean algebras are to set theory and or ...

s are the Lindenbaum–Tarski algebras for

intuitionistic logic Intuitionistic logic, sometimes more generally called constructive logic, refers to systems of symbolic logic that differ from the systems used for classical logic by more closely mirroring the notion of constructive proof. In particular, systems ...

and the modal logic S4, respectively. A logic for which Tarski's method is applicable, is called ''algebraizable''. There are however a number of logics where this is not the case, for instance the modal logics S1, S2, or S3, which lack the

rule of necessitation Modal logic is a collection of formal systems developed to represent statements about necessity and possibility. It plays a major role in philosophy of language, epistemology, metaphysics, and natural language semantics. Modal logics extend other ...

(⊢φ implying ⊢□φ), so ~ (defined above) is not a congruence (because ⊢φ→ψ does not imply ⊢□φ→□ψ). Another type of logic where Tarski's method is inapplicable is

relevance logic Relevance logic, also called relevant logic, is a kind of non-classical logic requiring the antecedent and consequent of implications to be relevantly related. They may be viewed as a family of substructural or modal logics. It is generally, but ...

s, because given two theorems an implication from one to the other may not itself be a theorem in a relevance logic. The study of the algebraization process (and notion) as topic of interest by itself, not necessarily by Tarski's method, has led to the development of abstract algebraic logic.

References

* {{DEFAULTSORT:Lindenbaum-Tarski algebra Algebraic logic Algebraic structures

Operations

Related algebras

See also

References