Brown's lemma in second-order arithmetic
We show that Brown's lemma is equivalent to Sigma02-induction over RCA0* and that the finite version of Brown's lemma is provable in RCA0 but not in RCA0*.
Source author record
Emanuele Frittaion
Emanuele Frittaion appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
ResearcherUnclaimed source record
Catalog footprint
What is connected
5works
2topics
4close collaborators
Research graph
See the researcher in context
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
5 published item(s)
preprint2016arXiv
Coloring the rationals in reverse mathematics
Ramsey's theorem for pairs asserts that every 2-coloring of the pairs of integers has an infinite monochromatic subset. In this paper, we study a strengthening of Ramsey's theorem for pairs due to Erdos and Rado, which states that every 2-coloring of the pairs of rationals has either an infinite 0-homogeneous set or a 1-homogeneous set of order type eta, where eta is the order type of the rationals. This theorem is a natural candidate to lie strictly between the arithmetic comprehension axiom and Ramsey's theorem for pairs. This Erdos-Rado theorem, like the tree theorem for pairs, belongs to a family of Ramsey-type statements whose logical strength remains a challenge.
0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv
The strength of the SCT criterion
We undertake the study of size-change analysis in the context of Reverse Mathematics. In particular, we prove that the SCT criterion is equivalent to $Σ^0_2$-induction over RCA$_0$.
0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv
Reverse Mathematics and initial intervals
In this paper we study the reverse mathematics of two theorems by Bonnet about partial orders. These results concern the structure and cardinality of the collection of the initial intervals. The first theorem states that a partial order has no infinite antichains if and only if its initial intervals are finite unions of ideals. The second one asserts that a countable partial order is scattered and does not contain infinite antichains if and only if it has countably many initial intervals. We show that the left to right directions of these theorems are equivalent to ACA_0 and ATR_0, respectively. On the other hand, the opposite directions are both provable in WKL_0, but not in RCA_0. We also prove the equivalence with ACA_0 of the following result of Erdös and Tarski: a partial order with no infinite strong antichains has no arbitrarily large finite strong antichains.
0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv
Linear extensions of partial orders and Reverse Mathematics
We introduce the notion of τ-like partial order, where τis one of the linear order types ω, ω*, ω+ω*, and ζ. For example, being ω-like means that every element has finitely many predecessors, while being ζ-like means that every interval is finite. We consider statements of the form "any τ-like partial order has a τ-like linear extension" and "any τ-like partial order is embeddable into τ" (when τ is ζ this result appears to be new). Working in the framework of reverse mathematics, we show that these statements are equivalent either to BΣ^0_2 or to ACA_0 over the usual base system RCA_0.
0 citations0 reviewsNo code linkedOpen access