betaFeedback

WorksMathematics

Strong Standard Completeness of a Hypersequent Calculus for Cyclic Involutive Residuated Lattices

Abstract

We present a hypersequent calculus HRH_R for cyclic involutive residuated lattices and prove strong standard completeness for arbitrary theories in a fixed countable propositional language. Standard models are chains on [0,1][0,1]; neither commutativity nor equality of the monoid unit and the dualizing constant is assumed. The chain semantics is the class KRK_R defined by unit cyclicity and all ordered finite-history conditions. Every countable member of KRK_R embeds into a standard chain preserving the entire signature. The construction combines central-support reconstruction, gap insertion and relative contraction. A relative comparison construction supplies the required chain countermodels. We also prove admissibility of the unrestricted density rule for theoremhood and effective elimination from finite proofs without additional assumption leaves. Elimination uses terminating enumeration of density-free proofs; ordinary Cut is retained, and no complexity bound is claimed. Further constructions give bounded standard embeddings for nontrivial countable chains of involutive uninorm logic and pseudo-uninorm logic with weak commutativity. Using ordinary chain completeness for arbitrary theories, these yield strong standard completeness for both logics. A companion Lean~4 development formalizes the main results, with its scope and external inputs stated explicitly.

2020 MSC: 03B47, 03B52, 06F05, 03B35

Email address: [email protected] (SanMin Wang)

Introduction

We introduce an explicit hypersequent calculus HR\mathrm{H}_{\mathrm{R}} in the setting of cyclic involutive residuated lattices and prove its strong standard completeness. The standard models are chains whose underlying ordered set is the real unit interval [0,1][0,1]; neither commutativity nor identification of the monoid unit with the dualizing constant is assumed. The completeness theorem concerns consequence from arbitrary theories in a fixed countable propositional language, with all premises interpreted under the same valuation.

The chain semantics of HR\mathrm{H}_{\mathrm{R}} is the class KR\mathcal{K}_{\mathrm{R}} specified in § 2: cyclic involutive residuated chains satisfying unit cyclicity and every ordered finite-history condition. These requirements hold in every densely ordered cyclic involutive residuated chain (Lemma 2.2), hence in every standard model.

The main algebraic result is a full standard representation theorem for every countable member of KR\mathcal{K}_{\mathrm{R}} (Theorem 7.1). It preserves multiplication, both residuals, involution and both designated constants simultaneously. A comparison construction relative to arbitrary theories supplies countable countermodels in KR\mathcal{K}_{\mathrm{R}} (Theorem 2.5); a single full embedding transports each countermodel and all its premises to a standard chain. This yields strong standard completeness for HR\mathrm{H}_{\mathrm{R}} (Theorem 8.2). We also obtain effective density elimination for finite proofs without additional assumption leaves, retaining ordinary Cut (Theorem 8.6).

Sections 9 and 10 apply these constructions to IUL and HpsUL*. The applications require, respectively, commutative specializations and an involutive extension satisfying all histories, together with preservation of the original endpoints. The resulting bounded standard embeddings yield strong standard completeness for these logics using their ordinary chain-completeness theorems for arbitrary theories in the respective countable languages.

The connection between density elimination and standard completeness is established in the theory of substructural fuzzy logics. Metcalfe and Montagna developed this approach for uninorm logic and several of its extensions [1]. Ciabattoni and Metcalfe subsequently gave general sufficient conditions for density elimination by substitution [2]. These proof-theoretic criteria require hypotheses on the underlying calculus; they do not establish admissibility for an arbitrary extension by additional structural rules. Our use of ordinary Cut and the entire family of ordered history rules therefore requires a separate argument.

The algebraic counterpart is densification: embedding a chain into a dense chain while preserving its operations and the defining conditions of the class. Metcalfe and Tsinakis show that every dense residuated chain is ee-cyclic, and relate densification of semilinear varieties to generation by their dense chains as quasivarieties [3 Theorem 1 and Lemma 1]. Baldi and Terui obtain densification through residuated frames for specified integral varieties and commutative varieties [4]; Galatos and Horčík give an explicit one-gap construction for commutative residuated chains [5 Theorems 3.5–3.6]. Preservation of an existing residuated reduct does not by itself make the old designated element dualizing on the extension. This is a separate requirement in the present problem.

