The notion of a complete type can be generalized in a natural manner to allow assigning a value in an arbitrary Boolean algebra $\mathcal {B}$ to each formula. We show some basic results regarding the effect of the properties of $\mathcal {B}$ on the behavior of such types, and show they are particularity well behaved in the case of NIP theories. In particular, we generalize the third author’s result about counting types, as well as the notion of (...) a smooth type and extending a type to a smooth one. We then show that Keisler measures are tied to certain Boolean types and show that some of the results can thus be transferred to measures—in particular, giving an alternative proof of the fact that every measure in a dependent theory can be extended to a smooth one. We also study the stable case. We consider this paper as an invitation for more research into the topic of Boolean types. (shrink)

The problem of enumerating the types of Boolean functions under the group of variable permutations and complementations was first stated by Jevons in the 1870s. but not solved in a satisfactory way until the work of Pólya in 1940. This paper explains the details of Pólya's solution, and also the history of the problem from the 1870s to the 1970s.

We give a necessary and sufficient condition for a Bell-type inequality to hold in a horizontal sum of finitely many finite Boolean algebras.

We analyze Zorn's Lemma and some of its consequences for Boolean algebras in a constructive setting. We show that Zorn's Lemma is persistent in the sense that, if it holds in the underlying set theory, in a properly stated form it continues to hold in all intuitionistic type theories of a certain natural kind. (Observe that the axiom of choice cannot be persistent in this sense since it implies the law of excluded middle.) We also establish the persistence of (...) some familiar results in the theory of (complete) Boolean algebras--notably, the proposition that every complete Boolean algebra is an absolute subretract. This (almost) resolves a question of Banaschewski and Bhutani as to whether the Sikorski extension theorem for Boolean algebras is persistent. (shrink)

We analyze Zorn's Lemma and some of its consequences for Boolean algebras in a constructive setting. We show that Zorn's Lemma is persistent in the sense that, if it holds in the underlying set theory, in a properly stated form it continues to hold in all intuitionistic type theories of a certain natural kind. We also establish the persistence of some familiar results in the theory of Boolean algebras--notably, the proposition that every complete Boolean algebra is an (...) absolute subretract. This resolves a question of Banaschewski and Bhutani as to whether the Sikorski extension theorem for Boolean algebras is persistent. (shrink)

A regularity theory of causation analyses type-level causation in terms of Boolean difference-making. The essential ingredient that helps this theoretical framework overcome the problems of Hume’s and Mill’s classical accounts is a principle of non-redundancy: only Boolean dependency structures from which no elements can be eliminated track causation. The first part of this article argues that the recent regularity-theoretic literature has not consistently implemented this principle, for it disregarded an important type of redundancies: structural redundancies. Moreover, it is (...) shown that a regularity theory needs to be underwritten by a hitherto neglected metaphysical background assumption stipulating that the world’s causal makeup is not ambiguous. Against that background, the second part then develops a new regularity theory that does justice to all types of redundancies and, thereby, provides the first all-inclusive notion of Boolean difference-making. (shrink)

A regularity theory of causation analyses type-level causation in terms of Boolean difference-making. The essential ingredient that helps this theoretical framework overcome the problems of Hume’s and Mill’s classical accounts is a principle of non-redundancy: only Boolean dependency structures from which no elements can be eliminated track causation. The first part of this paper argues that the recent regularity theoretic literature has not consistently implemented this principle, for it disregarded an important type of redundancies: structural redundancies. Moreover, it (...) is shown that a regularity theory needs to be underwritten by a hitherto neglected metaphysical background assumption stipulating that the world's causal makeup is not ambiguous. Against that background, the second part then develops a new regularity theory that does justice to all types of redundancies and, thereby, provides the first all-inclusive notion of Boolean difference-making. (shrink)

