Equivalence and conditional independence in atomic sheaf logic

Simpson, Alex (author)

We propose a semantic foundation for logics for reasoning in settings that possess a distinction between equality of variables, a coarser equivalence of variables, and a notion of conditional independence between variables. We show that such relations can be modelled naturally in atomic sheaf toposes. Equivalence of variables is modelled by an intrinsic relation of atomic equivalence that is possessed by every atomic sheaf. We identify additional structure on the category generating the atomic topos (primarily, the existence of a system of independent pullbacks) that allows the relation of conditional independence to be interpreted in the topos. We then study the logic of equivalence and conditional independence that is induced by the internal logic of the topos. This atomic sheaf logic is a classical logic that validates a number of fundamental reasoning principles relating equivalence and conditional independence. As a concrete example of this abstract framework, we use the atomic topos over the category of surjections between inite nonempty sets as our main running example. In this category, the interpretations of equivalence and conditional independence coincide with those given by the multiteam semantics of independence logic, in which the role of equivalence is taken by the relation of mutual inclusion. A major diference from independence logic is that, in atomic sheaf logic, the multiteam semantics of the equivalence and conditional independence relations is embedded within a classical surrounding logic. At the end of the paper, we briely outline two other instances of our framework, to demonstrate its versatility. The irst of these is a category of probability sheaves, in which atomic equivalence is equality-in-distribution, and the conditional independence relation is the usual probabilistic one. Our other example is the Schanuel topos (equivalent to nominal sets) where equivalence is orbit equality and conditional independence amounts to a relative form of separatedness.

• Language: English
• Keywords: logics for probability, categorical probability theory, conditional independence, dependence logic, team semantics, sheaves, toposes
• Work type: Article
• Typology: 1.01 - Original Scientific Article
• Organization: FMF - Faculty of Mathematics and Physics
• Publication status: Published
• Publication version: Version of Record
• Year: 2026
• Number of pages: Str. 17:1-17:53
• Numbering: Vol. 73, iss. 3, article no. 17
• PID: 20.500.12556/RUL-183773
• UDC: 510.6
• ISSN on article: 0004-5411
• DOI: 10.1145/3809163
• COBISS.SI-ID: 276922371
• Publication date in RUL: 18.06.2026

Record is a part of a journal

• Title: Journal of the Association for Computing Machinery
• Shortened title: J. Assoc. Comput. Mach.
• Publisher: Association for Computing Machinery
• ISSN: 0004-5411
• COBISS.SI-ID: 25797888

Licences

• License: CC BY 4.0, Creative Commons Attribution 4.0 International
• Link: http://creativecommons.org/licenses/by/4.0/
• Description: This is the standard Creative Commons license that gives others maximum freedom to do what they want with the work as long as they credit the author.