Matching logic - a new axiomatization

Laurenţiu Leuştean, Dafina Trufaş, [2mm] Institute for Logic, Data Science, Bucharest · 2025

Read Matching logic - a new axiomatization by Laurenţiu Leuştean, Dafina Trufaş, [2mm] Institute for Logic, Data Science, Bucharest (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-13801.txt.

Introduction

Laurenţiu Leuştean and Dafina Trufaş proposed a simpler proof system for matching logic, in 2025 lecture notes. Matching logic is a framework for defining programming language meaning and for reasoning about programs. Its proof rules, like those of older logics, can be trimmed without losing power.

The new system follows Tarski's spare axiomatization of first-order logic with equality, in a form later simplified by others. It avoids the notions of free variable and free substitution, which often clutter proofs. The notes also give a second system for the version of matching logic with application. That system adapts Gödel's rules for intuitionistic logic to the matching setting. The authors present the pair as cleaner foundations for work in the logic.

Catalog record

CREATORLaurenţiu Leuştean, Dafina Trufaş, [2mm] Institute for Logic, Data Science, Bucharest
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE227 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-13801

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Matching logic - a new axiomatization Laurenţiu Leuştean, Dafina Trufaş, [2mm] Institute for Logic, Data Science, Bucharest Abstract Chapter 1 Introduction Matching logic was introduced by Grigore Roşu [ 15 , 14 ] . Different versions of matching logic were recently studied (see, for example, [ 4 , 5 , 6 , 3 ] ). In Chapter 2 we propose a new proof system for appML , first-order matching logic with application. This proof system, denoted \mathcal{G}^{c} , is obtained by adapting to matching logic Gödel’s proof sytem for first-order intuitionistic logic (see [ 7 , 18 ] ). We prove different useful theorems and derived rules, important properties of the proof system. For different proofs in the propositional fragment of \mathcal{G}^{c} , Kleene’s textbook [ 9 ] was a source of inspiration. Finally, we prove that \mathcal{G}^{c} is equivalent with the proof system \mathcal{H} for appML, obtained from the proof system defined in [ 1 ] by considering only the axioms and deduction rules from the categories FOL reasoning and Frame reasoning. In Chapter 3 we give a new, simpler proof system \mathcal{T}_{def} for first-order matching logic with application and definedness ( appML_{def} ​). The proof system \mathcal{T}_{def} is inspired by Tarski’s [ 17 , 16 ] axiomatization for first order-logic with equality (simplified by Kalish and Montague [ 8 , 13 ] ), that does not involve the notions of a free variable and free substitution. We prove different useful theorems and derived rules for the propositional and first-order connectives, as well as for definedness, equality, totality, membership and application (contexts). Some of the results are obtained by adapting to our setting proofs from [ 12 , Chapter 10] . The propositional axioms and deduction rules of \mathcal{T}_{def} coincide with the ones of the proof system \mathcal{G}^{c} , hence we can use in this setting propositional theorems and derived deduction rules from Chapter 2 . We point out the following important results: (i) replacement theorems (Subsection 3.1.6 ); (ii) substitution of equal variables (Subsection 3.2.1 ); (iii) the bounded substitution theorem (Subsection 3.2.2 ); (iv) universal and existential specification (Subsection 3.2.3 ); (v) substitution of equal patterns (Subsection 3.2.7 ); (vi) the deduction theorem (Subsection 3.2.8 ); (vii) the propagation and framing rules from the proof system for applicative matching logic used in [ 4 , 3 , 2 ] (Subsection 3.2.9 ); (viii) theorems and rules for definedness, totality, equality (Subsections 3.1.3 , 3.2.5 ) and membership (Subsection 3.2.10 ). Theorem 3.3.1 , the main result of Section 3.3 , shows that \mathcal{G}^{c} is weaker than \mathcal{T}_{def} . As \mathcal{G}^{c} is equivalent with \mathcal{H} , we get that \mathcal{H} is also weaker than \mathcal{T}_{def} . By using notions and results from [ 11 ] , we prove in Section 3.4 a soundness theorem for \mathcal{T}_{def} . Throughout these notes, we use the terminology for abstract matching logic from [ 10 ] . Thus, we refer to [ 10 ] for definitions and properties of free and bound variables, free substitution Subf and bounded substitution Subb , variable free for patterns, congruences, contexts, proof systems, as well as for all the undefined notions from these notes. Chapter 2 Applicative matching logic with application appML The logic appML is defined as follows: (i) \mathcal{L}_{appML} : \mathcal{P}_{C}=\{\bot\} , \mathcal{P}_{1}=\{\neg\} , \mathcal{P}_{2}=\{\to,\wedge,\vee,\cdot\} , \mathcal{Q}=\{\forall,\exists\} , Equal={\overline{\mathcal{Q}}}=SVar=\emptyset . (ii) Its proof system, \mathcal{G}^{c} , is given in Appendix A . We write simply \vdash instead of \vdash_{\mathcal{G}^{c}} . We shall use the infix notation for patterns. Thus, we write \varphi\to\psi instead of \to\varphi\psi , \varphi\wedge\psi instead of \wedge\varphi\psi , \varphi\vee\psi instead of \vee\varphi\psi , {\varphi}\cdot{\psi} instead of \cdot\varphi\psi . We also use parentheses when it is necessary to make clear the structure of a pattern. For example, we write (\varphi\to\psi)\to\chi . We introduce the derived connective \leftrightarrow by the following abbreviation \varphi\leftrightarrow\psi:=(\varphi\to\psi)\wedge(\psi\to\varphi). To reduce the use of parentheses, we assume that (i) quantifiers \exists , \forall , application, \neg have higher precedence than \rightarrow , \wedge , \vee , \leftrightarrow ; (ii) \wedge,\vee have higher precedence than \rightarrow , \leftrightarrow . 2.1 Theorems and derived rules in \mathcal{G}^{c} In the following, \Gamma is an arbitrary set of patterns and \varphi , \psi , \chi , \varphi^{\prime} , \psi^{\prime} are arbitrary patterns. 2.1.1 Propositional connectives Lemma 2.1.1 . \displaystyle\vdash \displaystyle\,\psi\to\varphi\vee\psi, (2.1) \displaystyle\vdash \displaystyle\,\varphi\wedge\psi\to\psi, (2.2) \displaystyle\vdash \displaystyle\,\varphi\to(\psi\to\varphi), (2.3) \displaystyle\vdash \displaystyle\,\varphi\to\varphi, (2.4) \displaystyle\vdash \displaystyle\,\varphi\to(\psi\to\varphi\wedge\psi), (2.5) \displaystyle\vdash \displaystyle\,(\varphi\to\psi)\wedge\varphi\to\psi, (2.6) \displaystyle\vdash \displaystyle\,\varphi\wedge(\varphi\to\psi)\to\psi, (2.7) \displaystyle\vdash \displaystyle\,\varphi\to((\varphi\to\psi)\to\psi), (2.8) \displaystyle\vdash \displaystyle\,(\varphi\wedge\psi)\wedge\chi\to\varphi, (2.9) \displaystyle\vdash \displaystyle\,\varphi\wedge(\psi\wedge\chi)\to\psi, (2.10) \displaystyle\vdash \displaystyle\,(\varphi\wedge\psi)\wedge\chi\to\psi, (2.11) \displaystyle\vdash \displaystyle\varphi\wedge(\psi\wedge\chi)\to\chi, (2.12) \displaystyle\vdash \displaystyle\psi\to\varphi\vee(\psi\vee\chi), (2.13) \displaystyle\vdash \displaystyle\chi\to\varphi\vee(\psi\vee\chi), (2.14) \displaystyle\vdash \displaystyle\varphi\to(\varphi\vee\psi)\vee\chi, (2.15) \displaystyle\vdash \displaystyle\psi\to(\varphi\vee\psi)\vee\chi. (2.16) Proof. ( 2.1 ): (1) \vdash\psi\to\psi\vee\varphi (weakening) (2) \vdash\psi\vee\varphi\to\varphi\vee\psi (permutation) (3) \vdash\psi\to\varphi\vee\psi (syllogism) : (1), (2) ( 2.2 ): (1) \vdash\varphi\wedge\psi\to\psi\wedge\varphi (permutation) (2) \vdash\psi\wedge\varphi\to\psi (weakening) (3) \vdash\varphi\wedge\psi\to\psi (syllogism) : (1), (2) ( 2.3 ): (1) \vdash\varphi\wedge\psi\to\varphi (weakening) (2) \vdash\varphi\to(\psi\to\varphi) (exportation) : (1) ( 2.4 ): (1) \vdash\varphi\to\varphi\wedge\varphi (contraction) (2) \vdash\varphi\wedge\varphi\to\varphi (weakening) (3) \vdash\varphi\to\varphi (syllogism) : (1), (2) ( 2.5 ): (1) \vdash\varphi\wedge\psi\to\varphi\wedge\psi ( 2.4 ) (2) \vdash\varphi\to(\psi\to\varphi\wedge\psi) (exportation) : (1) ( 2.6 ): (1) \vdash(\varphi\to\psi)\to(\varphi\to\psi) ( 2.4 ) (2) \vdash(\varphi\to\psi)\wedge\varphi\to\psi (importation) : (1) ( 2.7 ): (1) \vdash(\varphi\to\psi)\wedge\varphi\to\psi ( 2.6 ) (2) \vdash\varphi\wedge(\varphi\to\psi)\to(\varphi\to\psi)\wedge\varphi (permutation) (3) \vdash\varphi\wedge(\varphi\to\psi)\to\psi (syllogism) : (2), (1) ( 2.8 ): (1) \vdash\varphi\wedge(\varphi\to\psi)\to\psi ( 2.7 ) (2) \vdash\varphi\to((\varphi\to\psi)\to\psi) (exportation) : (1) ( 2.9 ): (1) \vdash(\varphi\wedge\psi)\wedge\chi\to\varphi\wedge\psi (weakening) (2) \vdash\varphi\wedge\psi\to\varphi (weakening) (3) \vdash(\varphi\wedge\psi)\wedge\chi\to\varphi (syllogism) : (1), (2) ( 2.10 ): (1) \vdash\varphi\wedge(\psi\wedge\chi)\to\psi\wedge\chi ( 2.2 ) (2) \vdash\psi\wedge\chi\to\psi (weakening) (3) \vdash\varphi\wedge(\psi\wedge\chi)\to\psi (syllogism) : (1), (2) ( 2.11 ): (1) \vdash(\varphi\wedge\psi)\wedge\chi\to\varphi\wedge\psi (weakening) (2) \vdash\varphi\wedge\psi\to\psi ( 2.2 ) (3) \vdash(\varphi\wedge\psi)\wedge\chi\to\psi (syllogism) : (1), (2) ( 2.12 ): (1) \vdash\varphi\wedge(\psi\wedge\chi)\to\psi\wedge\chi ( 2.2 ) (2) \vdash\psi\wedge\chi\to\chi ( 2.2 ) (3) \vdash\varphi\wedge(\psi\wedge\chi)\to\chi (SYLLOGISM): (1), (2) ( 2.13 ): (1) \vdash\psi\to\psi\vee\chi (weakening) (2) \vdash\psi\vee\chi\to\varphi\vee(\psi\vee\chi) ( 2.1 ) (3) \vdash\psi\to\varphi\vee(\psi\vee\chi) (syllogism) : (1), (2) ( 2.14 ): (1) \vdash\chi\to\psi\vee\chi ( 2.1 ) (2) \vdash\psi\vee\chi\to\varphi\vee(\psi\vee\chi) ( 2.1 ) (3) \vdash\chi\to\varphi\vee(\psi\vee\chi) (syllogism) : (1), (2) ( 2.15 ): (1) \vdash\varphi\to\varphi\vee\psi (weakening) (2) \vdash\varphi\vee\psi\to(\varphi\vee\psi)\vee\chi (weakening) (3) \vdash\varphi\to(\varphi\vee\psi)\vee\chi (syllogism) : (1), (2) ( 2.16 ): (1) \vdash\psi\to\varphi\vee\psi ( 2.1 ) (2) \vdash\varphi\vee\psi\to(\varphi\vee\psi)\vee\chi (weakening) (3) \vdash\psi\to(\varphi\vee\psi)\vee\chi (syllogism) : (1), (2) ∎ Lemma 2.1.2 . \displaystyle\Gamma\vdash\varphi implies \displaystyle\Gamma\vdash\psi\to\varphi, (2.17) \displaystyle\Gamma\vdash\varphi\,\,\text{and}\,\,\Gamma\vdash\psi iff \displaystyle\Gamma\vdash\varphi\wedge\psi, (2.18) \displaystyle\Gamma\vdash\varphi\to\psi implies \displaystyle\Gamma\vdash\varphi\vee\chi\to\psi\vee\chi, (2.19) \displaystyle\Gamma\vdash\varphi\to\psi implies \displaystyle\Gamma\vdash\varphi\vee\psi\to\psi\text{~and~}\Gamma\vdash\psi\vee\varphi\to\psi, (2.20) \displaystyle\Gamma\vdash\varphi\to\psi imply \displaystyle\Gamma\vdash\varphi\wedge\chi\to\psi\text{~and~}\Gamma\vdash\chi\wedge\varphi\to\psi, (2.21) \displaystyle\Gamma\vdash\varphi\to\psi\,\,\text{and}\,\,\Gamma\vdash\varphi\to\chi iff \displaystyle\Gamma\vdash\varphi\to\psi\wedge\chi, (2.22) \displaystyle\Gamma\vdash\varphi\to\chi\,\,\text{and}\,\,\Gamma\vdash\psi\to\chi imply \displaystyle\Gamma\vdash\varphi\vee\psi\to\chi, (2.23) \displaystyle\Gamma\vdash\varphi\to\psi implies \displaystyle\Gamma\vdash(\chi\to\varphi)\to(\chi\to\psi), (2.24) \displaystyle\Gamma\vdash\varphi\to\psi\,\,\text{and}\,\,\Gamma\vdash\chi\to\gamma imply \displaystyle\Gamma\vdash\varphi\wedge\chi\to\psi\wedge\gamma, (2.25) \displaystyle\Gamma\vdash\varphi\to\psi\,\,\text{and}\,\,\Gamma\vdash\chi\to\gamma imply \displaystyle\Gamma\vdash\varphi\vee\chi\to\psi\vee\gamma, (2.26) \displaystyle\Gamma\vdash\varphi\wedge\psi\to\chi imply \displaystyle\Gamma\vdash\psi\wedge\varphi\to\chi, (2.27) \displaystyle\Gamma\vdash\varphi\to(\psi\to\chi) imply \displaystyle\Gamma\vdash\psi\wedge\varphi\to\chi, (2.28) \displaystyle\Gamma\vdash\varphi\to(\psi\to\chi) imply \displaystyle\Gamma\vdash\psi\to(\varphi\to\chi), (2.29) \displaystyle\Gamma\vdash\varphi\to\psi implies \displaystyle\Gamma\vdash\varphi\wedge\chi\to\psi\wedge\chi (2.30) \displaystyle\text{~and~}\Gamma\vdash\chi\wedge\varphi\to\chi\wedge\psi, (2.31) \displaystyle\Gamma\vdash\varphi\to\psi implies \displaystyle\Gamma\vdash(\psi\to\chi)\to(\varphi\to\chi), (2.32) \displaystyle\Gamma\vdash\varphi\to\psi implies \displaystyle\Gamma\vdash\varphi\to\varphi\wedge\psi\text{~and~}\Gamma\vdash\varphi\to\psi\wedge\varphi, (2.33) \displaystyle\Gamma\vdash\varphi\to\psi\,\,\text{and}\,\,\Gamma\vdash\varphi\to(\psi\to\chi) imply \displaystyle\Gamma\vdash\varphi\to\chi, (2.34) \displaystyle\Gamma\vdash\varphi\to(\psi\to\chi)\,\,\text{and}\,\,\Gamma\vdash\chi\to\gamma implies \displaystyle\Gamma\vdash\varphi\to(\psi\to\gamma). (2.35) Proof. ( 2.17 ): Immediate from ( 2.3 ) by (modus ponens) . ( 2.18 ): (\Rightarrow) : (1) \Gamma\vdash\varphi (Assumption) (2) \Gamma\vdash\psi (Assumption) (3) \Gamma\vdash\varphi\wedge\psi\to\varphi\wedge\psi ( 2.4 ) (4) \Gamma\vdash\varphi\to(\psi\to\varphi\wedge\psi) (exportation) : (3) (5) \Gamma\vdash\psi\to\varphi\wedge\psi (modus ponens) : (1), (4) (6) \Gamma\vdash\varphi\wedge\psi (modus ponens) : (2), (5) (\Leftarrow) : (1) \Gamma\vdash\varphi\wedge\psi (Assumption) (2) \Gamma\vdash\varphi\wedge\psi\to\varphi (weakening) (3) \Gamma\vdash\varphi (modus ponens) : (1), (2) (4) \Gamma\vdash\varphi\wedge\psi (Assumption) (5) \Gamma\vdash\varphi\wedge\psi\to\psi ( 2.2 ) (6) \Gamma\vdash\psi (modus ponens) : (4), (5) ( 2.19 ): (1) \Gamma\vdash\varphi\to\psi (Assumption) (2) \Gamma\vdash\chi\vee\varphi\to\chi\vee\psi (expansion) : (1) (3) \Gamma\vdash\varphi\vee\chi\to\chi\vee\varphi (permutation) (4) \Gamma\vdash\varphi\vee\chi\to\chi\vee\psi (syllogism) : (3), (2) (5) \Gamma\vdash\chi\vee\psi\to\psi\vee\chi (permutation) (6) \Gamma\vdash\varphi\vee\chi\to\psi\vee\chi (syllogism) : (4), (5) ( 2.20 ): (1)

Read the complete text