Relevant logics have traditionally been viewed as paraconsistent. This paper shows that this view of relevant logics is wrong. It does so by showing forth a logic which extends classical logic, yet satisfies the Entailment Theorem as well as the variable sharing property. In addition it has the same S4-type modal feature as the original relevant logic E as well as the same enthymematical deduction theorem. The variable sharing property was only ever regarded as a necessary property for a logic (...) to have in order for it to not validate the so-called paradoxes of implication. The Entailment Theorem on the other hand was regarded as both necessary and sufficient. This paper shows that the latter theorem also holds for classical logic, and so cannot be regarded as a sufficient property for blocking the paradoxes. The concept of suppression is taken up, but shown to be properly weaker than that of variable sharing. (shrink)

For an arbitrary similarity type of Boolean Algebras with Operators we define a class of Sahlqvist identities. Sahlqvist identities have two important properties. First, a Sahlqvist identity is valid in a complex algebra if and only if the underlying relational atom structure satisfies a first-order condition which can be effectively read off from the syntactic form of the identity. Second, and as a consequence of the first property, Sahlqvist identities are canonical, that is, their validity is preserved under taking (...) canonical embedding algebras. Taken together, these properties imply that results about a Sahlqvist variety V van be obtained by reasoning in the elementary class of canonical structures of algebras in V. We give an example of this strategy in the variety of Cylindric Algebras: we show that an important identity called Henkin's equation is equivalent to a simpler identity that uses only one variable. We give a conceptually simple proof by showing that the firstorder correspondents of these two equations are equivalent over the class of cylindric atom structures. (shrink)

For an arbitrary similarity type of Boolean Algebras with Operators we define a class ofSahlqvist identities. Sahlqvist identities have two important properties. First, a Sahlqvist identity is valid in a complex algebra if and only if the underlying relational atom structure satisfies a first-order condition which can be effectively read off from the syntactic form of the identity. Second, and as a consequence of the first property, Sahlqvist identities arecanonical, that is, their validity is preserved under taking canonical embedding (...) algebras. Taken together, these properties imply that results about a Sahlqvist variety V van be obtained by reasoning in the elementary class of canonical structures of algebras in V.We give an example of this strategy in the variety of Cylindric Algebras: we show that an important identity calledHenkin's equation is equivalent to a simpler identity that uses only one variable. We give a conceptually simple proof by showing that the first-order correspondents of these two equations are equivalent over the class of cylindric atom structures. (shrink)

We investigate small theories of Boolean ordered o-minimal structures. We prove that such theories are $\aleph_{0}-categorical$ . We give a complete characterization of their models up to bi-interpretability of the language. We investigate types over finite sets, formulas and the notions of definable and algebraic closure.

The basic quasi-Boolean negation expansions of relevance logics included in Anderson and Belnap’s relevance logic R are defined. We consider two types of QB-negation: H-negation and D-negation. The former one is of paraintuitionistic or superintuitionistic character, the latter one, of dual intuitionistic nature in some sense. Logics endowed with H-negation are paracomplete; logics with D-negation are paraconsistent. All logics defined in the paper are given a Routley-Meyer ternary relational semantics.

In this paper we investigate computable isomorphisms of Boolean algebras with operators (BAOs). We prove that there are examples of polymodal Boolean algebras with finitely many computable isomorphism types. We provide an example of a polymodal BAO such that it has exactly one computable isomorphism type but whose expansions by a constant have more than one computable isomorphism type. We also prove a general result showing that BAOs are complete with respect to the degree spectra of structures, (...) computable dimensions, expansions by constants, and the degree spectra of relations. (shrink)

This paper presents the algebraic and Kripke modelsoundness and completeness ofa logic over Boolean monoids. An additional axiom added to thelogic will cause the resulting monoid models to be representable as monoidsof relations. A star operator, interpreted as reflexive, transitiveclosure, is conservatively added to the logic. The star operator isa relative modal operator, i.e., one that is defined in terms ofanother modal operator. A further example, relative possibility,of this type of operator is given. A separate axiom,antilogism, added to the (...) logic causes the Kripke models to support acollection of abstract topological uniformities which become concretewhen the Kripke models are dual to monoids of relations. The machineryfor the star operator is shownto be a recasting of Scott-Montague neighborhood models. An interpretationof the Kripke frames and properties thereof is presented in terms ofcertain CMOS transister networks and some circuit transformation equivalences.The worlds of the Kripke frame are wires and the Kripke relation is a specializedCMOS pass transistor network. (shrink)

