Premium
UNIVERSAL FUNCTIONS IN PARTIAL STRUCTURES
Author(s) -
Negri Maurizio
Publication year - 1992
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/malq.19920380121
Subject(s) - recursion (computer science) , partial function , mathematics , simple (philosophy) , class (philosophy) , universal turing machine , pure mathematics , algebra over a field , computer science , discrete mathematics , algorithm , turing machine , computation , artificial intelligence , philosophy , epistemology
In this work we show that every structure can be expanded to a partial structure * with universal functions for the class of polynomials on *. We can embed * monomorphically in a total structure º that preserves universal functions of * and that is universal among such structures, i.e. º can be homomorphically embedded in every total structure that preserves universal functions of *. Universal functions are the starting point for developing recursion theoretic tools in an * that satisfies some simple additional conditions.