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.     

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.     

On topological set theory

This paper is concerned with topological set theory, and particularly with Skala's and Manakos' systems for which we give a topological characterization of the models. This enables us to answer natural questions about those theories, reviewing previous results and proving new ones. One of these shows that Skala's set theory is in a sense compatible with any ‘normal’ set theory, and another appears on the semantic side as a ‘Cantor theorem’ for the category of Alexandroff spaces. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

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.     

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.”     

Relativistically Covariant Quantum Field Theory of the Maslov Complex Germ

We consider an explicitly covariant formulation of the quantum field theory of the Maslov complex germ (semiclassical field theory) in the example of a scalar field. The main object in the theory is the “semiclassical bundle” whose base is the set of classical states and whose fibers are the spaces of states of the quantum theory in an external field. The respective semiclassical states occurring in the Maslov complex germ theory at a point and in the theory of Lagrangian manifolds with a complex germ are represented by points and surfaces in the semiclassical bundle space. We formulate semiclassical analogues of quantum field theory axioms and establish a relation between the covariant semiclassical theory and both the Hamiltonian formulation previously constructed and the axiomatic field theory constructions Schwinger sources, the Bogoliubov S-matrix, and the Lehmann-Symanzik-Zimmermann R-functions. We propose a new covariant formulation of classical field theory and a scheme of semiclassical quantization of fields that does not involve a postulated replacement of Poisson brackets with commutators.__________Translated from Teoreticheskaya i Matematicheskaya Fizika, Vol. 144, No. 3, pp. 492–512, September, 2005.     

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.     

Weakly Terminal Objects in Quasicategories of $\mathbb{SET}$ Endofunctors

The quasicategory ℚ of all set functors (i.e. endofunctors of the category of all sets and mappings) and all natural transformations has a terminal object – the constant functor C₁. We construct here the terminal (or at least the smallest weakly terminal object, which is rigid) in some important subquasicategories of ℚ – in the quasicategory of faithful connected set functors and all natural transformations, and in the quasicategories of all set functors and natural transformations which preserve filters of points (up to cardinality κ).Mathematics Subject Classifications (2000) 18A22, 18A25.Libor Barto: This work was completed with the support of the Grant Agency of the Czech Republic under the grant 201/02/0148; supported also by MSM 113200007.     

Canonical form of Tarski sets in Zermelo-Fraenkel set theory

We establish the equivalence of the notions of an inaccessible cumulative set and uncountable Tarski set. In addition, the equivalence of these notions and that of a galactic set is proved.Translated from Matematicheskie Zametki, vol. 77, no. 3, 2005, pp. 323–333.Original Russian Text Copyright © 2005 by E. I. Bunina, V. K. Zakharov.This revised version was published online in April 2005 with a corrected issue number.     

A remark on uniform spaces with invariant nonstandard hulls

Let (X , Γ) be a uniform space with its uniformity generated by a set of pseudo‐metrics Γ. Let the symbol ? denote the usual infinitesimal relation on *X , and define a new infinitesimal relation ≈ on *X by writing x ≈ y whenever *? (x, p ) ? *? (y, p ) for each ? ∈ Γ and each p ∈ X . We call (X , Γ) an S‐space if the relations ? and ≈ coincide on fin(*X ). S ‐spaces are interesting because their nonstandard hulls have representations within Nelson's internal set theory (IST, [5]). This was shown in [1], where it was also observed that the class of uniform spaces that have invariant nonstandard hulls is contained in the class of S ‐spaces. The question of whether there are S ‐spaces that do not have invariant nonstandard hulls was left open in [1]. In this note we show that when the uniformity of an S ‐space is given by a single pseudometric, the space has invariant nonstandard hulls. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

About the Admissible Predicates on Admissible Sets

We study the admissible predicates, i.e., the predicates having the property that their addition to the signature of an admissible set preserves the property “to be an admissible set.” We show that the family of these predicates is much wider than the family of Δ-predicates. We also construct a family of admissible predicates of cardinality 2^ω such that the addition of an arbitrary pair of predicates of this family to the signature of an admissible set violates the admissibility of the latter as well as other examples of families of admissible predicates.Original Russian Text Copyright © 2005 Morozov A. S.The author was supported by the International Russian-German Program (Grant RFRB-DFG 01-01-04003), the Russian Science Support Foundation, and the State Maintenance Program for the Leading Scientific Schools of the Russian Federation (Grant 2112.2003.1).__________Translated from Sibirskii Matematicheskii Zhurnal, Vol. 46, No. 4, pp. 841–850, July–August, 2005.     

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.     

Wightman axiomatic approach in noncommutative field theory

The axiomatic approach based on Wightman functions is developed in noncommutative field theory. We prove that the main results of the axiomatic approach remain valid if the noncommutativity affects only the spatial variables.Translated from Teoreticheskaya i Matematicheskaya Fizika, Vol. 142, No. 2, pp. 403#x2013;416, February, 2005.     

Slice-Continuous Sets in Reflexive Banach Spaces: Some Complements

In this paper we study a class of closed convex sets introduced recently by Ernst et al. (J Funct Anal 223:179–203, 2005) and called by these authors slice-continuous sets. This class, which plays an important role in the strong separation of convex sets, coincides in ℝ ⁿ with the well known class of continuous sets defined by Gale and Klee in the 1960s. In this article we achieve, in the setting of reflexive Banach spaces, two new characterizations of slice-continuous sets, similar to those provided for continuous sets in ℝ ⁿ by Gale and Klee. Thus, we prove that a slice-continuous set is precisely a closed and convex set which does not possess neither boundary rays, nor flat asymptotes of any dimension. Moreover, a slice-continuous set may also be characterized as being a closed and convex set of non-void interior for which the support function is continuous except at the origin. Dedicated to Boris Mordukhovich in honour of his 60th birthday.     

