Finite-injury computable colouring of pairs
ID: finite-injury-computable-colouring-of-pairs
There is a two-colour computable colouring of pairs with no infinite computably enumerable set homogeneous for it. Enumerate these sets as . In stages, give each eligible requirement two markers from its enumerated set, avoiding markers of higher priority, and cancel all lower-priority markers whenever a new assignment is made. Colour by the marker status of at stage : first markers have colour zero, second markers colour one, and unmarked points colour zero. Each requirement is injured only finitely often by induction on its index. If is infinite it eventually has permanent distinct markers ; for every sufficiently large , the pairs and have different colours. Simulating finitely many stages computes each pair's colour, proving both effectiveness and the obstruction.
New to topics? Read the docs here!