2 ms·

Not just infinite, but also uncountable. > The hard part Quite hard: Not computable, in fact.

• less_less 4y ago
  > Not just infinite, but also uncountable. If the players are countable and the colors are countable, then each equivalence class is also countable. I guess that might also make it computable, in some model that lets you deal with infinite objects? Eg suppose you have a 2-tape Turing machine where one read-write tape is input which records what you see. There is a separate tape for the Turing machine's internal state. The machine outputs an infinite stream of assignments by doing normal Turing machine things, plus a "yield" instruction that yields the current state of the input tape as an output. The equivalence classes ought to be computable in that model. Note that the equivalence class is a set, so the Turing machine's output should be interpreted that way, i.e. two equivalent inputs will give outputs in a different order. (They can't always give outputs in the same order, because F isn't computable.) But yeah, there are uncountably many equivalence classes, and F is not computable. If it were, then as I understand it, then you wouldn't need choice.