The Axiom of Choice Is Wrong (2007)

Seeing only an infinite number of hats ahead, which match some pre-chosen sequence after an unspecified finite number of hats, how do they know if they are in position, 1, .... i-1, i, i+1, etc?

I mean, even if you know which equivalence class the sequence belongs to, you won't be able to guess at the color of your own hat without knowing your position.

Careful there: Gödels first incompleteness theorem proves that in a consistent effectively axiomatized formal system, there will be statements that are true or false that cannot be proven to be true or false.

So let's assume there were such a thing as objective mathematical reality and that it could be formalized as The System. As far as I'm aware, all the incompleteness theorem implies is that The System's set of theorems is not recursively enumerable (ie we will never be able to 'write them down').

All we can do is craft necessarily incomplete subsystems applicable to areas of our interest. It's a bit sad that humans will never know the Whole Truth, but such is life...

Assuming the original system was consistent (which you can never prove), yes.

But that doesn't help you, because the new system with these additional axioms will still, provably, contain statements that can't be proven true or false within that system (or else be inconsistent). (Turing did try some programme where you keep adding new axioms and take the transitive closure over all the axioms you'd add, but AIUI that doesn't work out either).

However, if said strategy's implementation requires actual infinities, eg each prisoner having an infinite memory, then that is why you find it intuitively objectionable.

It is useful here to think of computer algorithms and not just math. While mathematical arguments have no problem supposing infinite amounts of actors, the next question is whether each actor can have infinite memory.

In mathematics, infinity can be thought of as a property of a set. It can also be thought of as some limit of an infinite sequence of operations on sets, which is a statement that is simultaneously true about each member of that sequence.

This is useful because it can tie constructions we observe in the real world into patterns that approximate and converge to the limit of this infinite sequence. And then the question is how the computational complexity grows.

So in your example here, each FINITE set of prisoners can't coordinate a strategy. So there is no "approaching a limit" - the thing only starts working with an infinite set of prisoners, each of whom has infinite memory etc. And that is why you get your intuition alarm bells go off :)

But it is even more than that. Your construction requires each prisoner to use the axiom of choice in order to take an action based on the NAME of the chosen member which is used to demonstrate the existence of a sequence of actions that satisfies a certain property. However, when the axiom of choice is used normally, it is not used to actually NAME the chosen element, but merely work with it like a black box. By NAME, I mean an id that distinguishes it from all other elementa, and lets you pick it out and examine is properties THAT ARE DIFFERENT than all other elements in that set.

In other words, Sure, you can assume that the chosen "representative" sequence has the same property as any other in the equivalence class -- namely that all but finitely many terms are equal. BUT the part where you "cheat" is having the prisoner "find out" more than that about the representative sequence, in particular its initial values up to an arbitrary depth.