We investigate what it means for a (Hausdorff, second-countable) topological group to be computable. We compare several potential definitions based on classical notions in the literature. We relate these notions with the well-established definitions of effective presentability for discrete and profinite groups, and compare our results with similar results in computable topology.

An algebra with fuzzy equality is a set with operations on it that is equipped with similarity ≈, i.e. a fuzzy equivalence relation, such that each operation f is compatible with ≈. Described verbally, compatibility says that each f yields similar results if applied to pairwise similar arguments. On the one hand, algebras with fuzzy equalities are structures for the equational fragment of fuzzy logic. On the other hand, they are the formal counterpart to the intuitive idea of having functions (...) that are not allowed to map similar objects to dissimilar ones. In this paper, we present a generalization of the well-known Birkhoff’s variety theorem: a class of algebras with fuzzy equality is the class of all models of a fuzzy set of identities iff it is closed under suitably defined morphisms, substructures, and direct products. (shrink)

A version of Birkhoff's theorem is proved by constructive, predicative, methods. The version we prove has two conditions more than the classical one. First, the class considered is assumed to contain a generic family, which is defined to be a set-indexed family of algebras such that if an identity is valid in every algebra of this family, it is valid in every algebra of the class. Secondly, the class is assumed to be closed under inductive limits.

In the context of implicational tonoid logics, this paper investigates analogues of Birkhoff’s two theorems, the so-called subdirect representation and varieties theorems, and of Mal’cev’s quasi-varieties theorem. More precisely, we first recall the class of implicational tonoid logics. Next, we establish the subdirect product representation theorem for those logics and then consider some more related results such as completeness. Thirdly, we consider the varieties theorem for them. Finally, we introduce an analogue of Mal’cev’s quasi-varieties theorem for (...) algebras. (shrink)

We develop an abstract proof calculus for logics whose sentences are ‘Horn sentences’ of the form: $(\forall X)H \Rightarrow c$ and prove an institutional generalization of Birkhoff completeness theorem. This result is then applied to the particular cases of Horn clauses logic, the ‘Horn fragment’ of preorder algebras, order-sorted algebras and partial algebras and their infinitary variants.

Steve Awodey and Jesse Hughes. Modal Operators and the Formal Dual of Birkhoff's Completeness Theorem.

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 investigate Birkhoff’s conditions and. We prove that a discrete lattice L satisfies the condition ) if and only if L is a 4-cell lattice not containing a cover-preserving sublattice isomorphic to the lattice S*7. As a corollary we obtain a well known result of J. Jakub´ık from [6]. Furthermore, lattices S7 and S*7 are considered as so-called partially cover-preserving sublattices of a given lattice L, S7 ≪ L and S7 ≪ L, in symbols. It is shown (...) that an upper continuous lattice L satisfies if and only if L is a 4-cell lattice such that S7 ≪/ L. The final corollary is a generalization of Jakubík’s theorem for upper continuous and strongly atomic lattices. Keywords: Birkhoff’s conditions, semimodularity conditions, modular lattice, discrete lattices, upper continuous lattice, strongly atomic lattice, cover-preserving sublattice, cell, 4-cell lattice. (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)

Political theorists study the attributes of desirable social-moral states of affairs. Schaefer (forthcoming) aims to show that "static political theory" of this kind rests on shaky foundations. His argument revolves around an application of an abstruse mathematical theorem -- Kakutani's fixed point theorem -- to the social-moral domain. We show that Schaefer has misunderstood the implications of this theorem for political theory. Theorists who wish to study the attributes of social-moral states of affairs should carry on, safe (...) in the knowledge that Kakutani's theorem poses no threat to this enterprise. (shrink)

In this paper, we investigate the logical strength of two types of fixed point theorems in the context of reverse mathematics. One is concerned with extensions of the Banach contraction principle. Among theorems in this type, we mainly show that the Caristi fixed point theorem is equivalent to math formula over math formula. The other is dedicated to topological fixed point theorems such as the Brouwer fixed point theorem. We introduce some variants of the Fan-Browder fixed point (...) class='Hi'>theorem and the Kakutani fixed point theorem, which we call math formula and math formula, respectively. Then we show that math formula is equivalent to math formula and math formula is equivalent to math formula, over math formula. In addition, we also study the application of the Fan-Browder fixed point theorem to game systems. (shrink)

We formulate a general institution-independent (i.e. independent of the details of the actual logic formalised as institution) version of the Craig Interpolation Theorem and prove it in dependence of Birkhoff-style axiomatizability properties of the actual logic.We formalise Birkhoff-style axiomatizability within the general abstract model theoretic framework of institution theory by the novel concept of Birkhoff institution.

