An undecidable problem in correspondence theory (Q3984404)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 26183
Language Label Description Also known as
default for all languages
No label defined
    English
    An undecidable problem in correspondence theory
    scientific article; zbMATH DE number 26183

      Statements

      An undecidable problem in correspondence theory (English)
      0 references
      0 references
      27 June 1992
      0 references
      undecidability of first-order definability of propositional formulas
      0 references
      intuitionistic formulas
      0 references
      correspondence theory
      0 references
      Minsky machine
      0 references
      We prove undecidability of first-order definability of propositional formulas. The main result is proved for intuitionistic formulas, but it remains valid for other kinds of propositional formulas by analogous arguments or with the help of various translations. For general background on correspondence theory the reader is referred to \textit{J. van Benthem} [Handbook of philosophical logic, Vol. II, 167-247 (1984; Zbl 0572.03003); Modal logic and classical logic (1985; Zbl 0639.03014); see Notre Dame J. Formal Logic 30, No. 1, 20-35 (1989; Zbl 0671.03013) for a survey of recent results]. The method for the proofs of undecidability in this paper will be to simulate calculations of a Minsky machine by intuitionistic formulas.
      0 references

      Identifiers

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