This chapter surveys set theory, model theory, and computability theory: how they first emerged from the foundations of mathematics, and how they have developed since. There are any amounts of mathematical technicalities in the background, but the chapter highlights those themes that have some philosophical resonance.

Michael Potter presents a comprehensive new philosophical introduction to set theory. Anyone wishing to work on the logical foundations of mathematics must understand set theory, which lies at its heart. Potter offers a thorough account of cardinal and ordinal arithmetic, and the various axiom candidates. He discusses in detail the project of set-theoretic reduction, which aims to interpret the rest of mathematics in terms of set theory. The key question here is how to deal with the paradoxes (...) that bedevil set theory. Potter offers a strikingly simple version of the most widely accepted response to the paradoxes, which classifies sets by means of a hierarchy of levels. What makes the book unique is that it interweaves a careful presentation of the technical material with a penetrating philosophical critique. Potter does not merely expound the theory dogmatically but at every stage discusses in detail the reasons that can be offered for believing it to be true. Set Theory and its Philosophy is a key text for philosophy, mathematical logic, and computer science. (shrink)

We study randomness beyond${\rm{\Pi }}_1^1$-randomness and its Martin-Löf type variant, which was introduced in [16] and further studied in [3]. Here we focus on a class strictly between${\rm{\Pi }}_1^1$and${\rm{\Sigma }}_2^1$that is given by the infinite time Turing machines introduced by Hamkins and Kidder. The main results show that the randomness notions associated with this class have several desirable properties, which resemble those of classical random notions such as Martin-Löf randomness and randomness notions defined via effective descriptive set theory such (...) as${\rm{\Pi }}_1^1$-randomness. For instance, mutual randoms do not share information and a version of van Lambalgen’s theorem holds.Towards these results, we prove the following analogue to a theorem of Sacks. If a real is infinite time Turing computable relative to all reals in some given set of reals with positive Lebesgue measure, then it is already infinite time Turing computable. As a technical tool towards this result, we prove facts of independent interest about random forcing over increasing unions of admissible sets, which allow efficient proofs of some classical results about hyperarithmetic sets. (shrink)

This monograph is a follow up to the author's classic text Boolean-Valued Models and Independence Proofs in Set Theory, providing an exposition of some of the most important results in set theory obtained in the 20th century--the independence of the continuum hypothesis and the axiom of choice. Aimed at research students and academics in mathematics, mathematical logic, philosophy, and computer science, the text has been extensively updated with expanded introductory material, new chapters, and a new appendix on category (...) theory, and includes recent developments in the field. Numerous exercises, along with the enlarged and entirely updated background material, make this an ideal text for students in logic and set theory. (shrink)

A practical viewpoint links reality, representation, and language to calculation by the concept of Turing (1936) machine being the mathematical model of our computers. After the Gödel incompleteness theorems (1931) or the insolvability of the so-called halting problem (Turing 1936; Church 1936) as to a classical machine of Turing, one of the simplest hypotheses is completeness to be suggested for two ones. That is consistent with the provability of completeness by means of two independent Peano arithmetics discussed in Section I. (...) Many modifications of Turing machines cum quantum ones are researched in Section II for the Halting problem and completeness, and the model of two independent Turing machines seems to generalize them. Then, that pair can be postulated as the formal definition of reality therefore being complete unlike any of them standalone, remaining incomplete without its complementary counterpart. Representation is formal defined as a one-to-one mapping between the two Turing machines, and the set of all those mappings can be considered as “language” therefore including metaphors as mappings different than representation. Section III investigates that formal relation of “reality”, “representation”, and “language” modeled by (at least two) Turing machines. The independence of (two) Turing machines is interpreted by means of game theory and especially of the Nash equilibrium in Section IV. Choice and information as the quantity of choices are involved. That approach seems to be equivalent to that based on set theory and the concept of actual infinity in mathematics and allowing of practical implementations. (shrink)

This book bridges the gaps between logic, mathematics and computer science by delving into the theory of well-quasi orders, also known as wqos. This highly active branch of combinatorics is deeply rooted in and between many fields of mathematics and logic, including proof theory, commutative algebra, braid groups, graph theory, analytic combinatorics, theory of relations, reverse mathematics and subrecursive hierarchies. As a unifying concept for slick finiteness or termination proofs, wqos have been rediscovered in diverse contexts, (...) and proven to be extremely useful in computer science. The book introduces readers to the many facets of, and recent developments in, wqos through chapters contributed by scholars from various fields. As such, it offers a valuable asset for logicians, mathematicians and computer scientists, as well as scholars and students. (shrink)

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. (shrink)