In this paper the class of Fidel-structures for the paraconsistent logic mbC is studied from the point of view of Model Theory and Category Theory. The basic point is that Fidel-structures for mbC (or mbC-structures) can be seen as first-order structures over the signature of Boolean algebras expanded by two binary predicate symbols N (for negation) and O (for the consistency connective) satisfying certain Horn sentences. This perspective allows us to consider notions and results from Model Theory in order to (...) analyze the class of mbC-structures. Thus, substructures, union of chains, direct products, direct limits, congruences and quotient structures can be analyzed under this perspective. In particular, a Birkhoff-like representation theorem for mbC-structures as subdirect poducts in terms of subdirectly irreducible mbC-structures is obtained by adapting a general result for first-order structures due to Caicedo. Moreover, a characterization of all the subdirectly irreducible mbC-structures is also given. An alternative decomposition theorem is obtained by using the notions of weak substructure and weak isomorphism considered by Fidel for Cn-structures. (shrink)

Presented is a completeness theorem for fuzzy equational logic with truth values in a complete residuated lattice: Given a fuzzy set Σ of identities and an identity p≈q, the degree to which p≈q syntactically follows (is provable) from Σ equals the degree to which p≈q semantically follows from Σ. Pavelka style generalization of well-known Birkhoff's theorem is therefore established.

The general set of doubly stochastic matrices of order n corresponding to ordinary nonrelativistic quantum mechanical transition probability matrices is given. Landé's discussion of the nonquantal origin of such matrices is noted. Several concrete examples are presented for elementary and composite angular momentum systems with the focus on the unitary symmetry associated with such systems in the spirit of the recent work of Bohr and Ulfbeck. Birkhoff's theorem on doubly stochastic matrices of order n is reformulated in a geometrical (...) language suitable for application to the subset of quantum mechanical doubly stochastic matrices. Specifically, it is shown that the set of points on the unit sphere in cartesian n!-space is surjective with the set of doubly stochastic matrices of order n. The question is raised, but not answered, as to what is the subset of points of this unit sphere that correspond to the quantum mechanical transition probability matrices, and what is the symmetry group of this subset of matrices. (shrink)

Multialgebras have been much studied in mathematics and in computer science. In 2016 Carnielli and Coniglio introduced a class of multialgebras called swap structures, as a semantic framework for dealing with several Logics of Formal Inconsistency that cannot be semantically characterized by a single finite matrix. In particular, these LFIs are not algebraizable by the standard tools of abstract algebraic logic. In this paper, the first steps towards a theory of non-deterministic algebraization of logics by swap structures are given. Specifically, (...) a formal study of swap structures for LFIs is developed, by adapting concepts of universal algebra to multialgebras in a suitable way. A decomposition theorem similar to Birkhoff’s representation theorem is obtained for each class of swap structures. Moreover, when applied to the 3-valued algebraizable logics J3 and Ciore, their classes of algebraic models are retrieved, and the swap structures semantics become twist structures semantics. This fact, together with the existence of a functor from the category of Boolean algebras to the category of swap structures for each LFI, suggests that swap structures can be seen as non-deterministic twist structures. This opens new avenues for dealing with non-algebraizable logics by the more general methodology of multialgebraic semantics. (shrink)

In this paper we mainly deal with first-order languages without equality and introduce a weak form of equality predicate, the so-called Leibniz equality. This equality is characterized algebraically by means of a natural concept of congruence; in any structure, it turns out to be the maximum congruence of the structure. We show that first-order logic without equality has two distinct complete semantics (fll semantics and reduced semantics) related by the reduction operator. The last and main part of the paper contains (...) a series of Birkhoff-style theorems characterizing certain classes of structures defined without equality, not only full classes but also reduced ones. (shrink)

The idea of a 'logic of quantum mechanics' or quantum logic was originally suggested by Birkhoff and von Neumann in their pioneering paper [1936]. Since that time there has been much argument about whether, or in what sense, quantum 'logic' can be actually considered a true logic (see, e.g. Bell and Hallett [1982], Dummett [1976], Gardner [1971]) and, if so, how it is to be distinguished from classical logic. In this paper I put forward a simple and natural semantical framework (...) for quantum logic which reveals its difference from classical logic in a strikingly intuitive way, viz. through the fact that quantum logic admits (suitably formulated versions of) the characteristic quantum-mechanical notions of superposition and incompatibility of attributes. That is, precisely the features that distinguish quantum from classical physics also serve, within this framework, to distinguish quantum from classical logic. Some light is shed on the question of whether quantum logic is a genuine logical system by introducing a natural entailment relation for quantum-logical formulas with the implication symbol. The novelty is that, although implication behaves as it should (i.e. the 'deduction theorem' holds), the order of introduction of premises is significant. The fact that a reasonable entailment relation can be formulated for quantum logic supports the view that it is a genuine logical system and not merely an algebraic formalism. (shrink)

