Local set theory

In 1945, Eilenberg and MacLane introduced the new mathematical notion of category. Unfortunately, from the very beginning, category theory did not fit into the framework of either Zermelo—Fraenkel set theory or even von Neumann—Bernays—Gödel set-class theory. For this reason, in 1959, MacLane posed the general problem of constructing a new, more flexible, axiomatic set theory which would be an adequate logical basis for the whole of naïve category theory. In this paper, we give axiomatic foundations for local set theory. This theory might be one of the possible solutions of the MacLane problem.Translated from Matematicheskie Zametki, vol. 77, no. 2, 2005, pp. 194–212.Original Russian Text Copyright © 2005 by V. K. Zakharov.This revised version was published online in April 2005 with a corrected issue number.     

Finite axiomatizability of local set theory

The need for modifying axiomatic set theories was caused, in particular, by the development of category theory. The ZF and NBG axiomatic theories turned out to be unsuitable for defining the notion of a model of category theory. The point is that there are constructions such as the category of categories in naïve category theory, while constructions like the set of sets are strongly restricted in the ZF and NBG axiomatic theories. Thus, it was required, on the one hand, to restrict constructions similar to the category of categories and, on the other hand, adapt axiomatic set theory in order to give a definition of a category which survives restricted construction similar to the category of categories. This task was accomplished by promptly inventing the axiom of universality (AU) asserting that each set is an element of a universal set closed under all NBG constructions. Unfortunately, in the theories ZF + AU and NBG + AU, there are toomany universal sets (as many as the number of all ordinals), whereas to solve the problem stated above, a countable collection of universal sets would suffice. For this reason, in 2005, the first-named author introduced local-minimal set theory, which preserves the axiom AU of universality and has an at most countable collection of universal sets. This was achieved at the expense of rejecting the global replacement axiom and using the local replacement axiom for each universal class instead. Local-minimal set theory has 14 axioms and one axiom scheme (of comprehension). It is shown that this axiom scheme can be replaced by finitely many axioms that are special cases of the comprehension scheme. The proof follows Bernays’ scheme with significant modifications required by the presence of the restricted predicativity condition on the formula in the comprehension axiom scheme.     

Ultrapowers as sheaves on a category of ultrafilters

In the paper we investigate the topos of sheaves on a category of ultrafilters. The category is described with the help of the Rudin-Keisler ordering of ultrafilters. It is shown that the topos is Boolean and two-valued and that the axiom of choice does not hold in it. We prove that the internal logic in the topos does not coincide with that in any of the ultrapowers. We also show that internal set theory, an axiomatic nonstandard set theory, can be modeled in the topos.Mathematics Subject Classification (2000): Primary 03G30, 03C20, Secondary 03E05, 03E70, 03H05The author would like to thank the Mittag-Leffler Institute for partial suport.     

Toward an Elementary Axiomatic Theory of the Category of LP-Matroids

The purpose of this paper is to provide the beginnings of an elementary theory for the category of loopless pointed matroids and strong maps. We propose a finite set of elementary axioms that is the beginning of an elementary axiomatic theory for this category.     

Asymptotic Homomorphisms of C *-Algebras and C *-Extensions

We present a brief introduction to two theories in the category of C ^*-algebras—theory of asymptotic homomorphisms and theory of extensions—and explain how these theories are related to each other.     

Geometric separation and exact solutions for the parameterized independent set problem on disk graphs

We consider the parameterized problem, whether for a given set  of n disks (of bounded radius ratio) in the Euclidean plane there exists a set of k non-intersecting disks. For this problem, we expose an algorithm running in time that is—to our knowledge—the first algorithm with running time bounded by an exponential with a sublinear exponent. For λ-precision disk graphs of bounded radius ratio, we show that the problem is fixed parameter tractable with a running time  . The results are based on problem kernelization and a new “geometric ( -separator) theorem” which holds for all disk graphs of bounded radius ratio. The presented algorithm then performs, in a first step, a “geometric problem kernelization” and, in a second step, uses divide-and-conquer based on our new “geometric separator theorem.”     

Derived Functors of Graded Theories

The homotopy category of one point unions of spheres and the homotopy category of Eilenberg–MacLane spaces are examples of graded theories. Spaces yield models of these theories which can be described in terms of iterated comma categories given by functors. The associated derived functors play an important role in spectral sequences computing homotopy groups. Using cross-effect methods, the derived functors are studied and the existence of a vanishing line is proven.     

The strength of Mac Lane set theory

