Binary clustering

In many clustering systems (hierarchies, pyramids and more generally weak hierarchies) clusters are generated by two elements only.This paper is devoted to such clustering systems (called binary clustering systems). It provides some basic properties, links with (closed) weak hierarchies and some qualitative versions of bijection theorems that occur in Numerical Taxonomy. Moreover, a way to associate a binary clustering system to every clustering system is discussed.Finally, introducing the notion of weak ultrametrics, a bijection between indexed weak hierarchies and weak ultrametrics is obtained (the standard theorem involves closed weak hierarchies and quasi-ultrametrics).     

Inhabitation of polymorphic and existential types

This paper shows that the inhabitation problem in the lambda calculus with negation, product, polymorphic, and existential types is decidable, where the inhabitation problem asks whether there exists some term that belongs to a given type. In order to do that, this paper proves the decidability of the provability in the logical system defined from the second-order natural deduction by removing implication and disjunction. This is proved by showing the quantifier elimination theorem and reducing the problem to the provability in propositional logic. The magic formulas are used for quantifier elimination such that they replace quantifiers. As a byproduct, this paper also shows the second-order witness theorem which states that a quantifier followed by negation can be replaced by a witness obtained only from the formula. As a corollary of the main results, this paper also shows Glivenko’s theorem, Double Negation Shift, and conservativity for antecedent-empty sequents between the logical system and its classical version.     

Towards a new theory of confirmation

Any sequence of events can be “explained” by any of an infinite number of hypotheses. Popper describes the “logic of discovery” as a process of choosing from a hierarchy of hypotheses the first hypothesis which is not at variance with the observed facts. Blum and Blum formalized these hierarchies of hypotheses as hierarchies of infinite binary sequences and imposed on them certain decidability conditions. In this paper we also consider hierarchies of infinite binary sequences but we impose only the most elementary Bayesian considerations. We use the structure of such hierarchies to define “confirmation”. We then suggest a definition of probability based on the amount of confirmation a particular hypothesis (i.e. pattern) has received. We show that hypothesis confirmation alone is a sound basis for determining probabilities and in particular that Carnap’s logical and empirical criteria for determining probabilities are consequences of the confirmation criterion in appropriate limiting cases.     

Approximate decidability in euclidean spaces

We study concepts of decidability (recursivity) for subsets of Euclidean spaces ?^k within the framework of approximate computability (type two theory of effectivity). A new notion of approximate decidability is proposed and discussed in some detail. It is an effective variant of F. Hausdorff's concept of resolvable sets, and it modifies and generalizes notions of recursivity known from computable analysis, formerly used for open or closed sets only, to more general types of sets. Approximate decidability of sets can equivalently be expressed by computability of the characteristic functions by means of appropriately working oracle Turing machines. The notion fulfills some natural requirements and is hereditary under canonical embeddings of sets into spaces of higher dimensions. However, it is not closed under binary union or intersection of sets. We also show how the framework of resolvability and approximate decidability can be applied to investigate concepts of reducibility for subsets of Euclidean spaces.     

An Intuitionistic Axiomatisation of Real Closed Fields

We give an intuitionistic axiomatisation of real closed fields which has the constructive reals as a model. The main result is that this axiomatisation together with just the decidability of the order relation gives the classical theory of real closed fields. To establish this we rely on the quantifier elimination theorem for real closed fields due to Tarski, and a conservation theorem of classical logic over intuitionistic logic for geometric theories.     

Elementary Regular Rings. II

We extend the well-known result by Burris and Werner on existence of defining sequences for elementary products of models to arbitrary enrichments of Boolean algebras (we obtain a complete analog of the Feferman–Vaught theorem). This enables us to establish decidability of the elementary theory of a classical object of number theory, the ring of adeles.     

Nice Local-Global Fields. IV

The notion of a nice local-global field, introduced and studied in the author's previous articles, is extended to the fields for which the family of all quasiclassical valuation rings is near Boolean. The main result of the article is the theorem of decidability of the elementary theory of the class of all such fields satisfying the maximality condition.     