A Construction of Difference Sets in High Exponent 2-Groups Using Representation Theory

Nontrivial difference sets in groups of order a power of 2 are part of the family of difference sets called Menon difference sets (or Hadamard), and they have parameters (2^2d+2, 2^2d+1±2 ^d , 2^2d ±2 ^d ). In the abelian case, the group has a difference set if and only if the exponent of the group is less than or equal to 2 ^d+2. In [14], the authors construct a difference set in a nonabelian group of order 64 and exponent 32. This paper generalizes that result to show that there is a difference set in a nonabelian group of order 2^2d+2 with exponent 2 ^d+3. We use representation theory to prove that the group has a difference set, and this shows that representation theory can be used to verify a construction similar to the use of character theory in the abelian case.     

Forcing under Anti‐Foundation Axiom: An expression of the stalks

We introduce a new simple way of defining the forcing method that works well in the usual setting under FA, the Foundation Axiom, and moreover works even under Aczel's AFA, the Anti‐Foundation Axiom. This new way allows us to have an intuition about what happens in defining the forcing relation. The main tool is H. Friedman's method of defining the extensional membership relation ∈ by means of the intensional membership relation ε . Analogously to the usual forcing and the usual generic extension for FA‐models, we can justify the existence of generic filters and can obtain the Forcing Theorem and the Minimal Model Theorem with some modifications. These results are on the line of works to investigate whether model theory for AFA‐set theory can be developed in a similar way to that for FA‐set theory. Aczel pointed out that the quotient of transition systems by the largest bisimulation and transition relations have the essentially same theory as the set theory with AFA. Therefore, we could hope that, by using our new method, some open problems about transition systems turn out to be consistent or independent. (© 2006 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Szegö theorem,Carathéodory domains,and boundedness of calculating functionals

Convex Chebyshev sets M in a linear space X with norm or nonsymmetric norm ‖ · ‖ which are contained in a subspace H of X are considered. It is proved that if | { |_{H, φ} is the nonsymmetric norm on H determined by the Minkowski functional of , where B is the unit ball of X and ‖φ‖, with respect to 0, then M is a Chebyshev set in for any φ. From this result sufficient and necessary conditions for the convexity of Chebyshev sets and bounded Chebyshev sets contained in a subspace H of X are derived.__________Translated from Matematicheskie Zametki, vol. 78, no. 1, 2005, pp. 3–15.Original Russian Text Copyright © 2005 by A. R. Alimov.     

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.     

Computational adequacy for recursive types in models of intuitionistic set theory

This paper provides a unifying axiomatic account of the interpretation of recursive types that incorporates both domain-theoretic and realizability models as concrete instances. Our approach is to view such models as full subcategories of categorical models of intuitionistic set theory. It is shown that the existence of solutions to recursive domain equations depends upon the strength of the set theory. We observe that the internal set theory of an elementary topos is not strong enough to guarantee their existence. In contrast, as our first main result, we establish that solutions to recursive domain equations do exist when the category of sets is a model of full intuitionistic Zermelo–Fraenkel set theory. We then apply this result to obtain a denotational interpretation of FPC, a recursively typed lambda-calculus with call-by-value operational semantics. By exploiting the intuitionistic logic of the ambient model of intuitionistic set theory, we analyse the relationship between operational and denotational semantics. We first prove an “internal” computational adequacy theorem: the model always believes that the operational and denotational notions of termination agree. This allows us to identify, as our second main result, a necessary and sufficient condition for genuine “external” computational adequacy to hold, i.e. for the operational and denotational notions of termination to coincide in the real world. The condition is formulated as a simple property of the internal logic, related to the logical notion of 1-consistency. We provide useful sufficient conditions for establishing that the logical property holds in practice. Finally, we outline how the methods of the paper may be applied to concrete models of FPC. In doing so, we obtain computational adequacy results for an extensive range of realizability and domain-theoretic models.     

A core of voting games with improved foresight

This paper considers voting situations in which the vote takes place iteratively. If a coalition replaces the status quo a with a contestant b, then b becomes the new status quo, and the vote goes on until a candidate is reached that no winning coalition is willing to replace. It is well known that the core, that is, the set of undominated alternatives, may be empty. To alleviate this problem, Rubinstein [Rubinstein, A., 1980. Stability of decision systems under majority rule. Journal of Economic Theory 23, 150–159] assumes that voters look forward one vote before deciding to replace an alternative by a new one. They will not do so if the new status quo is going to be replaced by a third that is less interesting than the first. The stability set, that is, the set of undominated alternatives under this behavior, is always non-empty when preferences are strict. However, this is not necessarily the case when voters’ indifference is allowed. Le Breton and Salles [Le Breton, M., Salles, M., 1990. The stability set of voting games: Classification and generecity results. International Journal of Game Theory 19, 111–127], Li [Li, S., 1993. Stability of voting games. Social Choice and Welfare 10, 51–56] and Martin [Martin, M., 1998. Quota games and stability set of order d. Economic Letters 59, 145–151] extend the sophistication of the voters by having them look d votes forward along the iterative process. For d sufficiently large, the resulting set of undominated alternatives is always non-empty even if indifference is allowed. We show that it may be unduly large. Next, by assuming that other voters along a chain of votes are also rational, that is, they also look forward to make sure that the votes taking place later on will not lead to a worst issue for them, we are able to reduce the size of this set while insuring its non-emptiness. Finally, we show that a vote with sufficient foresight satisfies a no-regret property, contrarily to the classical core and the stability set.