scientific article; zbMATH DE number 4114609

From MaRDI portal
Publication:4729773





[For the entire collection see Zbl 0666.00011.] Let F be the set of propositional calculus formulae constructed by means of \(\wedge\), \(\vee\), \(\neg\) and the variables \(x_ i\). Every consistent and tautologically closed subset \(T\varsubsetneq F\) is called a theory. A set \(M\subseteq N\) is said to be a model for a formula \(f\in F\) if \(f(C^ M(1),C^ M(2),...,C^ M(n))=1\), where \(C^ M\) is the characteristic function of M. Let \(\nu\) be a Gödel numbering of F and \(\nu^{-1}(f)\) be the number of f in this numbering. By \(T^*_ R\) denote the set \(\{\nu^{- 1}(f)|\) \(f\in F\) \& \(R\vDash f\}\) and let \(S'\) (S) be the set of all (finite) binary sequences (so \(C^ M\in S')\). Supposing that S is ordered lexicographically, for \(n\in {\mathbb{N}}\) let \(\mu (n)=\sigma\) if \(\sigma\) is the n-th element of this ordering. The author investigates some relationships between \(T^*_ M\), M and several related sets with respect to different reducibilities. Among other results he shows that m-degrees of hereditary sets (and only these sets) are m-degrees of theories. There exists a recursive theory which has only one nonrecursive complete extension. The author suggests to describe a family of sets which can be models for recursive theories having unique nonrecursive complete extensions.











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4729773)