Difference Hierarchy in ϕ-Spaces

Some results on the Borel and difference hierarchies of subsets in -spaces are established. For instance, we prove analogs of the Hausdorff theorem (relating the difference and Borel hierarchies) and the Lavrentyev theorem (asserting the non-collapse of the difference hierarchy).     

Derivation of Hartreeʼs theory for generic mean-field Bose systems

In this paper we provide a novel strategy to prove the validity of Hartree?s theory for the ground state energy of bosonic quantum systems in the mean-field regime. For the known case of trapped Bose gases, this can be shown using the strong quantum de Finetti theorem, which gives the structure of infinite hierarchies of k-particles density matrices. Here we deal with the case where some particles are allowed to escape to infinity, leading to a lack of compactness. Our approach is based on two ingredients: (1) a weak version of the quantum de Finetti theorem, and (2) geometric techniques for many-body systems. Our strategy does not rely on any special property of the interaction between the particles. In particular, our results cover those of Benguria–Lieb and Lieb–Yau for, respectively, bosonic atoms and boson stars.     

Inconsistency-Tolerant Bunched Implications

It is known that logical systems with the property of paraconsistency can deal with inconsistency-tolerant and uncertainty reasoning more appropriately than systems which are non-paraconsistent. It is also known that the logic BI of bunched implications is useful for formalizing resource-sensitive reasoning. In this paper, a paraconsistent extension PBI of BI is studied. The logic PBI is thus intended to formalize an appropriate combination of inconsistency-tolerant reasoning and resource-sensitive reasoning. A Gentzen-type sequent calculus SPBI for PBI is introduced, and the cut-elimination and decidability theorems for SPBI are proved. An extension of the Grothendieck topological semantics for BI is introduced for PBI, and the completeness theorem with respect to this semantics is proved.     

Universal Horn classes and antivarieties of algebraic systems

We define and study universal Horn classes dual to varieties in both the syntactic and the semantic sense. Such classes, which we call antivarieties, appear naturally, e.g., in graph theory and in formal language theory. The basic results are the characterization theorem for antivarieties, the theorem on cores in axiomatizable color-families, and the decidability theorem for universal theories of families of interpretations of formal languages. Supported by RFFR grants Nos. 99-01-000485 and 96-01-00097, and also by DFG grant No. 436113/2670. Translated fromAlgebra i Logika, Vol. 39, No. 1, pp. 3–22, January–February, 2000.     

On the Decidability of Iterated Semidirect Products with Applications to Complexity

The notion of hyperdecidability has been introduced by the firstauthor as a tool to prove decidability of semidirect productsof pseudovarieties of semigroups. In this paper we considersome stronger notions which lead to improved decidability resultsallowing us in turn to establish the decidability of some iteratedsemidirect products. Roughly speaking, the decidability of asemidirect product follows from a mild, commonly verified propertyof the first factor plus the stronger property for all the otherfactors. A key role in this study is played by intermediatefree semigroups (relatively free objects of expanded type lyingbetween relatively free and relatively free profinite objects).As an application of the main results, the decidability of theKrohn–Rhodes (group) complexity is shown to follow fromnon-algorithmic abstract properties likely to be satisfied bythe pseudovariety of all finite aperiodic semigroups, therebysuggesting a new approach to answer (affirmatively) the questionas to whether complexity is decidable. 1991 Mathematics SubjectClassification: primary 20M05, 20M07, 20M35; secondary 08B20.     

Burgers and Kadomtsev-Petviashvili hierarchies: A functional representation approach

Functional representations of (matrix) Burgers and potential Kadomtsev-Petviashvili (pKP) hierarchies (and others), as well as some corresponding Bäcklund transformations, can be obtained surprisingly simply from a “discrete” functional zero-curvature equation. We use these representations to show that any solution of a Burgers hierarchy is also a solution of the pKP hierarchy. Moreover, the pKP hierarchy can be expressed in the form of an inhomogeneous Burgers hierarchy. In particular, this leads to an extension of the Cole-Hopf transformation to the pKP hierarchy. Furthermore, these hierarchies are solved by the solutions of certain functional Riccati equations.     

