On a very natural conception of sets, every set has an absolute complement. The ordinary cumulative hierarchy dismisses this idea outright. But we can rectify this, whilst retaining classical logic. Indeed, we can develop a boolean algebra of sets arranged in well-ordered levels. I show this by presenting Boolean Level Theory, which fuses ordinary Level Theory (from Part 1) with ideas due to Thomas Forster, Alonzo Church, and Urs Oswald. BLT neatly implement Conway’s games and surreal numbers; (...) and a natural extension of BLT is definitionally equivalent with ZF. (shrink)

Using a combinatorial theorem of Herwig on extending partial isomorphisms of relational structures, we give a simple proof that certain classes of algebras, including Crs, polyadic Crs, and WA, have the `finite base property' and have decidable universal theories, and that any finite algebra in each class is representable on a finite set.

Using a combinatorial theorem of Herwig on extending partial isomorphisms of relational structures, we give a simple proof that certain classes of algebras, including Crs, polyadic Crs, and WA, have the `finite base property' and have decidable universal theories, and that any finite algebra in each class is representable on a finite set.

The algebra of sets has, basically, two different types of symbols. One type of symbol (∩, ?, +, ?) defines another set from two other sets. A second type of symbol (?, ?, =, ?) makes a proposition about two sets. When the construction of these two types of symbols is based on the same four-dot matrix as the logic symbols described in a previous paper, the three symbol types then dovetail together into a harmonious whole (...) that greatly simplifies derivation in the algebra of sets. (shrink)

We introduce a new sheaf-theoretic construction called the ideal completion of a category and investigate its logical properties. We show that it satisfies the axioms for a category of classes in the sense of Joyal and Moerdijk [17], so that the tools of algebraic set theory can be applied to produce models of various elementary set theories. These results are then used to prove the conservativity of different set theories over various classical and constructive type theories.

We generalize the construction of lattice-valued models of set theory due to Takeuti, Titani, Kozawa and Ozawa to a wider class of algebras and show that this yields a model of a paraconsistent logic that validates all axioms of the negation-free fragment of Zermelo-Fraenkel set theory.

We show that the conceptual distance between any two theories of first-order logic is the same as the generator distance between their Lindenbaum–Tarski algebras of concepts. As a consequence of this, we show that, for any two arbitrary mathematical structures, the generator distance between their meaning algebras (also known as cylindric set algebras) is the same as the conceptual distance between their first-order logic theories. As applications, we give a complete description for the distances between meaning algebras corresponding to structures (...) having at most three elements and show that this small network represents all the possible conceptual distances between complete theories. As a corollary of this, we will see that there are only two non-trivial structures definable on three-element sets up to conceptual equivalence (i.e., up to elementary plus definitional equivalence). (shrink)

One of the basic theorems in universal algebra is Birkhoff's variety theorem: the smallest equationally axiomatizable class containing a class K of algebras coincides with the class obtained by taking homomorphic images of subalgebras of direct products of elements of K. G. Gratzer asked whether the variety theorem is equivalent to the Axiom of Choice. In 1980, two of the present authors proved that Birkhoff's theorem can already be derived in ZF. Surprisingly, the Axiom of Foundation plays a crucial (...) role here: we show that Birkhoff's theorem cannot be derived in ZF + AC {Foundation}. even if we add Foundation for Finite Sets. We also prove that the variety theorem is equivalent to a purely set-theoretical statement, the Collection Principle. This principle is independent of $ZF \{\operatorname{Foundation}$ . The second part of the paper deals with further connections between axioms of ZF-set theory and theorems of universal algebra. (shrink)

