2025/12/01 by Huishan Wu
paper · doi:10.4467/20842589rm.25.001.22717
published in Reports on Mathematical Logic 2025(60), 47 (Uniwersytet Jagiellonski - Wydawnictwo Uniwersytetu Jagiellonskiego)
crossref issued 2025/12/01 · crossref published 2025/12/01 · crossref published-online 2025/12/01 · crossref created 2025/12/02 · crossref deposited 2025/12/02 · crossref indexed 2026/07/30
Positive region plays a fundamental role in rough set-based attribute reduction. We study positive regions of decision systems and of binary relations in rough set theory within the framework of reverse mathematics and computability theory. First, we propose the notion of infinite decision systems and prove that the existence of positive regions of decision systems is equivalent to arithmetic comprehension over the weak base theory RCA0. We also show that the complexity of positive regions of computable decision systems lies exactly in π02 of the arithmetic hierarchy. Next, we study positive regions of equivalence relations and binary relations. We show that the existence of each of the two positive regions is equivalent to arithmetic comprehension over RCA0; however, the exact complexity of positive regions of computable equivalence relations lies in π01 and the exact complexity of positive regions of computable binary relations lies in ∑02 of the arithmetic hierarchy.