2018/05/13 by Jaroslav Nešetřil, Nesetril, Jaroslav, Patrice Ossona de Mendez +1
Computer Science · Mathematics · #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Logic (math.LO) #Mathematical Dynamics and Fractals #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1805.04834
openalex publication_date 2018/05/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider mappings, which are structure consisting of a single function (and possibly some number of unary relations) and address the problem of approximating a continuous mapping by a finite mapping. This problem is the inverse problem of the construction of a continuous limit for first-order convergent sequences of finite mappings. We solve the approximation problem and, consequently, the full characterization of limit objects for mappings for first-order (i.e. \rm FO) convergence and local (i.e. \rm FO\rm local) convergence. This work can be seen both as a first step in the resolution of inverse problems (like Aldous-Lyons conjecture) and a strengthening of the classical decidability result for finite satisfiability in Rabin class (which consists of first-order logic with equality, one unary function, and an arbitrary number of monadic predicates). The proof involves model theory and analytic techniques.