Completeness of quantum logic

This paper is based on a semantic foundation of quantum logic which makes use of dialog-games. In the first part of the paper the dialogic method is introduced and under the conditions of quantum mechanical measurements the rules of a dialog-game about quantum mechanical propositions are established. In the second part of the paper the quantum mechanical dialog-game is replaced by a calculus of quantum logic. As the main part of the paper we show that the calculus of quantum logic is complete and consistent with respect to the dialogic semantics. Since the dialog-game does not involve the excluded middle the calculus represents a calculus of effective (intuitionistic) quantum logic.In a forthcoming paper it is shown that this calculus is equivalent to a calculus of sequents and more interestingly to a calculus of propositions. With the addition of the excluded middle the latter calculus is a model for the lattice of subspaces of a Hilbert space.On leave of absence from the Institut für Theoretische Physik der Universität zu Köln, W.-Germany.     

A cut-free gentzen-type system for the logic of the weak law of excluded middle

The logic of the weak law of excluded middleKC _p is obtained by adding the formula A A as an axiom scheme to Heyting's intuitionistic logicH _p . A cut-free sequent calculus for this logic is given. As the consequences of the cut-elimination theorem, we get the decidability of the propositional part of this calculus, its separability, equality of the negationless fragments ofKC _p andH _p , interpolation theorems and so on. From the proof-theoretical point of view, the formulation presented in this paper makes clearer the relations betweenKC _p ,H _p , and the classical logic. In the end, an interpretation of classical propositional logic in the propositional part ofKC _p is given.     

Second order propositional operators over cantor space

We consider propositional operators defined by propositional quantification in intuitionistic logic. More specifically, we investigate the propositional operators of the formA* :p q(p A(q)) whereA(q) is one of the following formulae: (¬¬q q) V ¬¬q, (¬¬q q) (¬¬q V ¬q), ((¬¬q q) (¬¬q V ¬q)) ((¬¬q q) V ¬¬q). The equivalence ofA*(p) to ¬¬p is proved over the standard topological interpretation of intuitionistic second order propositional logic over Cantor space.We relate topological interpretations of second order intuitionistic propositional logic over Cantor space with the interpretation of propositional quantifiers (as the strongest and weakest interpolant in Heyting calculus) suggested by A. Pitts. One of the merits of Pitts' interpretation is shown to be valid for the interpretation over Cantor space.Presented byJan Zygmunt     

The principle of excluded middle in quantum logic

The principle of excluded middle is the logical interpretation of the law V A v in an orthocomplemented lattice and, hence, in the lattice of the subspaces of a Hilbert space which correspond to quantum mechanical propositions. We use the dialogic approach to logic in order to show that, in addition to the already established laws of effective quantum logic, the principle of excluded middle can also be founded. The dialogic approach is based on the very conditions under which propositions can be confirmed by measurements. From the fact that the principle of excluded middle can be confirmed for elementary propositions which are proved by quantum mechanical measurements, we conclude that this principle is inherited by all finite compound propositions. For this proof it is essential that, in the dialog-game about a connective, a finite confirmation strategy for the mutual commensurability of the subpropositions is used.     

Decidability of Quantified Propositional Intuitionistic Logic and S4 on Trees of Height and Arity ≤ω

Quantified propositional intuitionistic logic is obtained from propositional intuitionistic logic by adding quantifiers p, p, where the propositional variables range over upward-closed subsets of the set of worlds in a Kripke structure. If the permitted accessibility relations are arbitrary partial orders, the resulting logic is known to be recursively isomorphic to full second-order logic (Kremer, 1997). It is shown that if the Kripke structures are restricted to trees of at height and width at most , the resulting logics are decidable. This provides a partial answer to a question by Kremer. The result also transfers to modal S4 and some Gödel–Dummett logics with quantifiers over propositions.     

An extension of the Łukasiewicz logic to the modal logic of quantum mechanics

An attempt is made to include the axioms of Mackey for probabilities of experiments in quantum mechanics into the calculus _x0 of ukasiewicz. The obtained calculusQ contains an additional modal signQ and four modal rules of inference. The propositionQx is read x is confirmed. The most specific rule of inference may be read: for comparable observations implication is equivalent to confirmation of material implication.The semantic truth ofQ is established by the interpretation with the help of physical objects obeying to the rules of quantum mechanics. The embedding of the usual quantum propositional logic inQ is accomplished.Allatum est die 9 Junii 1976     

