Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2603.27007 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918427298365440 |
|---|---|
| author | Palmieri, Stefano |
| author_facet | Palmieri, Stefano |
| contents | Nontrivial combinatory algebras with S and K must be infinite. Associativity is incompatible with combining a classifier and a retraction pair in a finite extensional magma. These obstructions exclude several standard settings from the finite extensional framework studied here, most notably nontrivial finite S+K-style combinatory algebras and associative structures (semigroups, monoids, groups, rings) carrying both a classifier and a retraction pair. What algebraic structure exists in the remaining landscape: finite, non-associative, total?
We identify three properties of finite extensional 2-pointed magmas: self-representation (R), the classifier dichotomy (D), and the Internal Composition Property (H). We prove they are pairwise independent. Lean-verified finite counterexamples at sizes 4 through 10 establish all six non-implications, four with provably tight bounds. The minimum coexistence witness has N = 5, which is optimal: ICP requires 3 pairwise distinct core elements, so N \ge 5. The three-category decomposition induced by D is an isomorphism invariant, and the ICP is logically equivalent to the standard Compose+Inert axioms. All results are formalized in Lean 4 with zero sorry. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_27007 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Pairwise Independence of Representation, Classification, and Composition in Finite Extensional Magmas Palmieri, Stefano Logic in Computer Science Nontrivial combinatory algebras with S and K must be infinite. Associativity is incompatible with combining a classifier and a retraction pair in a finite extensional magma. These obstructions exclude several standard settings from the finite extensional framework studied here, most notably nontrivial finite S+K-style combinatory algebras and associative structures (semigroups, monoids, groups, rings) carrying both a classifier and a retraction pair. What algebraic structure exists in the remaining landscape: finite, non-associative, total? We identify three properties of finite extensional 2-pointed magmas: self-representation (R), the classifier dichotomy (D), and the Internal Composition Property (H). We prove they are pairwise independent. Lean-verified finite counterexamples at sizes 4 through 10 establish all six non-implications, four with provably tight bounds. The minimum coexistence witness has N = 5, which is optimal: ICP requires 3 pairwise distinct core elements, so N \ge 5. The three-category decomposition induced by D is an isomorphism invariant, and the ICP is logically equivalent to the standard Compose+Inert axioms. All results are formalized in Lean 4 with zero sorry. |
| title | Pairwise Independence of Representation, Classification, and Composition in Finite Extensional Magmas |
| topic | Logic in Computer Science |
| url | https://arxiv.org/abs/2603.27007 |