Premium
Computable choice functions for computable linear orderings
Author(s) -
Lerman Manuel,
Watnick Richard
Publication year - 2003
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.200310053
Subject(s) - mathematics , order type , computable function , order (exchange) , computable analysis , set (abstract data type) , integer (computer science) , characterization (materials science) , degree (music) , type (biology) , maximal element , computable number , discrete mathematics , combinatorics , computer science , ecology , materials science , physics , finance , acoustics , economics , biology , programming language , nanotechnology
A choice set for a computable linear ordering is a set which contains one element from each maximal block of the ordering. We obtain a partial characterization of the computable linear order‐types for which each computable model has a computable choice set, and a full characterization in the relativized case; Every model of the linear order‐type α of degree ≤ d has a choice set of degree ≤ d iff α can written as a finite sum of order‐types, each of which either has finitely many blocks, or has order‐type n · η for some integer n .