摘要:

AbstractA theoryTof a languageLis 1‐model complete (nearly model complete) iff for every formula ρ ofLthere is a formula ϕ (χ) ofLwhich is a ∀∃‐formula (a Boolean combination of universal formulas) such thatT⊨ ∀x[ϕ↔θ]. The main results of the paper give characterizations of nearly model complete theories and of 1‐model complete theories. As a consequence we obtain that a theoryTis nearly model complete iff whenever

ISSN:0942-5616    

DOI:10.1002/malq.19990450302

出版商:WILEY‐VCH Verlag Berlin GmbH    

年代:1999

数据来源: WILEY

摘要:

AbstractWe work in set theory ZF without axiom of choice. Though the Hahn‐Banach theorem cannot be proved in ZF, we prove that every Gateaux‐differentiable uniformly convex Banach spaceEsatisfies the following continuous Hahn‐Banach property: ifpis a continuous sublinear functional onE, ifFis a subspace ofE, and iff:F→ ℝ is a linear functional such thatf≤ p|F then there exists a linear functionalg:E→ ℝ such thatgextendsfandg≤p. We also prove that the continuous Hahn‐Banach property on a topological vector spaceEis equivalent to the classical geometrical forms of the Hahn‐Banach theorem onE. We then prove that the axiom of Dependent choices DC is equivalent to Ekeland's variational principle, and that it implies the continuous Hahn‐Banach property on Gateaux‐differentiable Banach spaces. Finally, we prove that, though separable normed spaces satisfy the continuous Hahn‐Banach property, they do not satisfy the whole Ha

ISSN:0942-5616    

DOI:10.1002/malq.19990450303

出版商:WILEY‐VCH Verlag Berlin GmbH    

年代:1999

数据来源: WILEY

摘要:

AbstractWe show that the existential preservation theorem fails for two‐variable first‐order logic FO2. It is known that for allk≥ 3, FOkdoes not have an existential preservation theorem, so this settles the last open case, answering a question of Andreka, van Benthem, and Németi. In contrast, we prove that the homomorphism preservation theorem holds f

ISSN:0942-5616    

DOI:10.1002/malq.19990450304

出版商:WILEY‐VCH Verlag Berlin GmbH    

年代:1999

数据来源: WILEY

摘要:

AbstractFor a primek, the embeddability of finite lattices are discussed for various kind of the MODkP degrees of recursive sets. In particular, all finite lattices are embeddable into the MODkP Turing degrees, whereas the non distributive latticeM3is embeddable into the MOD2P many‐one degrees butN5is no

ISSN:0942-5616    

DOI:10.1002/malq.19990450305

出版商:WILEY‐VCH Verlag Berlin GmbH    

年代:1999

数据来源: WILEY

摘要:

AbstractIn an attempt to give a unified account of common properties of various resource bounded reducibilities, we introduce conditions on a binary relation ≤rbetween subsets of the natural numbers, where ≤ris meant as a resource bounded reducibility. The conditions are a formalization of basic features shared by most resource bounded reducibilities which can be found in the literature. As our main technical result, we show that these conditions imply a result about exact pairs which has been previously shown by Ambos‐Spies [2] in a setting of polynomial time bounds: given some recursively presentable ≤r‐idealIand some recursive ≤r‐hard setBforIwhich is not contained inI, there is some recursive setC, whereBandCare an exact pair forI, that is,Iis equal to the intersection of the lower ≤r‐cones ofBandC, whereCis not inI. In particular, if the relation ≤ris in addition transitive and there are least sets, then every recursive set which is not in the least degree is half of a minimal pai

ISSN:0942-5616    

DOI:10.1002/malq.19990450306

出版商:WILEY‐VCH Verlag Berlin GmbH    

年代:1999

数据来源: WILEY

摘要:

AbstractWe generalize results of [3] and [1]to hyperprojective sets of reals, viz. to more than finitely many strong cardinals being involved. We show, for example, that if every set of reals in Lω(ℝ) is weakly homogeneously Souslin, then there is an inner model with an inaccessible limit of strong cardina

ISSN:0942-5616    

DOI:10.1002/malq.19990450307

出版商:WILEY‐VCH Verlag Berlin GmbH    

年代:1999

数据来源: WILEY

摘要:

AbstractWe demonstrate that the special model axiom SMA of Ross admits a natural formalization in Kawai's nonstandard set theory KST but is independent of KST. As an application of our methods to classical model theory, we present a short proof of the consistency (with ZFC) of the existence of ak+likek‐saturated model of PA for a given cardinal

ISSN:0942-5616    

DOI:10.1002/malq.19990450308

出版商:WILEY‐VCH Verlag Berlin GmbH    

年代:1999

数据来源: WILEY

摘要:

AbstractIn this paper we address our efforts to extend the well‐known connection in equational logic between equational theories and fully invariant congruences to other–possibly infinitary–logics. In the special case of algebras, this problem has been formerly treated by H. J. Hoehnke [10] and R. W. Quackenbush [14]. Here we show that the connection extends at least up to the universal fragment of logic. Namely, we establish that the concept of (infinitary) universal theory matches the abstract notion of fully invariant system. We also prove that, inside this wide group of theories, the ones which are strict universal Horn correspond to fully invariant closure systems, whereas those which are universal atomic can be characterized as principal fully invariant sy

ISSN:0942-5616    

DOI:10.1002/malq.19990450309

出版商:WILEY‐VCH Verlag Berlin GmbH    

年代:1999

数据来源: WILEY

摘要:

AbstractWe study, within the framework of intuitionistic logic, two well‐known general results of (classical logic) bounded arithmetic. Firstly, Parikh's theorem on the existence of bounding terms for the provably total functions. Secondly, the result which states that adding the scheme of bounded collection to (suitable) bounded theories does not yield new II2consequence

ISSN:0942-5616    

DOI:10.1002/malq.19990450310

出版商:WILEY‐VCH Verlag Berlin GmbH    

年代:1999

数据来源: WILEY

摘要:

AbstractWe study those relational structures S with the property (P) that each partition ofScontains a block isomorphic toS.We show that the Fraïsse limits of parametric classesK.have property (P); over a binary language, every countable structure inKsatisfying (P) along with a condition on 1‐extensions must be isomorphic to this lim

ISSN:0942-5616    

DOI:10.1002/malq.19990450311

出版商:WILEY‐VCH Verlag Berlin GmbH    

年代:1999

数据来源: WILEY