{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,14]],"date-time":"2025-05-14T09:58:52Z","timestamp":1747216732458,"version":"3.40.5"},"reference-count":39,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2023,8,10]],"date-time":"2023-08-10T00:00:00Z","timestamp":1691625600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Compositionality"],"abstract":"<jats:p>This article re-examines Lawvere's abstract, category-theoretic proof of the fixed-point theorem whose contrapositive is a `universal' diagonal argument. The main result is that the necessary axioms for both the fixed-point theorem and the diagonal argument can be stripped back further, to a semantic analogue of a weak substructural logic lacking weakening or exchange.<\/jats:p>","DOI":"10.32408\/compositionality-5-8","type":"journal-article","created":{"date-parts":[[2023,8,10]],"date-time":"2023-08-10T10:04:07Z","timestamp":1691661847000},"page":"8","source":"Crossref","is-referenced-by-count":1,"title":["Substructural fixed-point theorems and the diagonal argument: theme and variations"],"prefix":"10.46298","volume":"5","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3478-0522","authenticated-orcid":false,"given":"David Michael","family":"Roberts","sequence":"first","affiliation":[{"name":"School of Computer and Mathematical Sciences, The University of Adelaide, Adelaide, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"25203","published-online":{"date-parts":[[2023,8,10]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"Samson Abramsky. \u201cNo-cloning in categorical quantum mechanics\u201d. In: Semantic techniques in quantum computation. https:\/\/doi.org\/10.1017\/CBO9781139193313.002, arXiv:0910.2401. Cambridge Univ. Press, Cambridge, 2010, pp. 1\u201328.","DOI":"10.1017\/CBO9781139193313.002"},{"key":"1","doi-asserted-by":"publisher","unstructured":"Samson Abramsky and Jonathan Zvesper. \u201cFrom Lawvere to Brandenburger-Keisler: Interactive Forms of Diagonalization and Self-reference\u201d. In: Coalgebraic Methods in Computer Science. Ed. by Dirk Pattinson and Lutz Schr\u00f6der. https:\/\/doi.org\/10.1016\/j.jcss.2014.12.001, arXiv:1006.0992. 2012, pp. 1\u201319.","DOI":"10.1016\/j.jcss.2014.12.001"},{"key":"2","doi-asserted-by":"publisher","unstructured":"John Baez and Mike Stay. \u201cPhysics, topology, logic and computation: a Rosetta Stone\u201d. In: New structures for physics. Vol. 813. Lecture Notes in Phys. https:\/\/doi.org\/10.1007\/978-3-642-12821-9, arXiv:0903.0340. Springer, Heidelberg, 2011, pp. 95\u2013172.","DOI":"10.1007\/978-3-642-12821-9"},{"key":"3","unstructured":"Carsten Butz. \u201cRegular Categories and Regular Logic\u201d. In: BRICS LS-98-2 (1998). https:\/\/www.brics.dk\/LS\/98\/2\/."},{"key":"4","unstructured":"Georg Cantor. \u201cUeber eine elementare Frage der Mannigfaltigkeitslehre\u201d. In: Jahresber. Dtsch. Math.-Ver. 1 (1892), pp. 75\u201378."},{"key":"5","doi-asserted-by":"publisher","unstructured":"Karel Chvalovsk\u00fd and Rostislav Hor\u010d\u00edk. \u201cFull Lambek calculus with contraction is undecidable\u201d. In: J. Symb. Log. 81.2 (2016). https:\/\/doi.org\/10.1017\/jsl.2015.18, pp. 524\u2013540.","DOI":"10.1017\/jsl.2015.18"},{"key":"6","unstructured":"Alexei Davydov. \u201cNuclei of categories with tensor products\u201d. In: Theory and Applications of Categories 18 (2007). http:\/\/www.tac.mta.ca\/tac\/volumes\/18\/16\/18-16abs.html, arXiv:0708.2761, pp. 440\u2013472."},{"key":"7","unstructured":"Valeria de Paiva. Dialectica Categories: the Relevant version. Talk at ICM2018 logic-satellite meeting, Niteroi, Brazil, August 2018, https:\/\/www.slideshare.net\/valeria.depaiva\/dialectica-categories-the-relevant-version-valeria-de-paiva, 2018."},{"key":"8","unstructured":"Valeria de Paiva. Relevant Dialectica Categories. MIT Category Theory Seminar talk, https:\/\/youtu.be\/HnxUYb4FGzY. Aug. 2020."},{"key":"9","doi-asserted-by":"publisher","unstructured":"Kosta Do\u0161en and Zoran Petri\u0107. \u201cRelevant categories and partial functions\u201d. In: Publications de l\u2019Institut Math\u00e9matique 82 (2007). https:\/\/doi.org\/10.2298\/PIM0796017D, arXiv:math\/0504133, pp. 17\u201323.","DOI":"10.2298\/PIM0796017D"},{"key":"10","unstructured":"Mart\u00edn H\u00f6tzel Escard\u00f3. On Lawvere\u2019s Fixed Point Theorem (LFPT). Commented agda code available at https:\/\/www.cs.bham.ac.uk\/ mhe\/agda-new\/LawvereFPT.html. 2018."},{"key":"11","doi-asserted-by":"crossref","unstructured":"Robert Feys. \u201cLes Logiques nouvelles des modalit\u00e9s\u201d. In: Revue n\u00e9oscolastique de philosophie 40 (1937). Available from https:\/\/www.jstor.org\/stable\/26346052, pp. 517\u2013553.","DOI":"10.3406\/phlou.1937.3056"},{"key":"12","unstructured":"Misha Gromov. Ergostuctures, Ergologic and the Universal Learning Problem: Chapters 1, 2. https:\/\/www.ihes.fr\/ gromov\/wp-content\/uploads\/2018\/08\/ergologic31.pdf. 2013."},{"key":"13","doi-asserted-by":"publisher","unstructured":"Bart Jacobs. \u201cSemantics of lambda-${\\rm I}$ and of other substructure lambda calculi\u201d. In: Typed lambda calculi and applications (Utrecht, 1993). Vol. 664. Lecture Notes in Comput. Sci. https:\/\/doi.org\/10.1007\/BFb0037107. Springer, Berlin, 1993, pp. 195\u2013208.","DOI":"10.1007\/BFb0037107"},{"key":"14","doi-asserted-by":"publisher","unstructured":"F. William Lawvere. \u201cDiagonal arguments and Cartesian closed categories\u201d. In: Repr. Theory Appl. Categ. 15 (2006). Reprinted from Category Theory, Homology Theory and their Applications, II (Battelle Institute Conference, Seattle, Wash., 1968, Vol. Two) pp. 134\u2013145, https:\/\/doi.org\/10.1007\/BFb0080769.","DOI":"10.1007\/BFb0080769"},{"key":"15","doi-asserted-by":"publisher","unstructured":"F. William Lawvere and Stephen H. Schanuel. Conceptual mathematics. 2nd Edition. https:\/\/doi.org\/10.1017\/CBO9780511804199. Cambridge University Press, Cambridge, 2009.","DOI":"10.1017\/CBO9780511804199"},{"key":"16","doi-asserted-by":"publisher","unstructured":"Daniel R. Licata, Ian Orton, Andrew M. Pitts, and Bas Spitters. \u201cInternal universes in models of homotopy type theory\u201d. In: rd International Conference on Formal Structures for Computation and Deduction. Vol. 108. LIPIcs. Leibniz Int. Proc. Inform. https:\/\/doi.org\/10.4230\/LIPIcs.FSCD.2018.22, arXiv:1801.07664. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2018, Art. No. 22, 17.","DOI":"10.4230\/LIPIcs.FSCD.2018.22"},{"key":"17","doi-asserted-by":"publisher","unstructured":"William McCune and Larry Wos. \u201cA case study in automated theorem proving: finding sages in combinatory logic\u201d. In: J. Automat. Reasoning 3.1 (1987). https:\/\/doi.org\/10.1007\/BF00381147, pp. 91\u2013107.","DOI":"10.1007\/BF00381147"},{"key":"18","unstructured":"Mar\u00eda Claudia Mer\u00e9. \u201cL\u00f3gicas Relevantes: formalismo e sem\u00e2ntica\u201d. Available from https:\/\/www.dbd.puc-rio.br\/deptoinformatica\/93mere.pdf. PhD thesis. Pontif\u00edcia Universidade Cat\u00f3lica do Rio de Janeiro, 1993."},{"key":"19","doi-asserted-by":"publisher","unstructured":"Robert K. Meyer. \u201cConservative extension in relevant implication\u201d. In: Studia Logica 31 (1972). https:\/\/doi.org\/10.1007\/BF02120525, pp. 40\u201346.","DOI":"10.1007\/BF02120525"},{"key":"20","unstructured":"Robert K. Meyer and Richard Routley. \u201cAlgebraic analysis of entailment. I\u201d. In: Logique et Anal. (N.S.) 15 (1972). https:\/\/www.jstor.org\/stable\/44083856, pp. 407\u2013428. issn: 0024-5836."},{"key":"21","unstructured":"Bartosz Milewski. How to get enriched over magmas and monoids. Blog post, https:\/\/bartoszmilewski.com\/2014\/09\/29\/how-to-get-enriched-over-magmas-and-monoids\/. 2014."},{"key":"22","doi-asserted-by":"publisher","unstructured":"Philip S. Mulry. \u201cA categorical approach to the theory of computation\u201d. In: Ann. Pure Appl. Logic 43.3 (1989). https:\/\/doi.org\/10.1016\/0168-0072(89)90072-9, pp. 293\u2013305.","DOI":"10.1016\/0168-0072(89)90072-9"},{"key":"23","doi-asserted-by":"publisher","unstructured":"Peter W. O\u2019Hearn, A. John Power, Makoto Takeyama, and Robert D. Tennent. \u201cSyntactic control of interference revisited\u201d. In: Mathematical foundations of programming semantics (New Orleans, LA, 1995). Vol. 1. Electron. Notes Theor. Comput. Sci. https:\/\/doi.org\/10.1016\/S1571-0661(04)00026-X. Elsevier Sci. B. V., Amsterdam, 1995, pp. 447\u2013486.","DOI":"10.1016\/S1571-0661(04)00026-X"},{"key":"24","doi-asserted-by":"publisher","unstructured":"Hiroakira Ono. \u201cStructural rules and a logical hierarchy\u201d. In: Mathematical logic. https:\/\/doi.org\/10.1007\/978-1-4613-0609-2. Plenum, New York, 1990, pp. 95\u2013104.","DOI":"10.1007\/978-1-4613-0609-2"},{"key":"25","unstructured":"Greg Restall. \u201cModalities in substructural logics\u201d. In: Logique et Anal. (N.S.) 36.141-142 (1993). https:\/\/www.jstor.org\/stable\/44084365, pp. 25\u201338. issn: 0024-5836."},{"key":"26","unstructured":"Greg Restall. An Introduction to Substructural Logics. Routledge, 2000."},{"key":"27","unstructured":"Dana S. Scott. \u201cRelating theories of the $\\lambda $-calculus\u201d. In: To H. B. Curry: essays on combinatory logic, lambda calculus and formalism. Academic Press, London-New York, 1980, pp. 403\u2013450."},{"key":"28","doi-asserted-by":"publisher","unstructured":"Peter Selinger. \u201cCategorical structure of asynchrony\u201d. In: MFPS XV: Mathematical Foundations of Programming Semantics, Fifteenth Conference (New Orleans, LA, 1999). Vol. 20. Electron. Notes Theor. Comput. Sci. https:\/\/doi.org\/10.1016\/S1571-0661(04)80073-2. Elsevier Sci. B. V., Amsterdam, 1999, 24 pp.","DOI":"10.1016\/S1571-0661(04)80073-2"},{"key":"29","doi-asserted-by":"publisher","unstructured":"Michael Shulman. \u201cBrouwer\u2019s fixed-point theorem in real-cohesive homotopy type theory\u201d. In: Math. Structures Comput. Sci. 28.6 (2018). https:\/\/doi.org\/10.1017\/S0960129517000147, arXiv:1509.07584, pp. 856\u2013941.","DOI":"10.1017\/S0960129517000147"},{"key":"30","unstructured":"Raymond M. Smullyan. To Mock a Mocking Bird and Other Logic Puzzles: Including an Amazing Adventure in Combinatory Logic. Knopf, 1985."},{"key":"31","unstructured":"M. E. Szabo. Algebra of proofs. Vol. 88. Studies in Logic and the Foundations of Mathematics. North-Holland Publishing Co., Amsterdam-New York, 1978, pp. xii+297."},{"key":"32","doi-asserted-by":"publisher","unstructured":"Korn\u00e9l Szlach\u00e1nyi. \u201cSkew-monoidal categories and bialgebroids\u201d. In: Advances in Mathematics 231.3 (2012). https:\/\/doi.org\/10.1016\/j.aim.2012.06.027, arXiv:1201.4981, pp. 1694\u20131730.","DOI":"10.1016\/j.aim.2012.06.027"},{"key":"33","unstructured":"The Agda Team. Agda documentation: Flat Modality. https:\/\/agda.readthedocs.io\/en\/latest\/language\/flat.html. 2021."},{"key":"34","doi-asserted-by":"publisher","unstructured":"Vladimir L. Vasyukov. \u201cParaconsistency in categories: case of relevance logic\u201d. In: Studia Logica 98.3 (2011). https:\/\/doi.org\/10.1007\/s11225-011-9342-2, pp. 429\u2013443.","DOI":"10.1007\/s11225-011-9342-2"},{"key":"35","doi-asserted-by":"crossref","unstructured":"David Walker. \u201cSubstructural Type Systems\u201d. In: Advanced Topics in Types and Programming Languages. The MIT Press, 2005, pp. 3\u201343.","DOI":"10.7551\/mitpress\/1104.003.0003"},{"key":"36","doi-asserted-by":"publisher","unstructured":"Gijs Jasper Wijnholds. \u201cCoherent diagrammatic reasoning in compositional distributional semantics\u201d. In: Logic, language, information, and computation. Vol. 10388. Lecture Notes in Comput. Sci. https:\/\/doi.org\/10.1007\/978-3-662-55386-2. Springer, Berlin, 2017, pp. 371\u2013386.","DOI":"10.1007\/978-3-662-55386-2"},{"key":"37","unstructured":"Georg H. von Wright. An essay in modal logic. Vol. 5. Studies in Logic and the Foundations of Mathematics. North-Holland, 1951."},{"key":"38","doi-asserted-by":"publisher","unstructured":"Noson S. Yanofsky. \u201cA universal approach to self-referential paradoxes, incompleteness and fixed points\u201d. In: Bull. Symbolic Logic 9.3 (2003). https:\/\/doi.org\/10.2178\/bsl\/1058448677, arXiv:math\/0305282, pp. 362\u2013386.","DOI":"10.2178\/bsl\/1058448677"}],"container-title":["Compositionality"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/compositionality-journal.org\/papers\/compositionality-5-8\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2024,10,25]],"date-time":"2024-10-25T23:58:27Z","timestamp":1729900707000},"score":1,"resource":{"primary":{"URL":"https:\/\/compositionality.episciences.org\/13527"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,8,10]]},"references-count":39,"URL":"https:\/\/doi.org\/10.32408\/compositionality-5-8","relation":{},"ISSN":["2631-4444"],"issn-type":[{"type":"electronic","value":"2631-4444"}],"subject":[],"published":{"date-parts":[[2023,8,10]]},"article-number":"8"}}