We give a straightforward computable-model-theoretic definition of a property of \Delta^0_2 sets called order-computability. We then prove various results about these sets which suggest that, simple though the definition is, the property defies any easy characterization in pure computability theory. The most striking example is the construction of two computably isomorphic c.e. sets, one of which is order-computable and the other not.

Category theory is often treated as an algebraic foundation for mathematics, and the widely known algebraization of ZF set theory in terms of this discipline is referenced as “categorical set theory” or “set theory for category theory”. The method of algebraization used in this theory has not been formulated in terms of universal algebra so far. In current paper, a _universal algebraic_ method, i.e. one formulated in terms of universal algebra, is presented and used (...) for algebraization of a ground mereological system described as “quantitative” (QMS) and of the standard set theories built upon it. The QMS is algebraized by using abelian generalized groups (AGGs) generalizing both abelian groups and Boolean algebras. To algebraize set theory, the AGG are enriched with operators to produce _extensional algebras_ (EA) of Tarskian “Boolean algebras with operators” type. EAs explicate the intuition of set theory’ universes (of discourse). The axiomatic set theory presented in this paper, named _extension theory_, previously went through an intuitive phase of development during its use by the author in computer science projects, where it served as the basis for development of a foundational data science framework and an extensional model of natural languages also outlined here. (shrink)

In [7], a naive set theory is introduced based on a polynomial time logical system, Light Linear Logic (LLL). Although it is reasonably claimed that the set theory inherits the intrinsically polytime character from the underlying logic LLL, the discussion there is largely informal, and a formal justification of the claim is not provided sufficiently. Moreover, the syntax is quite complicated in that it is based on a non-traditional hybrid sequent calculus which is required for formulating LLL.In this (...) paper, we consider a naive set theory based on Intuitionistic Light Affine Logic (ILAL), a simplification of LLL introduced by [1], and call it Light Affine Set Theory (LAST). The simplicity of LAST allows us to rigorously verify its polytime character. In particular, we prove that a function over {0, 1}* is computable in polynomial time if and only if it is provably total in LAST. (shrink)

The size and variation in both meaning-making and populations that characterize much contemporary text data demand research processes that support both discovery, interpretation and measurement. We assess one dominant strategy within the social sciences that takes a computer-led approach to text analysis. The approach is coined computational grounded theory. This strategy, we argue, relies on a set of unwarranted assumptions, namely, that unsupervised models return natural clusters of meaning, that the researcher can understand text with limited immersion and that (...) indirect validation is sufficient for ensuring unbiased and precise measurement. In response to this criticism, we develop a framework that is computer assisted. We argue that our reformulation of computational grounded theory better aligns with the principles within grounded theory, anthropological theory generation and ethnography. (shrink)

Inasmuch as physical theories are formalizable, set theory provides a framework for theoretical physics. Four speculations about the relevance of set theoretical modeling for physics are presented: the role of transcendental set theory (i) in chaos theory, (ii) for paradoxical decompositions of solid three-dimensional objects, (iii) in the theory of effective computability (Church-Turing thesis) related to the possible “solution of supertasks,” and (iv) for weak solutions. Several approaches to set theory and their advantages and disadvatages (...) for physical applications are discussed: Canlorian “naive” (i.e., nonaxiomatic) set theory, contructivism, and operationalism. In the author's opinion, an attitude of “suspended attention” (a term borrowed from psychoanalysis) seems most promising for progress. Physical and set theoretical entities must be operationalized wherever possible. At the same time, physicists should be open to “bizarre” or “mindboggling” new formalisms, which need not be operationalizable or testable at the lime of their creation, but which may successfully lead to novel fields of phenomenology and technology. (shrink)

