On computable aspects of algebraic and definable closure

2020/12/07 by Nathanael Ackerman, Cameron Freer, Cameron E. Freer +1
Computer Science · Mathematics · #Advanced Topology and Set Theory #Algebraic closure #Algebraic number #Closure (psychology) #Combinatorics #Computability #Computability theory #Computability, Logic, AI Algorithms #Computable analysis #Computable number #Discrete mathematics #Mathematics #Quantifier elimination #Rank (graph theory) #cs.LO #math.LO #semigroups and automata theory

paper · pdf · doi:10.1093/logcom/exaa070

published in Journal of Logic and Computation 31(1), 2-19 (Oxford University Press) · 20 pages

openalex publication_date 2020/12/07 · arxiv created 2021/01/28 · arxiv updated 2021/03/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/06

Abstract

Abstract We investigate the computability of algebraic closure and definable closure with respect to a collection of formulas. We show that for a computable collection of formulas of quantifier rank at most n, in any given computable structure, both algebraic and definable closure with respect to that collection are \varSigma ⁰_n+2 sets. We further show that these bounds are tight.

Citations

• Model Theory
• INVARIANT MEASURES CONCENTRATED ON COUNTABLE STRUCTURES