Gentzen-type formulation of the prepositional logic LQ

We give a Gentzen-type formulation GQ for the intermediate logic LQ and prove the cut-elimination theorem on it, where LQ is the propositional logic obtained from the intuitionistic propositional logic LI by adding the axioms of the form AV A.     

Choice and Logic

There is a little known paradox the solution to which is a guide to a much more thoroughgoing solution to a whole range of classic paradoxes. This is shown in this paper with respect to Berrys Paradox, Heterologicality, Russells Paradox, and the Paradox of Predication, also the Liar and the Strengthened Liar, using primarily the epsilon calculus. The solutions, however, show not only that the first-order predicate calculus derived from Frege is inadequate as a basis for a clear science, and should be replaced with Hilbert and Bernays conservative extension. Standard second-order logic, and quantified propositional logic also must be substantially modified, to incorporate, in the first place, nominalizations of predicates, and whole sentences. And further modifications must be made, so as to insist that predicates are parts of sentences rather than forms of them, and that truth is a property of propositions rather than their sentential expressions. In all, a thorough reworking of what has been called logic in recent years must be undertaken, to make it more fit for use.Portions of this paper have previously been published in Logical Studies, vol. 9, http://www.logic.ru/LogStud/09/No9-06.html, and the Australasian Journal of Logic, vol. 2, http://www.philosophy.unimelb.edu.au/ajl/2004/2004_4.pdf.     

A new formulation of discussive logic

