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
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
0.8709671497344971
0 references
0.8495052456855774
0 references
0.7689614295959473
0 references
0.7669447064399719
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