Cover Image for System.Linq.Enumerable+EnumerablePartition`1[System.Char]

A universal algorithm for Krull's theorem

OAI: oai:purehost.bath.ac.uk:openaire_cris_publications/4196e3a9-5385-4400-81d6-aeaaccb4fd15 DOI: https://doi.org/10.1016/j.ic.2021.104761
Published by:

Abstract

We give a computational interpretation to an abstract formulation of Krull's theorem, by analysing its classical proof based on Zorn's lemma. Our approach is inspired by proof theory, and uses a form of update recursion to replace the existence of maximal ideals. Our main result allows us to derive, in a uniform way, algorithms which compute witnesses for existential theorems in countable abstract algebra. We give a number of concrete examples of this phenomenon, including the prime ideal theorem and Krull's theorem on valuation rings.