The closest proof-theoretic precedents include Wang’s published density-elimination arguments for involutive uninorm logic and for the noncommutative system GpsUL{sup}* [6, 7]. The latter system adds weak commutativity at the monoid unit to pseudo-uninorm logic; its language and rules do not impose a cyclic dualizing element. Its density-elimination and standard-completeness statements are Theorems 4 and 5 of the published article. The former paper concerns commutative involutive logic. Jenei’s later discussion [8 Introduction] records reservations about the verification of its proof. We neither use that proof as an input nor resolve those reservations here.

For commutative involutive chains, Jenei’s group representation [9, 10, 11] and subsequent densification theorem give a particularly close algebraic comparison. Every countable odd commutative involutive chain embeds into a countable dense chain of the same class [12 Corollary 17]; the bounded version preserves the endpoints, and yields strong standard completeness of IUL{sup}fp [12 Corollary 19 and Theorem 20]. Here odd means that the monoid unit and the dualizing constant coincide.

Table 1 distinguishes the input classes, constructions and preservation requirements. Our construction retains the full signature for the explicitly axiomatized class KR\mathcal{K}_{R}, allowing noncommutative products and d≠ed \ne e; its input conditions are essential to the representation statement.

The proof separates the chain by a closed central support term. The difficult lower branch is reduced to complete group fibres. Canonical completion attains their internal self-support maxima; pullback and a countable elementary substructure retain the exact original group. A lexicographic enlargement then makes that group dense. These preparation steps make it possible to insert points in all remaining gaps while preserving associativity, both actual residuals and all histories. The upper branch requires protected support intervals and a separate reconstruction. Detailed auxiliary construc-

AspectJenei’s densification resultPresent representation theorem
Input classOdd commutative involutive chainsKR\mathcal{K}_{R}, allowing d≠ed \ne e and noncommutative products
ConstructionRepresentation by layer groupsCentral support, complete fibres, and relative return collapse
Embedding resultDense extension in the same class; bounded endpoints retainedFull standard embedding; bounded endpoints treated separately in the IUL and pseudo-uninorm transfers
Stated logical resultStrong standard completeness of IULfp\mathrm{IUL}^{fp}Strong standard completeness of HR\mathrm{H}_{R}, IUL and HpsUL∗^{*}; the latter two use ordinary theory-chain completeness. Den admissibility for HR\mathrm{H}_{R}

caption: Table 1: Scope of the comparison with [12 Corollaries 17, 19 and Theorem 20].

:::

tions and the full chain-completeness proof are supplied in Appendices § 12–§ 15, with explicit cross-references.

Machine-checked formalization. A companion Lean 4 development provides machine-checked proofs of the main representation and completeness results established here, together with an executable procedure for Den elimination. The source code and reproducibility materials are archived on Zenodo [13]. Section E specifies the verified scope, external inputs, and computational guarantees.

The calculus and its chain semantics

A cyclic involutive residuated lattice is a lattice-ordered monoid (L,∧,∨,⋅,e)(L,\wedge,\vee,\cdot,e) with residuals satisfying

xy≤z  ⟺  y≤x\z  ⟺  x≤z/yxy \le z \iff y \le x\backslash z \iff x \le z/y

and a distinguished element dd such that x′=x\d=d/xx' = x\backslash d = d/x and x′′=xx'' = x. We use the derived operation x+y=(x′y′)′x+y=(x'y')'; in particular,

