Premium
A new technique for proving realisability and consistency theorems using finite paraconsistent models of cut‐free logic
Author(s) -
Daynes Arief
Publication year - 2006
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/malq.200610013
Subject(s) - paraconsistent logic , consistency (knowledge bases) , mathematics , semantics (computer science) , calculus (dental) , simple (philosophy) , discrete mathematics , algebra over a field , pure mathematics , computer science , philosophy , higher order logic , epistemology , artificial intelligence , programming language , medicine , dentistry , description logic
A new technique for proving realisability results is presented, and is illustrated in detail for the simple case of arithmetic minus induction. CL is a Gentzen formulation of classical logic. CPQ is CL minus the Cut Rule. The basic proof theory and model theory of CPQ and CL is developed. For the semantics presented CPQ is a paraconsistent logic, i.e. there are non‐trivial CPQ models in which some sentences are both true and false. Two systems of arithmetic minus induction are introduced, CL‐A and CPQ‐A based on CL and CPQ, respectively. The realisability theorem for CPQ‐A is proved: It is shown constructively that to each theorem A of CPQ‐A there is a formula A *, a so‐called “realised disjunctive form of A ”, such that variables bound by essentially existential quantifiers in A * can be written as recursive functions of free variables and variables bound by essentially universal quantifiers. Realisability is then applied to prove the consistency of CL‐A, making use of certain finite non‐trivial inconsistent models of CPQ‐A. (© 2006 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)