Partial classical propositional logic

University of Minho School of Sciences Hugo Morais Martins Partial classical propositional logic Master’s Dissertation Master’s in Mathematics and Computation Dissertation supervised by Professor José Carlos Soares Espírito Santo october 2023 Copyright and Terms of Use for Third Party Work This dissertation reports on academic work that can be used by third parties as long as the internationally accepted standards and good practices are respected concerning copyright and related rights. This work can thereafter be used under the terms established in the license below. Readers needing authorization conditions not provided for in the indicated licensing should contact the author through the RepositóriUM of the University of Minho. CC BY-NC-SA https://creativecommons.org/licenses/by-nc-sa/4.0/ i Acknowledgements Considering one of the most significant stages of my life, there have been many people who played a part in my academic journey. Therefore, I would like to leave a piece of all of you here: To my advisor, Professor José Carlos Soares Espírito Santo, and to Professor Luís Filipe Ribeiro Pinto, I am immensely grateful for your constant presence and guidance in all our weekly meetings, and for the knowledge shared. I also appreciate your persistence in not giving up on me. To my sister, Catarina, to my mother, Ermelinda, and to my father, Orlando, I thank you for providing the essential familial comfort that has been crucial for my emotional and mental stability. You have been and will continue to be a significant part of me. To my friends from all places, thank you for always believing in me and for giving me strength when I needed it the most. A special thanks to those who, along with me, turned the “salas 24” at the University of Minho into a second home. To Centro de Matemática (CMAT) of University of Minho and to the Fundação Portuguesa para a Ciência e Tecnologia (FCT), I express my gratitude for the funding of this dissertation through the CMAT Research Scholarship - I&D UIDB/00013/2020. ii Statement of Integrity I hereby declare having conducted this academic work with integrity. I confirm that I have not used plagiarism or any form of undue use of information or falsification of results along the process leading to its elaboration. I further declare that I have fully acknowledged the Code of Ethical Conduct of the University of Minho. University of Minho, Braga, december 2023 Hugo Morais Martins iii Abstract Kochen and Specker developed in the 1960s an alternative to Birkhoff and von Neumann’s quantum logic based on partial Boolean algebras, called partial classical propositional logic, which has been recently revisited in studies of contextuality. Unlike more common quantum logics, in the language of the logic studied here, a new symbol is added to express a relation of commeasurability or compatibility. Semantically, the binary connectives are partial functions, with the logical value of a connective defined only for compatible propositions. This dissertation explores partial algebras, partial Boolean algebras and the concept of validity that they originate, comparing the notions of validity in this logic with those in classical propositional logic. The logical calculus of Kochen and Specker, which axiomatizes validity in partial classical propositional logic, is also studied. The theorems of soundness and completeness are proven, establishing an equivalence between both ways of characterizing the validity of this logic. Keywords partial classical propositional logic, partial algebras, partial Boolean algebras, quantum logic iv Resumo Kochen e Specker desenvolveram nos anos 60 uma alternativa à lógica quântica de Birkhoff e von Neumann baseada em álgebras Booleanas parciais, a lógica clássica proposicional parcial, recentemente revisitada em estudos de contextualidade. Contrariamente às lógicas quânticas mais comuns, à linguagem da lógica aqui estudada adiciona-se um novo símbolo, para exprimir uma relação de comensurabilidade ou compatibilidade. A nível semântico, os conetivos binários são funções parciais, estando o valor lógico de um conetivo definido apenas para proposições compatíveis. Nesta dissertação estudam-se as álgebras parciais, as álgebras Booleanas parciais e a noção de validade que originam e comparam-se as noções de validade desta lógica com a noção de validade da lógica clássica proposicional. Estuda-se também o cálculo lógico de Kochen e Specker que axiomatiza a validade na lógica clássica proposicional parcial. Demonstram-se os teoremas da correção e da completude, o que estabelece uma equivalência entre ambas as formas de caracterizar a validade desta lógica. Palavras-chave lógica clássica proposicional parcial, álgebras parciais, álgebras Booleanas parciais, lógica quântica v Contents 1 Introduction 1 2 Preliminaries 4 2.1 Algebra over a field and its properties . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.2 Lattices and their properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.3 ClassicalLogic .................................... 7 2.3.1 Boolean algebra and its properties . . . . . . . . . . . . . . . . . . . . . . 7 2.3.2 PropositionalLogic.............................. 7 2.4 Graphs and equivalence relations . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3 Partial algebras 10 3.1 Partial algebra and its properties . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.2 Polynomials in the context of partial algebras . . . . . . . . . . . . . . . . . . . . . 13 3.3 A partial algebra in a graph context . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.4 Identities in a partial algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 4 Partial Boolean algebras 33 4.1 Partial Boolean algebra and its properties . . . . . . . . . . . . . . . . . . . . . . . 33 4.2 Partial Boolean algebra induced by a partial algebra . . . . . . . . . . . . . . . . . . 36 4.3 Boolean polynomials in the context of a partial Boolean algebra . . . . . . . . . . . . 44 5 Partial classical propositional logic 53 5.1 Q-validity....................................... 53 5.2 Axiomaticsystem................................... 57 5.2.1 Q-proofofaformula............................. 58 5.3 Soundness of the axiomatic system . . . . . . . . . . . . . . . . . . . . . . . . . . 60 5.4 Completeness of the axiomatic system . . . . . . . . . . . . . . . . . . . . . . . . . 64 vi 2.2 Lattices and their properties Definition 2.2.1. A lattice is a structure (B, ∨,∧) where B is a nonempty set and the operations ∨ and ∧ are defined from B×B to B and the following properties are satisfied: For all a, b, c ∈B , (i) a∨a=a∧a=a (Idempotency) (ii) a∨b=b∨a and a∧b=b∧a (Commutativity) (iii) (a∧b)∧c=a∧(b∧c) and (a∨b)∨c=a∨(b∨c) (Associativity) (iv) a∧(a∨b) = a∨(a∧b) = a (Absorption) We call ∨ as supremum and ∧ as infimum. Definition 2.2.2. Let A be a set and ≤ a binary relation in A . One says that ≤ is a partial order relation in A if the following properties are satisfied: For all a, b, c ∈A , (i) a≤a (Reflexivity) (ii) ( a≤b and b≤a ) ⇒a=b (Antisymmetry) (iii) ( a≤b and b≤c ) ⇒a≤c (Transitivity) We call the pair (A, ≤) a partially ordered set (poset). Definition 2.2.3. A lattice (B, ∨,∧) is distributive iff one of the following properties hold: For all a, b, c ∈B (i) a∧(b∨c) = (a∧b)∨(a∧c) (ii) a∨(b∧c) = (a∨b)∧(a∧c) Observations: Let us consider a lattice (B, ∨,∧). For all a, b ∈B, we have the following statements: (i) a∧b=aiff a∨b=b (ii) The relation ≤is defined such that a≤biff a∧b=a (iii) ≤is a partial order relation and, consequently, we have that (B, ≤)is a poset (iv) Let us consider a poset (B, ≤)such that, for all a, b ∈B, there exists W{a, b}and V{a, b}, where W{a, b}denotes the supremum of {a, b}and V{a, b}denotes the infimum of {a, b}. Then, (B, ≤)is a lattice, where W{a, b}=a∨band V{a, b}=a∧b. 6 2.3 Classical Logic 2.3.1 Boolean algebra and its properties Definition 2.3.1. A Boolean algebra is a structure B= (B, ∨,∧,¬,1,0) , where ∨ and ∧ are two binary operations on B , ¬ is a unary operation on B , 1∈B and 0∈B , such that: (i) (B, ∨,∧) is a distributive lattice (ii) a∧0=0 and a∨1=1 , for all a∈B (which is equivalent to a∨0=a and a∧1=a , respectively) (iii) a∧ ¬a=0 and a∨ ¬a=1 , for all a∈B We call the operation ¬ complement and for a∈B we say that ¬a is the complement of a . Lemma 2.3.2. Let B= (B, ∨,∧,¬,1,0) be a Boolean algebra. Then, we have the following properties: For all a, b ∈B , 1. ¬¬a=a 2. ¬0=1 and ¬1=0 3. ¬(a∨b) = ¬a∧ ¬b and ¬(a∧b) = ¬a∨ ¬b It is convenient to rephrase the usual truth-table semantics of classical propositional formulas, defined so that each connective is seen as an operation acting on the set {0,1}[13], as a semantics based on the following specific Boolean algebra: Definition 2.3.3. Let B= ({0,1},∨,∧,¬,1,0) be a Boolean algebra, where the operations are defined in the usual way by the truth tables. One calls B the Boolean algebra of truth values. [12] 2.3.2 Propositional Logic Definition 2.3.4. Let n∈N . Σn is the set of formulas of the propositional calculus in the variables x1,· · · , xn and the connectives ∨ and ¬ , defined inductively by: 1. xi∈Σn , for i∈ {1,· · · , n} 2. If α∈Σn , then (¬α)∈Σn 7 3. If α, β ∈Σn , then (α∨β)∈Σn We will call X to the set of all propositional variables xi , that is, X={xi:i∈N} . The set of all formulas of propositional calculus is Σ = S n∈N Σn . Observations: • In general, parentheses will be omitted in a formula when it does not cause ambiguity. • The lower case letters of the Greek alphabet α,β,γand θwill be used to denote formulas of the propositional calculus. Definition 2.3.5. A valuation in a Boolean algebra B= (B, ∨,∧,¬,1,0) is any map v from the set of propositional variables X to B . The value of a formula α∈Σn with respect to a valuation v , α(v) , is defined by recursion: (i) xi(v) = v(xi) , for all i∈N (ii) ¬α(v) = ¬α(v) , for all α∈Σn (iii) α∨β(v) = α(v)∨β(v) , for all α, β ∈Σn One writes: •B, v |=αwhen α(v) = 1in the Boolean algebra B; •B | =αwhen B, v | =α, for all vvaluation in the Boolean algebra B. Definition 2.3.6 (C-validity). Let B be the Boolean algebra of truth values. A propositional formula α is a tautology in classical logic if B|=α . Theorem 2.3.7. A propositional formula α is C -valid iff B |=α , for all Boolean algebras B . Proof. See [6, 12]. Notation: Let β∈Σn. We write β(α1,· · · , αn)to denote the simultaneous substitution in βof each formula αifor the corresponding variable xi, for i∈ {1,· · · , n}. Theorem 2.3.8 (Principle of substitution for tautologies). Let α1 , α2 , · · · , αn be n formulas of propositional logic in the variables x1,· · · , xn , n∈N , and β a tautology (in the same n variables). Then, β(α1, α2,· · · , αn) is also a tautology in the same n variables. 8 2.4 Graphs and equivalence relations Definition 2.4.1. A graph G is a structure (G, R) , where G is a nonempty set whose elements are called vertices and R⊆G2 is a binary symmetric and irreflexive relation on G . We are going to read R(a, b) as “ a and b are connected”, for all a, b ∈G . Observation: We will use both the notations R(a, b)and (a, b)∈Rto represent that the element (a, b)is in the relation R. Definition 2.4.2. Let A be a set and R be a binary relation on A . R is an equivalence relation if: 1. R is reflexive, i.e, for all a∈A , (a, a)∈R 2. R is symmetric, i.e., for all a, b ∈A , if (a, b)∈R , then (b, a)∈R 3. R is transitive, i.e., for all a, b, c ∈A , if (a, b)∈R and (b, c)∈R , then (a, c)∈R Definition 2.4.3. Let A be a set and R be a binary equivalence relation on A . The equivalence class of a∈A is defined as the set [a]R={x∈A: (a, x)∈R} , which represents the elements that are related to a under the relation R . The quotient set is represented by A/R={[a]R:a∈A} , which contains all the equivalence classes of the elements in A . 9 Chapter 3 Partial algebras In this chapter, we will introduce partial algebras along with associated definitions and propositions. Polynomials within the context of partial algebras, including their domain and associated mappings, will be discussed. The concept of identities in partial algebras will also be introduced, with examples illustrating both identities holding in all partial algebras and others that do not. Considerable space will be dedicated to one example of the latter kind, involving the construction of a partial algebra of functions associated with special graphs. 3.1 Partial algebra and its properties Definition 3.1.1. A partial algebra A= (A, ⊸ ,+,·,◦,1) is defined by a nonempty set A , a binary relation ⊸ on A , called compatibility or commeasurability, two partial binary operations on A , + and · , called sum and product, respectively, a function ◦ defined from R×A to A and the identity element for the operation product of A , called 1 , with the following properties: 1. The relation ⊸ is reflexive and symmetric 2. For all q∈A , q ⊸ 1 (i.e., 1 is compatible with all elements in A ) 3. The partial binary functions are defined exactly for those pairs (q1, q2)∈A×A for which q1 ⊸ q2 4. If any two of q1 , q2 and q3 are commeasurable (i.e., for all i, j ∈ {1,2,3}, qi ⊸ qj ), then (q1+ q2) ⊸ q3 , (q1·q2) ⊸ q3 and (a◦q1) ⊸ q2 ( a is a real number) 5. If any two of q1 , q2 and q3 are commeasurable, then the algebra of the polynomials in q1 , q2 and q3 (defined in the observation below) is a commutative algebra over the field of real numbers Following the article [9], we call the elements of A observables. 10 Observations: • It is important to note that the concept “partial algebra” is an abbreviation of “partial commutative algebra over the field of real numbers”, and the latter generalizes the concept of “commutative algebra over the field of real numbers”, as introduced in the previous definition. • Let us assume (A, ⊸ ,+,·,◦,1)defined as in the previous definition. If q1,q2, and q3are pairwise commeasurable, then the algebra of the polynomials in q1, q2and q3is the structure (A′,+′,·′,◦′,1), where: •A′⊆Ais inductively defined: 1. q1,q2,q3∈A′ 2. 1∈A′ 3. If x, y ∈A′and x ⊸ y, then x+y, x ·y∈A′ 4. If x∈A′and a∈R, then a◦x∈A′ • The operations +′,·′and ◦′are a restriction of the original ones +,·and ◦, respectively, that is: +′= +|A′×A′,·′=·|A′×A′,◦′=◦|R×A′ Now, we will verify that the previous structure (A′,+′,·′,◦′,1)constitutes an algebraic structure, that is, the operations +′,·′and ◦′are total functions and that A′is closed under these operations. Lemma 3.1.2. Any two elements of A′ are compatible. Proof. Let us suppose that x∈A′,q1 ⊸ q2, q1 ⊸ q3and q2 ⊸ q3. Let us consider P(x)the property: for all z∈A′,x ⊸ z. The proof follows by induction on x∈A′. 1. We want to show P(q1), that is, for all z∈A′,q1 ⊸ z. Let z∈A′and let us consider the following property: for all y∈A′,Q(y)iff y ⊸ q1. (i) Q(q1)iff q1 ⊸ q1. Since ⊸ is reflexive, then q1 ⊸ q1holds. (ii) Q(q2)iff q1 ⊸ q2, which is true based on the hypothesis. (iii) Q(q3)iff q1 ⊸ q3, which is also true based on the hypothesis. (iv) Q(1)iff 1 ⊸ q1. Since q1∈A′,1is commeasurable with all elements of Aand A′⊆A, then 1 ⊸ q1. 11 (v) Let us suppose Q(x),Q(y)and x ⊸ y,x, y ∈A′. We want to show Q(x+y)and Q(x·y), that is, (x+y) ⊸ q1and (x·y) ⊸ q1, respectively. Since x ⊸ q1,y ⊸ q1and x ⊸ y, i.e., any two of x, y, q1are commeasurable then, by definition 3.1.1, (x+y) ⊸ q1and (x·y) ⊸ q1. (vi) Let us suppose Q(x),x∈A′. We want to show Q(a◦x),a∈R. Since, by Q(x),x ⊸ q1 then, by definition 3.1.1, (a◦x) ⊸ q1,a∈R. The proofs of P(q2)and P(q3)are analogous. 2. We want to show P(1), that is, for all z∈A′,1 ⊸ z. Let z∈A′. Since 1is compatible with all the observables in Aand A′⊆A, then 1 ⊸ z. 3. Let us suppose P(x),P(y)and x ⊸ y, for x, y ∈A′. We want to show P(x+y)and P(x·y), that is, for all z∈A′,(x+y) ⊸ zand (x·y) ⊸ z, respectively. Let z∈A′. By the hypothesis P(x)and P(y), we have, respectively, that x ⊸ zand y ⊸ z, and by the fact that x ⊸ y, we have that any two of x, y, z are commeasurable. So, by definition 3.1.1, (x+y) ⊸ zand (x·y) ⊸ z. 4. Let us suppose P(x), for x∈A′. We want to show P(a◦x), that is, for all z∈A′,(a◦x) ⊸ z. Let z∈A′. By the hypothesis P(x),x ⊸ z. So, by definition 3.1.1, (a◦x) ⊸ z, for all a∈R. So P(x), for all x∈A′. Proposition 3.1.3. The operations +′,·′ and ◦′ are total functions and A′ is closed under these operations. Proof. Let us consider x, y ∈A′. We want to show that x+′y∈A′,x·′y∈A′and a◦′x∈A′, for all a∈R. By lemma 3.1.2, x ⊸ y. Consequently, the elements x+y,x·yand a◦ybelong to A′(due to the statements 3 and 4 of the definition of A′). By definition of restriction of a function, the value of x+′y is x+y, the value of x·′yis x·yand the value of a◦′yis a◦y. So, x+′y, x ·′y, a ◦′x∈A′. Observation: Sometimes, in order to clarify certain results, it can be useful to write (qi, qj)∈ ⊸ instead of qi ⊸ qj. Proposition 3.1.4. We can generalize the statement 5 of the definition of partial algebra (3.1.1) to any number of observables, that is, if any two of q1,· · · , qn are commeasurable, n∈N , then the algebra of the polynomials in q1,· · · , qn is a commutative algebra over the field of real numbers. 12 3.2 Polynomials in the context of partial algebras Definition 3.2.1. Let n∈N . Let Pn , the set of polynomials in x1,· · · , xn , be defined as: (i) 1∈Pn (ii) xi∈Pn , for all 1≤i≤n (iii) If φ∈Pn , then a◦φ∈Pn , for all a∈R (iv) If φ, ψ ∈Pn , then φ+ψ∈Pn and φ·ψ∈Pn The set of all polynomials is S n∈N Pn . Observations: • The polynomials of Pnare expressions over the alphabet {x1,· · · , xn}∪{1,◦,+,·} ∪ R. • The lower case letters of the Greek alphabet φ,ψand χwill be used to denote polynomials. Definition 3.2.2. Let A= (A, ⊸ ,+,·,◦,1) be a partial algebra and Pn be the set of polynomials previously defined. We define recursively on a polynomial φ∈Pn the set Dφ,n ⊆An and the map φ∗:Dφ,n →A as follows: 1. If φ= 1 , then Dφ,n =An and φ∗(q) = 11 2. If φ=xi,1≤i≤n , then Dφ,n =An and φ∗(q) = φ∗((q1,· · · , qn)) = qi 3. If φ=a◦ψ , then Dφ,n =Dψ,n and φ∗(q) = a◦ψ∗(q) 4. If φ=ψ⊗χ , where ⊗ ∈ {+,·} , then Dφ,n ={q ∈An:q ∈Dψ,n∩Dχ,n and ψ∗(q) ⊸ χ∗(q)} and φ∗(q) = ψ∗(q)⊗χ∗(q) Dφ,n and φ∗(q) are, respectively, the domain and the map associated to the polynomial φ relative to A . 1In order to simplify the notation, we will write q to denote (q1,··· , qn). 13 3.3 A partial algebra in a graph context Definition 3.3.1. A graph G= (G, R) satisfies condition C if it satisfies the following two properties: 1. For all a, b ∈G , if R(a, b) then there exists exactly one c∈G such that R(a, c) and R(b, c) , that is, any two connected vertices belong to exactly one triangle. 2. G contains, at least, one pair of connected vertices. The following graph satisfies the condition C: G= (G, R), where G={a1, a2, a3}and R(a, b)iff a6=b, for all a, b ∈G. In fact, Gis a triangle of the type: a1 a2a3 Definition 3.3.2. F is a class of functions associated with a graph G satisfying the condition C when any f∈F is a function whose values are real numbers and the domain, domf , is a set of three vertices of G any two of which are connected. Definition 3.3.3. Let F be a class of functions associated with a graph G . E is the binary relation defined on F such that E(f, g) holds iff one of the following conditions is satisfied: 1. f=g 2. The sets domf and domg have one element in common, say domf={a, b, c} , domg= {a, b′, c′} and f(a) = g(a) and f(b) = f(c) = g(b′) = g(c′) 3. f(a) = g(b) = r , r∈R , for all a∈domf, b ∈domg ( f and g are both constant functions with the same constant value) Observation: From now on, when we refer to relation E, we assume that a graph G= (G, R)that satisfies the condition C and a class of functions, F, associated with the graph G, are implicitly understood. Lemma 3.3.4. E is an equivalence relation. Proof. To prove that Eis an equivalence relation we need to show that: 14 (i) Eis reflexive: Let f∈F. By the first statement of the definition 3.3.3, E(f, f)holds. (ii) Eis symmetric: Let f, g ∈Fsuch that E(f, g). We want to prove E(g, f). Then, we have one of three cases: 1. Case f=g: Then, by hypothesis, we have that E(f, f)holds. 2. Case domf={a, b, c},domg={a, b′, c′},f(a) = g(a)and f(b) = f(c) = g(b′) = g(c′)(domfand domgonly have the element ain common). Since the relation =is symmetric, then g(a) = f(a)and g(b′) = g(c′) = f(b) = f(c), that is, E(g, f). 3. Case f(a) = g(b), for all a∈domfand b∈domg. Since the relation =is symmetric, then g(b) = f(a), for all b∈domgand a∈domf, that is, E(g, f). (iii) Eis transitive: Let f, g, h ∈Fsuch that E(f, g)and E(g, h)hold. We want to prove E(f, h). 1. Case f=gor g=h: Then, E(f, h)holds from one of the hypothesis. 2. Case E(f, g)and E(g, h)come from the second statement of the definition 3.3.3: • Case domfand domghave one element in common, say domf={a, b, c}, domg= {a, b′, c′}and f(a) = g(a),f(b) = f(c) = g(b′) = g(c′), and domgand domh have also one element in common but it is different from the common element of domf and domg, say domh={a′′, b′, c′′}and g(b′) = h(b′),g(a) = g(c′) = h(a′′) = h(c′′). Then, we have that for all x∈domf,y∈domg,z∈domh,f(x) = g(y) = h(z). Since f(x) = h(z)for all x∈domf,z∈domh,E(f, h)holds. • Case domf,domgand domhhave the same element in common (and the only one), say domf={a, b, c}, domg={a, b′, c′}, domh={a, b′′, c′′}and f(a) = g(a), f(b) = f(c) = g(b′) = g(c′)(this comes from E(f, g)) and g(a) = h(a),g(b′) = g(c′) = h(b′′) = h(c′′)(this comes from E(g, h)). Then, f(a) = h(a)and f(b) = f(c) = h(b′′) = h(c′′), that is, E(f, h)holds. 3. Case E(f, g)comes from the second statement of the definition 3.3.3, that is, domfand domghave one element in common, say domf={a, b, c}, domg={a, b′, c′},f(a) = g(a)and f(b) = f(c) = g(b′) = g(c′), and E(g, h)comes from the third statement of the same definition, i.e., g(x) = h(y), for all x∈domgand y∈domh. Then, gand 15 (iv) We want to prove that there exists a symmetric element for all the observables in Q′, that is, for all x∈Q′, there exists y∈Q′such that x+′y=y+′x=0, where 0is the identity element for the operation +′. Let us consider x∈Q′and f∈xand the function gdefined such that domg=domfand for all a∈domg, g(a) = −f(a). Then, for all a∈domg, (f+g)(a) = f(a) + g(a) = f(a)−f(a) = 0 and (g+f)(a) = g(a) + f(a) = −f(a) + f(a) = 0 Since f+g, g +f∈Fand for all a∈domf+g=domg+f,(f+g)(a) = (g+f)(a) = 0, then f+g, g +f∈0. So, x+′y=y+′x=0. (v) Let a, b ∈Rand x∈Q′. We want to prove that (a+b)◦′x=a◦′x+′b◦′x. Let f∈x. Then, (a+b)◦′x(a) = (a+b)◦′[f]E (b) = [(a+b)×f]E (c) = [a×f+b×f]E (d) = [a×f]E+′[b×f]E (e) =a◦′[f]E+′b◦′[f]E (f) =a◦′x+b◦′x, where +and × are the sum and the product in the field of real numbers, respectively. (a) fis a representative of the class x (b) Definition of scalar product in A′ (c) Distributivity of +with respect to ×, where +and ×are defined in the field of real numbers (d) Definition of sum of commeasurable observables (e) Definition of scalar product in A′ (f) fis a representative of the class x (vi) Let a∈Rand x, y ∈Q′. We want to prove that a◦′(x+′y) = a◦′x+′a◦′y. Let f∈xand g∈ysuch that domf=domg. Then, a◦′(x+′y)(a) =a◦′([f]E+′[g]E)(b) = a◦′[f+g]E (c) = [a×(f+g)]E (d) = [a×f+a×g]E (e) = [a×f]E+′[a×g]E (f) = a◦′[f]E+′a◦′[g]E (g) =a◦′x+′a◦′y, where +and ×are the sum and the product in the field of real numbers, respectively. (a) fand gare representatives of the classes xand y, respectively (b) Definition of sum of commeasurable observables (c) Definition of scalar product in A′ (d) Distributivity of +with respect to ×, where +and ×are defined in the field of real numbers 22 (e) Definition of sum of commeasurable observables (f) Definition of scalar product in A′ (g) fand gare representatives of the classes xand y, respectively (vii) Let a, b ∈Rand x∈Q′. We want to prove that (a×b)◦′x=a◦′(b◦′x). Let us consider f∈x. Then, (a×b)◦′x(a) = (a×b)◦′[f]E (b) = [(a×b)×f]E (c) = [a×(b×f)]E (d) =a◦′[b×f]E (e) =a◦′(b◦′[f]E)(f) =a◦′(b◦′x) (a) fis a representative of the class x (b) Definition of scalar product in A′ (c) The operation ×, in the field of real numbers, is associative (d) Definition of scalar product in A′ (e) Definition of scalar product in A′ (f) fis a representative of the class x (viii) Let x∈Q′. We want to show that 1◦′x=x, where 1is the multiplicative identity of the field of real numbers. Let us consider f∈x. Then, 1◦′x(a) = 1 ◦′[f]E (b) = [1 ×f]E (c) = [f]E (d) =x, where ×is the product in the field of real numbers. (a) fis a representative of the class x (b) Definition of scalar product in A′ (c) The real number 1is the identity of ◦in the field of real numbers (d) fis a representative of the class x So, Q′is a vector space over the field of real numbers. • Considering the previous fact, now we need to prove that the operation ·′satisfies the following four properties: associativity, right distributivity, left distributivity and compatibility with scalars. Once this is proved, A′will be an algebra over the field of real numbers. (i) Let x, y, z ∈Q′. We want to prove that (x·′y)·′z=x·′(y·′z). Let us consider f∈x,g∈yand h∈zsuch that domf=domg=domh. Then, (x·′y)·′z(a) = ([f]E·′[g]E)·′[h]E (b) = [f×g]E·′[h]E (c) = [(f×g)×h]E (d) = [f×(g×h)]E (e) = [f]E·′[g×h]E (f) = [f]E·′([g]E·′[h]E)(g) =x·′(y·′z), where ×is the product in the field of real numbers. (a) f,gand hare representatives of the classes x,yand z, respectively (b) Definition of product of commeasurable observables in A′ 23 (c) Definition of product of commeasurable observables in A′ (d) The operation ×, in the field of real numbers, is associative (e) Definition of product of commeasurable observables in A′ (f) Definition of product of commeasurable observables in A′ (g) f,gand hare representatives of the classes x,yand z, respectively (ii) Let x, y, z ∈Q′. We want to prove that (x+′y)·′z=x·′z+′y·′z. Let us consider f∈x,g∈yand h∈zsuch that domf=domg=domh. Then, (x+′y)·′z(a) = ([f]E+′[g]E)·′[h]E (b) = [f+g]E·′[h]E (c) = [(f+g)×h]E (d) = [f×h+g×h]E (e) = [f×h]E+′[g×h]E (f) = [f]E·′[h]E+′[g]E·′[h]E (g) =x·′z+′y·′z, where ×is the product in the field of real numbers. (a) f,gand hare representatives of the classes x,yand z, respectively (b) Definition of sum of commeasurable observables in A′ (c) Definition of product of commeasurable observables in A′ (d) Distributivity of ×with respect to +in the field of real numbers (e) Definition of sum of commeasurable observables in A′ (f) Definition of product of commeasurable observables in A′ (g) f,gand hare representatives of the classes x,yand z, respectively (iii) This case is analogous to the previous one. (iv) Let x, y ∈Q′and a, b ∈R. We want to prove that (a◦′x)·′(b◦′y) = (a×b)◦′(x·′y). Let us consider f∈xand g∈ysuch that domf=domg. Then, (a◦′x)·′(b◦′ y)(a) = (a◦′[f]E)·′(b◦′[g]E)(b) = [a×f]E·′[b×g]E (c) = [(a×f)×(b×g)]E (d) = [(a×b)×(f×g)]E (e) = (a×b)◦′[f×g]E (f) = (a×b)◦′([f]E·′[g]E)(g) = (a× b)◦′(x·′y), where ×is the product in the field of real numbers. (a) fand gare representatives of the classes xand y, respectively (b) Definition of scalar product in A′ (c) Definition of product of commeasurable observables in A′ (d) The operation ×, in the field of real numbers, is commutative and associative (e) Definition of scalar product in A′ (f) Definition of product of commeasurable observables in A′ (g) fand gare representatives of the classes xand y, respectively 24 So, since Q′is a vector space over the field of real numbers and the ·′operation satisfies these four properties, then A′is an algebra over the field of real numbers. • It remains to show that the operation ·′is commutative. Let x, y ∈Q′. We want to show that x·′y=y·′x. Let us consider f∈xand g∈ysuch that domf=domg. Then, x·′y(a) = [f]E·′[g]E (b) = [f×g]E (c) = [g×f]E (d) = [g]E·′[f]E (e) = y·′x (a) fand gare representatives of the classes xand y, respectively (b) Definition of product of commeasurable observables in A′ (c) The operation ×, in the field of real numbers, is commutative (d) Definition of product of commeasurable observables in A′ (e) fand gare representatives of the classes xand y, respectively So, since A′is an algebra over the field of real numbers and the operation ·′is commutative, we conclude that A′is a commutative algebra over the field of real numbers. 3.4 Identities in a partial algebra Definition 3.4.1. Let A be a partial algebra. One says “ φ is identically 1 on A ” or, equivalently, “the identity φ= 1 holds in A ”, if for all q∈Dφ,n, φ∗(q) = 1 . Observations: Let φand ψbe two polynomials in nvariables. Then, an identity φ=ψholding in A can be interpreted in two ways: • If q ∈Dφ,n ∩Dψ,n, then φ∗(q) = ψ∗(q)(the identity φ=ψholds strongly in A) • If q ∈Dφ,n ∩Dψ,n and φ∗(q) ⊸ ψ∗(q), then φ∗(q) = ψ∗(q)(the identity φ=ψholds weakly in A) The first statement implies the second one but the converse is not necessarily true. If ψ= 1, then both statements are equivalent. Now, we will give some examples of identities holding in all partial algebras and others that do not, which were taken from the article [9]. Example 1. Let us consider φ=x1+x2and ψ=x2+x1two polynomials in 2variables. The identity φ=ψholds strongly (and, consequently, weakly) in all partial algebras. 25 Proof. Let A= (A, ⊸ ,+,·,◦,1)be a partial algebra and φ=x1+x2and ψ=x2+x1be two polynomials in 2variables. We want to prove that the identity φ=ψholds in A, that is, for all q ∈Dφ,2∩Dψ,2, φ∗(q) = ψ∗(q). Let q = (q1, q2)∈Dφ,2∩Dψ,2. By definition, Dx1+x2,2={q ∈A2:q ∈Dx1,2∩Dx2,2and x1 ∗(q) ⊸ x2 ∗(q)} ={q ∈A2:q1 ⊸ q2} =Dx2+x1,2 So, φ∗(q)(i) =q1+q2 (ii) =q2+q1 (iii) =ψ∗(q). (i) Definition of φ∗(q) (ii) Since q1and q2are commeasurable ( by definition of Dx1+x2,2) the algebra of the polynomials in q1and q2is a commutative algebra over the field of real numbers (by definition 3.1.1, statement 5). Therefore, we have commutativity for the operation + (iii) Definition of ψ∗(q) Example 2. Let us consider φ= (x1+x2) + x3and ψ=x1+ (x2+x3)two polynomials in 3 variables. The identity φ=ψholds strongly (and, consequently, weakly) in all partial algebras. Proof. Let A= (A, ⊸ ,+,·,◦,1)be a partial algebra and φ= (x1+x2)+x3and ψ=x1+(x2+x3) be two polynomials in 3variables. We want to prove that the identity φ=ψholds in A, that is, for all q ∈Dφ,3∩Dψ,3, φ∗(q) = ψ∗(q). Let q = (q1, q2, q3)∈Dφ,3∩Dψ,3. By definition, Dφ,3={q ∈A3:q ∈Dx1+x2∩Dx3and (x1+x2)∗(q) ⊸ x3 ∗(q)} ={q ∈A3:q ∈Dx1∩Dx2∩Dx3and x1 ∗(q) ⊸ x2 ∗(q)and (x1+x2)∗(q) ⊸ x3 ∗(q)} ={q ∈A3:x1 ∗(q) ⊸ x2 ∗(q)and (x1+x2)∗(q) ⊸ x3 ∗(q)} ={q ∈A3:q1 ⊸ q2and (q1+q2) ⊸ q3} and Dψ,3={q ∈A3:q ∈Dx1∩Dx2+x3and x1 ∗(q) ⊸ (x2+x3)∗(q)} ={q ∈A3:q ∈Dx1∩Dx2∩Dx3and x2 ∗(q) ⊸ x3 ∗(q)and x1 ∗(q) ⊸ (x2+x3)∗(q)} ={q ∈A3:x2 ∗(q) ⊸ x3 ∗(q)and x1 ∗(q) ⊸ (x2+x3)∗(q)} ={q ∈A3:q2 ⊸ q3and q1 ⊸ (q2+q3)} 26 We have that q1 ⊸ q2,q2 ⊸ q3and q1 ⊸ (q2+q3). Consequently, due to the fact that q2 ⊸ q2and q2 ⊸ q3, we have q2 ⊸ (q2+q3). Therefore, any two of q1,q2and q2+q3are commeasurable, which implies that the algebra of the polynomials in q1,q2and q2+q3is a commutative algebra over the field of real numbers. Additionally, we also know (q1+q2) ⊸ q3. Analogously to what we have previously done, since q2 ⊸ q2 and q2 ⊸ q1,q2 ⊸ (q1+q2). Thus, any two of q1+q2,q2and q3are commeasurable and, consequently, the algebra of the polynomials in q1+q2,q2and q3is a commutative algebra over the field of real numbers. Then, we have: φ∗(q)(i) = (q1+q2) + q3 (ii) = [(q1+q2) + q3] + 0 (iii) = [(q1+q2) + q3]+(q2−q2) (iv) = (q1+q2)+[q3+ (q2−q2)] (v) = (q1+q2) + [(q2−q2) + q3] (vi) = (q1+q2) + [(−q2+q2) + q3] (vii) = (q1+q2)+[−q2+ (q2+q3)] (viii) = [(q1+q2)−q2]+(q2+q3) (ix) = [q1+ (q2−q2)] + (q2+q3) (x) = [q1+0]+(q2+q3) (xi) =q1+ (q2+q3) (xii) =ψ∗(q) (i) Definition of φ∗(q) (ii) Since q1+q2,q2and q3are all commeasurable, then there exists the identity element for the operation +, which is represented by 0 (iii) q1+q2,q2and q3have a symmetric element. −q2is the symmetric element of q2 (iv) Since q1+q2,q2and q3are all commeasurable, then we can apply the associative rule (v) Commutativity (of the algebra of the polynomials in q1+q2,q2and q3) (vi) Commutativity (of the algebra of the polynomials in q1+q2,q2and q3) (vii) Associativity (of the algebra of the polynomials in q1+q2,q2and q3) 27 (viii) Associativity (of the algebra of the polynomials in q1,q2and q2+q3) (ix) Associativity (of the algebra of the polynomials in q1,q2and q2+q3) (x) q2−q2=0 (xi) 0is the identity for the operation + (xii) Definition of ψ∗(q) Example 3. Let us consider φ= (x1+x2) + (x3+x4)and ψ= (x1+x4) + (x2+x3)two polynomials in 4variables. The identity φ=ψdoes not weakly (and, consequently, strongly) hold in all partial algebras. Proof. We want to show that there exists a partial algebra such that for all q = (q1, q2, q3, q4)∈ Dφ,4∩Dψ,4and φ∗(q) ⊸ ψ∗(q),φ∗(q)6=ψ∗(q), that is, for all q ∈Dφ,4∩Dψ,4and φ∗(q) ⊸ ψ∗(q), ((x1+x2)+(x3+x4))∗(q)6= ((x1+x4)+(x2+x3))∗(q), which simplifies to (q1+q2)+(q3+ q4)6= (q1+q4) + (q2+q3). Let us denote the following graph G, which satisfies the condition C(note that the vertices a1and a2appear twice in the graph): a1 a4a3 a2 a5 a6 a7a8 a9a10 a11 a1 a2 Now, let us consider four functions f1, f2, f3and f4such that domf1={a1, a3, a4},domf2= {a1, a3, a4},domf3={a2, a3, a5}and domf4={a2, a9, a11}. We are going to define them as follows: 28 f1:domf1→Rf2:domf2→Rf3:domf3→Rf4:domf4→R f1(a1) = 1 f2(a1) = 0 f3(a2) = 1 f4(a2) = 0 f1(a3) = 0 f2(a3) = 1 f3(a3) = 0 f4(a9) = 0 f1(a4) = 0 f2(a4) = 0 f3(a5) = 0 f4(a11) = 1 Observation: All the functions f1, f2, f3and f4belong to the class of functions Fassociated with the graph Gas they yield real numbers and their domain is a set of three vertices of Gany two of which are connected. So, henceforth, when introducing new functions and assuming they belong to F, it is implied that their domain is one of the triangles of the graph Gand they produce real values. We are going to consider the previous four functions as the representatives of the observables q1, q2, q3 and q4, i.e., q1= [f1]E,q2= [f2]E,q3= [f3]Eand q4= [f4]E. Then, we have: •q1+q2= [f1+f2]Eand we obtain f1+f2:domf1−→ R (f1+f2)(a1) = 1 + 0 = 1 (f1+f2)(a3) = 0 + 1 = 1 (f1+f2)(a4) = 0 + 0 = 0 •q3+q4is not equal to [f3+f4]Ebecause f3and f4have different domains and, therefore, they are not commeasurable and the operation sum is not defined. So, we just need to consider, for instance, a function g3such that domg3=domf4and g3∈[f3]E, that is, g3∈Fand E(f3, g3). Let domg3=domf4and g3(a2) = f3(a2) = 1 and g3(a9) = g3(a11) = f3(a3) = f3(a5) = 0. Then, domg3and domf3have one element in common and, by defining g3in this way, it satisfies the second statement of the definition of the relation E (3.3.3). So, q3+q4= [g3+f4]Eand we obtain g3+f4:domg3−→ R (g3+f4)(a2) = 1 + 0 = 1 (g3+f4)(a9) = 0 + 0 = 0 (g3+f4)(a11) = 0 + 1 = 1 29 • In a similar manner to the previous case, the domains of f1and f4are not the same and, therefore, it does not make sense to define q1+q4as [f1+f4]E. So, let us choose two functions g1and g4 such that g1∈[f1]E,g4∈[f4]Eand domg1=domg4. We need to guarantee that E(f1, g1)and E(f4, g4)hold. To address this, we are going to consider domg1={a1, a11, a10},g1(a1) = 1 and g1(a11) = g1(a10)=0as it is aligned with the second statement of the definition of the relation E(3.3.3). In an analogous way, let us consider domg4={a1, a11, a10},g4(a11) = 1 and g1(a1) = g1(a10) = 0. (It should be noted that we could have chosen, for instance, a function g4∈[f4]Esuch that domg4=domf1. However, in this case, we are following the counterexample provided by the authors of the article [9] and it is known that finding these counterexamples is not straightforward). So, q1+q4= [g1+g4]Eand we obtain g1+g4:domg1−→ R (g1+g4)(a1) = 1 + 0 = 1 (g1+g4)(a10) = 0 + 0 = 0 (g1+g4)(a11) = 0 + 1 = 1 • Once again, since domf2and domf3are not the same, it does not make sense to define q2+q3 as [f2+f3]E. So, we are going to find a function g2such that domg2=domf3and E(f2, g2) holds. Let us consider domg2=domf3,g2(a3) = f2(a3)and g2(a2) = g2(a5) = f2(a1) = f2(a4) = 0. Then E(f2, g2)holds, as we are under the second statement of the definition of the relation E (3.3.3). So, q2+q3= [g2+f3]Eand we obtain g2+f3:domg2−→ R (g2+f3)(a2) = 0 + 1 = 1 (g2+f3)(a3) = 1 + 0 = 1 (g2+f3)(a5) = 0 + 0 = 0 • We need the compatibility of q1+q2and q3+q4. Therefore, the previous representatives of these classes, f1+f2and g3+f4, respectively, don’t work for these cases. We want to find h1∈q1+q2 and h2∈q3+q4such that domh1=domh2and E(h1, f1+f2)and E(h2, g3+f4)hold. Let us consider domhi={a4, a7, a9}and hidefined as follows, for i∈ {1,2}: 30 h1:domh1→Rh2:domh2→R h1(a4) = 0 h2(a4) = 1 h1(a7) = 1 h2(a7) = 1 h1(a9) = 1 h2(a9) = 0 h1∈q1+q2because h1∈Fand E(h1, f1+f2)holds (it satisfies the second statement of the definition of the relation E (3.3.3)) and h2∈q3+q4because h2∈Fand E(h2, g3+f4) holds (for the same reason). So, (q1+q2)+(q3+q4) = [h1+h2]Eand we obtain: h1+h2:{a4, a7, a9} −→ R (h1+h2)(a4) = 0 + 1 = 1 (h1+h2)(a7) = 1 + 1 = 2 (h1+h2)(a9) = 1 + 0 = 1 • Now, we need the compatibility of q1+q4and q2+q3. Once again, the representatives of these classes, g1+g4and g2+f3, respectively, don’t work for these cases. So, we are going to find two functions h3∈q1+q4,h4∈q2+q3such that domh3=domh4,h3, h4∈Fand E(h3, g1+g4)and E(h4, g2+f3)hold. Let us consider domh3=domh4={a5, a8, a10} and hidefined as follows, for i∈ {3,4}: h3:domh3→Rh4:domh4→R h3(a5) = 1 h4(a5) = 0 h3(a8) = 1 h4(a8) = 1 h3(a10) = 0 h4(a10) = 1 h3∈q1+q4because h3∈Fand E(h3, g1+g4)holds (it satisfies the second statement of the definition of the relation E (3.3.3)) and h4∈q2+q3because h4∈Fand E(h4, g2+f3) holds (for the same reason). 31 a∧′a(a) =¬′(¬′a∨′¬′a) (b) =¬′(¬′a+′¬′a−′¬′a·′¬′a) (c) =¬′((1−′a) +′(1−′a)−′(1−′a)·′(1−′a)) (d) =¬′((1−′a) +′(1−′a)−′(1·′1−′1·′a−′a·1+′a·′a)) (e) =¬′((1−′a) +′(1−′a)−′(1−′a)) (f) =¬′(1−′a+′1−′a−′1+′a) (g) =1−′(1−′a) (h) =a (a) Definition of ∧′ (b) Definition of ∨′ (c) Definition of ¬′ (d) Distributivity of ·′with respect to +′ (e) 1is the identity for the operation ·′;1and aare idempotent elements; all the elements in B′have a symmetric one (f) Distributivity of scalar multiplication with respect to vector addition; associativity (g) All the elements in B′have a symmetric one; 0is the identity of the operation +′ (h) Distributivity of scalar multiplication with respect to vector addition; all the elements in B′have a symmetric one; associativity; 0is the identity of the operation +′ (ii) Commutativity for ∨′and ∧′, that is, a∨′b=b∨′aand a∧′b=b∧′a a∨′b(a) = (a+′b)−′a·b(b) = (b+′a)−′b·a(c) =b∨′a (a) Definition of ∨′ (b) Commutativity of the operations +′and ·′ (c) Definition of ∨′ It is analogous for ∧′. (iii) Associativity for ∨′and ∧′, that is, a∨′(b∨′c) = (a∨′b)∨′cand a∧′(b∧′c) = (a∧′b)∧′c 38 a∨′(b∨′c)(a) = (a+′(b∨′c)) −′(a·′(b∨′c)) (b) =a+′(b+′c−′(b·′c)) −′(a·′(b+′c−′(b·′c))) (c) =a+′(b+′c−′(b·′c)) −′((a·′b)+(a·′c)−′(a·′(b·′c))) (d) =a+′(b+′c−′(b·′c)) −′a·′b−a·′c+′(a·′(b·′c)) (e) =a+′b−′(a·′b) +′c−′(a+′b+′(a·′b)) ·′c (f) = (a∨′b) +′c−′(a∨′b)·′c (g) = (a∨′b)∨′c (a) Definition of ∨′ (b) Definition of ∨′ (c) Distributivity of ·′with respect to +′ (d) Distributivity of scalar multiplication with respect to vector addition (e) Commutativity; Associativity; Distributivity of scalar multiplication with respect to vector addition (f) Definition of ∨′ (g) Definition of ∨′ It is analogous for ∧′. (iv) Absorption, that is, a∧′(a∨′b) = a∨′(a∧′b) = a a∨′(a∧′b)(a) =a∨′(¬′(¬′a∨′¬′b)) (b) =a∨′(¬′(¬′a+¬′b−(¬′a·′¬′b))) (c) =a∨′(¬′((1−′a) +′(1−′b)−′((1−′a)·′(1−′b)))) (d) =a∨′(¬′((1−′a)+(1−′b)−′(1−′b−′a+′(a·′b)))) (e) =a∨′(¬′(1−′a+1−′b−′1+′b+′a−′(a·′b))) (f) =a∨′(¬′(1−′(a·′b))) (g) =a∨′(1−′1+′(a·′b)) (h) =a+′(a·′b)−′(a·′(a·′b)) (i) =a+′(a·′b)−′(a·′b) (j) =a (a) Definition of ∧′ (b) Definition of ∨′ 39 (c) Definition of ¬′ (d) Distributivity of ·′with respect to +′;1is the identity element for ·′ (e) Associativity; Distributivity of scalar multiplication with respect to vector addition (f) −′ais the symmetric of a;−′1is the symmetric of 1;0is the identity for +′ (g) Definition of ¬′; Distributivity of scalar multiplication with respect to +′ (h) −′1is the symmetric of 1;0is the identity for +′; Definition of ∨′ (i) Associativity; ais an idempotent element (j) −′(a·′b)is the symmetric of a·′b;0is the identity for +′ It is analogous to a∧′(a∨′b). So, since in (B′,∧′,∨′)we have the idempotency, commutativity, associativity and absorption laws, (B′,∧′,∨′)is a lattice. Now, we need to show that the lattice (B′,∧′,∨′)is distributive, that is, for all a, b, c ∈B′, a∧′(b∨′c) = (a∧′b)∨′(a∧′c). a∧′(b∨′c)(a) = (a) =¬′(¬′a∨′¬′(b∨′c)) (b) =¬′(¬′a∨′¬′(b+′c−′b·′c)) (c) =¬′(¬′a∨′(1−′b−′c+b·′c)) (d) =¬′(¬′a+′(1−′b′−′c+′b·′c)−′¬′a·′(1−′b−′c−′+′b·′c)) (e) =¬′(1−′a+′1−′b−′c+′b·′c−′(1−′a)·′(1−′b−′c+′b·′c)) (f) =¬(1−′a+′1−′b−′c+′b·′c−′(1−′b−′c+′b·′c−′a+′a·′b+′ a·′c−′a·′(b·′c))) (g) =1−′1+′a·′b+′a·′c−′a·′(b·′c) (h) =a·′b+′a·′c−′(a·′a)·′(b·′c) (i) =a·′b+′a·′c−′(a·′b)·′(a·′c) (j) = (a·′b)∨′(a·′c) (k) = (a∧′b)∨′(a∧′c) (a) Definition of ∧′ (b) Definition of ∨′ 40 (c) Definition of ¬′ (d) Definition of ∨′ (e) Definition of ¬′ (f) Distributivity of ·′with respect to +′;1is the identity for ·′ (g) Definition of ¬′;−′ais the symmetric of a;−′bis the symmetric of b;−′cis the symmetric of c;−′(b·′c)is the symmetric of b·′c;0is the identity for +′ (h) −′1is the symmetric element of 1;0is the identity for +′;ais an idempotent element; Associativity (i) Associativity; Commutativity (j) Definition of ∨′ (k) a∧′b=¬′(¬′a∨′¬′b) =¬′(¬′a+¬′b−′(¬′a)·′(¬′b)) =¬′(1−′a+′1−′b−′((1−′a)·′(1−′b))) =¬′(1−′a+′1−′b−′1+′b+′a−′a·′b) =1−′1+′a·′b =a·′b It is analogous to a∧′c=a·′c Finally, we need to demonstrate that a∧′0=0,a∨′1=1,a∧′¬′a=0and a∨′¬a=1. a∨′1(a) =a+′1−a·′1(b) =a+′1−′a(c) =1 (a) Definition of ∨′ (b) 1is the identity for the operation ·′ (c) −′ais the symmetric element of a;0is the identity for the operation + 41 a∧′0(a) =¬′(¬′a∨′¬′0) (b) =¬′(¬′a+′¬′0−′¬′a·′¬′0) (c) =¬′((1−′a) +′(1−′0)−′((1−′a)·′(1−′0))) (d) =¬′((1−′a) +′(1−′0)−′(1−′0−′a+′0)) (e) =¬′((1−′a) +′1−′(1−′a)) (f) =¬′(1−′a+′1−′1+′a) (g) =1−′1 (h) =0 (a) Definition of ∧′ (b) Definition of ∨′ (c) Definition of ¬′ (d) Distributivity of ·′with respect to +′;1is the identity for the operation ·′ (e) 0is the identity for the operation + (f) Associativity; Distributivity of scalar multiplication with respect to +′ (g) −′ais the symmetric of a;−′1is the symmetric of 1;0is the identity for the operation +; Definition of ¬′ (h) −′1is the symmetric of 1 a∨′¬′a(a) =a+′¬′a−′(a·′¬′a) (b) =a+′(1−′a)−′(a·′(1−′a)) (c) =1−′(a·′1−′a·′a) (d) =1−′(a−′a) (e) =1 (a) Definition of ∨′ (b) Definition of ¬′ (c) Associativity; Commutativity; 0is the identity for the operation + (d) 1is the identity for the operation ·′;ais an idempotent element (e) −′ais the symmetric of a;0is the identity for the operation + 42 a∧′¬′a(a) =¬′(¬′a∨′¬′(¬′a)) (b) =¬′(¬′a+′¬′(¬′a) +′(¬′a·′¬′(¬′a))) (c) =¬′((1−′a) +′(1−′(1−′a)) +′(1−′a)·′(1−′(1−′a))) (d) =¬′((1−′a) +′(1−′1+′a) +′((1−′a)·′(1−′1+′a))) (e) =¬′(1+′((1−′a)·′a′)) (f) =¬′(1+′a′−′a) (g) =1−′1 (h) =0 (a) Definition of ∧′ (b) Definition of ∨′ (c) Definition of ¬′ (d) Distributivity of scalar multiplication with respect to +′ (e) −′1is the symmetric of 1; Associativity; 0is the identity for the operation +′ (f) Distributivity of ·′with respect to +′;1is the identity for the operation ·′;ais an idempotent element (g) −′ais the symmetric of a;0is the identity for the operation +′ (h) −′1is the symmetric of 1 So, since (B′,∧′,∨′)is a distributive lattice and for all a∈B′,a∧′0=0,a∨′1=1,a∧′¬′a=0 and a∨′¬′a=1, we conclude that (B′,∨′,∧′,¬′,1,0)is a Boolean algebra. Therefore, we proved that B, induced by the partial algebra A, is a partial Boolean algebra. 43 4.3 Boolean polynomials in the context of a partial Boolean algebra Definition 4.3.1. Let n∈N . Let Qn , the set of Boolean polynomials, be defined as: (i) 1∈Qn (ii) 0∈Qn (iii) xi∈Qn , for all 1≤i≤n (iv) If φ∈Qn , then ¬φ∈Qn (v) If φ, ψ ∈Qn , then φ∨ψ∈Qn The set of all Boolean polynomials is S n∈N Qn . Observations: • From the previous definition is immediate that the formulas in nvariables are also Boolean polynomials, more precisely, Σn⊆Qn. • Both lower case letters of the Greek alphabet φ,ψ,χand α,β,γ(formulas of Σn) will be used to denote Boolean polynomials. In the context of a partial Boolean algebra on the set B, every polynomial φ∈Qndetermines a map φ∗:Domφ,n →B, with Domφ,n being a subset of Bn, according to the following definition. Definition 4.3.2. Let B= (B, ⊸ ,∨,¬,1,0) be a partial Boolean algebra and Qn be the set of Boolean polynomials previously defined. We define recursively on a polynomial φ∈Qn the set Domφ,n ⊆Bn and the map φ∗:Domφ,n → B , as follows: 1. If φ= 1 , then Domφ,n =Bn and φ∗(q) = 1 2. If φ= 0 , then Domφ,n =Bn and φ∗(q) = 0 3. If φ=xi , then Domφ,n =Bn and φ∗(q) = qi 4. If φ=¬ψ , then Domφ,n =Domψ,n and φ∗(q) = ¬ψ∗(q) 44 5. If φ=ψ∨χ , then Domφ,n ={q ∈Bn:q ∈Domψ,n ∩Domχ,n and ψ∗(q) ⊸ χ∗(q)} and φ∗(q) = ψ∗(q)∨χ∗(q) Domφ,n and φ∗(q) are, respectively, the domain and the map associated to the polynomial φ relative to B . Next, we show that the definition 4.3.2 is coherent with the definition 3.2.2. Theorem 4.3.3. Let A= (A, ⊸ ,+,·,◦,1) be a partial algebra, B= (B, ⊸ ,∨,¬,1,0) be the induced partial Boolean algebra and pn be the following function: pn:Qn→Pn pn(1) = 1 pn(0) = 0 ◦1, where 0 is the real number pn(xi) = xi pn(φ∨ψ) = (pn(φ) + pn(ψ)) −pn(φ)·pn(ψ) pn(¬φ) = 1 −pn(φ) Then, for all φ∈Qn : 1. Domφ,n =Dpn(φ),n Bn , where Dpn(φ),n Bn denotes the restriction of the domain Dpn(φ),n to Bn , Bn⊆An 2. For all q ∈Domφ,n, φ∗(q) = pn(φ)∗(q) Proof. Let P(φ) =      1. Domφ,n =Dpn(φ),n Bn 2. for all q ∈Domφ,n, φ∗(q) = pn(φ)∗(q) The proof follows by induction on φ. •φ= 1: 1. Domφ,n (i) =Bn(ii) =Dpn(φ),n Bn (i) Definition of Dom1,n in the partial Boolean algebra (ii) Dpn(φ),n Bn=D1,n|Bn=An|Bn=Bn 2. φ∗(q)(i) =1(ii) =pn(φ)∗(q) 45 (i) Definition of 1∗(q)in the partial Boolean algebra (ii) pn(φ)∗(q) = 1∗(q) = 1 Observation: 1 is in Bbecause, by definition, 1is an identity element of the product in A. In particular, 1=1·1, that is, 1is an idempotent element of A. •φ= 0: 1. Dpn(φ),n Bn (i) =D0◦1,n|Bn (ii) =Bn(iii) =Domφ,n (i) Definition of pn(0) (ii) D0◦1,n|Bn=D1,n|Bn=An|Bn=Bn (iii) Definition of Dom0,n in the partial Boolean algebra 2. pn(φ)∗(q)(i) = (0 ◦1)∗(q)(ii) = 0 ◦1(iii) =0(iv) =φ∗(q) (i) Definition of pn(0) (ii) (0 ◦1)∗(q) = 0 ◦1∗(q) = 0 ◦1 (iii) Definition of 0 (iv) Definition of 0∗(q)in the partial Boolean algebra Observations: • Since 0and 1are commeasurable, the algebra of the polynomials in 0and 1is a commutative algebra over the field of real numbers. •0is in Bbecause (0 ◦1)·(0 ◦1) = (0 ×0) ◦(1·1) = 0 ◦1. •φ=xi: 1. Domφ,n (i) =Bn(ii) =Dpn(φ),n Bn (i) Definition of Domxi,n in the partial Boolean algebra (ii) Dpn(φ),n Bn=Dxi,n|Bn=An|Bn=Bn(1 ≤i≤n) 2. φ∗(q)(i) =qi (ii) =pn(φ)∗(q) (i) Definition of xi∗(q)in the partial Boolean algebra (ii) pn(φ)∗(q) = x∗ i(q) = qi Observation: qi=qi·qibecause, by definition, q = (q1,· · · , qn)∈Bn. So, qi∈B and the elements in Bare the idempotent of A. 46 •φ=¬ψ: Suppose P(ψ). We want to show P(¬ψ). 1. Dpn(¬ψ),n Bn (i) =D1−pn(ψ),n Bn (ii) ={q ∈Bn:q ∈D1,n|Bn∩Dpn(ψ),n Bnand 1∗(q) ⊸ pn(ψ)∗(q)} (iii) ={q ∈Bn:q ∈Bn∩Dpn(ψ),n Bnand 1 ⊸ pn(ψ)∗(q)} (iv) ={q ∈Bn:q ∈Dpn(ψ),n Bn} (v) ={q ∈Bn:q ∈Domψ,n} (vi) =Domψ,n (i) Definition of pn(¬ψ) (ii) Definition of D1−pn(ψ),n in the partial algebra (iii) D1,n|Bn=Bn 1∗(q) = 1 (iv) Once Dpn(ψ),n Bn⊆Bn, then Dpn(ψ),n Bn∩Bn=Dpn(ψ),n Bn By definition, it is always true that 1 ⊸ pn(ψ)∗(q) (v) Induction hypothesis P(ψ) (vi) Definition of Domψ,n 2. (pn(¬ψ))∗(q)(i) = (1 −pn(ψ))∗(q) (ii) = 1∗(q)−pn(ψ)∗(q) (iii) =1−ψ∗(q) (iv) =¬ψ∗(q) (v) = (¬ψ)∗(q) (i) Definition of pn(¬ψ) (ii) Definition of (1 −pn(ψ))∗(q)in the partial algebra (iii) 1∗(q) = 1 Induction hypothesis P(ψ) (iv) Definition of the connective ¬ (v) Definition of (¬ψ)∗(q)in the partial Boolean algebra Observations: 47 αi,j has occurrences of both xiand xj(see the Observation below). We want to show that α∗(q) = 1. Given the construction of αi,j, it can only be in one of the following formats: xi∨xj,¬xi∨xj,xi∨¬xjor ¬xi∨¬xj. By definition of Dom_,n, we obtain that qi ⊸ qj, for all 1≤i < j ≤nand by proposition 4.1.4, the algebra of the Boolean polynomials in q1,· · · , qnis a Boolean algebra. Let B′be the Boolean algebra of the polynomials in q1,· · · , qnand α∗∗ the function associated to B′. Note that α∗(q) = α∗∗(q). Given that αis C-valid and B′is a Boolean algebra, α∗∗(q) = 1. Then, α∗(q) = 1. Observation: Such αi,j exists. We begin with αi,j as stated in the theorem. If this αi,j still does not satisfy the additional condition required, it is because we can choose a subpolynomial α′ i,j where both variables xiand xjoccur. Then, we select α′ i,j and repeat the process. Theorem 5.1.4. A formula in one or two variables is Q -valid if it is C -valid. Proof. We are going to consider two scenarios, the first one αbeing a formula in one variable and the second one in two variables. • Let us consider a partial Boolean algebra B= (B, ⊸ ,∨,¬,1,0)and a formula α∈Σ1such that αis C-valid. We want to show that α∗(q) = 1. By the proposition 4.1.4, the algebra of the Boolean polynomials in q1is a Boolean algebra. Let B′be the Boolean algebra of the polynomials in q1and α∗∗ the function associated to B′. Note that α∗(q) = α∗∗(q). Given that αis C-valid and B′is a Boolean algebra, α∗∗(q) = 1. Then, α∗(q) = 1. • Let us consider a partial Boolean algebra B= (B, ⊸ ,∨,¬,1,0)and a formula α∈Σ2such that αis C-valid. We want to show that α∗(q) = 1. Let us consider the property P(α)iff if q = (q1, q2)∈Domα,2, then q1 ⊸ q2. The proof of this property follows by induction on α. •P(xi), for i∈ {1,2}, iff q ∈Domxi,2implies q1 ⊸ q2. By definition, Domxi,2=B2. So, q1 ⊸ q2. •P(¬α)iff q ∈Dom¬α,2implies q1 ⊸ q2. Let us suppose P(α)and that q ∈Dom¬α,2. By definition, Dom¬α,2=Domα,2and, consequently, q ∈Domα,2. By induction hypothesis P(α),q1 ⊸ q2. •P(α∨β)iff q ∈Domα∨β,2implies q1 ⊸ q2. Let us suppose P(α),P(β)and that q ∈Domα∨β,2. By definition, Domα∨β,2= {q ∈B2:q ∈Domα,2∩Domβ,2and α∗(q) ⊸ β∗(q)}. Since q ∈Domα,2then, by induction hypothesis P(α),q1 ⊸ q2. 54 So, in all these cases, for all q in the domain of a formula α∈Σ2,q1 ⊸ q2. By proposition 4.1.4, the algebra of the Boolean polynomials in q1and q2is a Boolean algebra. Let B′be the Boolean algebra of the polynomials in q1and q2and α∗∗ the function associated to B′. Note that α∗(q) = α∗∗(q). Given that αis C-valid and B′is a Boolean algebra, α∗∗(q) = 1. Then, α∗(q) = 1. Now, we will give some examples of Q-valid formulas and not Q-valid formulas, which were taken from the article [9]. Example 1. The formula α= ((x1∨x2)∧x3)↔[(x1∧x3)∨(x2∧x3)] is a Q-valid formula. Proof. Since the subformulas in x1alone is x1, in x2alone is x2and in x3alone is x3, and for all 1≤i<j≤3there exists αi,j, where α1,2=x1∨x2,α1,3=x1∧x3and α2,3=x2∧x3, and given that αis C-valid (it is the distributive law), then by theorem 5.1.3, αis Q-valid. Example 2. The formula α= [(x1∨x2)∨x3]↔[x1∨(x2∨x3)] is Q-valid. Proof. Firstly, we can’t apply theorem 5.1.3 because this formula does not satisfy all the required hypothesis, specifically there does not exist α1,3, that is, a subformula of αinvolving only the variables x1and x3. However, this does not mean that it is not Q-valid. Let us consider a partial Boolean algebra B= (B, ⊸ ,∨,¬,1,0)and let q = (q1, q2, q3)∈Domα,3. By definition, Domα,3={q ∈B3:q ∈Dom(x1∨x2)∨x3,3∩Domx1∨(x2∨x3),3and ((x1∨x2)∨x3)∗(q) ⊸ (x1∨(x2∨x3))∗(q)} ={q ∈B3:q ∈Domx1,3∩Domx2,3∩Domx3,3and ((x1∨x2)∨x3)∗(q) ⊸ (x1∨(x2∨x3))∗(q)and (x1∨x2)∗(q) ⊸ x3 ∗(q)and x1 ∗(q) ⊸ (x2∨x3)∗(q)and x1 ∗(q) ⊸ x2 ∗(q)and x2 ∗(q) ⊸ x3 ∗(q)} ={q ∈B3: ((q1∨q2)∨q3) ⊸ (q1∨(q2∨q3)) and (q1∨q2) ⊸ q3and q1 ⊸ (q2∨q3) and q1 ⊸ q2and q2 ⊸ q3} We have that q1 ⊸ q2,q2 ⊸ q3and q1 ⊸ (q2∨q3). Consequently, due to the fact that q2 ⊸ q2and q2 ⊸ q3, we have q2 ⊸ (q2∨q3). Therefore, any two of q1,q2and q2∨q3are commeasurable, which implies that the algebra of the Boolean polynomials in q1,q2and q2∨q3is a Boolean algebra. 55 Additionally, we also know q1∨q2 ⊸ q3. Analogously to what we have previously done, since q2 ⊸ q2 and q2 ⊸ q1,q2 ⊸ (q1∨q2). Thus, any two of q1∨q2,q2and q3are commeasurable and, consequently, the algebra of the Boolean polynomials in q1∨q1,q2and q3is a Boolean algebra. Then, on one hand, (q1∨q2)∨(q2∨q3) = (i) =q1∨[q2∨(q2∨q3)] (ii) =q1∨[(q2∨q2)∨q3] (iii) =q1∨(q2∨q3) (i) Associativity (of the algebra of the Boolean polynomials in q1,q2and q2∨q3) (ii) Associativity (of the algebra of the Boolean polynomials in q1∨q2,q2and q3) (iii) Idempotency (of the algebra of the Boolean polynomials in q1∨q2,q2and q3) On the other hand, (q1∨q2)∨(q2∨q3) = (i) = [(q1∨q2)∨q2]∨q3 (ii) = [q1∨(q2∨q2)] ∨q3 (iii) = (q1∨q2)∨q3 (i) Associativity (of the algebra of the Boolean polynomials in q1∨q2,q2and q3) (ii) Associativity (of the algebra of the Boolean polynomials in q1,q2and q2∨q3) (iii) Idempotency (of the algebra of the Boolean polynomials in q1,q2and q2∨q3) Since q1∨(q2∨q3) = (q1∨q2)∨(q2∨q3) = (q1∨q2)∨q3, we conclude that q1∨(q2∨q3) = (q1∨q2)∨q3and, consequently, the formulas (x1∨x2)∨x3and x1∨(x2∨x3)have the same value, establishing that the formula αis Q-valid. Example 3. The formula [(x1↔x2)↔(x3↔x4)] ↔[(x1↔x4)↔(x2↔x3)] is C-valid but it is not Q-valid. The proof is by considering the same algebra and the same observables as in the example of the identity that does not hold in all partial algebras (3.4) for the corresponding formula but substituting ↔for +. 56 5.2 Axiomatic system Let Σ ⊸ be the set of formulas Σ∪ { ⊸ (α1,· · · , αm) : α1,· · · , αm∈Σ,for m∈N}.Σ ⊸ nwill be the subset of Σ ⊸ defined as Σn∪ { ⊸ (α1,· · · , αm) : α1,· · · , αm∈Σn,for m∈N}. Observation: We will assume that ∧,→and ↔are defined just with the connectives mentioned above, i.e., α1∧α2is an abbreviation of ¬(¬α1∨¬α2);α1→α2is an abbreviation of ¬α1∨α2and α1↔α2 is an abbreviation of ¬(¬(¬α1∨α2)∨ ¬(¬α2∨α1)). Definition 5.2.1. Let Φ be a subset of Σ ⊸ n . A sequence γ1,· · · , γk of formulas of Σ ⊸ n is Φ -admissible if the following condition is satisfied: For all i∈ {1,· · · , k} , γi is either of the type ⊸ (α1, α1) , where α1 is a subformula of a formula α∈Φ or of the type ⊸ (α1, α2) , where α1∨α2 is a subformula of a formula α∈Φ (we will call both of these subformulas “axioms extracted from α ”); or there exist indices i1,· · · , ip such that 1≤ik< i and γi follows from γi1,· · · , γip by one of the rules below (rules of inference): ⊸ (α1,· · · , αm) R1:where 1≤i, j ≤m ⊸ (αi, αj) ⊸ (α1, α1) ⊸ (α1, α2)· · · ⊸ (αi, αj)· · · ⊸ (αm, αm) R2: ⊸ (α1,· · · , αm) (There are m2premisses of the type ⊸ (αi, αj), where 1≤i, j ≤m) ⊸ (α1, α2)α2↔α3 R3: ⊸ (α1, α3) ⊸ (¬α1, α2) R4: ⊸ (α1, α2) ⊸ (α1, α2, α3) R5: ⊸ (α1∨α2, α3) ⊸ (α1,· · · , αn) S1:(where β(x1,· · · , xn)is a C-valid formula) β(α1,· · · , αn) α1α1→α2 S2:α2 57 5.2.1 Q-proof of a formula Definition 5.2.2. A sequence γ1,· · · , γk of formulas of Σ ⊸ n is a Q -proof of a formula α∈Σn if it is {α} -admissible and there exists i∈ {1,· · · , k} such that α=γi . Observations: As we said before, the connectives ∧,→and ↔are defined with the connectives ¬and ∨. It is important to note that if we have a formula αwith a subformula of the type α1∧α2,α1→α2 or α1↔α2, we can extract the axiom ⊸ (α1, α2), just like with the case of α1∨α2, as we show below: •α1∧α2=¬(¬α1∨ ¬α2). From here, we can extract a few axioms but the one needed is ⊸ (¬α1,¬α2). We want to show that we can obtain ⊸ (α1, α2)from ⊸ (¬α1,¬α2): Hypothesis ⊸ (¬α1,¬α2)(R1) ⊸ (¬α2,¬α1)(R4) ⊸ (α2,¬α1)(R1) ⊸ (¬α1, α2)(R4) ⊸ (α1, α2) •α1→α2=¬α1∨α2. From here, the most relevant axiom is ⊸ (¬α1, α2). Let us show that we can obtain ⊸ (α1, α2)from ⊸ (¬α1, α2): Hypothesis ⊸ (¬α1, α2)(R4) ⊸ (α1, α2) •α1↔α2=¬(¬(¬α1∨α2)∨ ¬(¬α2∨α1)). It is useful to see α1↔α2as (α1→ α2)∧(α2→α1), because α1→α2is a subformula of (α1→α2)∧(α2→α1)and we know that from α1→α2we can extract ⊸ (α1, α2). So, any kind of occurrences of formulas of this type, we will extract this axiom trivially. Let us consider some examples of Q-proofs to elucidate the definitions 5.2.1 and 5.2.2. It is important to mention that these Q-proofs will be presented in a tree format to enhance comprehension. Example 1. We want to construct a Q-proof of α= (x1∨ ¬x1)∨x2. From α, we extract the axioms: ⊸ (x1,¬x1), ⊸ (x1∨ ¬x1, x2)(as well as the reflexive ones, that is, ⊸ (x1, x1), ⊸ (¬x1,¬x1), ⊸ (x1∨ ¬x1, x1∨ ¬x1), ⊸ (x2, x2), ⊸ (α, α)). Then, 58 Axiom ⊸ (x1, x1)(R2) ⊸ (x1)(S1) x1∨ ¬x1 Axiom ⊸ (x1∨ ¬x1, x2)(S1) β(x1∨ ¬x1, x2)(S2) α is a Q-proof of α. Observations: β(x1, x2) = x1→(x1∨x2)is a classical tautology. So, β(x1∨ ¬x1, x2) = (x1∨ ¬x1)→((x1∨ ¬x1)∨x2) Example 2. We want to construct a Q-proof of α= (x1∨x2)∨ ¬x1. We extract the axioms ⊸ (x1, x2) and ⊸ (x1∨x2,¬x1)(as well as the reflexive ones) from α. Then, Axiom ⊸ (x1, x2)(S1) β(x1, x2) is a Q-proof of α. Observations: β(x1, x2) = (x1∨x2)∨ ¬x1=αis a classical tautology. Example 3. We want to construct a Q-proof of α= ((x2∨x2)∨x1)∨ ¬x2. The axioms extracted from αare: ⊸ (x2∨x2, x1), ⊸ ((x2∨x2)∨x1),¬x2)(as well as the reflexive ones). Then, Axiom ⊸ (x2∨x2, x1)(R1) ⊸ (x1, x2∨x2) Axiom ⊸ (x2, x2)(R2) ⊸ (x2)(S1) γ(x2)(R3) ⊸ (x1, x2)(S1) β(x1, x2) is a Q-proof of α. Observations: β(x1, x2) = αand γ(x2) = (x2∨x2)↔x2are C-valid formulas. Example 4. We want to construct a Q-proof of α= ((x1∨x2)∧x3)↔((x1∧x3)∨(x2∧x3)). The axioms extracted from αare: ⊸ (x1∨x2, x3), ⊸ (x1∧x3, x2∧x3), ⊸ (x1, x2), ⊸ (x1, x3), ⊸ (x2, x3), ⊸ ((x1∨x2)∧x3,(x1∧x3)∨(x2∧x3)) (as well as the reflexive ones). Then, 59 Axiom · · · Axiom ⊸ (x2, x3) Axiom ⊸ (x1, x3) Axiom ⊸ (x1, x2)(R2) ⊸ (x1, x2, x3)(S1) β(x1, x2, x3) is a Q-proof of α. Observations: In · · · are the formulas of the type ⊸ (xi, xi),1≤i≤3(reflexivity), which are axioms, and the formulas of the type ⊸ (xj, xi),1≤i < j ≤3, xi6=xj(symmetry), which can be obtained by the rule R1from ⊸ (xi, xj), that we already know to be axioms. β(x1, x2, x3) = αis a C-valid formula (it is the distributive law). Proposition 5.2.3. If α is a C -valid formula in n variables from which we can extract the axioms ⊸ (xi, xj) , for all 1≤i < j ≤n , then there exists a Q -proof of α . Proof. Let α=β(x1,· · · , xn)be a C-valid formula such that ⊸ (xi, xj)are axioms, for, at least, 1≤i < j ≤n. Then, Axiom ⊸ (x1, x1) Axiom · · · ⊸ (xi, xj)· · · Axiom · · · ⊸ (xi, xj)· · · (R1) ⊸ (xj, xi) Axiom ⊸ (xn−1, xn) Axiom ⊸ (xn, xn)(R2) ⊸ (x1,· · · , xn)(S1) β(x1,· · · , xn) is a Q-proof of α. 5.3 Soundness of the axiomatic system Lemma 5.3.1. Let α∈Σn and B= (B, ⊸ ,∨,¬,1,0) be a partial Boolean algebra. Let us also consider q ∈Domα,n . Then, for all i∈N , for all γ∈Σ ⊸ n , if γ is the i -th element of a Q-proof of α , then P′(γ) , where P′(γ) is defined as: If γ is a formula of Σn , then q is in the domain of the Boolean polynomial γ and γ∗(q) = 1 ; If γ is a formula of the type ⊸ (α1,· · · , αk) , then q is in the domain of the Boolean polynomials α1,· · · , αk and the elements αm∗(q) are all in relation ⊸ , for m∈ {1,· · · , k} . Proof. Let α∈Σnand B= (B, ⊸ ,∨,¬,1,0)be a partial Boolean algebra. Let P(i)be defined as: for all γ∈Σ ⊸ n, if γis the i-th element of a Q-proof of α, then P′(γ). We are going to prove P(i)by induction on i, for all i∈N. 60 •P(1) iff for all γ∈Σ ⊸ n, if γis the first element of a Q-proof of α, then P′(γ). • Case γ= ⊸ (α1, α1): Then, α1is a subformula of αand due to the recursive way the domain of the Boolean polynomials are defined, we have that q is in the domain of α1. Since ⊸ is reflexive, α1∗(q) ⊸ α1∗(q). • Case γ= ⊸ (α1, α2),α16=α2: Then, α1∨α2is a subformula of α. By definition of Domα1∨α2,n,q ∈Domα1,n∩Domα2,n and α1∗(q) ⊸ α2∗(q). • Let us assume P(j), for all j < k. We want to show P(k), i.e., for all γ∈Σ ⊸ n, if γis the k-th element of a Q-proof of α, then P′(γ). •R1: Case γ= ⊸ (αi, αj), where i, j ∈ {1,· · · , m}, is the k-th element of a Q-proof of α: Then, γ1= ⊸ (α1,· · · , αm)is the k−t-th element of the Q-proof of α, for some t∈N, and, by induction hypothesis, P′(γ1). Since γ1is a formula of the type ⊸ (α1,· · · , αm), we have that q is in the domain of the Boolean polynomials α1,· · · , αmand the elements αl∗(q)are all in relation ⊸ , for all l∈ {1,· · · , m}, that is, for all i, j ∈ {1,· · · , m}, αi∗(q) ⊸ αj∗(q). •R2: Case γ= (α1,· · · , αm)is the k-th element of a Q-proof of α: Then, γ1= ⊸ (α1, α1), γ2= ⊸ (α1, α2),· · · , γp= ⊸ (αi, αj),· · · , γm2= ⊸ (αm, αm),1< p < m2, are the k−t1, k−t2,· · · , k−tm2, for some t1, t2,· · · , tm2∈ N, elements of the Q-proof of α. By induction hypothesis applied to each γr, r ∈ {1,· · · , m2}, and due to the fact that γr∈Σ ⊸ n\Σn,q is in the domain of the Boolean polynomials α1,· · · , αmand α1∗(q) ⊸ α1∗(q),α1∗(q) ⊸ α2∗(q),· · · ,α1∗(q) ⊸ αm∗(q),· · · , αi∗(q) ⊸ αj∗(q),· · · ,αm∗(q) ⊸ αm∗(q), i.e., the elements αl∗(q)are all in relation ⊸ , for all l∈ {1,· · · , m}. •R3: Case γ= ⊸ (α1, α3)is the k-th element of a Q-proof of α: Then, γ1= ⊸ (α1, α2),γ2=α2↔α3are the k−t1-th, k−t2-th elements of the Q-proof of α, for some t1, t2∈N. By induction hypothesis applied to γ1and once γ1∈Σ ⊸ n\Σn, we have that q is in the domain of the Boolean polynomials α1, α2and α1∗(q) ⊸ α2∗(q). By induction hypothesis applied to γ2and once α2∈Σn,q is in the domain of the Boolean 61 polynomial θ=α2↔α3and θ∗(q) = 1.θ∗(q) = 1means, because of the observation below, that q ∈Domα2,n ∩Domα3,n,α2∗(q) ⊸ α3∗(q)and α2∗(q) = α3∗(q). Since α1∗(q) ⊸ α2∗(q)and α2∗(q) = α3∗(q), follows that α1∗(q) ⊸ α3∗(q). So, once q ∈Domα1,n ∩Domα3,n and α1∗(q) ⊸ α3∗(q), we conclude P′(γ). Observation: θ∗(q) = (α2↔α3)∗(q)is equivalent to (¬(¬(¬α2∨α3)∨ ¬(¬α3∨α2)))∗(q). Applying multiple times the definition of _∗in a partial Boolean algebra, we get that θ∗(q) = ¬(¬(¬α2∗(q)∨α3∗(q)) ∨ ¬(¬α3∗(q)∨α2∗(q))), i.e., θ∗(q) = α2∗(q)↔α3∗(q). •R4: Case γ= ⊸ (α1, α2)is the k-th element of a Q-proof of α: Then, γ1= ⊸ (¬α1, α2)is the k−t-th element of the Q-proof of α, for some t∈N, and, by induction hypothesis applied to γ1and due to the fact that γ1∈Σ ⊸ n\Σn,q is in the domain of the Boolean polynomials ¬α1and α2and (¬α1)∗(q) ⊸ α2∗(q). By definition, Dom¬α1,n =Domα1,n. So, q ∈Domα1,n. Since (¬α1)∗(q) = ¬α1∗(q)and (¬α1)∗(q)and α2∗(q)are commeasurable then, by theorem 4.2.2, ¬¬α1∗(q) ⊸ α2∗(q). By the observation below, ¬¬α1∗(q) = α1∗(q). So, α1∗(q) ⊸ α2∗(q) and we conclude P′(γ). Observation: Since ¬α1∗(q)and α2∗(q)are commeasurable, then the Boolean polynomials in ¬α1∗(q) and α2∗(q)form a Boolean algebra and, by lemma 2.3.2, we have the property ¬¬α1∗(q) = α1∗(q). •R5: Case γ= ⊸ (α1∨α2, α3)is the k-th element of a Q-proof of α: Then, γ1= ⊸ (α1, α2, α3)is the k−t-th element of the Q-proof of α, for some t∈N, and, by induction hypothesis applied to γ1and since γ∈Σ ⊸ n\Σn,q is in the domain of the Boolean polynomials α1,α2and α3and α1∗(q) ⊸ α2∗(q),α1∗(q) ⊸ α3∗(q)and α2∗(q) ⊸ α3∗(q)(as well as the symmetric elements and the reflexive ones). Since any two of the three previous elements are commeasurable then, by theorem 4.2.2, α1∗(q)∨α2∗(q) ⊸ α3∗(q), which is, by definition, (α1∨α2)∗(q) ⊸ α3∗(q). It remains to show that q is in the domain of the Boolean polynomial α1∨α2. By definition, q ∈Domα1∨α2,n if, in particular, q ∈Domα1,n ∩Domα2,n. So, P′(γ). 62 •S1: Case γ=β(α1,· · · , αn)(where β(x1,· · · , xn)is C-valid) is the k-th element of a Q-proof of α: Then, γ1= ⊸ (α1,· · · , αn)is the k−t-th element of the Q-proof of α, for some t∈N. By induction hypothesis applied to γ1and since α∈Σ ⊸ n\Σn,q is in the domain of the Boolean polynomials α1,· · · , αnand αi∗(q) ⊸ αj∗(q), for all i, j ∈ {1,· · · , n}. We want to prove that q ∈Domγ,n and that γ∗(q) = 1. By definition 4.3.2, since q ∈Domα1,n ∩· · ·∩Domαn,n and αi∗(q) ⊸ αj∗(q), for all i, j ∈ {1,· · · , n},q ∈Domγ,n =Bn. It remains to show that γ∗(q) = 1. Given that any pair among α1∗(q),· · · , αn∗(q)are commeasurable, the algebra of the Boolean polynomials in α1∗(q),· · · , αn∗(q)is a Boolean algebra. As β(x1,· · · , xn)is a C-valid formula then, by the principle of substitution for tautologies (2.3.8), β(α1,· · · , αn) = γis also a C-valid formula, that is, for all Boolean algebras B1and for all valuation v,γ(v) = 1. Once more, due to the commeasurability of all the elements of B, we have that B= (B, B2,∨,¬,1,0). Let us consider the Boolean algebra B1= (B, ∧,∨,¬,1,0)such that for all valuation vin B,v(xi) = αi∗(q), for all i∈ {1,· · · , n}. Then, by lemma 4.3.4, γ∗(q) = γ(v) = 1. •S2: Case γ=α2is the k-th element of a Q-proof of α: Then, γ1=α1and γ2=α1→α2are the k−t1-th, k−t2-th elements of the Q-proof of α, for some t1, t2∈N. By induction hypothesis applied to γ1,q is in the domain of the Boolean polynomial α1and α1∗(q) = 1. By induction hypothesis applied to γ2,q is in the domain of the Boolean polynomial θand θ∗(q) = 1, where θ=α1→α2. Once θis equivalent to ¬α1∨α2then, by definition, Dom¬α1∨α2,n = {q ∈Bn:q ∈Dom¬α1,n ∩Domα2,n and ¬α1∗(q) ⊸ α2∗(q)}={q ∈Bn:q ∈ Domα1,n ∩Domα2,n and α1∗(q) ⊸ α2∗(q)}. We have that α1∗(q) = 1. So, θ∗(q)=(α1→α2)∗(q) = 1implies, by the observation below, that α2∗(q) = 1. Since q ∈Domα2,n and α2∗(q) = 1, we conclude P′(γ). Observations: • Since α1∗(q)and α2∗(q)are commeasurable, then the Boolean polynomials in α1∗(q) and α2∗(q)form a Boolean algebra and since α1∗(q) = 1, we have by definition 4.3.2, by lemma 2.3.2 and by definition 2.3.1, the following equalities: 63 the fact that αk∈Ω, we have that ⊸ (αk, αk)are α-provable, for all k∈ {1,2,3}. So, to prove that ⊸ (α1∨α2, α3)is α-provable we just need to consider the following tree: α-provable ⊸ (αk, αk) α-provable ⊸ (α1, α2) α-provable ⊸ (α1, α3) α-provable ⊸ (α2, α3) α-provable ⊸ (αi, αj)(R1) ⊸ (αj, αi)(R2) ⊸ (α1, α2, α3)(R5) ⊸ (α1∨α2, α3) where 1≤i < j ≤3. Now, by definition, ¬[α1] = [¬α1]. We want to show that ⊸ (¬α1, α2)is α-provable. Acknowledging some of the facts mentioned above, we just need to consider the following tree: α-provable ⊸ (α1, α2)(R1) ⊸ (α2, α1) α-provable ⊸ (α1, α1)(R2) ⊸ (α1)(S1) α1↔ ¬¬α1(R3) ⊸ (α2,¬¬α1) α-provable ⊸ (α1, α1)(R2) ⊸ (α1)(S1) ¬¬α1↔α1(R3) ⊸ (α2,¬¬α1)(R1) ⊸ (¬¬α1, α2)(R4) ⊸ (¬α1, α2) 5. Let us consider that any two of [α1],[α2],[α3]∈Bare commeasurable. We want to prove that the algebra of the polynomials in [α1],[α2],[α3], that is, B= (B′,∨′,∧′,¬′,1,0), is a Boolean algebra, where: •B′⊆Bis inductively defined: 1. [α1],[α2],[α3]∈B′ 2. 0,1∈B′ 3. If [β],[σ]∈B′and [β] ⊸ [σ], then [β]∨[σ]∈B′and [β]∧′[σ]∈B′ 4. If [β]∈B′,[¬β]∈B′ • The operations ∨′,¬′and ∧′are defined as: ∨′:∨|B′×B′ ¬′:¬|B′ ∧′:B′×B′→B′such that for all [β],[σ]∈B′, with [β] ⊸ [σ],[β]∧′[σ] = [β∧σ] = [¬(¬β∨ ¬σ)] 70 Observations: We are going to assume that any two elements in B′are compatible, the three new operations are total functions and B′is closed under these operations. The proof is similar to the ones provided in lemma 4.1.2 and proposition 4.1.3. Since any two elements in B′are compatible, we will state some facts which are going to be useful throughout the following proofs: • For all [β]∈B′, ⊸ (β, β)is α-provable • For all [β],[σ]∈B′, ⊸ (β, σ)is α-provable (definition of compatibility) Let us consider the structure (B′,∧′,∨′). We want to show that it is a lattice, that is, for all [β],[σ],[θ]∈B′, we have: (a) Idempotency for ∨′and ∧′, that is, [β]∨′[β] = [β] = [β]∧′[β]. By definition, [β]∨′[β] = [β∨β]. We want show that (β∨β)↔αβ. We just need to consider the tree: α-provable ⊸ (β, β)(R2) ⊸ (β)(S1) (β∨β)↔β It is analogous to the operation ∧′. (b) Commutativity for ∨′and ∧′, that is, [β]∨′[σ] = [σ]∨′[β]and [β]∧′[σ] = [σ]∧′[β]. By definition, [β]∧′[σ] = [β∧σ]and [σ]∧′[β] = [σ∧β]. We want to show that β∧σ↔ασ∧β. We just need to consider the tree: α-provable ⊸ (β, σ)(S1) (β∧σ)↔(σ∧β) It is analogous to ∨′ (c) Associativity for ∨′and ∧′, that is, ([β]∨′[σ]) ∨′[θ] = [β]∨′([σ]∨′[θ]). By definition, ([β]∨′[σ]) ∨′[θ] = [(β∨σ)∨θ]and [β]∨′([σ]∨′[θ]) = [β∨(σ∨θ)]. We want to show that (β∨σ)∨θ↔αβ∨(σ∨θ). We just need o consider the tree: α-provable · · · α-provable ⊸ (β, σ) α-provable ⊸ (β, θ) α-provable ⊸ (σ, θ)(R2) ⊸ (β, σ, θ)(S1) (β∨σ)∨θ↔β∨(σ∨θ) In · · · are the formulas of Σ ⊸ nof the type ⊸ (β, β), ⊸ (θ, θ)and ⊸ (σ, σ)and the formulas of the type ⊸ (σ, β), ⊸ (θ, β)and ⊸ (θ, σ), that by R1rule, one obtains α-provable formulas. 71 It is analogous to ∧′. (d) Absorption, that is, [β]∧′([β∨′[σ]]) = [β]=[β]∨′([β∧′[σ]]). By definition, [β]∧′ ([β∨′[σ]]) = [β∧(β∨σ)]. We want to show that β∧(β∨σ)↔αβ. We just need to consider the tree: α-provable ⊸ (β, σ)(S1) β∧(β∨σ)↔β It is analogous to [β]∨′([β∧′[σ]]). So, we proved that (B′,∧′,∨′)is a lattice. Now, we need to show that the lattice (B′,∧′,∨′)is distributive, that is, for all [β],[σ],[θ]∈B′, [β]∧′([σ]∨′[θ]) = ([β]∧′[σ])∨′([β]∧′[θ]). By definition, [β]∧′([σ]∨′[θ]) = [β∧(σ∨θ)] and ([β]∧′[σ]) ∨′([β]∧′[θ]) = [(β∧σ)∨(β∧θ)]. We want to show that β∧(σ∨θ)↔α (β∧σ)∨(β∧θ). We just need to consider the tree: α-provable · · · α-provable ⊸ (β, σ) α-provable ⊸ (β, θ) α-provable ⊸ (σ, θ)(R2) ⊸ (β, σ, θ)(S1) β∧(σ∨θ)↔(β∧σ)∨(β∧θ) In · · · are the formulas of Σ ⊸ nof the type ⊸ (β, β), ⊸ (θ, θ)and ⊸ (σ, σ)and the formulas of the type ⊸ (σ, β), ⊸ (θ, β)and ⊸ (θ, σ), that by R1rule, one obtains α-provable formulas. So, (B′,∧′,∨′)is a distributive lattice. Finally, it remains to show that for all [β]∈B′,[β]∧′0=0,[β]∨′1=1,[β]∧′¬[β] = 0 and [β]∨′¬[β] = 1. Let us consider [β]∈1. Observations: For this part of the proof, it will be useful to see 1as [β∨ ¬β]and 0as [¬(β∨ ¬β)] = [β∧ ¬β](actually, we could consider any tautology in classical logic). Let us prove that 1= [β∨ ¬β]and 0= [β∧ ¬β]. We want to show that β∨ ¬βis α-provable. Then, we just need to consider the tree: α-provable ⊸ (β, β)(R2) ⊸ (β)(S1) β∨ ¬β 72 By definition, we have [β]∧′0= [β]∧′[β∧ ¬β]=[β∧(β∧ ¬β)]. We want to show that β∧(β∧ ¬β)↔αβ∧ ¬β. We just need to consider the tree: α-provable ⊸ (β, β)(R2) ⊸ (β)(S1) β∧(β∧ ¬β)↔β∧ ¬β By definition, we have [β]∨′1= [β]∨′[β∨ ¬β]=[β∨(β∨ ¬β)]. We want to show that β∨(β∨ ¬β)↔αβ∨ ¬β. We just need to consider the tree: α-provable ⊸ (β, β)(R2) ⊸ (β)(S1) β∨(β∨ ¬β)↔β∨ ¬β By definition, [β]∧′¬[β] = [β∧ ¬β]. We want to show that β∧ ¬β↔αβ∧ ¬β. We just need to consider the tree: α-provable ⊸ (β, β)(R2) ⊸ (β)(S1) β∧ ¬β↔β∧ ¬β By definition, [β]∨′¬[β] = [β∨ ¬β]. We want to show that β∨ ¬β↔αβ∨ ¬β. We just need to consider the tree: α-provable ⊸ (β, β)(R2) ⊸ (β)(S1) β∨ ¬β↔β∨ ¬β So, since (B′,∧′,∨′)is a distributive lattice and for all [β],[σ]∈B′,[β]∧′0=0,[β]∨′1=1, [β]∧′¬[β] = 0and [β]∨′¬[β] = 1, we conclude that (B′,∨′,∧′,¬′,1,0)is a Boolean algebra. Completeness Theorem. If a formula α∈Σn holds in all partial Boolean algebras, then there exists a Q -proof of α . Proof. Let us assume that there does not exist a Q-proof of the formula α∈Σn. We want to construct a partial Boolean algebra Bsuch that αdoes not hold in B. Let us consider the partial Boolean algebra B= (B, ⊸ ,∨,¬,1,0)previously defined in the definition 5.4.7. Let qibe the class of the formula xi∈Ωand let β∈Ω. So, [xi] = xi∗(q) = qi. Similarly, the class of βis the element β∗(q), that is, 73 [β] = β∗(q), which is easily proven by induction on β; we have chosen to omit it. By definition, βholds in the partial Boolean algebra Biff for all q ∈Domβ,n,β∗(q) = 1(definition 4.3.5). Consequently, β∗(q) = 1iff [β] = 1iff βis α-provable (the first equivalence is by the previous observation that β∗(q) = [β], and the second one is by definition of 1). So, βis α-provable iff βholds in B. In particular, αis α-provable3iff αholds in B. Since αis not α-provable, αdoes not hold in B. 3αis α-provable if there exists a Q-proof of α. 74 Chapter 6 Conclusion Having all the basic concepts clarified, our study began with an exploration of partial algebras, the foundational structures from which the compatibility relation originated. We studied polynomials within this context, their domains and their respective function, crucial for assigning values to these polynomials in the partial algebra. Subsequently, we extended our study to partial Boolean algebras, delving into Boolean polynomials, their domains and their respective function, in order to assign values to these Boolean polynomials in the partial Boolean algebra. We concluded that the set of formulas in nvariables constitutes a subset of the Boolean polynomials in nvariables, implying that the value of a propositional calculus formula aligns with the value of a Boolean polynomial, when it makes sense to do such a comparison, that is, when we have all the compatibilities inherent to the formula within the domain of the Boolean polynomial. The dissertation’s title, “Partial classical propositional logic”, was elucidated through the study of Qvalid formulas, accompanied by illustrative examples and counterexamples. The creation of a counterexample, which is not straightforward, involved utilizing partial algebras. So, although we initially defined partial Boolean algebras independently of partial algebras, studying them became necessary. The process of proving theorems within this newly formal system proved to be complex and, occasionally, counterintuitive. Certain seemingly straightforward logical deductions required significant effort. For instance, the direct demonstration (without resorting to the theorems of soundness and completeness) that any C-valid formula in one or two variables is Q-provable was omitted, because we could not prove it in full generality. The dissertation’s beginning involved the study of orthologic and ortholattices, although these studies did not make it into the dissertation. This exploration was essential in understanding the varying semantics of different quantum logics. Initially, our plan was to study two articles, one of which was [9] and the other [8]. However, we focused on the [9] because on the other one the formal system seemed to be less intuitive, due to the lack of resemblance to the formal system of classical logic, and more complex. Additionally, this paper did not explore the use of partial algebras. An area I had hoped to explore was 75 transitive Boolean algebras. Unfortunately, due to the complexity of the quantum logic currently being studied, I did not have the opportunity of such exploration. Diving into additional literature might have offered a deeper understanding of the different possibilities of interpretation of this logic, as seen in [8]. Looking ahead, delving deeper into this quantum logic and its related counterparts, such as transitive partial Boolean algebras, along with their connection to partially ordered orthomodular sets, would be a logical continuation. Understanding the alignment of these new concepts with the logic explored here and determining whether orthological and orthomodular quantum logics offer advantages over partial classical propositional logic would mark a promising starting point for future research. Additionally, fully understanding the recent article [1] would be interesting and it could be the next step to delve deeper into the world of quantum computing. 76 Bibliography [1] S. Abramsky and R. S. Barbosa. The logic of contextuality. In C.Baier and J.Goubault-Larrecq, editors, 29th EACSL Annual Conference on Computer Science Logic, CSL 2021, LIPIcs, 5:1-5:18, 2021. [2] Peter Burmeister. Partial Algebras — An Introductory Survey , pages 1–70. Springer Netherlands, Dordrecht, 1993. [3] Dalla Chiara. Quantum logic. In D. Gabbay and F. Guenthner, editors, Handbook of Philosophical Logic: Volume III: Alternatives in Classical Logic , pages 427–469. Springer Netherlands, Dordrecht, 1986. [4] Dalla Chiara, Roberto Giuntini, and Richard Greechie. Reasoning in Quantum Theory: Sharp and Unsharp Quantum Logics, in Series Trends in Logic . Springer, 2004. [5] Dalla Chiara, Roberto Giuntini, and Miklós Rédei. The history of quantum logic. Handbook of History of Logic , 38, 12 2007. [6] B. A. Davey and H. A. Priestley. Introduction to Lattices and Order . Cambridge University Press, 2 edition, 2002. [7] E. Gibney. Google publishes landmark quantum supremacy claim. Nature , 574:461–462, 2019. [8] S. Kochen and E. P. Specker. The calculus of partial propositional functions. In Y. Bar-Hillel, editor, Proceedings of the 1964 International Congress for Logic, Methodology and Philosophy of Science , pages 45–57, North-Holland, Amsterdam, 1965. [9] S. Kochen and E. P. Specker. Logical structures arising in quantum theory. In J. Addison, L. Henkin, and A. Tarski, editors, The Theory of Models , pages 177–189, North-Holland, Amsterdam, 1965. [10] Miklós Rédei. The birth of quantum logic. History and Philosophy of Logic , 28(2):107–122, 2007. [11] Richard D. Schafer. An Introduction to Nonassociative Algebras . Academic Press edition, 1966. 77 [12] Morten Heine Sørensen and Pawel Urzyczyn. Lectures on the Curry-Howard isomorphism . Elsevier, Amsterdam; Oxford, 2006. [13] Dirk van Dalen. Logic and Structure . Springer London, 5 edition, 2013. 78