Westerbaan, A;
Westerbaan, B;
Wetering, JVD;
(2020)
A characterisation of ordered abstract probabilities.
In: Hermanns, H and Zhang, L and Kobayashi, N and Miller, D, (eds.)
LICS '20: Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science.
(pp. pp. 944-957).
Association for Computing Machinery (ACM): New York, NY, USA.
Preview |
Text
Westerbaan_1912.10040v2.pdf - Accepted Version Download (282kB) | Preview |
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~1 -- x 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.
| Type: | Proceedings paper |
|---|---|
| Title: | A characterisation of ordered abstract probabilities |
| Event: | 35th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS '20) |
| ISBN-13: | 978-1-4503-7104-9 |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1145/3373718.3394742 |
| Publisher version: | https://doi.org/10.1145/3373718.3394742 |
| Language: | English |
| Additional information: | This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions. |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10104495 |
Archive Staff Only
 |
View Item |
