Proof-Theoretic Functional Completeness for the Connexive Logic C

Sara Ayhan & Hrafn Oddsson · 2025

Read Proof-Theoretic Functional Completeness for the Connexive Logic C by Sara Ayhan & Hrafn Oddsson (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-2507-06854.txt.

Introduction

Sara Ayhan and Hrafn Oddsson proved a functional completeness result in 2025 for the connexive logic called C, using only proof-theoretic tools. Connexive logics tie a conditional to its negation in ways classical logic rejects, and this one is inconsistent about negation without collapsing into triviality. Functional completeness asks whether its connectives can express every function of the right kind.

Because the logic has a strong negation that directly refutes, the proof must run two-sided: rule schemes for proofs and for refutations alike. Because the logic is connexive, refutation itself must be read in a connexive way, unlike the usual setup. The head gives the second author's fuller name. Readers get a completeness theorem earned inside the logic's own proof system, not borrowed from model theory.

Catalog record

CREATORSara Ayhan & Hrafn Oddsson
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE29 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-06854

Browse the full library · About the Tower of Babel

Full text

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

Proof-Theoretic Functional Completeness for the Connexive Logic C Sara Ayhan & Hrafn Oddsson Abstract We show the functional completeness for the connectives of the non-trivial negation inconsistent logic C by using a well-established method implementing purely proof-theoretic notions only. Firstly, given that C contains a strong negation, expressing a notion of direct refutation, the proof needs to be applied in a bilateralist way in that not only higher-order rule schemata for proofs but also for refutations need to be considered. Secondly, given that C is a connexive logic we need to take a connexive understanding of inference as a basis, leading to a different conception of (higher-order) refutation than is usually employed. Keywords : Functional completeness, Bilateralism, Connexive logic, Proof-theoretic semantics, Refutations, Higher-order derivability 1 Introduction From the viewpoint of what would nowadays be called ‘(bilateralist) proof-theoretic semantics’ Franz von Kutschera provided two very relevant and closely related papers [ 16 , 17 ] , in which he proves functional completeness of, respectively, intuitionistic logic and what he calls ‘direct logic’, nowadays better known as Nelson’s constructive logic with strong negation, N4 . Proof-theoretic semantics is the view that it is the rules of logical connectives governing their use in a proof system that determine their meaning. 1 1 1 Not unwarrantedly, von Kutschera called this ‘Gentzen semantics’, since this view’s origins are usually attributed to Gentzen’s famous paper [ 6 ] . For more details on proof-theoretic semantics, see [ 15 ] and [ 5 ] . Von Kutschera commits to this view in these papers in that he assumes rule schemata to define connectives and in conducting the proofs for functional completeness purely proof-theoretically, i.e., without reference to model-theoretic notions. The procedure is in both papers essentially the same. In a nutshell, he considers generalized derivability schemata for unspecified logical operators and shows that the connectives of intuitionistic propositional logic and N4 , respectively, are functionally complete when defined according to these rule schemata. The aim of the present paper is to transfer this approach to show the functional completeness for the connectives of the connexive logic C . As such, our paper is in a tradition of several others using von Kutschera’s approach in one way or another; to name just a few: Schroeder-Heister, combining von Kutschera’s higher level derivability with Prawitz’s natural deduction framework, shows completeness for intuitionistic propositional logic in such a system in [ 14 ] and for an extension to intuitionistic quantifier logic in [ 13 ] . Wansing uses von Kutschera’s approach to show the functional completeness of operators for substructural subsystems of intuitionistic propositional logic [ 19 ] and of N4 [ 20 , Ch. 7] and also for several normal modal and tense logics with respect to a representation of the generalized rules in display sequent calculi [ 21 ] . Braüner [ 3 ] does the same for hybridized versions of certain modal logics. It is especially von Kutschera’s later paper [ 17 ] that is interesting to consider from a bilateralist proof-theoretic semantics point of view and also for the present purpose. 2 2 2 See [ 18 ] for a translation of this paper as well as [ 2 ] for a comment on its relevance and its connection to [ 16 ] . In this paper von Kutschera is concerned with giving a concept of refutation that is -- other than in intuitionistic logic -- not derivative on a concept of proof but on a par with it. This is a very bilateralist stance, since bilateralism is the view that in proof-theoretic semantics it is not only the rules governing proofs of complex formulas but also the rules governing their refutations that need to be considered as meaning-determining and, importantly, that these concepts should be considered both as primitive, not one reducible to the other. 3 3 3 More often in bilateralism the terms ‘assertion’ and ‘denial’ are used as the relevant concepts but like von Kutschera we will stick to the terms ‘proof’ and ‘refutation’. Accordingly, in [ 17 ] , in order to define arbitrary n -ary connectives, he gives generalized rule schemata not only to introduce proofs but also to introduce refutations . We will start with a brief introduction to our system, considering the idea of connexive logics in general, the fact that C is a contradictory logic and the relevant differences to N4 and to von Kutschera’s approach (Section 2). To provide a basis for our proof of functional completeness, we will firstly consider generalized derivability schemata for unspecified logical operators as von Kutschera’s schemata but with a different background notion of higher-level refutability reflecting the connexive reading of consequence (Section 3-4). Subsequently, we trace von Kutschera’s proof of functional completeness for the N4 connectives, yielding the result that the connectives of C are functionally complete for these generalized schemata (Section 5-6). 2 The motivation: A contradictory logic that is functionally complete There has been a recent increase in attention with respect to studying connexive logics, resulting in a number of papers published on the subject. 4 4 4 See, e.g., the contributions in the special issue of Studia Logica on Frontiers of Connexive Logic [ 11 ] . The general idea of connexivity that should be implemented by these systems, is that no formula provably implies or is implied by its own negation. Formally this is usually realized by validating so-called Aristotle’s (AT) and Boethius’ Theses (BT), while not validating symmetry of implication. Hence, the following is the most common, agreed-upon definition: Definition 1 (Connexive logics) A logic is connexive iff 1.) the following formulas are provable in the system: • AT: {\sim}({\sim}A\rightarrow A) , • AT’: {\sim}(A\rightarrow{\sim}A) , • BT: (A\rightarrow B)\rightarrow{\sim}(A\rightarrow{\sim}B) , • BT’: (A\rightarrow{\sim}B)\rightarrow{\sim}(A\rightarrow B) , and 2.) the system satisfies non-symmetry of implication, i.e., (A\rightarrow B)\rightarrow(B\rightarrow A) is not provable. We will concentrate here on the system C , introduced in [ 22 ] , which is obtained by changing the falsification conditions of implication in Nelson’s four-valued constructive logic with strong negation, N4 [ 1 , 7 ] . 5 5 5 To give more context and references for the system C : See, e.g., [ 24 ] and [ 27 ] for motivations for C , [ 9 ] , where a direct completeness proof for 1st-order C is given, or [ 4 ] for an algebraic investigation of the system. For a sequent calculus for C , see Appendix. The following is a natural deduction calculus for the propositional fragment of C , which is adapted from a bilateral version given in [ 23 , p. 419f.] . Although in the paper introducing this system [ 22 ] , the aim is to present a connexive modal logic, we will not be concerned with modal operators here and rather concentrate on the way this system is constructed from N4 . NC Rules for {\sim} : {\sim}{\sim}AA\Gamma A{\sim}{\sim}A\Gamma Rules for \wedge : A\wedge B\;A\Gamma\quad\quad B\Delta AA\wedge B\Gamma BA\wedge B\Gamma {\sim}(A\wedge B){\sim}A\Gamma {\sim}(A\wedge B){\sim}B\Gamma C\;\;\;\;\;\;\;\;\;{\sim}(A\wedge B)\Gamma\quad C[{\sim}A],\Delta\quad C[{\sim}B],\Theta Rules for \vee : A\vee BA\Gamma A\vee BB\Gamma C\;\;\;\;\;\;\;\;\;A\vee B\Gamma\quad C[A],\Delta\quad C[B],\Theta {\sim}(A\vee B)\;{\sim}A\Gamma\quad\quad{\sim}B\Delta {\sim}A{\sim}(A\vee B)\Gamma {\sim}B{\sim}(A\vee B)\Gamma Rules for \rightarrow : A\rightarrow BB[A],\Gamma BA\Gamma\ \quad A\rightarrow

Read the complete text