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 existence 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 rates 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 quasivariety $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.