Consistency and Classical Satisfiability

Jui-Lin Lee

Center for General Education and Department of CSIE, National Formosa University – Taiwan

 

 

 

 

In classical logic the extended completeness theorem (T ⊨φ implies that T ⊢φ for any set of sentences T and any sentence φ) is frequently proved by the following two steps:

 (CME) Every consistent set has a (classical) model; and

(RAA) If T cannot derive φ, then T∪ {¬φ} is consistent (for any set T and any sentence φ).

 Sometimes the former statement, as a major step of this approach, is called the extended completeness theorem (or the strong completeness theorem). This is not always a correct name of it because there are some non-classical logics satisfying CME, the classical model existence property (which means that consistency implies classical satisfiability).

 

In this course we investigate this meta-logical property CME. Since there are many different consistencies and in non-classical logics they are not always equivalent, we will study consistency first. (Note that with different consistencies the meaning of CME could be different.) Then we present ways to construct non-classical logics/proof systems (by selecting axioms or rules) which satisfy CME, and discuss how one can construct a weaker system still satisfying CME. These (propositional or predicate) logics include some (weak extensions of) paraconsistent logics, subintuitionistic logics, or substructural logics. Applications of CME include Glivenko-style theorem and pure implicational logic. Furthermore, we will also analyze the necessary-and-sufficient condition of CME (which is related to Left Resolutation Gentzen system in [3]) and discuss other model existence property.

 

 

 

References:

[1]  J.-Y. Béziau, “Sequents and bivaluations”, Logique et Analyse, Vol. 44, pp.373-394, 2001.

[2]  Jui-Lin Lee, “Classical model existence theorem in propositional logics”, in Jean-Yves Béziau and Alexandre Costa-Leite (eds.), Perspectives on Universal Logic, pages 179-197, Polimetrica, Monza, Italy, 2007.

[3]  Jui-Lin Lee, “Classical Model Existence and Left Resolution”, Logic and Logical Philosophy, Vol. 16 No 4, pages 333-352, 2007.

[4]  Jui-Lin Lee, “The Classical Model Existence Theorem in Subclassical Predicate Logics I”, in D. Makinson, J. Malinowski, H. Wansing (eds.), Towards Mathematical Philosophy, Trends in Logic 28, pages 187-199, Springer, 2008.

[5]  Richard Zach, “Proof Theory of Finite-Valued Logics”, Diploma Thesis, Technische Universität Wien, Vienna, 1993.