کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4661821 1633466 2014 22 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Reverse mathematics and initial intervals
ترجمه فارسی عنوان
ریاضیات معکوس و فواصل اولیه
کلمات کلیدی
ریاضیات معکوس؛ نظم جزئی؛ فاصله اولیه؛ پراکنده؛ Antichain
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات منطق ریاضی
چکیده انگلیسی

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 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 ACA0ACA0 and ATR0ATR0, respectively. On the other hand, the opposite directions are both provable in WKL0WKL0, but not in RCA0RCA0. We also prove the equivalence with ACA0ACA0 of the following result of Erdös and Tarski: a partial order with no infinite strong antichains has no arbitrarily large finite strong antichains.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Annals of Pure and Applied Logic - Volume 165, Issue 3, March 2014, Pages 858–879
نویسندگان
, ,