Completed in 1983, this work culminates nearly half a century of the late Alfred Tarski's foundational studies in logic, mathematics, and the philosophy of science. Written in collaboration with Steven Givant, the book appeals to a very broad audience, and requires only a familiarity with first-order logic. It is of great interest to logicians and mathematicians interested in the foundations of mathematics, but also to philosophers interested in logic, semantics, algebraic logic, or the methodology of the deductive sciences, and to (...) computer scientists interested in developing very simple computer languages rich enough for mathematical and scientific applications. The authors show that set theory and number theory can be developed within the framework of a new, different, and simple equational formalism, closely related to the formalism of the theory of relation algebras. There are no variables, quantifiers, or sentential connectives. Predicates are constructed from two atomic binary predicates (which denote the relations of identity and set-theoretic membership) by repeated applications of four operators that are analogues of the well-known operations of relative product, conversion, Boolean addition, and complementation. All mathematical statements are expressed as equations between predicates. There are ten logical axiom schemata and just one rule of inference: the one of replacing equals by equals, familiar from high school algebra. Though such a simple formalism may appear limited in its powers of expression and proof, this book proves quite the opposite. The authors show that it provides a framework for the formalization of practically all known systems of set theory, and hence for the development of all classical mathematics. The book contains numerous applications of the main results to diverse areas of foundational research: propositional logic; semantics; first-order logics with finitely many variables; definability and axiomatizability questions in set theory, Peano arithmetic, and real number theory; representation and decision problems in the theory of relation algebras; and decision problems in equational logic. (shrink)

In this paper I propose a new approach to the foundation of mathematics: non-monotonic set theory. I present two completely different methods to develop set theories based on adaptive logics. For both theories there is a finitistic non-triviality proof and both theories contain (a subtle version of) the comprehension axiom schema. The first theory contains only a maximal selection of instances of the comprehension schema that do not lead to inconsistencies. The second allows for all the instances, also (...) the inconsistent ones, but restricts the conclusions one can draw from them in order to avoid triviality. The theories have enough expressive power to form a justification/explication for most of the established results of classical mathematics. They are therefore not limited by Gödel’s incompleteness theorems. This remarkable result is possible because of the non-recursive character of the final proofs of theorems of non-monotonic theories. I shall argue that, precisely because of the computational complexity of these final proofs, we cannot claim that non-monotonic theories are ideal foundations for mathematics. Nevertheless, thanks to their strength, first order language and the recursive dynamic (defeasible) proofs of theorems of the theory, the non-monotonic theories form (what I call) interesting pragmatic foundations. (shrink)

For a set A of non-negative integers, let D be the set of non-negative differences of elements of A. Clearly, if A is computable, then D is computably enumerable. We show that every simple set which contains 0 is the difference set of some computable set and that every computably enumerable set is computably isomorphic to the difference set of some computable set. Also, we prove that there is a computable set which is the difference set (...) of the complement of some computably enumerable set but not of any computably enumerable set. Finally, we show that every arithmetic set is in the Boolean algebra generated from the computable sets by the difference operator D and the Boolean operations. (shrink)

This is the first in a series of papers on Predicative Algebraic Set Theory, where we lay the necessary groundwork for the subsequent parts, one on realizability [B. van den Berg, I. Moerdijk, Aspects of predicative algebraic set theory II: Realizability, Theoret. Comput. Sci. . Available from: arXiv:0801.2305, 2008], and the other on sheaves [B. van den Berg, I. Moerdijk, Aspects of predicative algebraic set theory III: Sheaf models, 2008 ]. We introduce the notion of a predicative (...) category with small maps and show that it provides a sound and complete semantics for constructive set theories like IZF and CZF. The main technical contribution of this paper is that it shows in detail that such categories can always be conservatively embedded in categories that are exact. These exactness properties play a crucial rôle in showing that predicative categories with small maps contain models of set theory and that they are closed under sheaves and realizability. We will prove the former statement in this paper as well, leaving a proof of the closure properties to the papers on realizability and sheaves as mentioned above. (shrink)

Constructive set theory a' la Myhill-Aczel has been extended in (Cantini and Crosilla 2008, Cantini and Crosilla 2010) to incorporate a notion of (partial, non--extensional) operation. Constructive operational set theory is a constructive and predicative analogue of Beeson's Inuitionistic set theory with rules and of Feferman's Operational set theory (Beeson 1988, Feferman 2006, Jaeger 2007, Jaeger 2009, Jaeger 1009b). This paper is concerned with an extension of constructive operational set theory (Cantini and Crosilla 2010) by (...) a uniform operation of Transitive Closure, \tau. Given a set a, \tau produces its transitive closure \tau a. We show that the theory ESTE of (Cantini and Crosilla 2010) augmented by \tau is still conservative over Peano Arithmetic. (shrink)