In this paper, we give an algebraic completeness theorem for constructive logic with strong negation in terms of finite rough set-based Nelson algebras determined by quasiorders. We show how for a quasiorder R, its rough set-based Nelson algebra can be obtained by applying Sendlewski’s well-known construction. We prove that if the set of all R-closed elements, which may be viewed as the set of completely defined objects, is cofinal, then the rough set-based Nelson algebra determined by the quasiorder (...) R forms an effective lattice, that is, an algebraic model of the logic E 0, which is characterised by a modal operator grasping the notion of “to be classically valid”. We present a necessary and sufficient condition under which a Nelson algebra is isomorphic to a rough set-based effective lattice determined by a quasiorder. (shrink)

We prove the following theorems: (1) If X has strong measure zero and if Y has strong first category, then their algebraic sum has property s 0 . (2) If X has Hurewicz's covering property, then it has strong measure zero if, and only if, its algebraic sum with any first category set is a first category set. (3) If X has strong measure zero and Hurewicz's covering property then its algebraic sum with any set in APC ' is a (...) set in APC '. (APC ' is included in the class of sets always of first category, and includes the class of strong first category sets.) These results extend: Fremlin and Miller's theorem that strong measure zero sets having Hurewicz's property have Rothberger's property, Galvin and Miller's theorem that the algebraic sum of a set with the γ-property and of a first category set is a first category set, and Bartoszynski and Judah's characterization of SR M -sets. They also characterize the property (*) introduced by Gerlits and Nagy in terms of older concepts. (shrink)

Let T be a one-based theory. We define a notion of width, in the case of T having the finiteness property, for the lattice of finitely generated algebraically closed sets and prove Theorem. Let T be one-based with the finiteness property. If T is of bounded width, then every type in T is nonorthogonal to a weight one type. If T is countable, the converse is true.

The set (X, J) of fuzzy subsetsf:XJ of a setX can be equipped with a structure of -valued ukasiewicz-Moisil algebra, where is the order type of the totally ordered setJ. Conversely, every ukasiewicz-Moisil algebra — and in particular every Post algebra — is isomorphic to a subalgebra of an algebra of the form (X, J), whereJ has an order type . The first result of this paper is a characterization of those -valued ukasiewicz-Moisil algebras which are (...) isomorphic to an algebra of the form (X, J) (Theorem 1). Then we prove that (X, J) is a Post algebra if and only if the setJ is dually well-ordered (Theorem 2) and we give a characterization of those -valued Post algebras with are isomorphic to an algebra of the form (X, J) (Theorem 3 and Proposition 2). (shrink)

The aim of this paper is to give a new proof for the decidability and finite model property of first-order logic with two variables (without function symbols), using a combinatorial theorem due to Herwig. The results are proved in the framework of polyadic equality set algebras of dimension two (Pse 2 ). The new proof also shows the known results that the universal theory of Pse 2 is decidable and that every finite Pse 2 can be represented on a finite (...) base. Since the class Cs 2 of cylindric set algebras of dimension 2 forms a reduct of Pse 2 , these results extend to Cs 2 as well. (shrink)

The aim of this paper is to give a new proof for the decidability and finite model property of first-order logic with two variables, using a combinatorial theorem due to Herwig. The results are proved in the framework of polyadic equality set algebras of dimension two. The new proof also shows the known results that the universal theory of Pse$_2$ is decidable and that every finite Pse$_2$ can be represented on a finite base. Since the class Cs$_2$ of cylindric set (...) algebras of dimension 2 forms a reduct of Pse$_2$, these results extend to Cs$_2$ as well. (shrink)

We consider the sets definable in the countable models of a weakly o-minimal theory T of totally ordered structures. We investigate under which conditions their Boolean algebras are isomorphic , in other words when each of these definable sets admits, if infinite, an infinite coinfinite definable subset. We show that this is true if and only if T has no infinite definable discrete subset. We examine the same problem among arbitrary theories of mere linear orders. Finally we prove (...) that, within expansions of Boolean lattices, every weakly o-minimal theory is p-ω-categorical. (shrink)

This paper constructs models of intuitionistic set theory in suitable categories. First, a Basic Intuitionistic Set Theory (BIST) is stated, and the categorical semantics are given. Second, we give a notion of an ideal over a category, using which one can build a model of BIST in which a given topos occurs as the sets. And third, a sheaf model is given of a Basic Intuitionistic Class Theory conservatively extending BIST. The paper extends the results in [2] by introducing (...) a new and perhaps more natural notion of ideal, and in the class theory of part three. (shrink)

Let p be prime number, K be a p‐adically closed field, a semi‐algebraic set defined over K and the lattice of semi‐algebraic subsets of X which are closed in X. We prove that the complete theory of eliminates quantifiers in a certain language, the ‐structure on being an extension by definition of the lattice structure. Moreover it is decidable, contrary to what happens over a real closed field for. We classify these ‐structures up to elementary equivalence, and get in particular (...) that the complete theory of only depends on m, not on K nor even on p. As an application we obtain a classification of semi‐algebraic sets over countable p‐adically closed fields up to so‐called “pre‐algebraic” homeomorphisms. (shrink)

We construct an algebra of generalized functions endowed with a canonical embedding of the space of Schwartz distributions.We offer a solution to the problem of multiplication of Schwartz distributions similar to but different from Colombeau’s solution.We show that the set of scalars of our algebra is an algebraically closed field unlike its counterpart in Colombeau theory, which is a ring with zero divisors. We prove a Hahn–Banach extension principle which does not hold in Colombeau theory. We establish a (...) connection between our theory with non-standard analysis and thus answer, although indirectly, a question raised by Colombeau. This article provides a bridge between Colombeau theory of generalized functions and non-standard analysis. (shrink)

This paper is about pairing relation algebras as well as fork algebras and related subjects. In the 1991-92 fork algebra papers it was conjectured that fork algebras admit a strong representation theorem . Then, this conjecture was disproved in the following sense: a strong representation theorem for all abstract fork algebras was proved to be impossible in most set theories including the usual one as well as most non-well-founded set theories. Here we show that the above quoted conjecture can (...) still be made true by choosing an appropriate set theory as our foundation of mathematics. Namely, we show that there are non-well-founded set theories in which every abstract fork algebra is representable in the strong sense, i.e. it is isomorphic to a set relation algebra having a fork operation which is obtained with the help of the real pairing function. Further, these non-well-founded set theories are consistent if usual set theory is consistent. Finally, we will discuss related developments in propositional multi-modal logics of quantification and substitution, in algebraic logic e.g. cylindric algebras, the so called finitization problem, and applications to a logic introduced and studied in Tarski-Givant [42]. In particular, representable, weakly higher order cylindric algebras are finitely axiomatizable in a set theory which admits the axiom of foundation for finite sets. (shrink)

Intervals in boolean algebras enter into the study of conditional assertions (or events) in two ways: directly, either from intuitive arguments or from Goodman, Nguyen and Walker's representation theorem, as suitable mathematical entities to bear conditional probabilities, or indirectly, via a representation theorem for the family of algebras associated with de Finetti's three-valued logic of conditional assertions/events. Further representation theorems forge a connection with rough sets. The representation theorems and an equivalent of the boolean prime ideal theorem yield an (...) algebraic completeness theorem for the three-valued logic. This in turn leads to a Henkin-style completeness theorem. Adequacy with respect to a family of Kripke models for de Finetti's logic, Łukasiewicz's three-valued logic and Priest's Logic of Paradox is demonstrated. The extension to first-order yields a short proof of adequacy for Körner's logic of inexact predicates. (shrink)

In this article, we shall show the generalized notions of distributivity of Boolean algebras have essential relations with several axioms and properties of set theory, say the Axiom of Choice, the Axiom of Dependence Choice, the Prime Ideal Theorems, Martin's axioms, Lebesgue measurability and so on.

S. Ulam asked about the number of nonisomorphic projective algebras with k generators. This paper answers his question for projective algebras of finite dimension at least three and shows that there are the maximum possible number, continuum many, of nonisomorphic one-generated structures of finite dimension n, where n is at least three, of the following kinds: projective set algebras, projective algebras, diagonal-free cylindric set algebras, diagonal-free cylindric algebras, cylindric set algebras, and cylindric algebras. The results of this paper extend earlier (...) results to the collection of cylindric set algebras and provide a uniform proof for all the results. Extensions of these results for dimension two are discussed where some modifications on the hypotheses are needed. Furthermore for α |geq 2, the number of isomorphism classes of regular locally finite cylindric set algebras of dimension α of the following two kinds are computed: ones of power κ for infinite $\kappa \geq|\alpha|$ , and ones with a single generator. (shrink)

We consider formal theories synonymous with various free categories . Their Lindenbaum algebras may be described as the lattices of subobjects of a terminator. These theories have intuitionistic logic. We show that the Lindenbaum algebras of second order and higher order arithmetic , and set theory are not isomorphic to the Lindenbaum algebras of first order theories such as arithmetic . We also show that there are only five kernels of representations of the free Heyting algebra on one generator (...) in these Lindenbaum algebras. (shrink)

Multiverse Views in set theory advocate the claim that there are many universes of sets, no-one of which is canonical, and have risen to prominence over the last few years. One motivating factor is that such positions are often argued to account very elegantly for technical practice. While there is much discussion of the technical aspects of these views, in this paper I analyse a radical form of Multiversism on largely philosophical grounds. Of particular importance will be an account (...) of reference on the Multiversist conception, and the relativism that it implies. I argue that analysis of this central issue in the Philosophy of Mathematics indicates that Radical Multiversism must be algebraic, and cannot be viewed as an attempt to provide an account of reference without a softening of the position. (shrink)

Post algebras of order + as a semantic foundation for +-valued predicate calculi were examined in [5]. In this paper Post spaces of order + being a modification of Post spaces of order n2 (cf. Traczyk [8], Dwinger [1], Rasiowa [6]) are introduced and Post fields of order + are defined. A representation theorem for Post algebras of order + as Post fields of sets is proved. Moreover necessary and sufficient conditions for the existence of representations preserving a given (...) set of infinite joins and infinite meets are established and applied to Lindenbaum-Tarski algebras of elementary theories based on +-valued predicate calculi in order to obtain a topological characterization of open theories. (shrink)

This book explains, in lay terms, the surprisingly simple system of mathematical logic used in digital computer circuitry. Anecdotal in its style and often funny, it follows the development of this logic system from its origins in Victorian England to its rediscovery in this century as the foundation of all modern computing machinery. ONES AND ZEROS will be enjoyed by anyone who has a general interest in science and technology.

The semantics of directional prepositions is investigated from the perspective of aspect. What distinguishes telic PPs (like to the house) from atelic PPs (like towards the house), taken as denoting sets of paths, is their algebraic structure: atelic PPs are cumulative, closed under the operation of concatenation, telic PPs are not. Not only does this allow for a natural and compositional account of how PPs contribute to the aspect of a sentence, but it also guides our understanding of the (...) lexical semantics of prepositions in important ways. Semantically, prepositions turn out to be quite similar to nouns and verbs. Nominal distinctions (like singular and plural, mass and count) and verbal classes (like semelfactives and degree achievements) have their prepositional counterparts. (shrink)

The infinite-valued logic of ukasiewicz was originally defined by means of an infinite-valued matrix. ukasiewicz took special forms of negation and implication as basic connectives and proposed an axiom system that he conjectured would be sufficient to derive the valid formulas of the logic; this was eventually verified by M. Wajsberg. The algebraic counterparts of this logic have become know as Wajsberg algebras. In this paper we show that a Wajsberg algebra is complete and atomic (as a lattice) if (...) and only if it is a direct product of finite Wajsberg chains. The classical characterization of complete and atomic Boolean algebras as fields of sets is a particular case of this result. (shrink)

Let A₁,..., An, An+1 be a finite sequence of algebras of sets given on a set X, $\cup _{k=1}^{n}{\cal A}_{k}\neq \germ{P}(X)$, with more than $\frac{4}{3}n$ pairwise disjoint sets not belonging to An+1. It was shown in [4] and [5] that in this case $\cup _{k=1}^{n+1}{\cal A}_{k}\neq \germ{P}(X)$. Let us consider, instead An+1, a finite sequence of algebras An+1,..., An+l. It turns out that if for each natural i ≤ l there exist no less than $\frac{4}{3}(n+l)-\frac{l}{24}$ pairwise disjoint (...) class='Hi'>sets not belonging to An+i, then $\cup _{k=1}^{n+1}{\cal A}_{k}\neq \germ{P}(X)$. But if l ≥ 195 and if for each natural i ≤ l there exist no less than $\frac{4}{3}(n+l)-\frac{l}{15}$ pairwise disjoint sets not belonging to An+i, then $\cup _{k=1}^{n+1}{\cal A}_{k}\neq \germ{P}(X)$. After consideration of finite sequences of algebras, it is natural to consider countable sequences of algebras. We obtained two essentially important theorems on a countable sequence of almost σ-algebras (the concept of almost σ-algebra was introduced in [4]). (shrink)

Dougherty, R., Critical points in an algebra of elementary embeddings, Annals of Pure and Applied Logic 65 211-241.Given two elementary embeddings from the collection of sets of rank less than λ to itself, one can combine them to obtain another such embedding in two ways: by composition, and by applying one to the other. Hence, a single such nontrivial embedding j generates an algebra of embeddings via these two operations, which satisfies certain laws . Laver has shown, (...) among other things, that this algebra is free on one generator with respect to these laws.The set of critical points of members of this algebra is the subject of this paper. This set contains the critical point κ0 of j, as well as all of the other ordinals κn in the critical sequence of j ). But the set includes many other ordinals as well. The main result of this paper is that the number of critical points below κn grows so quickly with n that it dominates any primitive recursive function. In fact, it grows faster than the Ackermann function, and even faster than a slow iterate of the Ackermann function. Further results show that, even just below κ4, one can find so many critical points that the number is only expressible using fast-growing hierarchies of iterated functions. (shrink)