This paper discusses two challenges for a Boolean method for establishing constitutive regularity statements which, according to the regularity theory of mechanistic constitution, form the core of any mechanistic explanation in neuroscience. After presenting the regularity definition for the constitution relation and a methodology for constitutive inference, the paper discusses the problem of full variation of tested mechanistic factors and the problem of informational redundancy. A solution is offered for each problem. The first requires some adjustments to the original (...) theory by introducing the technical notion of a set of types satisfying independent instantiability. The second one is resolved by demonstrating that the problem of informational redundancy is based on a confusion that fails to challenge the theory. It is concluded that the methodology of constitutive inference is consistent and plausible with respect to actual practice in neuroscience. (shrink)

This paper discusses two challenges for a Boolean method for establishing constitutive regularity statements which, according to the regularity theory of mechanistic constitution, form the core of any mechanistic explanation in neuroscience. After presenting the regularity definition for the constitution relation and a methodology for constitutive inference, the paper discusses the problem of full variation of tested mechanistic factors and the problem of informational redundancy. A solution is offered for each problem. The first requires some adjustments to the original (...) theory by introducing the technical notion of a set of types satisfying independent instantiability. The second one is resolved by demonstrating that the problem of informational redundancy is based on a confusion that fails to challenge the theory. It is concluded that the methodology of constitutive inference is consistent and plausible with respect to actual practice in neuroscience. (shrink)

Effect algebras (EAs), play a significant role in quantum logic, are featured in the theory of partially ordered Abelian groups, and generalize orthoalgebras, MV-algebras, orthomodular posets, orthomodular lattices, modular ortholattices, and boolean algebras.We study centrally orthocomplete effect algebras (COEAs), i.e., EAs satisfying the condition that every family of elements that is dominated by an orthogonal family of central elements has a supremum. For COEAs, we introduce a general notion of decomposition into types; prove that a COEA factors uniquely (...) as a direct sum of types I, II, and III; and obtain a generalization for COEAs of Ramsay’s fourfold decomposition of a complete orthomodular lattice. (shrink)

We briefly overview some of the historical landmarks on the path leading to the reduction of the number of logical connectives in classical logic. Relying on the duality inherent in Boolean algebras, we introduce a new operator ( Nallor ) that is the dual of Schönfinkel’s operator. We outline the proof that this operator by itself is sufficient to define all the connectives and operators of classical first-order logic ( Fol ). Having scrutinized the proof, we pinpoint the theorems (...) of Fol that are needed in the proof. Using the insights gained from the proof, we show that there are four binary operators that each can serve as the only undefined logical constant for Fol . Finally, we show that from every n -ary connective that yields a functionally complete singleton set of connectives two Schönfinkel-type operators are definable, and all the latter are so definable. (shrink)

Many arguments for flexible type assignment to syntactic categories have to do with the need to account for the various scopings resulting from the interaction of quantified DPs with other quantified DPs or with intensional or negated verb contexts. We will define a type for arbitrary arity relations in polymorphic type theory. In terms of this, we develop the Boolean algebra of relations as far as needed for natural language semantics. The type for relations is flexible: it can do (...) duty for the whole family of types t, e → t, e → e → t, and so on. If we use this flexible type for the interpretations of verbs, we can perform a ‘flexible lift’ on DP interpretations, so that DPs get interpreted as operations on verb meanings. This leads to an elegant implementation of Keenan’s proposal for polyadic quantification in natural language (‘Beyond the Frege Boundary’). It turns out that scope reorderings are particularly easy to implement in this framework. (shrink)

In this article we will focus our attention on the variety of distributive bisemilattices and some linguistic expansions thereof: bounded, De Morgan, and involutive bisemilattices. After extending Balbes’ representation theorem to bounded, De Morgan, and involutive bisemilattices, we make use of Hartonas–Dunn duality and introduce the categories of 2spaces and 2spaces\. The categories of 2spaces and 2spaces\ will play with respect to the categories of distributive bisemilattices and De Morgan bisemilattices, respectively, a role analogous to the category of Stone spaces (...) with respect to the category of Boolean algebras. Actually, the aim of this work is to show that these categories are, in fact, dually equivalent. (shrink)

