Reverse mathematics and properties of finite character
type: Item
instance of: scholarly article
title: Reverse mathematics and properties of finite character
zbMATH Open document ID: 1253.03032
author: Damir D. Dzhafarov
author: Carl Mummert
published in: Annals of Pure and Applied Logic
publication date: 2012-07-11T00:00:00Z
full work available at URL: https://arxiv.org/abs/1109.3378
review text: This article analyzes the logical strength of variants of Tukey's lemma in the framework of reverse mathematics. A formula \(\varphi\) with one free set variable has the finite character property if \(\varphi (\emptyset )\) holds and for every set \(A\), \(\varphi (A)\) holds if and only if \(\varphi (F)\) holds for every finite \(F \subseteq A\). For a class of formulas \(\Gamma\), the principle \(\Gamma\)-FCP asserts that, given any formula of finite character in \(\Gamma\) (with parameters), every set \(A\) has a maximal subset \(B\) such that \(\varphi (B)\) holds. The authors show that RCA\(_0\) proves \(\Sigma^0_1\)-FCP, and that for \(n\geq 1\), RCA\(_0\) proves that ACA\(_0\) is equivalent to \(\Pi^0_n\)-FCP and \(\Pi^1_n\)-CA\(_0\) is equivalent to \(\Pi^1_n\)-FCP. The finite character principle can be strengthened by requiring that the maximal set is closed under a finitary closure operator, yielding the \(\Gamma\)-CE scheme, or under a nondeterministic finitary closure operator, yielding \(\Gamma\)-NCE. The authors show that QF-CE and \(\Sigma^0_1\)-CE are each equivalent to ACA\(_0\), while QF-NCE and \(\Sigma^0_1\)-NCE are each equivalent to \(\Pi^1_1\)-CA\(_0\). For \(n \geq 1\), RCA\(_0\) proves that \(\Pi^1_n\)-CA\(_0\) is equivalent to \(\Pi^1_n\)-NCE. The results in this paper provide an interesting contrast to the authors' work on finite intersection principles [``On the strength of the finite intersection principle'', Isr. J. Math. (2012; \url{doi:10.1007/s11856-012-1050-9}), \url{arXiv:1109.3374}].
reviewed by: Jeffry L. Hirst
Mathematics Subject Classification ID: 03B30
Mathematics Subject Classification ID: 03F35
Mathematics Subject Classification ID: 03E25
zbMATH DE Number: 6054360
zbMATH Keywords: reverse mathematics
zbMATH Keywords: finite character
zbMATH Keywords: axiom of choice
zbMATH Keywords: closure operator
zbMATH Keywords: Tukey's lemma
Wikidata QID: Q57951146
MaRDI profile type: Publication
OpenAlex ID: W2010324947
arXiv ID: 1109.3378
cites work: REVERSE MATHEMATICS OF MF SPACES
cites work: Equivalents of the axiom of choice. 2nd ed
cites work: Q3395521
DOI: 10.1016/J.APAL.2012.01.007
DBLP publication ID: journals/apal/DzhafarovM12
Recommended article: Characterizing von Neumann regular rings in reverse mathematics
Recommended article: Reverse Mathematics and Algebraic Field Extensions
Recommended article: Reverse mathematics and fully ordered groups
Recommended article: Reverse mathematics and semisimple rings
Recommended article: REVERSE MATHEMATICS OF MF SPACES
Recommended article: Reverse mathematics and well-ordering principles
Recommended article: Q4440538
Recommended article: Reverse Mathematics
Recommended article: Representations of Reals in Reverse Mathematics
Recommended article: Reverse mathematics and Weihrauch analysis motivated by finite complexity theory
description: scientific article; zbMATH DE number 6054360