Decidability of ∀*∀-Sentences in Membership Theories

The problem is addressed of establishing the satisfiability of prenex formulas involving a single universal quantifier, in diversified axiomatic set theories. A rather general decision method for solving this problem is illustrated through the treatment of membership theories of increasing strength, ending with a subtheory of Zermelo-Fraenkel which is already complete with respect to the ?*? class of sentences. NP-hardness and NP-completeness results concerning the problems under study are achieved and a technique for restricting the universal quantifier is presented. Mathematics Subject Classification: 03B25, 03E30.     

A Galois Connection

The connection presented in this paper mirror-links two metamathematical structures, the finitary closure operators, and the compact consistency properties, in such a way that a specification of one structure induces a provably equivalent specification of the other. Mathematics Subject Classification (2000): Primary 06A15, Secondary 28E10 03B22     

The Recursively Mahlo Property in Second Order Arithmetic

The paper characterizes the second order arithmetic theorems of a set theory that features a recursively Mahlo universe; thereby complementing prior proof-theoretic investigations on this notion. It is shown that the property of being recursively Mahlo corresponds to a certain kind of β-model reflection in second order arithmetic. Further, this leads to a characterization of the reals recursively computable in the superjump functional. Mathematics Subject Classification: 03F35, 03F15, 03E70.     

On nice equivalence relations on <Superscript>λ</Superscript>2

Let E be an equivalence relation on the powerset of an uncountable set, which is reasonably definable. We assume that any two subsets with symmetric difference of size exactly 1 are not equivalent. We investigate whether for E there are many pairwise non equivalent sets. I would like to thank Alice Leonhardt for the beautiful typing.This research was supported by The Israel Science Foundation. Publication 724. Mathematics Subject Classification (2000): 03E47, 03E35; 20K20, 20K35     

Choices of Convenient Sets

Proceeding in the theory with extensionality, comprehension for classes, existence of the empty set and the assumption the addition of one element to a set makes again a set (others usual set-theoretical operations are not required) we show a week assumption which guarantees existence of a saturated elementary extension (with absolute ?) of the system of hereditarily finite sets. Mathematics Subject Classification: 03C62, 03C50, 03E70.     

A partial model of NF with ZF

The theory New Foundations (NF) of Quine was introduced in [14]. This theory is finitely axiomatizable as it has been proved in [9]. A similar result is shown in [8] using a system called K. Particular subsystems of NF, inspired by [8] and [9], have models in ZF. Very little is known about subsystems of NF satisfying typical properties of ZF; for example in [11] it is shown that the existence of some sets which appear naturally in ZF is an axiom independent from NF (see also [12]). Here we discuss a model of subsystems of NF in which there is a set which is a model of ZF. MSC: 03E70.     

Hybridization of GRASP Metaheuristic with Data Mining Techniques

In this work, we propose a hybridization of GRASP metaheuristic that incorporates a data mining process. We believe that patterns obtained from a set of sub-optimal solutions, by using data mining techniques, can be used to guide the search for better solutions in metaheuristics procedures. In this hybrid GRASP proposal, after executing a significant number of GRASP iterations, the data mining process extracts patterns from an elite set of solutions which will guide the following iterations. To validate this proposal we have worked on the Set Packing Problem as a case study. Computational experiments, comparing traditional GRASP and different hybrid approaches, show that employing frequent patterns mined from an elite set of solutions conducted to better results. Besides, additional performed experiments evidence that data mining strategies accelerate the process of finding good solutions. ^★★Work sponsored by CNPq research grants 300879/00-8 and 475124/03-0. ^†Work sponsored by CNPq research grant 475124/03-0.     

Constructive strong regularity and the extension property of a compactification

In contexts in which the principle of dependent choice may not be available, as toposes or Constructive Set Theory, standard locale theoretic results related to complete regularity may fail to hold. To resolve this difficulty, B. Banaschewski and A. Pultr introduced strongly regular locales. Unfortunately, Banaschewski and Pultr's notion relies on non-constructive set existence principles that hinder its use in Constructive Set Theory. In this article, a fully constructive formulation of strong regularity for locales is introduced by replacing non-constructive set existence with coinductive set definitions, and exploiting the Relation Reflection Scheme. As an application, every strongly regular locale L is proved to have a compact regular compactification. The construction of this compactification is then used to derive the main result of this article: a characterization of locale compactifications (and thus, classically, of the compactifications of a space) in terms of their ability of extending continuous functions with compact regular codomains. Finally, an open problem related to the existence of the compact regular reflection of a locale is presented.     

On the regular extension axiom and its variants

The regular extension axiom, REA, was first considered by Peter Aczel in the context of Constructive Zermelo‐Fraenkel Set Theory as an axiom that ensures the existence of many inductively defined sets. REA has several natural variants. In this note we gather together metamathematical results about these variants from the point of view of both classical and constructive set theory.     

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.     