Generalized ordinal sums and the decidability of BL-chains

We present a general construction of a family of ordinal sums of a sequence of structures and prove an elimination theorem for the class of ordinal sums in an expanded language. From this we deduce the decidability of the class of -ordinal sums of models of a decidable theory T. As an application of this result we prove that the theory of BL-chains is decidable.In Celebration of the Sixtieth Birthday of Ralph N. McKenzieReceived June 9, 2002; accepted in final form June 19, 2003.     

Separability and decidability results for varieties of Jónsson dynamic algebras

Dynamic algebras are algebraic counterparts of dynamic logics: propositional logical systems endowed with a set of modal operators. In [18], B. Jónsson introduced dynamic algebras as Boolean algebras with unary operators, the indices of which range over a given Kleene algebra. On the other hand, V.R. Pratt and D. Kozen proposed a two-sorted approach to dynamic algebras, which was followed in the early papers on the topic, such as Fischer and Ladner [15] and Németi [28]. For a recent overview of the field cf. [4]. In the present paper we investigate connections (as well as diversities) between these two approaches. Our main aim is to transfer (where possible) two-sorted results on separability and decidability to the one-sorted case and to extend them to broad classes of varieties of Jónsson dynamic algebras. In particular, as a consequence of such considerations, we obtain a decidability result on Kleene algebras.     

A general approach to fuzzy concepts

The paper proposes a flexible way to build concepts within fuzzy logic and set theory. The framework is general enough to capture some important particular cases, with their own independent interpretations, like “antitone” or “isotone” concepts constructed from fuzzy binary relations, but also to allow the two universes (of objects and attributes) to be equipped each with its own truth structure. Perhaps the most important feature of our approach is that we do not commit ourselves to any kind of logical connector, covering thus the case of a possibly non‐commutative conjunction too. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Basic formulas and languages Part I. The theory

A general mathematical framework to deal with (the decidability status of) properties of derivations in E0L systems (forms) is developed. It is based on the theory of well-quasi-orders. This paper (the first of two parts) deals with the mathematical theory of the proposed approach.     

A new kind of geometric structures determining the chain good weight hierarchies

In this paper, by using a new kind of geometric structures, we present some sufficient conditions to determine the weight hierarchies of linear codes satisfying the chain condition.     

Bilinear spaces over a fixed field are simple unstable

We study the model theory of vector spaces with a bilinear form over a fixed field. For finite fields this can be, and has been, done in the classical framework of full first-order logic. For infinite fields we need different logical frameworks. First we take a category-theoretic approach, which requires very little set-up. We show that linear independence forms a simple unstable independence relation. With some more work we then show that we can also work in the framework of positive logic, which is much more powerful than the category-theoretic approach and much closer to the classical framework of full first-order logic. We fully characterise the existentially closed models of the arising positive theory. Using the independence relation from before we conclude that the theory is simple unstable, in the sense that dividing has local character but there are many distinct types. We also provide positive version of what is commonly known as the Ryll-Nardzewski theorem for ω-categorical theories in full first-order logic, from which we conclude that bilinear spaces over a countable field are ω-categorical.     

一个新的非等谱可积族和一些相关对称

利用李群$M_nC$的一个子群我们引入一个线性非等谱问题,该问题的相容性条件可导出演化方程的一个非等谱可积族,该可积族可约化成一个广义非等谱可积族.这个广义非等谱可积族可进一步约化成在物理学中具有重要应用的标准非线性薛定谔方程和KdV方程.基于此,我们讨论在广义非等谱可积族等谱条件下的一个广义AKNS族$u_t=K_m(u)$的$K$对称和$\tau$对称.此外,我们还考虑非等谱AKNS族$u_t=\tau_{N+1}^l$的$K$对称和$\tau$对称.最后,我们得到这两个可积族的对称李代数,并给出这些对称和李代数的一些应用,即生成了一些变换李群和约化方程的无穷小算子.