UCL logo

UCL Discovery

UCL home » Library Services » Electronic resources » UCL Discovery

Disjoint union partial algebras

Hirsch, R; McLean, B; (2017) Disjoint union partial algebras. Logical Methods in Computer Science , 13 (2) pp. 1-31. 10.23638/LMCS-13(2:10)2017. Green open access

[img]
Preview
Text
Hirsch_1612.00252.pdf - ["content_typename_Published version" not defined]

Download (506kB) | Preview

Abstract

Disjoint union is a partial binary operation returning the union of two sets if they are disjoint and undefined otherwise. A disjoint-union partial algebra of sets is a collection of sets closed under disjoint unions, whenever they are defined. We provide a recursive first-order axiomatisation of the class of partial algebras isomorphic to a disjoint-union partial algebra of sets but prove that no finite axiomatisation exists. We do the same for other signatures including one or both of disjoint union and subset complement, another partial binary operation we define. Domain-disjoint union is a partial binary operation on partial functions, returning the union if the arguments have disjoint domains and undefined otherwise. For each signature including one or both of domain-disjoint union and subset complement and optionally including composition, we consider the class of partial algebras isomorphic to a collection of partial functions closed under the operations. Again the classes prove to be axiomatisable, but not finitely axiomatisable, in first-order logic. We define the notion of pairwise combinability. For each of the previously considered signatures, we examine the class isomorphic to a partial algebra of sets/partial functions under an isomorphism mapping arbitrary suprema of pairwise combinable sets to the corresponding disjoint unions. We prove that for each case the class is not closed under elementary equivalence. However, when intersection is added to any of the signatures considered, the isomorphism class of the partial algebras of sets is finitely axiomatisable and in each case we give such an axiomatisation.

Type: Article
Title: Disjoint union partial algebras
Open access status: An open access version is available from UCL Discovery
DOI: 10.23638/LMCS-13(2:10)2017
Publisher version: http://dx.doi.org/10.23638/LMCS-13(2:10)2017
Language: English
Additional information: This work is licensed under the Creative Commons Attribution-NoDerivs License. To view a copy of this license, visit http://creativecommons.org/licenses/by-nd/2.0/ or send a letter to Creative Commons, 171 Second St, Suite 300, San Francisco, CA 94105, USA, or Eisenacher Strasse 2, 10777 Berlin, Germany.
Keywords: Mathematics - Rings and Algebras, Computer Science - Logic in Computer Science, Mathematics - Logic
UCL classification: 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: http://discovery.ucl.ac.uk/id/eprint/10037693
Downloads since deposit
7Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item