In quantum logic, introduced by Birkhoff and von Neumann, De Morgan's Laws play an important role in the projection-valued truth value assignment of observational propositions in quantum mechanics. Takeuti's quantum set theory extends this assignment to all the set-theoretical statements on the universe of quantum sets. However, Takeuti's quantum set theory has a problem in that De Morgan's Laws do not hold between universal and existential bounded quantifiers. Here, we solve this problem by introducing a new truth value assignment for (...) bounded quantifiers that satisfies De Morgan's Laws. To justify the new assignment, we prove the Transfer Principle, showing that this assignment of a truth value to every bounded ZFC theorem has a lower bound determined by the commutator, a projection-valued degree of commutativity, of constants in the formula. We study the most general class of truth value assignments and obtain necessary and sufficient conditions for them to satisfy the Transfer Principle, to satisfy De Morgan's Laws, and to satisfy both. For the class of assignments with polynomially definable logical operations, we determine exactly 36 assignments that satisfy the Transfer Principle and exactly 6 assignments that satisfy both the Transfer Principle and De Morgan's Laws. (shrink)

The abstract description of a physical system is developed, along lines originally suggested by Birkhoff and von Neumann, in terms of the complete lattice of propositions associated with that system, and the distinction between classical and quantum systems is made precise. With the help of the notion of state, a propositional system is defined: it is remarked that every irreducible propositional system (of more than three dimensions) is isomorphic to the lattice of all closed subspaces of a Hilbert space constructed (...) on some division ring with involution. The propositional system consisting of a family of separable complex Hilbert spaces is treated as a particular case which is sufficiently general to include both classical and quantum mechanics. The theory of the Galilean particle without spin is given as an illustration. Finally, the basis for the statistical interpretation of wave mechanics is developed with the help of Gleason's theorem. In an appendix, a proof of essentially the first part of Gleason's theorem is given which is a little different (perhaps more geometric) from that originally given by Gleason. (shrink)

This article provides an algebraic study of the propositional system $\mathtt {InqB}$ of inquisitive logic. We also investigate the wider class of $\mathtt {DNA}$ -logics, which are negative variants of intermediate logics, and the corresponding algebraic structures, $\mathtt {DNA}$ -varieties. We prove that the lattice of $\mathtt {DNA}$ -logics is dually isomorphic to the lattice of $\mathtt {DNA}$ -varieties. We characterise maximal and minimal intermediate logics with the same negative variant, and we prove a suitable version of Birkhoff’s classic variety (...) theorems. We also introduce locally finite $\mathtt {DNA}$ -varieties and show that these varieties are axiomatised by the analogues of Jankov formulas. Finally, we prove that the lattice of extensions of $\mathtt {InqB}$ is dually isomorphic to the ordinal $\omega +1$ and give an axiomatisation of these logics via Jankov $\mathtt {DNA}$ -formulas. This shows that these extensions coincide with the so-called inquisitive hierarchy of [9].1. (shrink)

Orthomodular logic is a weakening of quantum logic in the sense of Birkhoff and von Neumann. Orthomodular logic is shown to be a nonlinear noncommutative logic. Sequents are given a physically motivated semantics that is consistent with exactly one semantics for propositional formulas that use negation, conjunction, and implication. In particular, implication must be interpreted as the Sasaki arrow, which satisfies the deduction theorem in this logic. As an application, this deductive system is extended to two systems of predicate (...) logic: the first is sound for Takeuti’s quantum set theory, and the second is sound for a variant of Weaver’s quantum logic. (shrink)