基于粗糙集理论的舰船研制方案总体评价

以系统评价思想为指导,提出了基于粗糙集理论的多目标评价方法,对舰船研制方案综合评价问题进行了研究,建立了综合评价模型,并通过算例表明,该方法用于舰船研制方案的总体评价比现行方法有明显的优越性.     

A note on Bar Induction in Constructive Set Theory

Bar Induction occupies a central place in Brouwerian mathematics. This note is concerned with the strength of Bar Induction on the basis of Constructive Zermelo‐Fraenkel Set Theory, CZF. It is shown that CZF augmented by decidable Bar Induction proves the 1‐consistency of CZF. This answers a question of P. Aczel who used Bar Induction to give a proof of the Lusin Separation Theorem in the constructive set theory CZF. (© 2006 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

An Augmentation Algorithm for the Maximum Weighted Stable Set Problem

Edge projection is a specialization of Lovász and Plummer's clique reduction when restricted to edges. A concept of augmenting sequences of edge-projections is defined w.r.t. a stable set S. It is then proved the equivalence between the optimality of S and the existence of an augmenting sequence w.r.t. S. This result is then exploited to develop a new tabu-search heuristic for the Maximum Stable Set Problem (weighted and unweighted). The resulting code proved to be competitive with the best codes presented in the literature.     

The Mehler Formula for the Generalized Clifford-Hermite Polynomials

The Mehler formula for the Hermite polynomials allows for an integral representation of the one-dimensional Fractional Fourier transform. In this paper, we introduce a multi-dimensional Fractional Fourier transform in the framework of Clifford analysis. By showing that it coincides with the classical tensorial approach we are able to prove Mehler＇s formula for the generalized Clifford-Hermite polynomials of Clifford analysis.     

Value reducts and bireducts: A comparative study

In Rough Set Theory, the notion of bireduct allows to simultaneously reduce the sets of objects and attributes contained in a dataset. In addition, value reducts are used to remove some unnecessary values of certain attributes for a specific object. Therefore, the combination of both notions provides a higher reduction of unnecessary data. This paper is focused on the study of bireducts and value reducts of information and decision tables. We present theoretical results capturing different aspects about the relationship between bireducts and reducts, offering new insights at a conceptual level. We also analyze the relationship between bireducts and value reducts. The studied connections among these notions provide important profits for the efficient information analysis, as well as for the detection of unnecessary or redundant information.     

On the structure of kripke models of heyting arithmetic

Since in Heyting Arithmetic (HA) all atomic formulas are decidable, a Kripke model for HA may be regarded classically as a collection of classical structures for the language of arithmetic, partially ordered by the submodel relation. The obvious question is then: are these classical structures models of Peano Arithmetic (PA)? And dually: if a collection of models of PA, partially ordered by the submodel relation, is regarded as a Kripke model, is it a model of HA? Some partial answers to these questions were obtained in [6], [3], [1] and [2]. Here we present some results in the same direction, announced in [7]. In particular, it is proved that the classical structures at the nodes of a Kripke model of HA must be models of IΔ₁ (PA^- with induction for provably Δ₁ formulas) and that the relation between these classical structures must be that of a Δ₁-elementary submodel. MSC: 03F30, 03F55.     

Inconsistency of GPK + AFA

M. Forti and F. Honsell showed in [4] that the hyperuniverses defined in [2] satisfy the anti-foundation axiom X₁ introduced in [3]. So it is interesting to study the axiom AFA, which is equivalent to X₁ in ZF, introduced by P. Aczel in [1]. We show in this paper that AFA is inconsistent with the theory GPK. This theory, which is first order, is defined by E. Weydert in [6] and later by M. Forti and R. Hinnion in [2]. It includes all general hyperuniverses as defined in [5]. In order to achieve our aim, we need to define ordinals in GPK and to study some of their properties. Mathematics Subject Classification: 03E70, 03E10.     

On a duality between Boolean valued analysis and topological Reduction Theory

By creating an unbounded topological reduction theory for complex Hilbert spaces over Stonean spaces, we can give a category-theoretic duality between Boolean valued analysis and topological reduction theory for complex Hilbert spaces. MSC: 03C90, 03E40, 06E15, 46M99.     

BOOLEAN ALGEBRAS IN AST

In this paper we investigate Boolean algebras and their subalgebras in Alternative Set Theory (AST). We show that any two countable atomless Boolean algebras are isomorphic and we give an example of such a Boolean algebra. One other main result is, that there is an infinite Boolean algebra freely generated by a set. At the end of the paper we show that the sentence “There is no non-trivial free group which is a set” is consistent with AST.