2015/10/25 by Russell Miller, Miller, Russell, Bjorn Poonen +5 · 2 citations
Mathematics · #03C57 (Primary) 03D45 #08A35 (Secondary) #12L12 #18A15 #Category Theory (math.CT) #FOS: Mathematics #Logic (math.LO) #Number Theory (math.NT) #math.CT #math.LO #math.NT #msc:03C57 #msc:03D45 #msc:08A35 #msc:12L12 #msc:18A15
paper · pdf · doi:10.48550/arxiv.1510.07322
arxiv created 2015/10/25 · arxiv updated 2015/10/27
We construct a fully faithful functor from the category of graphs to the category of fields. Using this functor, we resolve a longstanding open problem in computable model theory, by showing that for every nontrivial countable structure S, there exists a countable field F with the same essential computable-model-theoretic properties as S. Along the way, we develop a new "computable category theory," and prove that our functor and its partially-defined inverse (restricted to the categories of countable graphs and countable fields) are computable functors.