We develop and defend the thesis that the Hilbert space formalism of quantum mechanics is a new theory of probability. The theory, like its classical counterpart, consists of an algebra of events, and the probability measures defined on it. The construction proceeds in the following steps: (a) Axioms for the algebra of events are introduced following Birkhoff and von Neumann. All axioms, except the one that expresses the uncertainty principle, are shared with the classical event space. The only models for (...) the set of axioms are lattices of subspaces of inner product spaces over a field K. (b) Another axiom due to Soler forces K to be the field of real, or complex numbers, or the quaternions. We suggest a probabilistic reading of Soler's axiom. (c) Gleason's theorem fully characterizes the probability measures on the algebra of events, so that Born's rule is derived. (d) Gleason's theorem is equivalent to the existence of a certain finite set of rays, with a particular orthogonality graph (Wondergraph). Consequently, all aspects of quantum probability can be derived from rational probability assignments to finite "quantum gambles". (e) All experimental aspects of entanglement- the violation of Bell's inequality in particular- are explained as natural outcomes of the probabilistic structure. (f) We hypothesize that even in the absence of decoherence macroscopic entanglement can very rarely be observed, and provide a precise conjecture to that effect .We also discuss the relation of the present approach to quantum logic, realism and truth, and the measurement problem. (shrink)

In the paper we introduce two conditions and ) which are strengthenings of Birkhoff’s conditions. We prove that an upper continuous and strongly atomic lattice is distributive if and only if it satisfies and ). This result extends a theorem of R.P. Dilworth characterizing distributivity in terms of local distributivity and a theorem of M. Ward characterizing distributivity by means of covering diamonds.

General Equilibrium Theory: An Introduction treats the classic Arrow-Debreu general equilibrium model in a form accessible to graduate students and advanced undergraduates in economics and mathematics. Topics covered include mathematical preliminaries, households and firms, existence of general equilibrium, Pareto efficiency of general equilibrium, the First and Second Fundamental Theorems of Welfare Economics, the core and core convergences, future markets over time and contingent commodity markets under uncertainty. Demand, supply, and excess demand appear first as functions, then optionally as correspondences. The (...) mathematics presented includes a real analysis, the Brouwer fixed point theorem, and separating and supporting hyperplane theorems. Optional chapters introduce the existence of equilibrium with set-valued supply and demand, the mathematics of upper and lower hemicontinuous correspondences, and the Kakutani fixed point theorem. The treatment emphasizes clarity and accessibility to the student through use of examples and intuition. (shrink)

This paper is concerned with a problem of an equitable allocation. We consider the concept of ψ‐equity, which is a general concept of equity. We provide a series of examples of equity concepts that are captured by ψ‐equity. We show the existence of an efficient and ψ‐equitable allocation by employing Kakutani's fixed‐point theorem.

A decade ago, Isham and Butterfield proposed a topos-theoretic approach to quantum mechanics, which meanwhile has been extended by Döring and Isham so as to provide a new mathematical foundation for all of physics. Last year, three of the present authors redeveloped and refined these ideas by combining the C*-algebraic approach to quantum theory with the so-called internal language of topos theory (Heunen et al. in arXiv:0709.4364). The goal of the present paper is to illustrate our abstract setup through the (...) concrete example of the C*-algebra M n (ℂ) of complex n×n matrices. This leads to an explicit expression for the pointfree quantum phase space Σ n and the associated logical structure and Gelfand transform of an n-level system. We also determine the pertinent non-probabilisitic state-proposition pairing (or valuation) and give a very natural topos-theoretic reformulation of the Kochen–Specker Theorem.In our approach, the nondistributive lattice ℘(M n (ℂ)) of projections in M n (ℂ) (which forms the basis of the traditional quantum logic of Birkhoff and von Neumann) is replaced by a specific distributive lattice $\mathcal{O}(\Sigma_{n})$ of functions from the poset $\mathcal{C}(M_{n}(\mathbb{C}))$ of all unital commutative C*-subalgebras C of M n (ℂ) to ℘(M n (ℂ)). The lattice $\mathcal{O}(\Sigma_{n})$ is essentially the (pointfree) topology of the quantum phase space Σ n , and as such defines a Heyting algebra. Each element of $\mathcal{O}(\Sigma_{n})$ corresponds to a “Bohrified” proposition, in the sense that to each classical context $C\in\mathcal{C}(M_{n}(\mathbb{C}))$ it associates a yes-no question (i.e. an element of the Boolean lattice ℘(C) of projections in C), rather than being a single projection as in standard quantum logic. Distributivity is recovered at the expense of the law of the excluded middle (Tertium Non Datur), whose demise is in our opinion to be welcomed, not just in intuitionistic logic in the spirit of Brouwer, but also in quantum logic in the spirit of von Neumann. (shrink)

