Metraipolis › archive › dc_c19877cd46a2

Pointwise provable equality and the failure of composition — arXiv:2609.25556

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.25556
License (as archived)
CC0-1.0
Archived
2026-10-08T16:34:12.993Z
SHA-256 of the archived text
99a83194915e690b179b3c0ca0d3041491aa9a2a14e0df570cc8ce0f1ac987fc
Stable URL of this page
https://metraipolis.com/documento/dc_c19877cd46a2

How to cite

Pointwise provable equality and the failure of composition — arXiv:2609.25556 — arXiv (en), https://arxiv.org/abs/2609.25556 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_c19877cd46a2 (Metraipolis archive dc_c19877cd46a2, sha256 99a83194915e690b179b3c0ca0d3041491aa9a2a14e0df570cc8ce0f1ac987fc)
BibTeX
@misc{dcc19877cd46a2,
  title = {Pointwise provable equality and the failure of composition — arXiv:2609.25556},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.25556},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_c19877cd46a2; sha256 99a83194915e690b179b3c0ca0d3041491aa9a2a14e0df570cc8ce0f1ac987fc},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.25556. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

In their studies of pathologies in recursion categories, Montagna (1989) and Di Paola--Montagna (1991) introduce the algebraic systems $S'$ and $S'_T$, respectively, and claim that they are categories. We show that the proposed composition is not independent of the choice of representatives. For every consistent recursively enumerable extension $T$ of Peano arithmetic ($\mathrm{PA}$), we exhibit two unary programs whose partial functions are provably equal in $T$, separately at each standard input. Composing each after a program that searches for a $T$-proof of contradiction and returns its code yields programs that are not equivalent in this sense. An alternative proof uses the productivity of the complement of the diagonal halting set. Montagna's $S'$ is the case $T=\mathrm{PA}$. More generally, for consistent $T\supseteq\mathrm{PA}$, pointwise provable equality is a composition congruence exactly when $T$ proves every true $\Pi^0_1$ sentence, in which case it is extensional equality. This completeness condition fails for every consistent recursively enumerable $T\supseteq\mathrm{PA}$ by Gödel's second incompleteness theorem. For every extension $T\supseteq\mathrm{PA}$, the least composition congruence containing pointwise provable equality is extensional equality if $T$ is $\Sigma^0_1$-sound and the universal relation otherwise.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-23 in math.LO).
Categorie arXiv: Logic (math.LO) ; Logic in Computer Science (cs.LO).
Pagina del lavoro: https://arxiv.org/abs/2609.25556 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-08T15:54:33.540Z dalla pagina https://arxiv.org/catchup/math.LO/2026-09-23?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).