Localization of a theorem of Ambos-Spies and the strong anti-splitting property

LetA be an r.e. nonrecursive set. We sayA has thestrong antisplitting property if there exists an r.e. setB with 0< _T B< _T A such that ifA ₁ A ₂=A andA ₁A ₂=0 thenA _{1 T} B impliesA _{1 T} 0 andB _T A ₁ impliesA _{1 T} A. It is shown that below any high r.e. degree there exists an r.e. set with the strong antisplitting property. The main ingredient of the proof is a localization of Ambos-Spies' result that the cup or cap theorem fails forW-degrees.Research partially supported by N.U.S. Grant RP 85/83 (Singapore).     

The endomorphism spectrum of an ordered set

Theendomorphism spectrum of an ordered setP, spec(P)={|f(P)|:f End(P)} andspectrum number, sp(P)=max(spec(P)\{|P|}) are introduced. It is shown that |P|>(1/2)n(n – 1) ^{n – 1} implies spec(P) = {1, 2, ...,n} and that if a projective plane of ordern exists, then there is an ordered setP of size 2n ²+2n+2 with spec(P)={1, 2, ..., 2n+2, 2n+4}. Lettingh(n)=max{|P|: sp(P)n}, it follows thatc ₁ n ²h(n)c ₂ n ⁿ⁺¹ for somec ₁ andc ₂. The lower bound disproves the conjecture thath(n)2n. It is shown that if |P| – 1 spec(P) thenP has a retract of size |P| – 1 but that for all there is a bipartite ordered set with spec(P) = {|P| – 2, |P| – 4, ...} which has no proper retract of size|P| – . The case of reflexive graphs is also treated.Partially supported by a grant from the NSERC.Partially supported by a grant from the NSERC.     

A note on theΠ 2 0 -induction rule

It is well-known (due to C. Parsons) that the extension of primitive recursive arithmeticPRA by first-order predicate logic and the rule of ₂ ⁰ -induction ₂ ⁰ -IR is ₂ ⁰ -conservative overPRA. We show that this is no longer true in the presence of function quantifiers and quantifier-free choice for numbersAC ^0,0-qf. More precisely we show that :=PRA ² + ₂ ⁰ -IR+AC ^0,0-qf proves the totality of the Ackermann function, wherePRA ² is the extension ofPRA by number and function quantifiers and ₂ ⁰ -IR may contain function parameters.This is true even forPRA ² + ₁ ⁰ -IR+ ₂ ⁰ -IR ^–+AC ^0,0-qf, where ₂ ⁰ -IR ^– is the restriction of ₂ ⁰ -IR without function parameters.I am grateful to an anonymous referee whose suggestions led to an improved discussion of our results     

Density results for uniform families

A familyF of subsets is calledk-dense if there exists ak-element setA such that all 2 ^k of its subsets can be obtained in the formAF for someFF. Best possible bounds are obtained for the maximum number of sets in notk-densek-partite families. This is a consequence of a new rank formula for inclusion matrices.     

Cutting planes,connectivity, and threshold logic

Originating from work in operations research the cutting plane refutation systemCP is an extension of resolution, where unsatisfiable propositional logic formulas in conjunctive normal form are recognized by showing the non-existence of boolean solutions to associated families of linear inequalities. Polynomial sizeCP proofs are given for the undirecteds-t connectivity principle. The subsystemsCP _q ofCP, forq2, are shown to be polynomially equivalent toCP, thus answering problem 19 from the list of open problems of [8]. We present a normal form theorem forCP ₂-proofs and thereby for arbitraryCP-proofs. As a corollary, we show that the coefficients and constant terms in arbitrary cutting plane proofs may be exponentially bounded by the number of steps in the proof, at the cost of an at most polynomial increase in the number of steps in the proof. The extensionCPLE ⁺, introduced in [9] and there shown top-simulate Frege systems, is proved to be polynomially equivalent to Frege systems. Lastly, since linear inequalities are related to threshold gates, we introduce a new threshold logic and prove a completeness theorem.Supported in part by NSF grant DMS-9205181 and by US-Czech Science and Technology Grant 93-205Partially supported by NSF grant CCR-9102896 and by US-Czech Science and Technology Grant 93-205     