e′=d,x\y=(y′x)′=y+x′,y/x=(xy′)′=x′+y.(1)e' = d,\qquad x\backslash y=(y'x)'=y+x',\qquad y/x=(xy')'=x'+y. \tag*{(1)}

A chain has a total lattice order. A standard chain has underlying ordered set [0,1][0,1]. Neither ee nor dd is required to be an endpoint, and multiplication need not be commutative. The class of all standard cyclic involutive residuated chains is denoted by Std.

Formulas are built from countably many variables, their formal duals, ee, dd, and ⋅\cdot, ++, ∧\wedge, ∨\vee. Involution is extended as a syntactic operation by A′′=AA''=A, e′=de'=d, d′=ed'=e, and

(AB)′=A′+B′,(A+B)′=A′B′,(A∧B)′=A′∨B′,(A∨B)′=A′∧B′.(AB)'=A'+B',\qquad(A+B)'=A'B',\qquad(A\wedge B)'=A'\vee B',\qquad(A\vee B)'=A'\wedge B'.

Thus the displayed order is not reversed under involution. Residual formulas abbreviate the terms in (1). All substitution instances use this convention.

A word Γ\Gamma is a finite ordered list of formulas, possibly empty. A sequent is ⇒Γ\Rightarrow\Gamma, and a hypersequent is a finite multiset of sequents, written with external bars. External permutation is implicit; internal exchange is not. Capital Latin letters GG, HH, JJ denote hypersequents, and Greek capitals denote words. A missing external background denotes the empty multiset. All words in the following rules may be empty.

The initial sequents and logical rules are

⇒A,A′Id⇒eUnit,G∣⇒A,ΓH∣⇒B,ΔG∣H∣⇒AB,Γ,Δ(⋅),G∣⇒Γ,A,B,ΔG∣⇒Γ,A+B,Δ(+)G∣⇒Γ,ΔG∣⇒Γ,d,Δ(d),G∣⇒Γ,A,ΔG∣⇒Γ,B,ΔG∣⇒Γ,A∧B,Δ(∧),G∣⇒Γ,A,ΔG∣⇒Γ,A∨B,Δ(∨1)G∣⇒Γ,B,ΔG∣⇒Γ,A∨B,Δ(∨2).(2)\begin{aligned} &\Rightarrow A,A' \quad\mathrm{Id} &&\Rightarrow e \quad\mathrm{Unit},\\ &\frac{G\mid\Rightarrow A,\Gamma\qquad H\mid\Rightarrow B,\Delta} {G\mid H\mid\Rightarrow AB,\Gamma,\Delta}\quad(\cdot),\\ &\frac{G\mid\Rightarrow\Gamma,A,B,\Delta} {G\mid\Rightarrow\Gamma,A+B,\Delta}\quad(+) &&\frac{G\mid\Rightarrow\Gamma,\Delta} {G\mid\Rightarrow\Gamma,d,\Delta}\quad(d),\\ &\frac{G\mid\Rightarrow\Gamma,A,\Delta\qquad G\mid\Rightarrow\Gamma,B,\Delta} {G\mid\Rightarrow\Gamma,A\wedge B,\Delta}\quad(\wedge),\\ &\frac{G\mid\Rightarrow\Gamma,A,\Delta} {G\mid\Rightarrow\Gamma,A\vee B,\Delta}\quad(\vee_1) &&\frac{G\mid\Rightarrow\Gamma,B,\Delta} {G\mid\Rightarrow\Gamma,A\vee B,\Delta}\quad(\vee_2). \tag*{(2)} \end{aligned}

The context of (∧)(\wedge) is shared literally. The structural rules and ordinary Cut are

G⇒Γ,ΔG⇒Δ,Γ CycGG∣S EWG∣S∣SG∣S EC,\frac{G \Rightarrow\Gamma,\Delta}{G \Rightarrow\Delta,\Gamma}\ \mathrm{Cyc} \qquad \frac{G}{G\mid S}\ \mathrm{EW} \qquad \frac{G\mid S\mid S}{G\mid S}\ \mathrm{EC},
G⇒Γ1,Γ2H⇒Δ1,Δ2G∣H⇒Γ1,Δ2∣⇒Δ1,Γ2 COM,(3)\frac{G\Rightarrow\Gamma_1,\Gamma_2\qquad H\Rightarrow\Delta_1,\Delta_2}{G\mid H\Rightarrow\Gamma_1,\Delta_2\mid\Rightarrow\Delta_1,\Gamma_2}\ \mathrm{COM}, \tag*{(3)}
G⇒Γ,Δ,eG⇒Δ,Γ,e WCMG⇒Γ,AH⇒A′,ΔG∣H⇒Γ,Δ Cut.\frac{G\Rightarrow\Gamma,\Delta,e}{G\Rightarrow\Delta,\Gamma,e}\ \mathrm{WCM} \qquad \frac{G\Rightarrow\Gamma,A\qquad H\Rightarrow A',\Delta}{G\mid H\Rightarrow\Gamma,\Delta}\ \mathrm{Cut}.

Here SS is an arbitrary sequent. Cyclically rotating the two active premises and the two outputs of COM gives its equivalent presentation that exchanges a middle block in each premise. The displayed WCM retains its literal final formula ee; it is not unrestricted exchange.

For every finite word ww over {S,T}\{S,T\} (with empty word ϵ\epsilon) define closed formulas by

(cϵ,hϵ)=(e,e),(c_\epsilon,h_\epsilon)=(e,e),
(cwS,hwS)=(dcw,e+hw),(cwT,hwT)=(e+cw,dhw).(4)(c_{wS},h_{wS})=(dc_w,e+h_w),\qquad(c_{wT},h_{wT})=(e+c_w,dh_w). \tag*{(4)}

The remaining rules, one for every such ww, are exactly

G⇒cw,Σ,ΠH⇒hw,Ω,ΛJ⇒Γ,ΔG∣H∣J⇒Π,Σ,Γ,Λ,Ω,Δ Rw.(5)\frac{G\Rightarrow c_w,\Sigma,\Pi\qquad H\Rightarrow h_w,\Omega,\Lambda\qquad J\Rightarrow\Gamma,\Delta}{G\mid H\mid J\Rightarrow\Pi,\Sigma,\Gamma,\Lambda,\Omega,\Delta}\ R_w. \tag*{(5)}

We denote this calculus by HR\mathrm{H_R}. Its proofs are finite trees. There is no initial sequent ⇒d\Rightarrow d, no internal weakening or contraction, and no density rule in HR\mathrm{H_R}. Ordinary Cut is retained.

Under a valuation in a chain, put Γ♯=A1′⋯An′\Gamma^\sharp=A'_1\cdots A'_n for Γ=A1,…,An\Gamma=A_1,\ldots,A_n, with ∅♯=e\varnothing^\sharp=e. The sequent ⇒Γ\Rightarrow\Gamma means Γ♯≤d\Gamma^\sharp\le d, and an external bar means disjunction. The empty hypersequent is therefore false. Let KR\mathcal{K}_R consist of the cyclic involutive residuated chains satisfying

ab≤e ⇒ ba≤e(6)ab\le e\ \Rightarrow\ ba\le e \tag*{(6)}

and, for every w∈{S,T}∗w\in\{S,T\}^*,

ab≤cw,uv≤hw ⇒ bazvu≤z(a,b,u,v,z∈L).(7)ab\le c_w,\qquad uv\le h_w\ \Rightarrow\ bazvu\le z\qquad(a,b,u,v,z\in L). \tag*{(7)}

The history terms in these conditions are evaluated by (4). In particular, membership in KR\mathcal{K}_R requires every finite history, without a fixed bound on its length.

Lemma 2.1 (Rotation on a dense chain). Let LL be a densely ordered chain. Suppose that f,g:L→Lf,g:L\to L are monotone, gg has a right adjoint g∗g^{*}, and f(g(t))≤tf(g(t))\le t for all tt. Then g(f(t))≤tg(f(t))\le t for all tt.

Proof. If g(f(x))>xg(f(x))>x, adjunction implies g∗(x)<f(x)g^{*}(x)<f(x). Choose g∗(x)<t<f(x)g^{*}(x)<t<f(x). Then g(t)>xg(t)>x, whence f(g(t))≥f(x)>tf(g(t))\ge f(x)>t, a contradiction.

Lemma 2.2. Every densely ordered cyclic involutive residuated chain belongs to KR\mathcal{K}_{R}.

Proof. If ab≤eab\le e, apply Lemma 2.1 to f(t)=atf(t)=at and g(t)=btg(t)=bt. Evaluating g(f(t))≤tg(f(t))\le t at ee gives ba≤eba\le e. Condition (6), with a,ba,b interchanged, says precisely x\e=e/xx\backslash e=e/x. By (1),

References

  1. [1]G. Metcalfe, F. Montagna, Substructural fuzzy logics. The Journal of Symbolic Logic 72(3) (2007) 834–864. doi:10.2178/jsl/1191333844DOI
  2. [2]A. Ciabattoni, G. Metcalfe, Density elimination. Theoretical Computer Science 403(2-3) (2008) 328–346. doi:10.1016/j.tcs.2008.05.019DOI
  3. [3]G. Metcalfe, C. Tsinakis, Density revisited. Soft Computing 21(1) (2017) 175–189. doi:10.1007/s00500-016-2420-7DOI
  4. [4]P. Baldi, K. Terui, Densification of FL chains via residuated frames. Algebra Universalis 75(2) (2016) 169–195. doi:10.1007/s00012-016-0372-5
  5. [5]N. Galatos, R. Horčík, Densification via polynomials, languages, and frames. Journal of Pure and Applied Algebra 226(3) (2022) 106852. doi:10.1016/j.jpaa.2021.106852DOI
  6. [6]S. Wang, A Proof of the Standard Completeness for the Involutive Uninorm Logic. Symmetry 11(4) (2019) 445. doi:10.3390/sym11040445DOI
  7. [7]S. Wang, The Logic of Pseudo-Uninorms and Their Residua. Symmetry 11(3) (2019) 368. doi:10.3390/sym11030368DOI
  8. [8]S. Jenei, Involutive Uninorm Logic with Fixed Point enjoys finite strong standard completeness. Archive for Mathematical Logic 62 (2023) 67–86. doi:10.1007/s00153-022-00839-1DOI
  9. [9]S. Jenei, Group Representation for Even and Odd Involutive Commutative Residuated Chains. Studia Logica 110(4) (2022) 881–922. doi:10.1007/s11225-021-09981-yDOI
  10. [10]S. Jenei, Correction to: Group Representation for Even and Odd Involutive Commutative Residuated Chains. Studia Logica 110(4) (2022) 923–924. doi:10.1007/s11225-022-09991-4DOI
  11. [11]S. Jenei, Correction to: Group Representation for Even and Odd Involutive Commutative Residuated Chains. Studia Logica 111(5) (2023) 897–898. doi:10.1007/s11225-023-10059-0DOI
  12. [12]S. Jenei, Densification in Classes of Involutive Commutative Residuated Lattices. Studia Logica (2025). Published online 7 July 2025. doi:10.1007/s11225-025-10190-0DOI
  13. [13]S. Wang, CyclicInvolutive: Lean 4 Companion to “Strong Standard Completeness of a Hypersequent Calculus for Cyclic Involutive Residuated Lattices”, software and accompanying materials, Zenodo, 2026. doi: 10.5281/zenodo.24242771.
  14. [14]J. Gil-Férez, L. Spada, C. Tsinakis, H. Zhou, Join-completions of ordered algebras. arXiv:1708.04990v1 (2017). https://arxiv.org/abs/1708.04990v1
  15. [15]J. Gil-Férez, L. Spada, C. Tsinakis, H. Zhou, Join-completions of partially ordered algebras. Annals of Pure and Applied Logic 171(10) (2020) 102842. doi:10.1016/j.apal.2020.102842
  16. [16]S. Wang, Logics for Finite UL and IUL-Algebras Are Substructural Fuzzy Logics. Symmetry 10(12) (2018) 755. doi:10.3390/sym10120755DOI
  17. [17]N. Galatos, J.G. Raftery, Adding Involution to Residuated Structures. Studia Logica 77(2) (2004) 181–207. doi:10.1023/B:STUD.0000037126.29193.09DOI
  18. [18]M. Gehrke, Topological Duality and Algebraic Completions. In: Galatos, N., Terui, K. (eds.) Hiroakira Ono on Substructural Logics. Outstanding Contributions to Logic, vol. 23, pp. 143–184. Springer, Cham (2022). doi:10.1007/978-3-030-76920-8_4
  19. [19]T. Kowalski, G. Metcalfe, Uniform interpolation and coherence. Annals of Pure and Applied Logic 170(7) (2019) 825–841. doi:10.1016/j.apal.2019.02.004DOI

Paper details

vlnc:W_zdscakzv
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

OpenAI ChatGPT

View statement
Looking for related papers…
Contents