This article is devoted to two different generalizations of projective Boolean algebras: openly generated Boolean algebras and tightly ϭ-filtered Boolean algebras. We show that for every uncountable regular cardinal κ there are 2κ pairwise non-isomorphic openly generated Boolean algebras of size κ > N1 provided there is an almost free non-free abelian group of size κ. The openly generated Boolean algebras constructed here are almost free. Moreover, for every infinite regular cardinal κ we construct 2κ (...) pairwise non-isomorphic Boolean algebras of size κ that are tightly ϭ-filtered and c.c.c. These two results contrast nicely with Koppelberg's theorem in [12] that for every uncountable regular cardinal κ there are only 2<κ isomorphism types of projective Boolean algebras of size κ. (shrink)

© 2018, Springer International Publishing AG, part of Springer Nature. Aristotelian diagrams are used extensively in contemporary research in artificial intelligence. The present paper investigates the geometric and cognitive differences between two types of Aristotelian diagrams for the Boolean algebra B4. Within the class of 3D visualizations, the main geometric distinction is that between the cube-based diagrams and the tetrahedron-based diagrams. Geometric properties such as collinearity, central symmetry and distance are examined from a cognitive perspective, focusing on diagram (...) design principles such as congruence/isomorphism and apprehension. The cognitive effectiveness of the different visualizations is compared for the representation of implication versus opposition relations, and for subdiagram embeddings. (shrink)

Various threshold Boolean networks, a formalism used to model different types of biological networks, can produce similar dynamics, i.e. share same behaviors. Among them, some are complex, others not. By computing both structural and behavioral complexities, we show that most TBNs are structurally complex, even those having simple behaviors. For this purpose, we developed a new method to compute the structural complexity of a TBN based on estimates of the sizes of equivalence classes of the threshold Boolean (...) functions composing the TBN. (shrink)

The first main result isolates some conditions which fail for the class of graphs and hold for the class of Abelian p-groups, the class of Abelian torsion groups, and the special class of "rank-homogeneous" trees. We consider these conditions as a possible definition of what it means for a class of structures to have "Ulm type". The result says that there can be no Turing computable embedding of a class not of Ulm type into one of Ulm type. We apply (...) this result to show that there is no Turing computable embedding of the class of graphs into the class of "rank-homogeneous" trees. The second main result says that there is a Turing computable embedding of the class of rank-homogeneous trees into the class of torsion-free Abelian groups. The third main result says that there is a "rank-preserving" Turing computable embedding of the class of rank-homogeneous trees into the class of Boolean algebras. Using this result, we show that there is a computable Boolean algebra of Scott rank ${\mathrm{\omega }}_{1}^{\mathrm{C}\mathrm{K}}$. (shrink)

We define the paraconsistent supra-logic Pσ by a type-shift from the booleans o of propositional logic Po to the supra-booleans σ of the propositional type logic P obtained as the propositional fragment of the transfinite type theory Q defined by Peter Andrews (North-Holland Studies in Logic 1965) as a classical foundation of mathematics. The supra-logic is in a sense a propositional logic only, but since there is an infinite number of supra-booleans and arithmetical operations are available for this and other (...) types, virtually anything can be specified. The supra-logic is a generalization of Lukasiewicz's three-valued logic, with the intermediate value duplicated many times and ordered such that none of the copies of this value imply other ones, but it differs from Lukasiewicz's many-valued logics as well as from logics based on bilattices. There are several automated theorem provers for classical higher order logic (finite type theory) and it should be possible to modify these to our needs. (shrink)