Saunders Mac Lane has drawn attention many times, particularly in his book Mathematics: Form and Function, to the system of set theory of which the axioms are Extensionality, Null Set, Pairing, Union, Infinity, Power Set, Restricted Separation, Foundation, and Choice, to which system, afforced by the principle, , of Transitive Containment, we shall refer as . His system is naturally related to systems derived from topos-theoretic notions concerning the category of sets, and is, as Mac Lane emphasises, one that is adequate for much of mathematics. In this paper we show that the consistency strength of Mac Lane's system is not increased by adding the axioms of Kripke–Platek set theory and even the Axiom of Constructibility to Mac Lane's axioms; our method requires a close study of Axiom H, which was proposed by Mitchell; we digress to apply these methods to subsystems of Zermelo set theory , and obtain an apparently new proof that is not finitely axiomatisable; we study Friedman's strengthening of , and the Forster–Kaye subsystem of , and use forcing over ill-founded models and forcing to establish independence results concerning and ; we show, again using ill-founded models, that proves the consistency of ; turning to systems that are type-theoretic in spirit or in fact, we show by arguments of Coret and Boffa that proves a weak form of Stratified Collection, and that is a conservative extension of for stratified sentences, from which we deduce that proves a strong stratified version of ; we analyse the known equiconsistency of with the simple theory of types and give Lake's proof that an instance of Mathematical Induction is unprovable in Mac Lane's system; we study a simple set theoretic assertion—namely that there exists an infinite set of infinite sets, no two of which have the same cardinal—and use it to establish the failure of the full schema of Stratified Collection in ; and we determine the point of failure of various other schemata in . The paper closes with some philosophical remarks.     

On the sectional category of subgroup inclusions and Adamson cohomology theory

The sectional category of a subgroup inclusion $H?G$ can be defined as the sectional category of the corresponding map between Eilenberg–MacLane spaces. We extend a characterization of topological complexity of aspherical spaces given by Farber, Grant, Lupton and Oprea to the context of sectional category of subgroup inclusions and investigate it by means of Adamson cohomology theory.     

Multiple positive solutions for semi‐linear elliptic systems involving sign‐changing weight

In this paper, we study the multiplicity results of positive solutions for a semi‐linear elliptic system involving critical growth terms. With the help of Nehari manifold and Ljusternik‐Schnirelmann category, we investigate how the coefficient h(x) of the critical nonlinearity affects the number of positive solutions of that problem and get a relationship between the number of positive solutions and the topology of the global maximum set of h. Copyright © 2014 John Wiley & Sons, Ltd.     

Heuristic Methods for Large Centroid Clustering Problems

This article presents new heuristic methods for solving a class of hard centroid clustering problems including the p-median, the sum-of-squares clustering and the multi-source Weber problems. Centroid clustering is to partition a set of entities into a given number of subsets and to find the location of a centre for each subset in such a way that a dissimilarity measure between the entities and the centres is minimized. The first method proposed is a candidate list search that produces good solutions in a short amount of time if the number of centres in the problem is not too large. The second method is a general local optimization approach that finds very good solutions. The third method is designed for problems with a large number of centres; it decomposes the problem into subproblems that are solved independently. Numerical results show that these methods are efficient—dozens of best solutions known to problem instances of the literature have been improved—and fast, handling problem instances with more than 85,000 entities and 15,000 centres—much larger than those solved in the literature. The expected complexity of these new procedures is discussed and shown to be comparable to that of an existing method which is known to be very fast.     

Axiomatic systems for rough sets and fuzzy rough sets

Rough set theory is an important tool for approximate reasoning about data. Axiomatic systems of rough sets are significant for using rough set theory in logical reasoning systems. In this paper, outer product method are used in rough set study for the first time. By this approach, we propose a unified lower approximation axiomatic system for Pawlak’s rough sets and fuzzy rough sets. As the dual of axiomatic systems for lower approximation, a unified upper approximation axiomatic characterization of rough sets and fuzzy rough sets without any restriction on the cardinality of universe is also given. These rough set axiomatic systems will help to understand the structural feature of various approximate operators.     

An algebraic geometry algorithm for scheduling in presence of setups and correlated demands

We study here a problem of schedulingn job types onm parallel machines, when setups are required and the demands for the products are correlated random variables. We model this problem as a chance constrained integer program.Methods of solution currently available—in integer programming and stochastic programming—are not sufficient to solve this model exactly. We develop and introduce here a new approach, based on a geometric interpretation of some recent results in Gröbner basis theory, to provide a solution method applicable to a general class of chance constrained integer programming problems.Out algorithm is conceptually simple and easy to implement. Starting from a (possibly) infeasible solution, we move from one lattice point to another in a monotone manner regularly querying a membership oracle for feasibility until the optimal solution is found. We illustrate this methodology by solving a problem based on a real system.Corresponding author.     

Error bounds for analytic systems and their applications

