اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدColoring the rationals in reverse mathematics
85
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Ramseys 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 Ramseys 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 Ramseys 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.
قيم البحث
اقرأ أيضاً
Using the tools of reverse mathematics in second-order arithmetic, as developed by Friedman, Simpson, and others, we determine the axioms necessary to develop various topics in commutative ring theory. Our main contributions to the field are as follo
ws. We look at fundamental results concerning primary ideals and the radical of an ideal, concepts previously unstudied in reverse mathematics. Then we turn to a fine-grained analysis of four different definitions of Noetherian in the weak base system $mathsf{RCA}_0 + mathsf{I}Sigma_2$. Finally, we begin a systematic study of various types of integral domains: PIDs, UFDs and Bezout and GCD domains.
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 infini
te 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 Erdos and Tarski: a partial order with no infinite strong antichains has no arbitrarily large finite strong antichains.
We investigate the strength of a randomness notion $mathcal R$ as a set-existence principle in second-order arithmetic: for each $Z$ there is an $X$ that is $mathcal R$-random relative to $Z$. We show that the equivalence between $2$-randomness and b
eing infinitely often $C$-incompressible is provable in $mathsf{RCA}_0$. We verify that $mathsf{RCA}_0$ proves the basic implications among randomness notions: $2$-random $Rightarrow$ weakly $2$-random $Rightarrow$ Martin-L{o}f random $Rightarrow$ computably random $Rightarrow$ Schnorr random. Also, over $mathsf{RCA}_0$ the existence of computable randoms is equivalent to the existence of Schnorr randoms. We show that the existence of balanced randoms is equivalent to the existence of Martin-L{o}f randoms, and we describe a sense in which this result is nearly optimal.
Let $S$ be the group of finitely supported permutations of a countably infinite set. Let $K[S]$ be the group algebra of $S$ over a field $K$ of characteristic $0$. According to a theorem of Formanek and Lawrence, $K[S]$ satisfies the ascending chain
condition for two-sided ideals. We study the reverse mathematics of this theorem, proving its equivalence over RCA$_0$ (or even over RCA$_0^*$) to the statement that $omega^omega$ is well ordered. Our equivalence proof proceeds via the statement that the Young diagrams form a well partial ordering.
The Jordan decomposition theorem states that every function $f colon [0,1] to mathbb{R}$ of bounded variation can be written as the difference of two non-decreasing functions. Combining this fact with a result of Lebesgue, every function of bounded v
ariation is differentiable almost everywhere in the sense of Lebesgue measure. We analyze the strength of these theorems in the setting of reverse mathematics. Over $mathsf{RCA}_0$, a stronger version of Jordans result where all functions are continuous is equivalent to $mathsf{ACA}_0$, while the version stated is equivalent to $mathsf{WKL}_0$. The result that every function on $[0,1]$ of bounded variation is almost everywhere differentiable is equivalent to $mathsf{WWKL}_0$. To state this equivalence in a meaningful way, we develop a theory of Martin-Lof randomness over $mathsf{RCA}_0$.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