A DO model (here also referred to a Paris model) is a model of set theory all of whose ordinals are first order definable in . Jeffrey Paris (1973) initiated the study of DO models and showed that (1) every consistent extension T of ZF has a DO model, and (2) for complete extensions T, T has a unique DO model up to isomorphism iff T proves V=OD. Here we provide a comprehensive treatment of Paris models. Our results include the (...) following:1. If T is a consistent completion of ZF+V≠OD, then T has continuum-many countable nonisomorphic Paris models.2. Every countable model of ZFC has a Paris generic extension.3. If there is an uncountable well-founded model of ZFC, then for every infinite cardinal κ there is a Paris model of ZF of cardinality κ which has a nontrivial automorphism.4. For a model ZF, is a prime model ⇒ is a Paris model and satisfies AC⇒ is a minimal model. Moreover, Neither implication reverses assuming Con(ZF). (shrink)

We employ the notions of "sequential function" and "interrogation" (dialogue) in order to define new partial combinatory algebra structures on sets of functions. These structures are analyzed using Longley's preorder-enriched category of partial combinatory algebras and decidable applicative structures. We also investigate total combinatory algebras of partial functions. One of the results is that every realizability topos is a geometric quotient of a realizability topos on a total combinatory algebra.

In this paper we introduce the notion of a set algebra $\mathscr{S}$ satisfying a system $\mathscr{E}$ equations. After defining a notion of freeness for such algebras, we show that, for any system $\mathscr{E}$ of equations, set algebras that are free in the class of structures satisfying $\mathscr{E}$ exist and are unique up to a bisimulation. Along the way, analogues of classical set-theoretic and algebraic properties are investigated.

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)