Borel ideals vs. Borel sets of countable relations and trees

AbstractFor every μ < ω1, let Iμ be the ideal of all sets S⊆ ωμ whose order type is <ωμ. If μ = 1, then I1 is simply the ideal of all finite subsets of ω, which is known to be Σ02-complete. We show that for every μ < ω1, Iμ is Σ02μ-complete. As corollaries to this theorem, we prove that the set WOωμ of well orderings R⊆ω × ω of order type <ωμ is Σ02μ-complete, the set LPμ of linear orderings R⊆ ω × ωthat have a μ-limit point is Σ02μ+1-complete. Similarly, we determine the exact complexity of the set LTμ of trees T⊆ <ωω of Luzin height <μ, the set WRμ of well-founded partial orderings of height <μ, the set LRμ of partial orderings of Luzin height <μ, the set WFμ of well-founded trees T⊆ <ωω of height