S. Jakowski introduced the discussive prepositional calculus D ₂as a basis for a logic which could be used as underlying logic of inconsistent but nontrivial theories (see, for example, N. C. A. da Costa and L. Dubikajtis, On Jakowski's discussive logic, in Non-Classical Logic, Model Theory and Computability, A. I. Arruda, N. C. A da Costa and R. Chuaqui edts., North-Holland, Amsterdam, 1977, 37–56). D ₂has afterwards been extended to a first-order predicate calculus and to a higher-order logic (cf. the quoted paper). In this paper we present a natural version of D ₂, in the sense of Jakowski and Gentzen; as a consequence, we suggest a new formulation of the discussive predicate calculus (with equality). A semantics for the new calculus is also presented.     

Theorem counting

Consider the set of tautologies of the classical propositional calculus containing no connective other than and, or, and not. Consider the subset of this set containing tautologies in exactlyn propositional variables. This paper provides a method for determining the number of equivalence classes of each such subset modulo equivalence in the infinite-valued Lukasiewicz propositional calculus.     

Consistent Fragments of Grundgesetze and the Existence of Non-Logical Objects

In this paper, I consider two curious subsystems ofFrege's Grundgesetze der Arithmetik: Richard Heck's predicative fragment H, consisting of schema V together with predicative second-order comprehension (in a language containing a syntactical abstraction operator), and a theory T in monadic second-order logic, consisting of axiom V and ¹ ₁-comprehension (in a language containing anabstraction function). I provide a consistency proof for the latter theory, thereby refuting a version of a conjecture by Heck. It is shown that both Heck and T prove the existence of infinitely many non-logical objects (T deriving,moreover, the nonexistence of the value-range concept). Some implications concerning the interpretation of Frege's proof of referentiality and the possibility of classifying any of these subsystems as logicist are discussed. Finally, I explore the relation of T toCantor's theorem which is somewhat surprising.     

The Classification of Propositional Calculi

We discuss Smirnovs problem of finding a common background for classifying implicational logics. We formulate and solve the problem of extending, in an appropriate way, an implicational fragment H of the intuitionistic propositional logic to an implicational fragment TV of the classical propositional logic. As a result we obtain logical constructions having the form of Boolean lattices whose elements are implicational logics. In this way, whole classes of new logics can be obtained. We also consider the transition from implicational logics to full logics. On the base of the lattices constructed, we formulate the main classification principles for propositional logics.     

Proper n-valued Łukasiewicz algebras as S-algebras of Łukasiewicz n-valued prepositional calculi

Proper n-valued ukasiewicz algebras are obtained by adding some binary operators, fulfilling some simple equations, to the fundamental operations of n-valued ukasiewicz algebras. They are the s-algebras corresponding to an axiomatization of ukasiewicz n-valued propositional calculus that is an extention of the intuitionistic calculus.Dedicated to the memory of Gregorius C. Moisil     

Three prepositional calculi of probability

Attempts are made to transform the basis of elementary probability theory into the logical calculus.We obtain the propositional calculus NP by a naive approach. As rules of transformation, NP has rules of the classical propositional logic (for events), rules of the ukasiewicz logic ₀ (for probabilities) and axioms of probability theory, in the form of rules of inference. We prove equivalence of NP with a fragmentary probability theory, in which one may only add and subtract probabilities.The second calculus MP is a usual modal propositional calculus. It has the modal rules x x, x y x y, x x, x y (y x), (y x), in addition to the rules of classical propositional logic. One may read x as x is probable. Imbeddings of NP and of ₀ into MP are given.The third calculus P is a modal extension of ₀. It may be obtained by adding the rule ((xy)y) xy to the modal logic of quantum mechanics Q [5]. One may read x in P as x is observed. An imbedding of NP into P is given.     

What is the upper part of the lattice of bimodal logics?

We define an embedding from the lattice of extensions ofT into the lattice of extensions of the bimodal logic with two monomodal operators ₁ and ₂, whose ₂-fragment isS5 and ₁-fragment is the logic of a two-element chain. This embedding reflects the fmp, decidability, completenes and compactness. It follows that the lattice of extension of a bimodal logic can be rather complicated even if the monomodal fragments of the logic belong to the upper part of the lattice of monomodal logics.Presented byWolfgang Rautenberg     

Disjunctive Quantum Logic in Dynamic Perspective

In Coecke (2002) we proposed the intuitionistic or disjunctive representation of quantum logic, i.e., a representation of the property lattice of physical systems as a complete Heyting algebra of logical propositions on these properties, where this complete Heyting algebra goes equipped with an additional operation, the operational resolution, which identifies the properties within the logic of propositions. This representation has an important application towards dynamic quantum logic, namely in describing the temporal indeterministic propagation of actual properties of physical systems. This paper can as such by conceived as an addendum to Quantum Logic in Intuitionistic Perspective that discusses spin-off and thus provides an additional motivation. We derive a quantaloidal semantics for dynamic disjunctive quantum logic and illustrate it for the particular case of a perfect (quantum) measurement.     

Individual Concepts in Modal Predicate Logic

The article deals with the interpretation of propositional attitudes in the framework of modal predicate logic. The first part discusses the classical puzzles arising from the interplay between propositional attitudes, quantifiers and the notion of identity. After comparing different reactions to these puzzles it argues in favor of an analysis in which evaluations of de re attitudes may vary relative to the ways of identifying objects used in the context of use. The second part of the article gives this analysis a precise formalization from a model- and proof-theoretic perspective. This material has grown out of Chapters 2 and 4 of my PhD thesis Quantification under Conceptual Covers.     

Three-valued Logic,Indeterminacy and Quantum Mechanics

The paper consists of two parts. The first part begins with the problem of whether the original three-valued calculus, invented by J. ukasiewicz, really conforms to his philosophical and semantic intuitions. I claim that one of the basic semantic assumptions underlying ukasiewicz's three-valued logic should be that if under any possible circumstances a sentence of the form X will be the case at time t is true (resp. false) at time t, then this sentence must be already true (resp. false) at present. However, it is easy to see that this principle is violated in ukasiewicz's original calculus (as the cases of the law of excluded middle and the law of contradiction show). Nevertheless it is possible to construct (either with the help of the notion of supervaluation, or purely algebraically) a different three-valued, semi-classical sentential calculus, which would properly incorporate ukasiewicz's initial intuitions. Algebraically, this calculus has the ordinary Boolean structure, and therefore it retains all classically valid formulas. Yet because possible valuations are no longer represented by ultrafilters, but by filters (not necessarily maximal), the new calculus displays certain non-classical metalogical features (like, for example, non-extensionality and the lack of the metalogical rule enabling one to derive p is true or q is true from pqq is true).The second part analyses whether the proposed calculus could be useful in formalizing inferences in situations, when for some reason (epistemological or ontological) our knowledge of certain facts is subject to limitation. Special attention should be paid to the possibility of employing this calculus to the case of quantum mechanics. I am going to compare it with standard non-Boolean quantum logic (in the Jauch–Piron approach), and to show that certain shortcomings of the latter can be avoided in the former. For example, I will argue that in order to properly account for quantum features of microphysics, we do not need to drop the law of distributivity. Also the idea of reading off the logical structure of propositions from the structure of Hilbert space leads to some conceptual troubles, which I am going to point out. The thesis of the paper is that all we need to speak about quantum reality can be acquired by dropping the principle of bivalence and extensionality, while accepting all classically valid formulas.     

The impossibility of a bivalent truth-functional semantics for the non-Boolean propositional structures of quantum mechanics

Summary The general fact of the impossibility of a bivalent, truth-functional semantics for the propositional structures determined by quantum mechanics should be more subtly demarcated according to whether the structures are taken to be orthomodular latticesP _L or partial-Boolean algebrasP _A; according to whether the semantic mappings are required to be truth-functional or truth-functional ; and according to whether two-or-higher dimensional Hilbert spaceP structures or three-or-higher dimensional Hilbert spaceP structures are being considered. If the quantumP structures are taken to be orthomodular latticesP _L, then bivalent mappings which preserve the operations and relations of aP _L must be truth-functional . Then as suggested by von Neumann and Jauch-Piron and as proven in this paper, the mere presence of incompatible elements in aP _L is sufficient to rule out any semantical or hidden-variable proposal which imposes this strong condition, for anytwo-or-higher dimensional Hilbert spaceP _L structure. Thus from the orthomodular lattice perspective, the peculiarly non-classical feature of quantum mechanics and the peculiarly non-Boolean feature of the quantum propositional structures is the existence of incompatible magnitudes and propositions. However, the weaker truth-functionality condition can instead be imposed upon the semantic or hidden-variable mappings on theP _L structures, although such mappings ignore the lattice meets and joins of incompatibles and preserve only the partial-Boolean algebra structural features of theP _L structures. Or alternatively, the quantum propositional structures can be taken to be partial-Boolean algebrasP _A, where bivalent mappings which preserve the operations and relations of aP _A need only be truth-functional (c). In either case, the Gleason, Kochen-Specker proofs show that any semantical or hidden variable proposal which imposes this truth-functionality (c) condition is impossible for anythree-or-higher dimensional Hilbert spaceP _A orP _L structures. But such semantical or hidden-variable proposals are possible for any two dimensional Hilbert spaceP _A orP _L structures, in spite of the presence of incompatibles in these structures, in spite of the fact that Heisenberg's Uncertainty Principle applies to the incompatible elements in these structures, and in spite of the fact that these structures are non-Boolean in the Piron sense. The present paper is a sequel of the proceedings of theSociety of Exact Philosophy annual meeting, published in our issue 9:2, pp. 187–278. — Ed. I am indebted to my supervisor, Dr. Edwin Levy, for many hours of helpful discussion on the drafts leading to this paper.     

The abstract variable-binding calculus

Theabstract variable binding calculus (VB-calculus) provides a formal frame-work encompassing such diverse variable-binding phenomena as lambda abstraction, Riemann integration, existential and universal quantification (in both classical and nonclassical logic), and various notions of generalized quantification that have been studied in abstract model theory. All axioms of the VB-calculus are in the form of equations, but like the lambda calculus it is not a true equational theory since substitution of terms for variables is restricted. A similar problem with the standard formalism of the first-order predicate logic led to the development of the theory of cylindric and polyadic Boolean algebras. We take the same course here and introduce the variety of polyadic VB-algebras as a pure equational form of the VB-calculus. In one of the main results of the paper we show that every locally finite polyadic VB-algebra of infinite dimension is isomorphic to a functional polyadic VB-algebra that is obtained from a model of the VB-calculus by a natural coordinatization process. This theorem is a generalization of the functional representation theorem for polyadic Boolean algebras given by P. Halmos. As an application of this theorem we present a strong completeness theorem for the VB-calculus. More precisely, we prove that, for every VB-theory T that is obtained by adjoining new equations to the axioms of the VB-calculus, there exists a model D such that _T s=t iff _D s=t. This result specializes to a completeness theorem for a number of familiar systems that can be formalized as VB-calculi. For example, the lambda calculus, the classical first-order predicate calculus, the theory of the generalized quantifierexists uncountably many and a fragment of Riemann integration.The work of the first author was supported in part by National Science Foundation Grant #DMS 8805870.