Positive regions of computable binary relations

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.