This two-volume work bridges the gap between introductory expositions of logic or set theory on one hand, and the research literature on the other. It can be used as a text in an advanced undergraduate or beginning graduate course in mathematics, computer science, or philosophy. The volumes are written in a user-friendly conversational lecture style that makes them equally effective for self-study or class use. Volume II, on formal (ZFC) set theory, incorporates a self-contained 'chapter 0' on proof (...) techniques so that it is based on formal logic, in the style of Bourbaki. The emphasis on basic techniques will provide the reader with a solid foundation in set theory and provides a context for the presentation of advanced topics such as absoluteness, relative consistency results, two expositions of Godel's constructible universe, numerous ways of viewing recursion, and a chapter on Cohen forcing. (shrink)

We consider all combinatorially possible systems corresponding to subsets of finite set theory (i.e., Zermelo-Fraenkel set theory without the axiom of infinity) and for each of them either provide a well-founded locally finite graph that is a model of that theory or show that this is impossible. To that end, we develop the technique of _axiom closure of graphs_.

As proved recently, the satisfaction problem for all prenex formulae in the set-theoretic Bernays-Shönfinkel-Ramsey class is semi-decidable over von Neumann's cumulative hierarchy. Here that semi-decidability result is strengthened into a decidability result for the same collection of formulae.

Using two distinct membership symbols makes possible to base set theory on one general axiom schema of comprehension. Is the resulting system consistent? Can set theory and mathematics be based on a single axiom schema of comprehension?

Mīmāṁsā, an Indian hermeneutics provides an exhaustive methodology to interpret Vedic statements. A formalism namely, Mīmāṁsā Inspired Representation of Actions has already been proposed in a preliminary manner. This paper expands the formalism logically and includes Syntax and Semantics covering Soundness and Completeness. Here, several interpretation techniques from Mīmāṁsā have been considered for formalising the statements. Based on these, instructions that denote actions are categorized into positive and prohibitive unconditional imperatives and conditional imperatives that enjoin reason, temporal action and goal. (...) These instructions are evaluated to three values S, V and N. If the instruction is executed with the intention of goal, then it acquires the value of S; if the intention of goal is present and the instruction is not executed, then it assumes the value of V; and if there is no intention of goal, then the instruction is evaluated to N. This formalism has also been applied in different computational settings such as AI planning, Robotics, task analysis and classification of natural language instructions. An outline of these applications and the comparison of this formalism with other relevant theories are also presented in this paper. (shrink)

We exploit properties of certain directed graphs, obtained from the families of sets with special effective enumeration properties, to generalize several results in computable model theory to higher levels of the hyperarithmetical hierarchy. Families of sets with such enumeration features were previously built by Selivanov, Goncharov, and Wehner. For a computable successor ordinal α, we transform a countable directed graph into a structure such that has a isomorphic copy if and only if has a computable isomorphic (...) copy.A computable structure is categorical if for all computable isomorphic copies of , there is an isomorphism from onto , which is . We prove that for every computable successor ordinal α, there is a computable, categorical structure, which is not relatively categorical. This generalizes the result of Goncharov that there is a computable, computably categorical structure, which is not relatively computably categorical.An additional relation R on the domain of a computable structure is intrinsically on if in all computable isomorphic copies of , the image of R is . We prove that for every computable successor ordinal α, there is an intrinsically relation on a computable structure, which not relatively intrinsically . This generalizes the result of Manasse that there is an intrinsically computably enumerable relation on a computable structure, which is not relatively intrinsically computably enumerable.The dimension of a structure is the number of computable isomorphic copies, up to isomorphisms. We prove that for every computable successor ordinal α and every n≥1, there is a computable structure with dimension n. This generalizes the result of Goncharov that there is a structure of computable dimension n for every n≥1.Finally, we prove that for every computable successor ordinal α, there is a countable structure with isomorphic copies in just the Turing degrees of sets X such that relative to X is not . In particular, for every finite n, there is a structure with isomorphic copies in exactly the non- Turing degrees. This generalizes the result obtained by Wehner, and independently by Slaman, that there is a structure with isomorphic copies in exactly the nonzero Turing degrees. (shrink)

