David Bourget (Western Ontario)
David Chalmers (ANU, NYU)
Rafael De Clercq
Jack Alan Reynolds
Learn more about PhilPapers
Notre Dame Journal of Formal Logic 47 (4):479-485 (2006)
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
|Keywords||computable poset filter reverse mathematics|
|Categories||categorize this paper)|
|Through your library||Configure|
Similar books and articles
Ramon Jansana (2003). Leibniz Filters Revisited. Studia Logica 75 (3):305 - 317.
Carl G. Jockusch Jr, Bart Kastermans, Steffen Lempp, Manuel Lerman & Reed Solomon (2009). Stability and Posets. Journal of Symbolic Logic 74 (2):693 - 711.
Andreas Blass (1990). Infinitary Combinatorics and Modal Logic. Journal of Symbolic Logic 55 (2):761-778.
Otmar Spinas (1999). Countable Filters on Ω. Journal of Symbolic Logic 64 (2):469-478.
Steffen Lempp, Charles McCoy, Russell Miller & Reed Solomon (2005). Computable Categoricity of Trees of Finite Height. Journal of Symbolic Logic 70 (1):151-215.
Jeremy Avigad (2012). Uncomputably Noisy Ergodic Limits. Notre Dame Journal of Formal Logic 53 (3):347-350.
Russell Miller (2005). The Computable Dimension of Trees of Infinite Height. Journal of Symbolic Logic 70 (1):111-141.
Michael Moses (2010). The Block Relation in Computable Linear Orders. Notre Dame Journal of Formal Logic 52 (3):289-305.
Janusz Pawlikowski (2001). Cohen Reals From Small Forcings. Journal of Symbolic Logic 66 (1):318-324.
Rod Downey, Steffen Lempp & Guohua Wu (2010). On the Complexity of the Successivity Relation in Computable Linear Orderings. Journal of Mathematical Logic 10 (01n02):83-99.
Uri Avraham & Saharon Shelah (1982). Forcing with Stable Posets. Journal of Symbolic Logic 47 (1):37-42.
Sato Kentaro (2008). Proper Semantics for Substructural Logics, From a Stalker Theoretic Point of View. Studia Logica 88 (2):295 - 324.
Anatolij Dvurečenskij & Hee Sik Kim (1998). Connections Between BCK-Algebras and Difference Posetse. Studia Logica 60 (3):421-439.
Sorry, there are not enough data points to plot this chart.
Added to index2010-08-24
Recent downloads (6 months)0
How can I increase my downloads?