Mathematical foundations for symmetric programming and reasoning
We develop a mathematical abstraction for uniformly exploiting symmetries in programming and reasoning based on the mathematical proof principle `without-loss-of-generality' (w.l.o.g.). Given: group actions that describe symmetries of the input and the output; and a canoniser, which captures how arbitrary inputs get sent to canonical ones, our construction extends any function from the canonical inputs to the whole domain. We characterise the conditions on the canonisers which guarantee that the construction gives the unique equivariant (i.e. symmetry-preserving) extension. Furthermore, we adapt the construction to a dependently-typed setting, where it captures traditional symmetric w.l.o.g. arguments via the Curry-Howard correspondence. Finally, we extend the construction to algebraic data types, where the symmetries of the constructors both uniquely determine the symmetries of the data type and pave the way for efficient execution.
- quotes — Mathematical foundations for symmetric programming and reasoning (witness: https://oaipmh.arxiv.org/oai; method: quoted collector metadata from an original HTTP response; citation: https://arxiv.org/abs/2611.17106; status: unverified)
- quotes — summary: We develop a mathematical abstraction for uniformly exploiting symmetries in programming and reasoning based on the mathematical proof principle `without-loss-of-generality' (w.l.o.g.). Given: group actions that describe symmetries of the input and the output; and a canoniser, which captures how arbitrary inputs get sent to canonical ones, our construction extends any function from the canonical inputs to the whole domain. We characterise the conditions on the canonisers which guarantee that the construction gives the unique equivariant (i.e. symmetry-preserving) extension. Furthermore, we adapt the construction to a dependently-typed setting, where it captures traditional symmetric w.l.o.g. arguments via the Curry-Howard correspondence. Finally, we extend the construction to algebraic data types, where the symmetries of the constructors both uniquely determine the symmetries of the data type and pave the way for efficient execution. (witness: https://oaipmh.arxiv.org/oai; method: quoted collector metadata from an original HTTP response; citation: https://arxiv.org/abs/2611.17106; status: unverified)
- quotes — url: https://arxiv.org/abs/2611.17106 (witness: https://oaipmh.arxiv.org/oai; method: quoted collector metadata from an original HTTP response; citation: https://arxiv.org/abs/2611.17106; status: unverified)
- quotes — source-subject: arxiv:2611.17106 (witness: https://oaipmh.arxiv.org/oai; method: quoted collector metadata from an original HTTP response; citation: https://arxiv.org/abs/2611.17106; status: unverified)
- quotes — source-edition: sha256:ddced6d9d7491e3fbab63321904dfa9acfd6c6f431097519e05d5099d9aceb78 (witness: https://oaipmh.arxiv.org/oai; method: quoted collector metadata from an original HTTP response; citation: https://arxiv.org/abs/2611.17106; status: unverified)
- quotes — source-metadata: {"subject":"arxiv:2611.17106","id":"2611.17106","url":"https://arxiv.org/abs/2611.17106","datestamp":"2026-11-13","status":"present","title":"Mathematical foundations for symmetric programming and reasoning","abstract":"We develop a mathematical abstraction for uniformly exploiting symmetries in programming and reasoning based on the mathematical proof principle `without-loss-of-generality' (w.l.o.g.). Given: group actions that describe symmetries of the input and the output; and a canoniser, which captures how arbitrary inputs get sent to canonical ones, our construction extends any function from the canonical inputs to the whole domain. We characterise the conditions on the canonisers which guarantee that the construction gives the unique equivariant (i.e. symmetry-preserving) extension. Furthermore, we adapt the construction to a dependently-typed setting, where it captures traditional symmetric w.l.o.g. arguments via the Curry-Howard correspondence. Finally, we extend the construction to algebraic data types, where the symmetries of the constructors both uniquely determine the symmetries of the data type and pave the way for efficient execution.","authors":["Ohad Kammar","Matija Pretnar"],"categories":["cs.PL","cs.LO","math.CT","math.GR","math.LO"],"created":"2026-11-12","updated":"2026-11-13","articleLicense":"http://creativecommons.org/licenses/by-sa/4.0/","version":null,"editionDigest":"sha256:ddced6d9d7491e3fbab63321904dfa9acfd6c6f431097519e05d5099d9aceb78","sourceResponseAt":"2026-11-18T21:09:11Z","sourceDigest":"sha256:9463ef807009af84c66928c04f1b177905cda41c60c5b55e502ef901a90fca83"} (witness: https://oaipmh.arxiv.org/oai; method: quoted collector metadata from an original HTTP response; citation: https://arxiv.org/abs/2611.17106; status: unverified)
- quotes — editorial-standing: source metadata; editorial acceptance pending (witness: https://oaipmh.arxiv.org/oai; method: quoted collector metadata from an original HTTP response; citation: https://arxiv.org/abs/2611.17106; status: unverified)