Using a 1958 result of Lojasiewicz, we establish an error bound for analytic systems consisting of equalities and inequalities defined by real analytic functions. In particular, we show that over any bounded region, the distance from any vectorx in the region to the solution set of an analytic system is bounded by a residual function, raised to a certain power, evaluated atx. For quadratic systems satisfying certain nonnegativity assumptions, we show that this exponent is equal to 1/2. We apply the error bounds to the Karush—Kuhn—Tucker system of a variational inequality, the affine variational inequality, the linear and nonlinear complementarity problem, and the 0–1 integer feasibility problem, and obtain new error bound results for these problems. The latter results extend previous work for polynomial systems and explain why a certain square-root term is needed in an error bound for the (monotone) linear complementarity problem.The research of this author is based on work supported by the Natural Sciences and Engineering Research Council of Canada under grant OPG0090391.The research of this author is based on work supported by the National Science Foundation under grants DDM-9104078 and CCR-9213739 and by the Office of Naval Research under grant 4116687-01.     

Consistency and monotonicity in assignment problems

This paper presents axiomatic characterizations of the core of assignment problems. In the main axiomatization theorem we use six axioms including the consistency (CONS) and the weak pairwise-monotonicity (W.P.MON) which are firstly proposed and defined for this setup in the present paper. Since an assignment problem may be converted into a model of a private ownership economy with indivisible goods and the core of the assignment problem coincides with the set of the competitive allocations of the economy, our characterization theorems also give axiomatic characterizations of the set of competitive allocations. Because the consistency is a desirable property of resource allocation mechanisms, our main result gives a new normative implication of competitive equilibria.     

On uniqueness of （fuzzy） relation in some generalized rough set model

In rough set theory, crisp and/or fuzzy binary relations play an important role in both constructive and axiomatic considerations of various generalized rough sets. This paper considers the uniqueness problem of the （fuzzy） relation in some generalized rough set model. Our results show that by using the axiomatic approach, the （fuzzy） relation determined by （fuzzy） approximation operators is unique in some （fuzzy） double-universe model.     

The Ehrhart Polynomial of the Birkhoff Polytope

The nth Birkhoff polytope is the set of all doubly stochastic n × n matrices, that is, those matrices with nonnegative real coefficients in which every row and column sums to one. A wide open problem concerns the volumes of these polytopes, which have been known for n $\leq$ 8. We present a new, complex-analytic way to compute the Ehrhart polynomial of the Birkhoff polytope, that is, the function counting the integer points in the dilated polytope. One reason to be interested in this counting function is that the leading term of the Ehrhart polynomial is—up to a trivial factor—the volume of the polytope. We implemented our methods in the form of a computer program, which yielded the Ehrhart polynomial (and hence the volume) of the ninth Birkhoff polytope, as well as the volume of the tenth Birkhoff polytope.     

Autour de la cohomologie de MacLane des corps finis

Résumé Nous décrivons une nouvelle méthode de calcul de la cohomologie de MacLane des corps finis. Cette théorie est intimement reliée aux extensions du groupe additif déjà étudiées par L. Breen et à l'homologie de Hochschild topologique de M. Bökstedt (et donc à la K-théorie stable). Notre approche utilise de manière cruciale l'annulation de la cohomologie de MacLane du corpsF _P , avec pour coefficients l'algèbre symétrique où l'on a inversé le Frobenius. Nous recourons alors à l'analyse des complexes de Koszul et de De Rham en caractéristique non nulle.

---

Summary A new way of computing MacLane cohomology of finite fields is described. Closely related to this theory are L. Breen's extensions du groupe additif and M. Bökstedt's topological Hochschild homology (and so is stable K-theory, hence). Our approach makes essential use of a cancellation result for MacLane cohomology ofF _P with coefficients in the symmetric algebra where the Frobenius has been inverted. We then proceed through an analysis of the Koszul complex and the De Rham complex in non-zero characteristic.

---

---

Oblatum 28-XI-1992 & 3-IX-1993     

Auslander-Reiten Triangles, Ziegler Spectra and Gorenstein Rings

We investigate (existence of) Auslander—Reiten triangles in a triangulated category in connection with torsion pairs, existence of Serre functors, representability of homological functors and realizability of injective modules. We also develop an Auslander—Reiten theory in a compactly generated triangulated category and we study the connections with the naturally associated Ziegler spectrum. Our analysis is based on the relative homological theory of purity and Brown's Representability Theorem. Our main interest lies in the structure of Auslander—Reiten triangles in the full subcategory of compact objects. We also study the connections and the interplay between Auslander—Reiten theory, pure-semisimplicity and the finite type property, Grothendieck groups, and we give applications to derived categories of Gorenstein rings.     

Simplified Optimality Conditions for Minimizing the Difference of Vector-Valued Functions

This paper deals with an axiomatic approach to certain optimality conditions for the vector nonconvex minimization problem min{g(x)–h(x): xX}, where X is an arbitrary set and g, h are functions defined on X with values in an ordered topological vector space Z.