Search

The foundation scheme in set theory asserts that every nonempty class has an $$\in $$ -minimal element. In this paper, we investigate the logical strength of the foundation principle in basic set theory and $$\alpha $$ -recursion theory. We take KP set theory without foundation (called KP $$^-$$ ) as the base theory. We show that KP $$^-$$ + $$\Pi _1$$ -Foundation + $$V=L$$ is enough to carry out finite injury arguments in $$\alpha $$ -recursion theory, proving both the Friedberg-Muchnik theorem and the Sacks splitting theorem in this theory. In addition, we compare the strengths of some fragments of KP. [ABSTRACT FROM AUTHOR]

This paper gives the additivity and reduction formulas for mixed multiplicities of multi-graded modules M and mixed multiplicities of arbitrary ideals, and establishes the recursion formulas for the sum of all the mixed multiplicities of M. As an application of these formulas we get the recursion formulas for the multiplicity of multi-graded Rees modules. [ABSTRACT FROM AUTHOR]

This paper presents a sound and complete category-theoretic notion of models for Linear Abadi & Plotkin Logic [Birkedal et al., 2006], a logic suitable for reasoning about parametricity in combination with recursion. A subclass of these called parametric LAPL structures can be seen as an axiomatization of domain theoretic models of parametric polymorphism, and we show how to solve general (nested) recursive domain equations in these. Parametric LAPL structures constitute a general notion of model of parametricity in a setting with recursion. In future papers we will demonstrate this by showing how many different models of parametricity and recursion give rise to parametric LAPL structures, including Simpson and Rosolini's set theoretic models [Rosolini and Simpson, 2004], a syntactic model based on Lily [Pitts, 2000, Bierman et al., 2000] and a model based on admissible pers over a reflexive domain [Birkedal et al., 2007]. [ABSTRACT FROM AUTHOR]

This paper provides an axiomatic framework to compare the D-core (the set of undominated imputations) and the core of a cooperative game with transferable utility. Theorem 1 states that the D-core is the only solution satisfying projection consistency, reasonableness (from above), (*)-antimonotonicity, and modularity. Theorem 2 characterizes the core replacing (*)-antimonotonicity by antimonotonicity. Moreover, these axioms also characterize the core on the domain of convex games, totally balanced games, balanced games, and superadditive games. [ABSTRACT FROM AUTHOR]

Sacks [23] asks if the metarecursively enumerable degrees are elementarily equivalent to the r.e. degrees. In unpublished work, Slaman and Shore proved that they are not. This paper provides a simpler proof of that result and characterizes the degree of the theory as $\mathcal{O}^{(\omega)}$ or, equivalently, that of the truth set of $L_{\omega_{1}^{CK}}$.. [ABSTRACT FROM AUTHOR]

This paper is a companion to work of Feferman, Jäger, Glaß, and Strahm on the proof theory of the type two functionals μ and E1 in the context of Feferman-style applicative theories. In contrast to the previous work, we analyze these two functionals in the context of Schlüter's weakened applicative basis PRON which allows for an interpretation in the primitive recursive indices. The proof-theoretic strength of PRON augmented by μ and E1 is measured in terms of the two subsystems of second order arithmetic, Π10-CA and Π11-CA, respectively. (© 2006 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim) [ABSTRACT FROM AUTHOR]

We develop the concepts of recursively nowhere dense sets and sets that are recursively of first category and study closed sets of points in light of Baire's Category Theorem. Our theorems are primarily concerned with exdomains (i. e. complements of domains) of recursive quantum functions and hence with avoidable points (i. e. points that can be forced into exdomains of recursive quantum functions). An avoidance function is a recursive function which can be used to expel avoidable points from domains of recursive quantum functions. We define an avoidable set of points to be an arbitrary subset of the avoidable points of a single avoidance function, and we study an effective union of such sets which we call a piecemeal avoidable set. We note that each of ‘the set of recursive points’ and ‘the set of avoidable points’ is of first category but not recursively of first category. We show an exdomain exists which is recursively nowhere dense, as well as one that is nowhere dense but not recursively nowhere dense. After establishing that every exdomain is recursively of first category, we prove that given any fixed exdomain, there is another exdomain, which while dense in the underlying space, is disjoint from the fixed exdomain. Finally, we show how to build a recursive sequence of recursive quantum functions that have mutually disjoint, dense exdomains. (© 2004 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim) [ABSTRACT FROM AUTHOR]

We investigate connections between the syntactic and semantic distance of programs on an abstract, recursion theoretic level. For a certain rather restrictive notion of interdependency of the two kinds of distances, there remain only few and “unnatural” numberings allowing such close relationship. Weakening the requirements leads to the discovery of universal metrics such that for an arbitrary recursively enumerable family of functions a numbering compatible with such a metric can uniformly be constructed. We conclude our considerations with some implications on learning theory. [ABSTRACT FROM AUTHOR]

The article focuses on a class of recursively enumerable (r.e.) sets, considering r.e. sets as an amount of information content. It demonstrates that an integer n can be considered both an index of a r.e. set of codes of information and a set of indices of such sets of information. It studies the properties of a class of sets by defining it as a natural closure of recursively enumerable sets.

The article presents a research study which defines the notion called k-immunity which can be found between immunity and hyperimmunity in strength. It examines the findings that ϕ' does not k-tt reduce to a k-immune set which justified the concepts of k-immunity. It also applies the result to MIN, the set of minimal programs, to show that ϕ' cannot btt-reduce to MIN.

The article examines the cohesive degrees of unsolvability of sets. It has proven that every strongly hyperimmune set whose degree contains either a Boolean combination or a generic set is of high degree. Moreover, the corresponding degrees are also characterized in relation to the primitive recursive analogues of the notion.

The article presents a solution to a problem on Grzegorczyk hierarchy or classes. It introduces intermediate classes using bounded recursion schema. It presents basic notions and facts of the definition of Grzegorczyk classes. It also illustrates the replacement of bounded recursion by the short recursion (SR&#x006En;) schema.

The article presents a study which focuses on the development of an arithmetical measure theory based on the approach of J.H. Lutz. The arithmetic measure yielded same notion of measure 0 set as considered before the Martin-Löf randomness. The location of the class of r.e. sets through common recursion-theoritic reducibilities is highlighted,

The article explores some lattice constructions in high recursively enumerable (R. E.) degrees. The constructions are carried any given high R. E. degree without maximal supersets. Every degree has a dense simple, strongly hypersimple set A which is contained neither in a hyperhypersimple nor in an r-maximal set. Refinements of known constructions are made.