A general method for constructing a new class of topological Ramsey spaces is presented. Members of such spaces are infinite sequences of products of Fraïssé classes of finite relational structures satisfying the Ramsey property. The Product Ramsey Theorem of Sokič is extended to equivalence relations for finite products of structures from Fraïssé classes of finite relational structures satisfying the Ramsey property and the Order-Prescribed Free Amalgamation Property. This is essential to proving Ramsey-classification theorems for equivalence relations on fronts, generalizing the (...) Pudlák–Rödl Theorem to this class of topological Ramsey spaces. To each topological Ramsey space in this framework corresponds an associated ultrafilter satisfying some weak partition property. By using the correct Fraïssé classes, we construct topological Ramsey spaces which are dense in the partial orders of Baumgartner and Taylor generating p-points which are k-arrow but not \-arrow, and in a partial order of Blass producing a diamond shape in the Rudin-Keisler structure of p-points. Any space in our framework in which blocks are products of n many structures produces ultrafilters with initial Tukey structure exactly the Boolean algebra \\). If the number of Fraïssé classes on each block grows without bound, then the Tukey types of the p-points below the space’s associated ultrafilter have the structure exactly \. In contrast, the set of isomorphism types of any product of finitely many Fraïssé classes of finite relational structures satisfying the Ramsey property and the OPFAP, partially ordered by embedding, is realized as the initial Rudin-Keisler structure of some p-point generated by a space constructed from our template. (shrink)

Fix 2 < n < ω. Let CA n denote the class of cylindric algebras of dimension n, and let RCA n denote the variety of representable CA n ’s. Let L n denote first-order logic restricted to the first n variables. Roughly, CA n, an instance of Boolean algebras with operators, is the algebraic counterpart of the syntax of L n, namely, its proof theory, while RCA n algebraically and geometrically represents the Tarskian semantics of L n. Unlike (...) Boolean algebras having a Stone representation theorem, RCA n ⊊ CA n. Using combinatorial game theory, we show that the existence of certain finite relation algebras RA, which are algebras whose domain consists of binary relations, implies that the celebrated Henkin omitting types theorem fails in a very strong sense for L n. Using special cases of such finite RA ’s, we recover the classical nonfinite axiomatizability results of Monk, Maddux, and Biro on RCA n and we re-prove Hirsch and Hodkinson’s result that the class of completely representable CA n ’s is not first-order definable. We show that if T is an L n countable theory that admits elimination of quantifiers, λ is a cardinal < 2 ℵ 0, and F = 〈 Γ i : i < λ 〉 is a family of complete nonprincipal types, then F can be omitted in an ordinary countable model of T. (shrink)

We characterize the 3-stratifiable theorems of NF as a 3-stratifiable extension of NF 3 ; and show that NF is equiconsistent with TT plus raising type axioms for sentences asserting the existence of some predicate over an atomic Boolean algebra.

In the context of proliferation of many logical systems in the area of mathematical logic and computer science, we present a generalization of forcing in institution-independent model theory which is used to prove two abstract results: Downward Löwenheim-Skolem Theorem and Omitting Types Theorem . We instantiate these general results to many first-order logics, which are, roughly speaking, logics whose sentences can be constructed from atomic formulas by means of Boolean connectives and classical first-order quantifiers. These include first-order logic (...) , logic of order-sorted algebras , preorder algebras , as well as their infinitary variants \ , \ , \ . In addition to the first technique for proving OTT, we develop another one, in the spirit of institution-independent model theory, which consists of borrowing the Omitting Types Property from a simpler institution across an institution comorphism. As a result we export the OTP from FOL to partial algebras and higher-order logic with Henkin semantics , and from the institution of \ to \ and \ . The second technique successfully extends the domain of application of OTT to non conventional logical systems for which the standard methods may fail. (shrink)

This paper presents a generalization of a proposal of van Benthem’s who has shown how to provide a canonical name for any object in propositional type theory. Van Benthem’s idea is to characterize any function in the hierarchy by the Boolean values the function takes for any sequence of arguments. The recursive definition of canonical names uses only the abstraction, functional application, the identity operator and the fact that we have a name for the true and the false. We (...) show that this result can be extended to the finite theory of types by the introduction of an algebra on individuals. (shrink)

A method for constructing Boolean-valued models of some fragments of arithmetic was developed in Krajíček (Forcing with Random Variables and Proof Complexity, London Mathematical Society Lecture Notes Series, Cambridge University Press, Cambridge, 2011), with the intended applications in bounded arithmetic and proof complexity. Such a model is formed by a family of random variables defined on a pseudo-finite sample space. We show that under a fairly natural condition on the family [called compactness in Krajíček (Forcing with Random Variables and (...) Proof Complexity, London Mathematical Society Lecture Notes Series, Cambridge University Press, Cambridge, 2011)] the resulting structure has a property that is naturally interpreted as saturation for existential types. We also give an example showing that this cannot be extended to universal types. (shrink)

