Equivalence and conditional independence in atomic sheaf logic

Simpson, Alex (avtor)

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.

• Jezik: Angleški jezik
• Ključne besede: logics for probability, categorical probability theory, conditional independence, dependence logic, team semantics, sheaves, toposes
• Vrsta gradiva: Članek v reviji
• Tipologija: 1.01 - Izvirni znanstveni članek
• Organizacija: FMF - Fakulteta za matematiko in fiziko
• Status publikacije: Objavljeno
• Različica publikacije: Objavljena publikacija
• Leto izida: 2026
• Št. strani: Str. 17:1-17:53
• Številčenje: Vol. 73, iss. 3, article no. 17
• PID: 20.500.12556/RUL-183773
• UDK: 510.6
• ISSN pri članku: 0004-5411
• DOI: 10.1145/3809163
• COBISS.SI-ID: 276922371
• Datum objave v RUL: 18.06.2026

Gradivo je del revije

• Naslov: Journal of the Association for Computing Machinery
• Skrajšan naslov: J. Assoc. Comput. Mach.
• Založnik: Association for Computing Machinery
• ISSN: 0004-5411
• COBISS.SI-ID: 25797888

Licence

• Licenca: CC BY 4.0, Creative Commons Priznanje avtorstva 4.0 Mednarodna
• Povezava: http://creativecommons.org/licenses/by/4.0/deed.sl
• Opis: To je standardna licenca Creative Commons, ki daje uporabnikom največ možnosti za nadaljnjo uporabo dela, pri čemer morajo navesti avtorja.