ترغب بنشر مسار تعليمي؟ اضغط هنا

Very weak fragments of weak KH{o}nigs lemma

55   0   0.0 ( 0 )
 نشر من قبل Keita Yokoyama
 تاريخ النشر 2021
  مجال البحث
والبحث باللغة English




اسأل ChatGPT حول البحث

It is well-known that any finite $Pi^{0}_{1}$-class of $2^{mathbb N}$ has a computable member. Then, how can we understand this in the context of reverse mathematics? In this note, we consider several very weak fragments of KH{o}nigs lemma to answer this qeustion.



قيم البحث

اقرأ أيضاً

We present a relatively simple description of binary, definable subsets of models of weakly quasi-o-minimal theories. In particular, we closely describe definable linear orders and prove a weak version of the monotonicity theorem. We also prove that weak quasi-o-minimality of a theory with respect to one definable linear order implies weak quasi-o-minimality with respect to any other such order.
The classical theorem of Vizing states that every graph of maximum degree $d$ admits an edge-coloring with at most $d+1$ colors. Furthermore, as it was earlier shown by KH{o}nig, $d$ colors suffice if the graph is bipartite. We investigate the exis tence of measurable edge-colorings for graphings. A graphing is an analytic generalization of a bounded-degree graph that appears in various areas, such as sparse graph limits, orbit equivalence theory and measurable group theory. We show that every graphing of maximum degree $d$ admits a measurable edge-coloring with $d + O(sqrt{d})$ colors; furthermore, if the graphing has no odd cycles, then $d+1$ colors suffice. In fact, if a certain conjecture about finite graphs that strengthens Vizings theorem is true, then our method will show that $d+1$ colors are always enough.
We consider two combinatorial principles, ${sf{ERT}}$ and ${sf{ECT}}$. Both are easily proved in ${sf{RCA}}_0$ plus ${Sigma^0_2}$ induction. We give two proofs of ${sf{ERT}}$ in ${sf{RCA}}_0$, using different methods to eliminate the use of ${Sigma^0 _2}$ induction. Working in the weakened base system ${sf{RCA}}_0^*$, we prove that ${sf{ERT}}$ is equivalent to ${Sigma^0_1}$ induction and ${sf{ECT}}$ is equivalent to ${Sigma^0_2}$ induction. We conclude with a Weihrauch analysis of the principles, showing ${sf{ERT}} {equiv_{rm W}} {sf{LPO}}^* {<_{rm W}}{{sf{TC}}_{mathbb N}}^* {equiv_{rm W}} {sf{ECT}}$.
This paper is devoted to Fokker-Planck and linear kinetic equations with very weak confinement corresponding to a potential with an at most logarithmic growth and no integrable stationary state. Our goal is to understand how to measure the decay rate s when the diffusion wins over the confinement although the potential diverges at infinity.
For (finitary) deductive systems, we formulate a signature-independent abstraction of the emph{weak excluded middle law} (WEML), which strengthens the existing general notion of an inconsistency lemma (IL). Of special interest is the case where a qua sivariety $mathsf{K}$ algebraizes a deductive system $,vdash$. We prove that, in this case, if $,vdash$ has a WEML (in the general sense) then every relatively subdirectly irreducible member of $mathsf{K}$ has a greatest proper $mathsf{K}$-congruence; the converse holds if $,vdash$ has an inconsistency lemma. The result extends, in a suitable form, to all protoalgebraic logics. A super-intuitionistic logic possesses a WEML iff it extends $mathbf{KC}$. We characterize the IL and the WEML for normal modal logics and for relevance logics. A normal extension of $mathbf{S4}$ has a global consequence relation with a WEML iff it extends $mathbf{S4.2}$, while every axiomatic extension of $mathbf{R^t}$ with an IL has a WEML.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا