Computable choice functions for computable linear orderings | Zendy

Lerman Manuel | Zendy; Watnick Richard | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

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 .

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research