This edited work presents contemporary mathematical practice in the foundational mathematical theories, in particular set theory and the univalent foundations. It shares the work of significant scholars across the disciplines of mathematics, philosophy and computer science. Readers will discover systematic thought on criteria for a suitable foundation in mathematics and philosophical reflections around the mathematical perspectives. The first two sections focus on the two most prominent candidate theories for a foundation of mathematics. Readers may trace current research in set (...) theory, which has widely been assumed to serve as a framework for foundational issues, as well as new material elaborating on the univalent foundations, considering an approach based on homotopy type theory (HoTT). The further sections then build on this and are centred on philosophical questions connected to the foundations of mathematics. Here, the authors contribute to discussions on foundational criteria with more general thoughts on the foundations of mathematics which are not connected to particular theories. This book shares the work of some of the most important scholars in the fields of set theory (S. Friedman), non-classical logic (G. Priest) and the philosophy of mathematics (P. Maddy). The reader will become aware of the advantages of each theory and objections to it as a foundation, following the latest and best work across the disciplines and it is therefore a valuable read for anyone working on the foundations of mathematics or in the philosophy of mathematics. (shrink)

As is well-known, the Bernays-Schönfinkel-Ramsey class of all prenex ∃*∀* -sentences which are valid in classical first-order logic is decidable. This paper paves the way to an analogous result which the authors deem to hold when the only available predicate symbols are ∈ and =, no constants or function symbols are present, and one moves inside a (rather generic) Set Theory whose axioms yield the well-foundedness of membership and the existence of infinite sets. Here semi-decidability of the satisfiability problem (...) for the BSR class is proved by following a purely semantic approach, the remaining part of the decidability result being postponed to a forthcoming paper. (shrink)

Reasonning in naive set theory (with unlimited comprehension), we derive a paradox (a formal contradiction) which can be seen as a variant of the Burali-Forti paradox.

This book deals with two important branches of mathematics, namely, logic and set theory. Logic and set theory are closely related and play very crucial roles in the foundation of mathematics, and together produce several results in all of mathematics. The topics of logic and set theory are required in many areas of physical sciences, engineering, and technology. The book offers solved examples and exercises, and provides reasonable details to each topic discussed, for easy understanding. The book (...) is designed for readers from various disciplines where mathematical logic and set theory play a crucial role. The book will be of interested to students and instructors in engineering, mathematics, computer science, and technology. (shrink)

We present correct and natural development of fundamental analysis in a predicative set theory we call PZFU\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathsf {PZF}^{\mathsf {U}}}$$\end{document}. This is done by using a delicate and careful choice of those Dedekind cuts that are adopted as real numbers. PZFU\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathsf {PZF}^{\mathsf {U}}}$$\end{document} is based on ancestral logic rather than on first-order logic. Its key feature is that it is definitional in the (...) sense that every object which is shown in it to exist is defined by some closed term of the theory. This allows for a very concrete, computationally-oriented model of it, and makes it very suitable for MKM and ITP. The development of analysis in PZFU\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathsf {PZF}^{\mathsf {U}}}$$\end{document} does not involve coding, and the definitions it provides for the basic notions are the natural ones, almost the same as one can find in any standard analysis book. (shrink)

Three systems of double extension set theory have been proposed by Andrzej Kisielewicz in two papers. In this paper, it is shown that the two stronger systems are inconsistent, and that the third, weakest system does not admit extensionality for general sets or the use of general sets as parameters in its comprehension scheme. The parameter-free version of the comprehension principle of double extension set theory is also shown to be inconsistent with extensionality. The definitions of the systems (...) and a self-contained exposition of their properties is given, sufficient to develop the inconsistency proofs. (shrink)

This commentary is an elaboration on Schyns, Goldstone & Thibaut's proposal for flexible features in categorization in the light of three areas not explicitly discussed by the authors: connectionist models of categorization, computational learning theory, and constructivist theories of the mind. In general, the authors' proposal is strongly supported, paving the way for model extensions and for interesting novel cognitive research. Nor is the authors' proposal incompatible with theories positing some fixed set of features.