On the interpolation property of some intuitionistic modal logics

LetL be one of the intuitionistic modal logics considered in [7] (or one of its extensions) and letM _L be the algebraic semantics ofL. In this paper we will extend toL the equivalence, proved in the classical case (see [6]), among he weak Craig interpolation theorem, the Robinson theorem and the amalgamation property of varietyM _L. We will also prove the equivalence between the Craig interpolation theorem and the super-amalgamation property of varietyM _L. Then we obtain the Craig interpolation theorem and Robinson theorem for two intuitionistic modal logics, one ofS ₄-type and the other one ofS ₅-type, showing the super-amalgamation property of the corresponding algebraic semantics.     

Sensitivity analysis of the greatest eigenvalue of a symmetric matrix via the ɛ-subdifferential of the associated convex quadratic form

LetA(·) be ann × n symmetric affine matrix-valued function of a parameteruR ^m , and let (u) be the greatest eigenvalue ofA(u). Recently, there has been interest in calculating (u), the subdifferential of atu, which is useful for both the construction of efficient algorithms for the minimization of (u) and the sensitivity analysis of (u), namely, the perturbation theory of (u). In this paper, more generally, we investigate the Legendre-Fenchel conjugate function of (·) and the -subdifferential (u) of atu. Then, we discuss relations between the set (u) and some perturbation bounds for (u).The author is deeply indebted to Professor J. B. Hiriart-Urruty who suggested this study and provided helpful advice and constant encouragement. The author also thanks the referees and the editors for their substantial help in the improvement of this paper.     

An application of Shoenfield's absoluteness theorem to the theory of uniform distribution

IfC is a Polish probability space, a Borel set whose sectionsW _x ( have measure one and are decreasing , then we show that the set _x W _x has measure one. We give two proofs of this theorem—one in the language of set theory, the other in the language of probability theory, and we apply the theorem to a question on completely uniformly distributed sequences.Supported by DFG grant Ko 490/7-1.     

γ-sets and other singular sets of real numbers

A family of $\text{J}$ of open subsets of the real line is called an ω-cover of a set X iff every finite subset of X is contained in an element of $\text{J}$. A set of reals X is a γ-set iff for every ω-cover $\text{J}$ of X there exists $\text{〈D}{}_{\mathrm{n}}\text{: n < ω〉?}\text{J}{}^{\mathrm{\omega }}$ such that

In this paper we show that assuming Martin's axiom there is a γ-set X of cardinality the continuum.     

Amorphe Potenzen kompakter Räume

A set is amorphous, if it is not a union of two disjoint infinite subsets. The following variants of the Tychonoff product theorem are investigated in the hierarchy of weak choice principles. TA1: An amorphous power of a compactT ₂ space is compact. TA2: An amorphous power of a compactT ₂ space which as a set is wellorderable is compact. In ZF⁰TA1 is equivalent to the assertion, that amorphous sets are finite. RT is Ramsey's theorem, that every finite colouring of the set ofn-element subsets of an infinite set has an infinite homogeneous subset and PW is Rubin's axiom, that the power set of an ordinal is wellorderable. In ZF⁰RT+PW implies TA2. Since RT+PW is compatible with the existence of infinite amorphous sets, TA2 does not imply TA1 in ZF⁰. But TA2 cannot be proved in ZF⁰ alone. As an application, we prove a theorem of Stone, using a weak wellordering axiomD ₃ (a set is wellorderable, if each of its infinite subsets is structured) together with RT.

Diese Arbeit ist Teil der Habilitationsschrift des Verfassers im Fachgebiet Mathematische Analysis an der Technischen Universität Wien.