Subrecursive functions on partial sequences

The paper studies a domain theoretical notion of primitive recursion over partial sequences in the context of Scott domains. Based on a non-monotone coding of partial sequences, this notion supports a rich concept of parallelism in the sense of Plotkin. The complexity of these functions is analysed by a hierarchy of classes similar to the Grzegorczyk classes. The functions considered are characterised by a function algebra generated by continuity preserving operations starting from computable initial functions. Its layers are related to those above by showing , thus generalising results of Schwichtenberg/Müller and Niggl. Received: 18 November 1996     

Subrecursive degrees and fragments of Peano Arithmetic

Let T ₀?T ₁ denote that each computable function, which is provable total in the first order theory T ₀, is also provable total in the first order theory T ₁. Te relation ? induces a degree structure on the sound finite Π₂ extensions of EA (Elementary Arithmetic). This paper is devoted to the study of this structure. However we do not study the structure directly. Rather we define an isomorphic subrecursive degree structure <≤,?>, and then we study <≤,?> by ubrecursive and computability-theoretic means. Furthermore, we introduce and investigate some operators on the degrees of <≤,?>. These operators corresponds to inferencerules in formal arithmetic. One operator corresponds to the Σ₁ collection rule. Another operator corresponds to the Σ₁ induction rule.     

A restricted computation model on Scott domains and its partial primitive recursive functionals

The paper builds on both a simply typed term system and a computation model on Scott domains via so-called parallel typed while programs (PTWP). The former provides a notion of partial primitive recursive functional on Scott domains supporting a suitable concept of parallelism. Computability on Scott domains seems to entail that Kleene's schema of higher type simultaneous course-of-values recursion (scvr) is not reducible to partial primitive recursion. So extensions and PTWP are studied that are closed under scvr. The twist are certain type 1 G?del recursors for simultaneous partial primitive recursion. Formally, denotes a function , however, is modelled such that is finite, or in other words, a partial sequence. As for PTWP, the concept of type writable variables is introduced, providing the possibility of creating and manipulating partial sequences. It is shown that the PTWP-computable functionals coincide with those definable in plus a constant for sequential minimisation. In particular, the functionals definable in denoted can be characterised by a subclass of PTWP-computable functionals denoted . Moreover, hierarchies of strictly increasing classes in the style of Heinermann and complexity classes are introduced such that . These results extend those for and PTWP [Nig94]. Finally, scvr is employed to define for each type the enumeration functional of all finite elements of . Received January 30, 1996     

Isomorphisms,definable relations,and Scott families for integral domains and commutative semigroups

In the present article, we prove the following four assertions: (1) For every computable successor ordinal α, there exists a Δ _α ⁰ -categorical integral domain (commutative semigroup) which is not relatively Δ _α ⁰ -categorical (i.e., no formally Σ _α ⁰ Scott family exists for such a structure). (2) For every computable successor ordinal α, there exists an intrinsically Σ _α ⁰ -relation on the universe of a computable integral domain (commutative semigroup) which is not a relatively intrinsically Σ _α ⁰ -relation. (3) For every computable successor ordinal α and finite n, there exists an integral domain (commutative semigroup) whose Δ _α ⁰ -dimension is equal to n. (4) For every computable successor ordinal α, there exists an integral domain (commutative semigroup) with presentations only in the degrees of sets X such that Δ _α ⁰ (X) is not Δ _α ⁰ . In particular, for every finite n, there exists an integral domain (commutative semigroup) with presentations only in the degrees that are not n-low.     

Pulsating hierarchies

The research was supported by the Russian Foundation for Fundamental Research (Grant 93-011-16014).     

偏序集中网和滤子的Scott收敛及其Scott拓扑

本文的目的是在偏序集上直接定义和研究网和滤子的Scott收敛理论,指出其相互之间的协调性,及其它们的导出拓扑与Scott拓扑的一致性.     

Long Borel hierarchies