In this paper, the class of Fidel-structures for the paraconsistent logic mbC is studied from the point of view of Model Theory and Category Theory. The basic point is that Fidel-structures for mbC can be seen as first-order structures over the signature of Boolean algebras expanded by two binary predicate symbols N and O satisfying certain Horn sentences. This perspective allows us to consider notions and results from Model Theory in order to analyze the class of mbC-structures. Thus, substructures, union (...) of chains, direct products, direct limits, congruences and quotient structures can be analyzed under this perspective. In particular, a Birkhoff-like representation theorem for mbC-structures as subdirect products in terms of subdirectly irreducible mbC-structures is obtained by adapting a general result for first-order structures due to Caicedo. Moreover, a characterization of all the subdirectly irreducible mbC-structures is also given. An alternative decomposition theorem is obtained by using the notions of weak substructure and weak isomorphism considered by Fidel for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$C_n$$\end{document}-structures. (shrink)

This paper studies definability within the theory of institutions, a version of abstract model theory that emerged in computing science studies of software specification and semantics. We generalise the concept of definability to arbitrary logics, formalised as institutions, and we develop three general definability results. One generalises the classical Beth theorem by relying on the interpolation properties of the institution. Another relies on a meta Birkhoff axiomatizability property of the institution and constitutes a source for many new actual definability (...) results, including definability in (fragments of) classical model theory. The third one gives a set of sufficient conditions for 'borrowing' definability properties from another institution via an 'adequate' encoding between institutions. The power of our general definability results is illustrated with several applications to (many-sorted) classical model theory and partial algebra, leading for example to definability results for (quasi-)varieties of models or partial algebras. Many other applications are expected for the multitude of logical systems formalised as institutions from computing science and logic. (shrink)

We provide tools for a concise axiomatization of a broad class of quantifiers in many-valued logic, so-called distribution quantifiers. Although sound and complete axiomatizations for such quantifiers exist, their size renders them virtually useless for practical purposes. We show that for quantifiers based on finite distributive lattices compact axiomatizations can be obtained schematically. This is achieved by providing a link between skolemized signed formulas and filters/ideals in Boolean set lattices. Then lattice theoretic tools such as Birkhoff's representation theorem for (...) finite distributive lattices are used to derive tableau-style axiomatizations of distribution quantifiers. (shrink)

Constantin Caratheodory offered the first systematic and contradiction free formulation of thermodynamics on the basis of his mathematical work on Pfaff forms. Moreover, his work on measure theory provided the basis for later improved formulations of thermodynamics and physics of continua where extensive variables are measures and intensive variables are densities. Caratheodory was the first to see that measure theory and not topology is the natural tool to understand the difficulties (ergodicity, approach to equilibrium, irreversibility) in the Foundations of Statistical (...) Physics. He gave a measure-theoretic proof of Poincaré's recurrence theorem in 1919. This work paved the way for Birkhoff to identify later ergodicity as metric transitivity and for Koopman and von Neumann to introduce spectral analysis of dynamical systems in Hilbert spaces. Mixing provided an explanation of the approach to equilibrium but not of irreversibility. The recent extension of spectral theory of dynamical systems to locally convex spaces, achieved by the Brussels–Austin groups, gives new nontrivial time asymmetric spectral decompositions for unstable and/or non-integrable systems. In this way irreversibility is resolved in a natural way. (shrink)

Using coding devices based on a theorem due to Zsigmondy, Birkhoff and Vandiver, we first define in terms of successor S and coprimeness predicate $\perp$ a full arithmetic over the set of powers of some fixed prime, then we define in the same terms a restriction of the exponentiation. Hence we prove the main result insuring that all arithmetical relations and functions over prime powers and their opposite are $\{S, \perp\}$ -definable over Z. Applications to definability over Z and (...) N are stated as corollaries of the main theorem. (shrink)

The general concept of a causal system has been basic in scientific thought. It may be formulated as follows. The system in question possesses certain measurable attributes such as those of dimensions, temperature, and so forth. In the case of a causal system, it is affirmed that the subsequent development of the system from a known initial condition—that is, a condition in which the measurable variables have known values—is uniquely determined by these values. More definitely, the value of these same (...) variables after any interval of time depends only on the initial values of the variables and the time interval which has elapsed. (shrink)

There is a theorem that shows that it is impossible for an algorithm to jointly satisfy the statistical fairness criteria of Calibration and Equalised Odds non-trivially. But what about the recently advocated alternative to Calibration, Base Rate Tracking? Here, we show that Base Rate Tracking is strictly weaker than Calibration, and then take up the question of whether it is possible to jointly satisfy Base Rate Tracking and Equalised Odds in non-trivial scenarios. We show that it is not, thereby (...) establishing an even more general impossibility theorem. (shrink)