On a Dichotomy related to Colourings of Definable Graphs in Generic Models
Vladimir Kanovei
Abstract:
We prove that in the Solovay model every OD graph G on reals satisfies
one and only one of the following two conditions: (I) G admits an OD
colouring by ordinals; (II) there exists a continuous homomorphism of G_0
into G; where G 0 is a certain F_sigma locally countable graph which is not
ROD colourable by ordinals in the Solovay model. If the graph G is locally
countable or acyclic then (II) can be strengthened by the requirement that
the homomorphism is a 1-1 map, i. e. an embedding.
As the second main result we prove that \Sigma^1_2 graphs admit the dichotomy
(I) vs. (II) in set-generic extensions of the constructible universe L (al
though now (I) and (II) may be in general compatible). In this case (I) can
be strengthened to the existence of a \Delta^1_3 colouring by countable
ordinals provided the graph is locally countable.
The proofs are based on a topology generated by OD sets.