1,721,047 research outputs found
Borel quasi-orderings in subsystems of second-order arithmetic
No full textAbstractWe study the provability in subsystems of second-order arithmetic of two theorems of Harrington and Shelah [6] about Borel quasi-orderings of the reals. These theorems turn out to be provable in ATR0, thus giving further evidence to the observation that ATR0 is the minimal subsystem of second-order arithmetic in which significant portion of descriptive set theory can be developed. As in [6] considering the lightface versions of the theorems will be instrumental in their proof and the main techniques employed will be the reflection principles and Gandy forcing
Effective aspects of Hausdorff and Fourier dimension
Full text linkIn this paper, we study Hausdorff and Fourier dimension from the point of
view of effective descriptive set theory and Type-2 Theory of Effectivity.
Working in the hyperspace of compact subsets of , with
or , we characterize the complexity of the family
of sets having sufficiently large Hausdorff or Fourier dimension. This, in
turn, allows us to show that family of all the closed Salem sets is
-complete. One of our main tools is a careful analysis of the
effectiveness of a classical theorem of Kaufman. We furthermore compute the
Weihrauch degree of the functions computing Hausdorff and Fourier dimension of
closed sets.Comment: 36 page
Interval orders and reverse mathematics
No full textWe study the reverse mathematics of interval orders. We establish the logical strength of the implications between various definitions of the notion of interval order. We also consider the strength of different versions of the characterization theorem for interval orders: a partial order is an interval order if and only if it does not contain 2 \oplus 2. We also study proper interval orders and their characterization theorem: a partial order is a proper interval order if and only if it contains neither 2 \oplus 2 nor 3 \oplus 1
Reverse mathematics and initial intervals
No full textIn 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 ACA_0 and ATR_0, respectively. On the other hand, the opposite directions are both provable in WKL_0, but not in RCA_0. We also prove the equivalence with ACA0 of the following result of Erdös and Tarski: a partial order with no infinite strong antichains has no arbitrarily large finite strong antichains
- …
