摘要:

AbstractWe define and study a new notion calledk‐immunity that lies between immunity and hyperimmunity in strength. Our interest ink‐immunity is justified by the result that θ does notk‐tt reduce to ak‐immune set, which improves a previous result by Kobzev [7]. We apply the result to show that Φ′ does not btt‐reduce to MIN, the set of minimal programs. Other applications include the set of Kolmogorov random strings, and retraceable and regressive sets. We also give a new characterization of effectively simple sets and show that simple sets are not

ISSN:0942-5616    

DOI:10.1002/malq.19990450102

出版商:WILEY‐VCH Verlag Berlin GmbH    

年代:1999

数据来源: WILEY

摘要:

AbstractWe investigate computability of a self‐similar set on a Euclidean space. A nonempty compact subset of a Euclidean space is called a self‐similar set if it equals to the union of the images of itself by some set of contractions. The main result in this paper is that if all of the contractions are computable, then the self‐similar set is a recursive compact set. A further result on the case that the self‐similar set forms a curve is also di

ISSN:0942-5616    

DOI:10.1002/malq.19990450103

出版商:WILEY‐VCH Verlag Berlin GmbH    

年代:1999

数据来源: WILEY

摘要:

AbstractWe consider the relationship between the computational complexity classes NP and EL (deterministic exponential linear time). Taking into account the inclusion or incomparability of these classes, the existence or nonexistence of immune sets in their differences, and the existence or nonexistence of sparse sets in the differences, there are exactly 24 different cases for their relationship. We show that 16 cases are impossible in the real nonrelativized world as well as in any relativized world. Each of the remaining 8 cases is realizable in appropriate relativized worlds. Further we examine which of the 8 cases is most probably for a random oracle.

ISSN:0942-5616    

DOI:10.1002/malq.19990450104

出版商:WILEY‐VCH Verlag Berlin GmbH    

年代:1999

数据来源: WILEY

摘要:

AbstractWe present a labelled version of Lambek Calculus without unit, and we use it to prove a completeness theorem for Lambek Calculus with respect to some relational semantics.

ISSN:0942-5616    

DOI:10.1002/malq.19990450105

出版商:WILEY‐VCH Verlag Berlin GmbH    

年代:1999

数据来源: WILEY

摘要:

AbstractWe construct computably enumerable degreesa

ISSN:0942-5616    

DOI:10.1002/malq.19990450106

出版商:WILEY‐VCH Verlag Berlin GmbH    

年代:1999

数据来源: WILEY

摘要:

AbstractA formula ϕ(x) in the one non‐logical symbol ϵ with one free variablexis Russell if the sentence Vχ(χ ϵ τ ⟷ Φ (χ)) is logically valid. This note describes a pattern common to the classical examples of Russell formulas, adds a couple of new ones, and constructs many formulas that are n

ISSN:0942-5616    

DOI:10.1002/malq.19990450107

出版商:WILEY‐VCH Verlag Berlin GmbH    

年代:1999

数据来源: WILEY

摘要:

AbstractWe study the class of ω‐categorical structures withn‐degenerate algebraic closure for somenε ω, which includes ω‐categorical structures with distributive lattice of algebraically closed subsets (see [4]), and in particular those with degenerate (trivial) algebraic closure. We focus on the models of ω‐categorical universal theories, absolutely ubiquitous structures, and ω‐categorical structures generated by an indiscernible set. The assumption of n‐degeneracy implies total categoricity for the first class, stability for the second, and ω‐sta

ISSN:0942-5616    

DOI:10.1002/malq.19990450108

出版商:WILEY‐VCH Verlag Berlin GmbH    

年代:1999

数据来源: WILEY

摘要:

AbstractWe find topological characterizations of the pseudointersection number

ISSN:0942-5616    

DOI:10.1002/malq.19990450109

出版商:WILEY‐VCH Verlag Berlin GmbH    

年代:1999

数据来源: WILEY

摘要:

AbstractIn positive theories, we have an axiom scheme of comprehension for positive formulas. We study here the “generalized positive” theory GPK∞+. Natural models of this theory are hyperuniverses. The author has shown in [2] that GPK∞+interprets the Kelley Morse class theory. Here we prove that GPK∞++ ACWF(ACWFbeing a form of the axiom of choice allowing to choose elements in well‐founded sets) and the Kelley‐Morse class theory with the axiom of global choice and the axiom “On is ramifiable” are mutually interpretable. This shows that GPK∞++ ACWFis a “strong” theory since “On is ramifiable” implies the existence of a proper clas

ISSN:0942-5616    

DOI:10.1002/malq.19990450110

出版商:WILEY‐VCH Verlag Berlin GmbH    

年代:1999

数据来源: WILEY

摘要:

AbstractIn her well‐known book, Rasiowa states without proof that in implicative algebras there is a one‐to‐one correspondence between kernels of epimorphisms and the so‐called special implicative filters, and that in the logic whose algebraic counterpart is the class of implicative algebras the deductive filters coincide with the special implicative filters. We show that neither claim is true, and how to repair the situation by redefining some of the notions involved. We answer other questions concerning special implicative filters, taking the theory of algebraizable logics of Blok and Pigozzi as a framework to approach the question in a systema

ISSN:0942-5616    

DOI:10.1002/malq.19990450111

出版商:WILEY‐VCH Verlag Berlin GmbH    

年代:1999

数据来源: WILEY