摘要:

AbstractWe study the degrees of unsolvability of sets which are cohesive (or have weaker recursion‐theoretic “smallness” properties). We answer a question raised by the first author in 1972 by showing that there is a cohesive setAwhose degree a satisfies a' = 0″ and hence is not high. We characterize the jumps of the degrees of r‐cohesive sets, and we show that the degrees of r‐cohesive sets coincide with those of the cohesive sets. We obtain analogous results for strongly hyperimmune and strongly hyperhyperimmune sets in place of r‐cohesive and cohesive sets, respectively. We show that every strongly hyperimmune set whose degree contains either a Boolean combination of ∑2 sets or a 1‐generic set is of high degree. We also study primitive recursive analogues of these notions and in this case we characterize the corresponding degrees exactly.

ISSN:0942-5616    

DOI:10.1002/malq.19930390153

出版商:WILEY‐VCH Verlag Berlin GmbH    

年代:1993

数据来源: WILEY

摘要:

AbstractSince in Heyting Arithmetic (HA) all atomic formulas are decidable, a Kripke model for HA may be regarded classically as a collection of classical structures for the language of arithmetic, partially ordered by the submodel relation. The obvious question is then: are these classical structures models of Peano Arithmetic (PA)? And dually: if a collection of models of PA, partially ordered by the submodel relation, is regarded as a Kripke model, is it a model of HA? Some partial answers to these questions were obtained in [6], [3], [1] and [2]. Here we present some results in the same direction, announced in [7]. In particular, it is proved that the classical structures at the nodes of a Kripke model of HA must be models of IΔ1(PA‐with induction for provably Δ1formulas) and that the relation between these classical structures must be that of a Δ1‐elementary submodel. MSC: 03F30,

ISSN:0942-5616    

DOI:10.1002/malq.19930390154

出版商:WILEY‐VCH Verlag Berlin GmbH    

年代:1993

数据来源: WILEY

摘要:

AbstractIn this paper a proof of the normal form theorem for the closed terms ofGirard's system Fis given by using a computability method à la Tait. It is worth noting that most of the standard consequences of the normal form theorem can be obtained using this version of the theorem as well. From the proof‐theoretical point of view the interest of the proof is that the definition of computable derivation here used does not seem to be well founded. MSC: 03F05, 03B

ISSN:0942-5616    

DOI:10.1002/malq.19930390155

出版商:WILEY‐VCH Verlag Berlin GmbH    

年代:1993

数据来源: WILEY

摘要:

AbstractWe show that it is consistent with ZFC that the additivity number add(R) of the ideal of meager sets of the real line is strictly greater than the tower number t of the reals. MSC: 03E35, 54D20.

ISSN:0942-5616    

DOI:10.1002/malq.19930390156

出版商:WILEY‐VCH Verlag Berlin GmbH    

年代:1993

数据来源: WILEY

摘要:

AbstractIn the present paper we concentrate on fundamental problems concerning ω‐operations over partial enumerated sets. The notion of “HOM‐lifts” seems to be an adequate tool for this kind of investigations. MSC: 03D4

ISSN:0942-5616    

DOI:10.1002/malq.19930390157

出版商:WILEY‐VCH Verlag Berlin GmbH    

年代:1993

数据来源: WILEY

摘要:

AbstractAssuming “Schanuel's Condition” for a certain class of exponential fields, Sturm's technique for polynomials in real closed fields can be extended to more complicated exponential terms in the corresponding exponential field. Hence for this class of terms the exact number of zeros can be calculated. These results give deeper insights into the model theory of exponential fields. MSC: 03C65, 03C60, 12

ISSN:0942-5616    

DOI:10.1002/malq.19930390158

出版商:WILEY‐VCH Verlag Berlin GmbH    

年代:1993

数据来源: WILEY

摘要:

AbstractThis is a supplement to the paper “Finitary Algebraic Logic” [1]. It includes corrections for several errors and some additional results. MSC: 03G15, 03

ISSN:0942-5616    

DOI:10.1002/malq.19930390159

出版商:WILEY‐VCH Verlag Berlin GmbH    

年代:1993

数据来源: WILEY

ISSN:0942-5616    

DOI:10.1002/malq.19930390160

出版商:WILEY‐VCH Verlag Berlin GmbH    

年代:1993

数据来源: WILEY

ISSN:0942-5616    

DOI:10.1002/malq.19930390102

出版商:WILEY‐VCH Verlag Berlin GmbH    

年代:1993

数据来源: WILEY