Linear extensions of partial orders and reverse mathematics
Linear extensions of partial orders and reverse mathematics
复制标题
偏序和逆向数学的线性扩展
DOI：
--
复制
发表时间：
2012
影响因子：
0.3
通讯作者：
Alberto Marcone
中科院分区：
文献类型：
--
作者：
Emanuele Frittaion;Alberto Marcone
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 documentclass{article}usepackage{amssymb}egin{document}pagestyle{empty}$mathsf {B}{Sigma }^{0}_{2}$end{document} or to documentclass{article}usepackage{amssymb}egin{document}pagestyle{empty}$mathsf {ACA}_0$end{document} over the usual base system documentclass{article}usepackage{amssymb}egin{document}pagestyle{empty}$mathsf {RCA}_0$end{document}.
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 documentclass{article}usepackage{amssymb}egin{document}pagestyle{empty}$mathsf {B}{Sigma }^{0}_{2}$end{document} or to documentclass{article}usepackage{amssymb}egin{document}pagestyle{empty}$mathsf {ACA}_0$end{document} over the usual base system documentclass{article}usepackage{amssymb}egin{document}pagestyle{empty}$mathsf {RCA}_0$end{document}.