Filters on Computable Posets
Lempp, Steffen ; Mummert, Carl
Notre Dame J. Formal Logic, Tome 47 (2006) no. 1, p. 479-485 / Harvested from Project Euclid
We explore the problem of constructing maximal and unbounded filters on computable posets. We obtain both computability results and reverse mathematics results. A maximal filter is one that does not extend to a larger filter. We show that every computable poset has a \Delta^0_2 maximal filter, and there is a computable poset with no \Pi^0_1 or \Sigma^0_1 maximal filter. There is a computable poset on which every maximal filter is Turing complete. We obtain the reverse mathematics result that the principle "every countable poset has a maximal filter" is equivalent to ACA₀ over RCA₀. An unbounded filter is a filter which achieves each of its lower bounds in the poset. We show that every computable poset has a \Sigma^0_1 unbounded filter, and there is a computable poset with no \Pi^0_1 unbounded filter. We show that there is a computable poset on which every unbounded filter is Turing complete, and the principle "every countable poset has an unbounded filter" is equivalent to ACA₀ over RCA₀. We obtain additional reverse mathematics results related to extending arbitrary filters to unbounded filters and forming the upward closures of subsets of computable posets.
Publié le : 2006-10-14
Classification:  computable poset,  filter,  reverse mathematics,  03D,  03B30,  06
@article{1168352662,
     author = {Lempp, Steffen and Mummert, Carl},
     title = {Filters on Computable Posets},
     journal = {Notre Dame J. Formal Logic},
     volume = {47},
     number = {1},
     year = {2006},
     pages = { 479-485},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1168352662}
}
Lempp, Steffen; Mummert, Carl. Filters on Computable Posets. Notre Dame J. Formal Logic, Tome 47 (2006) no. 1, pp.  479-485. http://gdmltest.u-ga.fr/item/1168352662/