Knowra Lindenbaum's lemma Lindenbaum's lemma Lindenbaum's lemma states that every consistent set of sentences can be extended to a maximal consistent set, one that decides every sentence in its language.
Maximal consistent set : A consistent set of sentences that cannot be enlarged without becoming inconsistent. The lemma’s extension is maximal precisely when no further sentence can be added consistently.
Gödel's completeness theorem : The theorem that every first-order sentence true in all models is derivable in classical first-order logic. Lindenbaum extensions support the construction of models needed to prove this theorem.
Propositional logic : The study of reasoning with propositions connected by truth-functional operators. The lemma already appears in propositional logic, where its construction is especially direct.
Adolf Lindenbaum : A Polish logician whose work contributed to mathematical logic and the study of formal theories. The lemma bears Lindenbaum’s name and reflects his work on extending consistent theories.
Consistency (logic) : A property of a set of sentences when no contradiction follows from it. Consistency is the condition that the extension process must preserve.
Henkin construction : A method for building a model by extending a theory with witness constants and completing it consistently. Henkin proofs combine witness addition with maximal consistent extension to obtain a model.
First-order logic : A formal system for reasoning about objects, properties, and relations using quantifiers. In first-order logic, the lemma extends consistent theories in a language with quantifiers.
Alfred Tarski : A Polish-American logician, mathematician, and philosopher known for foundational work in semantics and model theory. Tarski’s Polish logic milieu helped develop the ideas surrounding formal theories and their extensions.
Enumeration : An ordered listing of the members of a set, often used in mathematical constructions. For countable languages, listing sentences lets the construction decide them one at a time.
Canonical model : A model constructed from syntactic objects, such as theories or formulas, to establish semantic properties of a logic. Maximal consistent sets often serve as the worlds or theories from which canonical models are built.
Show all 20