In 1936, G. Birkhoff and J. v. Neumann published an article with the title The logic of quantum mechanics'. In this paper, the authors demonstrated that in quantum mechanics the most simple observables which correspond to yes-no propositions about a quantum physical system constitute an algebraic structure, the most important proper ties of which are given by an orthocomplemented and quasimodular lattice Lq. Furthermore, this lattice of quantum mechanical proposi tions has, from a formal point of view, many similarities with (...) a Boolean lattice L8 which is known to be the lattice of classical propositional logic. Therefore, one could conjecture that due to the algebraic structure of quantum mechanical observables a logical calculus Q of quantum mechanical propositions is established, which is slightly different from the calculus L of classical propositional logic but which is applicable to all quantum mechanical propositions. This calculus has sometimes been called 'quan tum logic'. However, the statement that propositions about quantum physical systems are governed by the laws of quantum logic, which differ from ordinary classical logic and which are based on the empirically well-established quantum theory, is exposed to two serious objec tions: Logic is a theory which deals with those relationships between various propositions that are valid independent of the content of the respective propositions. Thus, the validity of logical relationships is not restricted to a special type of proposition, e. g. to propositions about classical physical systems. (shrink)

We prove an extension of the Lemma of Rasiowa and Sikorski and give some applications. Moreover, we analyze the relationship to corresponding results on the omission of types.

Biochemical networks are often called upon to illustrate emergent properties of living systems. In this contribution, I question such emergentist claims by means of theoretical work on genetic regulatory models and random Boolean networks. If the existence of a critical connectivity Kc of such networks has often been coined “emergent” or “irreducible”, I propose on the contrary that the existence of a critical connectivity Kc is indeed mathematically explainable in network theory. This conclusion also applies to many other (...) class='Hi'>types of formal networks and weakens the emergentist claim attached to bio-molecular networks, and by extension to living systems. (shrink)

The relativized propositional calculus is a system of Boolean formulas with query symbols. A formula in this system is called a one-query formula if the number of occurrences of query symbols is just one. If a one-query formula is a tautology with respect to a given oracle A then it is called a one-query tautology with respect to A. By extending works of Ambos-Spies (1986) and us (2002), we investigate the measure of the class of all oracles A such (...) that the set of all one-query tautologies with respect to A does not p-btt-reduce to A, where p-btt denotes polynomial-time bounded-truth-table. We show that certain Dowd-type generic oracles all belong to the class, and hence measure of the class is one. (shrink)

In his milestone textbook Lattice Theory, Garrett Birkhoff challenged his readers to develop a "common abstraction" that includes Boolean algebras and lattice-ordered groups as special cases. In this paper, after reviewing the past attempts to solve the problem, we provide our own answer by selecting as common generalization of ������������ and ������������ their join ������������∨������������ in the lattice of subvarieties of ������ℒ (the variety of FL-algebras); we argue that such a solution is optimal under several respects and we give (...) an explicit equational basis for ������������∨������������ relative to ������ℒ. Finally, we prove a Holland-type representation theorem for a variety of FL-algebras containing ������������∨������������. (shrink)

In the paper we build up the ontology of Leśniewski’s type for formalizing synthetic propositions. We claim that for these propositions an unconventional square of opposition holds, where a, i are contrary, a, o (resp. e, i) are contradictory, e, o are subcontrary, a, e (resp. i, o) are said to stand in the subalternation. Further, we construct a non-Archimedean extension of Boolean algebra and show that in this algebra just two squares of opposition are formalized: conventional and the (...) square that we invented. As a result, we can claim that there are only two basic squares of opposition. All basic constructions of the paper (the new square of opposition, the formalization of synthetic propositions within ontology of Leśniewski’s type, the non-Archimedean explanation of square of opposition) are introduced for the first time. (shrink)