Since the world is full of indeterminacy, the Neutrosophics found their place into contemporary research. We now introduce for the first time the notions of Neutrosophic Crisp Sets and Neutrosophic Topology on Crisp Sets. We develop the 2012 notion of Neutrosophic Topological Spaces and give many practical examples. Neutrosophic Science means development and applications of Neutrosophic Logic, Set, Measure, Integral, Probability etc., and their applications in any field. It is possible to define the neutrosophic measure and consequently the neutrosophic integral (...) and neutrosophic probability in many ways, because there are various types of indeterminacies, depending on the problem we need to solve. Indeterminacy is different from randomness. Indeterminacy can be caused by physical space, materials and type of construction, by items involved in the space, or by other factors. In 1965 [51], Zadeh generalized the concept of crisp set by introducing the concept of fuzzy set, corresponding to the situation in which there is no precisely defined set;there are increasing applications in various fields, including probability, artificial intelligence, control systems, biology and economics. Thus, developments in abstract mathematics using the idea of fuzzy sets possess sound footing. In accordance, fuzzy topological spaces were introduced by Chang [12] and Lowen [33]. After the development of fuzzy sets, much attention has been paid to the generalization of basic concepts of classical topology to fuzzy sets and accordingly developing a theory of fuzzy topology [1-58]. In 1983, the intuitionistic fuzzy set was introduced by K. Atanassov [55, 56, 57] as a generalization of the fuzzy set, beyond the degree of membership and the degree of non-membership of each element. In 1999 and 2002, Smarandache [71, 72, 73, 74] defined the notion of Neutrosophic Sets, which is a generalization of Zadeh’s fuzzy set and Atanassov's intuitionistic fuzzy set. Some neutrosophic concepts have been investigated by Salama et al. [61-70]. Forwarding the study of neutrosophic sets, this book consists of seven chapters, targeting to:  generalize the previous studies in [1-59], and[91-94] so to define the neutrosopic crisp set and neutrosophic set concepts;  discuss their main properties; A. A. Salama & Florentin Smarandache  introduce and study some concepts of neutrosophic crisp and neutrosophic topological spaces and deduce their properties;  deduce many types of functions and give the relationships between different neutrosophic topological spaces, which helps to build new properties of neutrosophic topological spaces;  stress once more the importance of Neutrosophic Ideal as a nontrivial extension of neutrosophic set and neutrosophic logic [71, 72, 73, 74];  propose applications on computer sciences by using neutrosophic sets. (shrink)

For classical sets one has with the cumulative hierarchy of sets, with axiomatizations like the system ZF, and with the category SET of all sets and mappings standard approaches toward global universes of all sets.We discuss here the corresponding situation for fuzzy set theory. Our emphasis will be on various approaches toward (more or less naively formed) universes of fuzzy sets as well as on axiomatizations, and on categories of fuzzy sets.

We investigate a contractionless naive set theory, due to Grisin [11]. We prove that the theory is undecidable.

Many authors in the discipline as well as outsiders have claimed that the main results from Mathematical Economics are far removed from real world phenomena. A more precise version of this position is that one of the main reasons for this unrealistic stance is the use of the wrong formal tools. So, for example, it has been pointed out that the computability of choice functions as well as the existence of economic equilibria and of states of the world may not (...) be ensured in general if the assumed set theory is ZFC. We will show that there exists a very natural set theory that overcomes some formal limitations of contemporary economic theory. A switch to an alternative set theory helps to obtain in a more natural way results widely accepted by mathematical economists. Moreover, alternative set-theoretical frameworks convey different intuitions about how agents behave when solving problems. We claim that AFA−+AD+DC is the adequate alternative set-theoretical universe for economic theory. (shrink)

then essentially characterized the hypotheses that mechanical scientists can successfully decide in the limit in terms of arithmetic complexity. These ideas were developed still further by Peter Kugel [4]. In this paper, I extend this approach to obtain characterizations of identification in the limit, identification with bounded mind-changes, and identification in the short run, both for computers and for ideal agents with unbounded computational abilities. The characterization of identification with n mind-changes entails, as a corollary, an exact arithmetic characterization of (...) Putnam's n-trial predicates, which closes a gap of a factor of two in Putnam's original characterization [12]. (shrink)

The naive set theory problem is to begin with a full comprehension axiom, and to find a logic strong enough to prove theorems, but weak enough not to prove everything. This paper considers the sub-problem of expressing extensional identity and the subset relation in paraconsistent, relevant solutions, in light of a recent proposal from Beall, Brady, Hazen, Priest and Restall [4]. The main result is that the proposal, in the context of an independently motivated formalization of naive set (...) class='Hi'>theory, leads to triviality. (shrink)

