On Undecidability of Non-monotonic Logic

Abstract

The degree of undecidability of nonmonotonic logic is investigated. A proof is provided that arithmetical but not recursively enumerable sets of sentences definable by nonmonotonic default logic are elements of Dn+1 but not Sn nor Pn for some n>= 1 in Kleene-Mostowski hierarchy of arithmetical sets.