We show that there is a model of ZF in which the Borel hierarchy on the reals has length ω₂. This implies that ω₁ has countable cofinality, so the axiom of choice fails very badly in our model. A similar argument produces models of ZF in which the Borel hierarchy has exactly λ + 1 levels for any given limit ordinal λ less than ω₂. We also show that assuming a large cardinal hypothesis there are models of ZF in which the Borel hierarchy is arbitrarily long. (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Wilson's theorem for consensus functions on hierarchies

Wilson in 1972 gave a generalization of Arrow's theorem without the Pareto axiom. We prove a version of Wilson's theorem for consensus functions on hierarchies.     

模糊dcpo上的L-模糊Scott余拓

研究模糊dcpo上的L-模糊Scott余拓扑(即关于L-模糊集成为Scott闭集的程度映射)和L-Scott余拓扑(即全体L-Scott闭集构成的余拓扑),考察它们的特殊化L-序及其与模糊Scott连续映射的关系.     

From hierarchies to well-foundedness

We highlight that the connection of well-foundedness and recursive definitions is more than just convenience. While the consequences of making well-foundedness a sufficient condition for the existence of hierarchies (of various complexity) have been extensively studied, we point out that (if parameters are allowed) well-foundedness is a necessary condition for the existence of hierarchies e.g. that even in an intuitionistic setting \({(\Pi_1^0-\mathsf{CA}_0)_\alpha \vdash \mathsf{wf}(\alpha)\, {\rm where}\, (\Pi_1^0-\mathsf{CA}_0)_\alpha}\) stands for the iteration of \({\Pi^0_1}\) comprehension (with parameters) along some ordinal \({\alpha}\) and \({\mathsf{wf}(\alpha)}\) stands for the well-foundedness of \({\alpha}\) .     

Nested hierarchies in planar graphs

We construct a partial order relation which acts on the set of 3-cliques of a maximal planar graph G and defines a unique hierarchy. We demonstrate that G is the union of a set of special subgraphs, named ‘bubbles’, that are themselves maximal planar graphs. The graph G is retrieved by connecting these bubbles in a tree structure where neighboring bubbles are joined together by a 3-clique. Bubbles naturally provide the subdivision of G into communities and the tree structure defines the hierarchical relations between these communities.     

Commutator identities and integrable hierarchies

Theoretical and Mathematical Physics - The approach based on commutator identities for elements of associative algebras was previously effectively used to investigate $$(2{+}1)$$ -dimensional...     

Rank inclusion in criteria hierarchies

This paper presents a method called Rank Inclusion in Criteria Hierarchies (RICH) for the analysis of incomplete preference information in hierarchical weighting models. In RICH, the decision maker is allowed to specify subsets of attributes which contain the most important attribute or, more generally, to associate a set of rankings with a given set of attributes. Such preference statements lead to possibly non-convex sets of feasible attribute weights, allowing decision recommendations to be obtained through the computation of dominance relations and decision rules. An illustrative example on the selection of a subcontractor is presented, and the computational properties of RICH are considered.     

Set partitions and integrable hierarchies

We demonstrate that statistics for several types of set partitions are described by generating functions arising in the theory of integrable equations.     

Bounded Scott Set Saturation

We examine the relationship between two different notions of a structure being Scott set saturated and identify sufficient conditions which guarantee that a structure is uniquely Scott set saturated. We also consider theories representing Scott sets; in particular, we identify a sufficient condition on a theory T so that for any given countable Scott set there exists a completion of T that is saturated with respect to the given Scott set. These results extend Scott's characterization of countable Scott sets via models and completions of Peano arithmetic.     

Generalized nonisospectral super integrable hierarchies

For the Lie superalgebra B(0,1), we choose a set of basis matrices. Then we consider a linear combination of the basis matrices, which is exactly the spectral matrix of the spatial part for the super Ablowitz‐Kaup‐Newell‐Segur (AKNS) hierarchy. The compatible condition of the spatial and temporal spectral problems leads to the well‐known zero curvature equation. Here, when the spectral parameter is independent (dependent) of temporal parameter, we obtain isospectral (nonisospectral) super AKNS hierarchy. Furthermore, we derive the generalized nonisospectral super AKNS hierarchy (GNI‐SAKNS). As another example, similar method is successfully applied to the super Dirac hierarchy, and we obtain the generalized nonisospectral super Dirac hierarchy (GNI‐SD).