In this thesis, we study the complexity of some mathematical problems: in particular, those arising in computable analysis and algorithmic learning theory for algebraic structures. Our study is not limited to these two areas: indeed, in both cases, the results we obtain are tightly connected to ideas and tools coming from different areas of mathematical logic, including for example descriptive set theory and reverse mathematics.After giving the necessary preliminaries, we first study the uniform computational strength of the (...) Cantor–Bendixson theorem in the Weihrauch lattice. This work falls into the program connecting reverse mathematics and computable analysis via the framework of Weihrauch reducibility. We concentrate on problems related to perfect subsets of Polish spaces, studying the perfect set theorem, the Cantor–Bendixson theorem, and various problems arising from them. As far as we know, this is the first systematic study of problems at the level of $\mathbf {\Pi }^1_1\mathsf {-CA}_0$ in the Weihrauch lattice. We show that the strength of some of the problems we study depends on the topological properties of the Polish space under consideration, while others have the same strength once the space is rich enough.We continue considering problems related to (induced) subgraphs. We provide results on the (effective) Wadge complexity of sets of graphs, that are also used to determine the Weihrauch degree of certain decision problems. The decision problems we consider are defined for a fixed graph G, and they take as input a graph H, answering whether G is an (induced) subgraph of H: we also consider the opposite problem (i.e., answering whether H is an induced subgraph of G). We conclude this part on (induced) subgraphs considering the Weihrauch degree of “search problems.”These problems are defined for a fixed graph G, and they take as input a graph H such that G is an (induced) subgraph H: the output is a copy of G in H. In both cases, we highlight differences and analogies between the subgraph and the induced subgraph relation.We then move our attention to algorithmic learning theory, and we present the framework we use to study the learnability of families of algebraic structures: here, given a countable family of pairwise nonisomorphic structures $\mathfrak {K}$, a learner receives larger and larger pieces of an arbitrary copy of a structure in $\mathfrak {K}$ and, at each stage, is required to output a conjecture about the isomorphism type of such a structure. We say that $\mathfrak {K}$ is learnable if there exists a learner which eventually stabilizes to a correct guess. The framework was lacking a method for comparing the complexity of nonlearnable families, and so we propose a solution to this problem using tools coming from invariant descriptive set theory. To do so, we first prove that a family of structures is learnable if and only if its learning domain is continuously reducible to the relation $E_0$ of eventual agreement on infinite binary sequences and then, replacing $E_0$ with Borel equivalence relations of higher complexity, we obtain a new hierarchy of learning problems. This leads to the notion of E-learnability, where a family of structures $\mathfrak {K}$ is E-learnable, for a Borel equivalence relation E, if there is a continuous reduction from the isomorphism relation associated with $\mathfrak {K}$ to E. It is then natural to ask how the notion of E-learnability interacts with “classical” learning paradigms.Finally, we study the number of mind changes that a learner needs to learn a given family, both from a topological and a combinatorial point of view, and we consider how the complexity of a learner (in terms of Turing reducibility) affects the number of mind changes for learning a given family.Abstract prepared by Vittorio Cipriani.E-mail: [email protected]: https://air.uniud.it/handle/11390/1252226. (shrink)

