TY - GEN

T1 - A Gandy theorem for abstract structures and applications to first-order definability

AU - Kudinov, Oleg V.

AU - Selivanov, Victor L.

PY - 2009/12/1

Y1 - 2009/12/1

N2 - We establish a Gandy theorem for a class of abstract structures and deduce some corollaries, in particular the maximal definability result for arithmetical structures in the class. We also show that the arithmetical structures under consideration are biinterpretable (without parameters) with the standard model of arithmetic. As an example we show that for any k ≥ 3 a predicate on the quotient structure of the h-quasiorder of finite k-labeled forests is definable iff it is arithmetical and invariant under automorphisms. © 2009 Springer Berlin Heidelberg.

AB - We establish a Gandy theorem for a class of abstract structures and deduce some corollaries, in particular the maximal definability result for arithmetical structures in the class. We also show that the arithmetical structures under consideration are biinterpretable (without parameters) with the standard model of arithmetic. As an example we show that for any k ≥ 3 a predicate on the quotient structure of the h-quasiorder of finite k-labeled forests is definable iff it is arithmetical and invariant under automorphisms. © 2009 Springer Berlin Heidelberg.

KW - Biinterpretability

KW - Definability

KW - Gandy theorem

KW - H-quasiorder

KW - Labeled forest

KW - Least fixed point

UR - http://www.scopus.com/inward/record.url?scp=76249132792&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-03073-4_30

DO - 10.1007/978-3-642-03073-4_30

M3 - Conference contribution

AN - SCOPUS:76249132792

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 290

EP - 299

BT - Mathematical Theory and Computational Practice (CiE 2009)

T2 - computability in europe-2009

Y2 - 19 July 2009

ER -