摘要:

AbstractEnumeration reducibility is a notion of relative computability between sets of natural numbers where only positive information about the sets is used or produced. Extending e‐reducibility to partial functions characterises relative computability between partial functions. We define a polynomial time enumeration reducibility that retains the character of enumeration reducibility and show that it is equivalent to conjunctive non‐deterministic polynomial time reducibility. We define the polynomial timee‐degrees as the equivalence classes under this reducibility and investigate their structure on the recursive sets, showing in particular that the pe‐degrees of the computable sets are dense and do not form a lattice, but that minimal pairs exist. We define a jump operator and use it to produce a characterisation of the polynomial hi

ISSN:0942-5616    

DOI:10.1002/malq.19970430302

出版商:WILEY‐VCH Verlag Berlin GmbH    

年代:1997

数据来源: WILEY

摘要:

AbstractWe prove that if an incomplete computably enumerable set has the the universal splitting property then it is low2. This solves a question from Ambos‐Spies and Fejer [1] and Downey and Stob [7]. Some technical improvements are discusse

ISSN:0942-5616    

DOI:10.1002/malq.19970430303

出版商:WILEY‐VCH Verlag Berlin GmbH    

年代:1997

数据来源: WILEY

摘要:

AbstractSheaf semantics is developed within a constructive and predicative framework, Martin‐Löf's type theory. We prove strong completeness of many sorted, first order intuitionistic logic with respect to this semantics, by using sites of provably functional relatio

ISSN:0942-5616    

DOI:10.1002/malq.19970430304

出版商:WILEY‐VCH Verlag Berlin GmbH    

年代:1997

数据来源: WILEY

摘要:

AbstractLet ℸ be the set of Gödel numbers Gn(f) of function symbolsfsuch thatPRA⊢ and let γ be the function such that\documentclass{article}\pagestyle{empty}\begin{document}$$\begin{array}{*{20}c} {\gamma (n) = \left\{ {\mathop G\limits_0 n({\rm PRA} - {\rm proof}\,{\rm of}\,\forall x(f(x) = 0))} \right.} & {\mathop {{\rm if}\,n = }\limits_{otherwise.} Gn(f) \in \Gamma,}\\\end{array} $$\end{document}We prove: (1) The r. e. set ℸ is m‐complete; (2) the function γ is not primitive recursive in any class of functions {f1,f2, ⃛} so long as eachfihas a recursive upper bound. This implies that γ is not primitive recursive in ℸ although it is

ISSN:0942-5616    

DOI:10.1002/malq.19970430305

出版商:WILEY‐VCH Verlag Berlin GmbH    

年代:1997

数据来源: WILEY

摘要:

AbstractIt is known that a theory in S5‐epistemic logic with several agents may have numerous models. This is because each such model specifies also what an agent knows about infinite intersections of events, while the expressive power of the logic is limited to finite conjunctions of formulas. We show that this asymmetry between syntax and semantics persists also when infinite conjunctions (up to some given cardinality) are permitted in the language. We develop a strengthened S5‐axiomatic system for such infinitary logics, and prove a strong completeness theorem for them. Then we show that in every such logic there is always a theory with more than one mo

ISSN:0942-5616    

DOI:10.1002/malq.19970430306

出版商:WILEY‐VCH Verlag Berlin GmbH    

年代:1997

数据来源: WILEY

摘要:

AbstractWe show that various fragments of the intuitionistic/constructive theory of the reals are decidable.

ISSN:0942-5616    

DOI:10.1002/malq.19970430307

出版商:WILEY‐VCH Verlag Berlin GmbH    

年代:1997

数据来源: WILEY

摘要:

AbstractThe remainder equations were introduced by S. O. Hansson. In this paper, we will give an exhaustive characterization of the set of solutions for remainder equations. Moreover, solutions to some unsolved problems proposed by Hansson are reported.

ISSN:0942-5616    

DOI:10.1002/malq.19970430308

出版商:WILEY‐VCH Verlag Berlin GmbH    

年代:1997

数据来源: WILEY

摘要:

AbstractAn interesting positive theory is the GPK theory. The models of this theory include all hyperuniverses (see [5] for a definition of these ones). Here we add a form of the axiom of infinity and a new scheme to obtain GPK∞+. We show that in these conditions, we can interprete the Kelley‐Morse theory (KM) in GPK∞+(Theorem 3.7). This needs a preliminary property which give an interpretation of the Zermelo‐Fraenkel set theory (ZF) in GPK∞+. We also see what happens in the original GPK theory. Before doing this, we first need to study the basic properties of the theory. This is done in the first two

ISSN:0942-5616    

DOI:10.1002/malq.19970430309

出版商:WILEY‐VCH Verlag Berlin GmbH    

年代:1997

数据来源: WILEY

摘要:

AbstractIn this note, we study the complementedness and the distributivity of upper semilattices of Kleene degrees assumingV = L. Kdenotes the upper semilattice of all Kleene degrees. We prove that ifV = L, then some sub upper semilattices ofKare non‐complemented and some are non‐distribut

ISSN:0942-5616    

DOI:10.1002/malq.19970430310

出版商:WILEY‐VCH Verlag Berlin GmbH    

年代:1997

数据来源: WILEY

摘要:

AbstractWe prove that a Spector‐like ultrapower extension

ISSN:0942-5616    

DOI:10.1002/malq.19970430311

出版商:WILEY‐VCH Verlag Berlin GmbH    

年代:1997

数据来源: WILEY