Quine's ‘limits of decision’ (Q4948519)
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 1429764
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Quine's ‘limits of decision’ |
scientific article; zbMATH DE number 1429764 |
Statements
Quine's ‘limits of decision’ (English)
0 references
7 June 2000
0 references
first-order logic
0 references
decidability
0 references
presentation
0 references
free algebra
0 references
satisfiability problem
0 references
lattice of logics
0 references
fluted logic
0 references
0.7638359069824219
0 references
0.7583336234092712
0 references
0.7450999617576599
0 references
0.743324875831604
0 references
The author approaches logics from an algebraic perspective: a logic has a presentation as a free algebra of type \(T\) on a set \(X\) of generators. The logical vocabulary is the set of operations on \(T\) and the logical generators. This paper takes this viewpoint in studying sublogics of classical first-order logic. It investigates the relationship between a sublogic's logical vocabulary and the decidability of the satisfiability problem for that sublogic. The author adds seven logical entities to the logical entities \(\wedge,\neg,\exists\). These, along with identity, generate a lattice of logics bounded below by fluted logic and above by first-order logic with identity. From the author's introduction: ``This paper demonstrates that in this lattice, the limits of decision are located precisely between the ideal generated by fluted logic with identity, binary converse and functions, and the filter generated by fluted logic with relational composition''.
0 references