A structural (as opposed to Zadeh's quantitative) approach to fuzziness is given, based on the operator "very", which is added to the language of set theory together with some elementary axioms about it. Due to the axiom of foundation and to a lifting axiom, the operator is proved trivial on the cumulative hierarchy of ZF. So we have to drop either foundation or lifting. Since fuzziness concerns complemented predicates rather than sets, a class theory is needed for the (...) very operator. And of them the Kelley-Morse (KM) theory is more appropriate for reasons of class existence. Several definable realizations of the very-operator are presented in KM⁻. In the last section we consider the operator "very" without the lifting axiom on classes of urelements. To each structurally fuzzy set X a traditional quantitative fuzzy set X̄ is assigned -- its quantitative representation. This way we are able partly to recover ordinary fuzzy sets from the structurally fuzzy ones. (shrink)

Volume II of Classical Recursion Theory describes the universe from a local (bottom-up or synthetical) point of view, and covers the whole spectrum, from the recursive to the arithmetical sets. The first half of the book provides a detailed picture of the computable sets from the perspective of Theoretical Computer Science. Besides giving a detailed description of the theories of abstract Complexity Theory and of Inductive Inference, it contributes a uniform picture of the most basic complexity classes, (...) ranging from small time and space bounds to the elementary functions, with a particular attention to polynomial time and space computability. It also deals with primitive recursive functions and larger classes, which are of interest to the proof theorist. The second half of the book starts with the classical theory of recursively enumerable sets and degrees, which constitutes the core of Recursion or Computability Theory. Unlike other texts, usually confined to the Turing degrees, the book covers a variety of other strong reducibilities, studying both their individual structures and their mutual relationships. The last chapters extend the theory to limit sets and arithmetical sets. The volume ends with the first textbook treatment of the enumeration degrees, which admit a number of applications from algebra to the Lambda Calculus. The book is a valuable source of information for anyone interested in Complexity and Computability Theory. The student will appreciate the detailed but informal account of a wide variety of basic topics, while the specialist will find a wealth of material sketched in exercises and asides. A massive bibliography of more than a thousand titles completes the treatment on the historical side. (shrink)

Computability theoretic aspects of Polish metric spaces are studied by adapting notions and methods of computable structure theory. In this dissertation, we mainly investigate index sets and classification problems for computably presentable Polish metric spaces. We find the complexity of a number of index sets, isomorphism problems, and embedding problems for computably presentable metric spaces. We also provide several computable structure theory results related to some classical Polish metric spaces such as the Urysohn space $\mathbb {U}$, (...) the Cantor space $2^{\mathbb {N}}$, the Baire space $\mathbb {N}^{\mathbb {N}}$, and spaces of continuous functions.Abstract prepared by Teerawat Thewmorakot.E-mail: [email protected]. (shrink)

What can computers do in principle? What are their inherent theoretical limitations? These are questions to which computer scientists must address themselves. The theoretical framework which enables such questions to be answered has been developed over the last fifty years from the idea of a computable function: intuitively a function whose values can be calculated in an effective or automatic way. This book is an introduction to computability theory (or recursion theory as it is traditionally known to (...) mathematicians). Dr Cutland begins with a mathematical characterisation of computable functions using a simple idealised computer (a register machine); after some comparison with other characterisations, he develops the mathematical theory, including a full discussion of non-computability and undecidability, and the theory of recursive and recursively enumerable sets. The later chapters provide an introduction to more advanced topics such as Gildel's incompleteness theorem, degrees of unsolvability, the Recursion theorems and the theory of complexity of computation. Computability is thus a branch of mathematics which is of relevance also to computer scientists and philosophers. Mathematics students with no prior knowledge of the subject and computer science students who wish to supplement their practical expertise with some theoretical background will find this book of use and interest. (shrink)

We describe an organizing framework for the study of infinitary combinatorics. This framework is Čech cohomology. It describes ZFC principles distinguishing among the ordinals of the form $\omega _n$. More precisely, this framework correlates each $\omega _n$ with an $$ -dimensional generalization of Todorcevic’s walks technique, and begins to account for that technique’s “unreasonable effectiveness” on $\omega _1$.We show in contrast that on higher cardinals $\kappa $, the existence of these principles is frequently independent of the ZFC axioms. Finally, we (...) detail implications of these phenomena for the computation of strong homology groups and higher derived limits, deriving independence results in algebraic topology and homological algebra, respectively, in the process.Abstract prepared by Jeffrey Bergfalk.E-mail: [email protected]. (shrink)

We don't yet have adequate theories of what the human mind is representing when it represents a social group. Worse still, many people think we do. This mistaken belief is a consequence of the state of play: Until now, researchers have relied on their own intuitions to link up the conceptsocial groupon the one hand and the results of particular studies or models on the other. While necessary, this reliance on intuition has been purchased at a considerable cost. When looked (...) at soberly, existing theories of social groups are either (i) literal, but not remotely adequate (such as models built atop economic games), or (ii) simply metaphorical (typically a subsumption or containment metaphor). Intuition is filling in the gaps of an explicit theory. This paper presents a computational theory of what, literally, a group representation is in the context of conflict: It is the assignment of agents to specific roles within a small number of triadic interaction types. This “mental definition” of a group paves the way for acomputational theory of social groups– in that it provides a theory of what exactly the information-processing problem of representing and reasoning about a group is. For psychologists, this paper offers a different way to conceptualize and study groups, and suggests that a non-tautological definition of a social group is possible. For cognitive scientists, this paper provides a computational benchmark against which natural and artificial intelligences can be held. (shrink)

Social choice rules are often evaluated and compared by inquiring whether they satisfy certain desirable criteria such as the Condorcet criterion, which states that an alternative should always be chosen when more than half of the voters prefer it over any other alternative. Many of these criteria can be formulated in terms of choice sets that single out reasonable alternatives based on the preferences of the voters. In this paper, we consider choice sets whose definition merely relies on the pairwise (...) majority relation. These sets include the Copeland set, the Smith set, the Schwartz set, von Neumann-Morgenstern stable sets, the Banks set, and the Slater set. We investigate the relationships between these sets and completely characterize their computational complexity, which allows us to obtain hardness results for entire classes of social choice rules. (shrink)

Aleksandar Ignjatović. Delineating Classes of Computational Complexity via Second Order Theories with Weak Set Existence Principles (I).