Lune

LICS2020Top-tier venue

A characterisation of ordered abstract probabilities

Abraham Westerbaan, Bas Westerbaan, John van de Wetering

Abstract

In computer science, especially when dealing with quantum computing or other non-standard models of computation, basic notions in probability theory like "a predicate" vary wildly. There seems to be one constant: the only useful example of an algebra of probabilities is the real unit interval. In this paper we try to explain this phenomenon. We will show that the structure of the real unit interval naturally arises from a few reasonable assumptions. We do this by studying effect monoids, an abstraction of the algebraic structure of the real unit interval: it has an addition x + y which is only defined when x + y ≤ 1 and an involution x → 1x which make it an effect algebra, in combination with an associative (possibly non-commutative) multiplication. Examples include the unit intervals of ordered rings and Boolean algebras.

We present a structure theory for effect monoids that are ωcomplete, i.e. where every increasing sequence has a supremum.

We show that any ω-complete effect monoid embeds into the direct sum of a Boolean algebra and the unit interval of a commutative unital C * -algebra. This gives us from first principles a dichotomy between sharp logic, represented by the Boolean algebra part of the effect monoid, and probabilistic logic, represented by the commutative C * -algebra. Some consequences of this characterisation are that the multiplication must always be commutative, and that the unique ω-complete effect monoid without zero divisors and more than 2 elements must be the real unit interval. Our results give an algebraic characterisation and motivation for why any physical or logical theory would represent probabilities by real numbers.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

Questions to start from

Lune can draw on

the full paper · related work

Get the answer

Free to start. No credit card required.

Related papers

  1. The next 700 relational program logicsKenji Maillard, Catalin Hritcu, Exequiel Rivas, Antoine Van MuylderPOPL 2020 · 41 citations
  2. Central Submonads and Notions of Computation: Soundness, Completeness and Internal LanguagesTitouan Carette, Louis Lemonnier, Vladimir ZamdzhievLICS 2023 · 3 citations
  3. Cones as a model of intuitionistic linear logicThomas EhrhardLICS 2020 · 4 citations
  4. A Cartesian Closed Category for Random VariablesPietro Di Gianantonio, Abbas EdalatLICS 2024 · 1 citation
  5. Commutative Monads for Probabilistic Programming LanguagesXiaodong Jia, Bert Lindenhovius, Michael W. Mislove, Vladimir ZamdzhievLICS 2021 · 19 citations
Dusk over the sea between two cliffs drawn in fine vertical lines