A universal algorithm for Krull's theorem

Powell, Thomas; Schuster, Peter und Wiesnet, Franziskus (2022): A universal algorithm for Krull's theorem. In: Information and Computation, Vol. 287, 104761

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. (C) 2021 Elsevier Inc. All rights reserved.

• Item Type: Journal article
• Faculties: Mathematics, Computer Science and Statistics > Mathematics
• Subjects: 500 Science > 510 Mathematics
• ISSN: 0890-5401
• Language: English