Elimination problems in logic: a brief history (Q1024114): Difference between revisions

From MaRDI portal
Import240304020342 (talk | contribs)
Set profile property.
Set OpenAlex properties.
Property / full work available at URL
 
Property / full work available at URL: https://doi.org/10.1007/s11229-008-9352-4 / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W2061497937 / rank
 
Normal rank

Revision as of 19:22, 19 March 2024

scientific article
Language Label Description Also known as
English
Elimination problems in logic: a brief history
scientific article

    Statements

    Elimination problems in logic: a brief history (English)
    0 references
    0 references
    0 references
    16 June 2009
    0 references
    The kind of elimination problem the author refers to in this paper is of the following type: If \(R\) and \(S\) are disjoint sets of predicate letters and \(A(R,S)\) is a sentence (or a conjunction of sentences) such that every predicate symbol that occurs in \(A(R,S)\) belongs to \(R\cup S\), find a sentence (or a conjunction of sentences) \(A^{\bigtriangledown}(S)\) that axiomatizes the set of \(S\)-logical consequences of \(A(R,S)\). Interest in elimination may be seen to go back to Aristotle's syllogistic, later to be emphasized by G. Boole (whose line of thought has long been considered deficient, until S. Burris (2001) managed to clarify it) and E. Schröder, who turned it into an algebra problem to be solved inside Boolean algebras. The author presents in detail Schröder's solution to the elimination problem, followed by an outline of Skolem's proof of what the author considers to be ``the most important elimination result in logic'': Given any formula \(A\) in the language of monadic second-order logic, one can find a formula \(A'\) in monadic first-order logic with equality, such that \(A\) and \(A'\) are logically equivalent. The paper ends with questions regarding quantifier elimination and some problems raised by the author's paper [J. Symb. Log. 25, 97--142 (1960; Zbl 0108.00304)].
    0 references
    elimination of variables and quantifiers
    0 references
    Boolean equations
    0 references
    monadic second-order logic
    0 references
    atomless and atomic Boolean algebras
    0 references
    Boole
    0 references
    Schröder
    0 references
    Skolem
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references