Mfcttrf

Is there a set $mathcal Xsubset0,1^Bbb N$ of 0/1-sequences, so that

• For any two 0/1-sequences $x,yin0,1^Bbb N$ for which there is an $NinBbb N$ with
  $$x_i=y_i,;;textfor all $i< N$,qquad x_inot=y_i,;;textfor all $ige N$,$$
  exactly one of these belongs to $mathcal X$.




• $mathcal X$ can be proven to exist without using the Axiom of Choice.

A set $mathcal X$ with the first of the two properties you want cannot have the Baire property (in the space $0,1^omega$ with the product topology).

Proof: Suppose it had the Baire property, so it differs from an open set $U$ by a meager set.

Suppose for a moment that $U$ is nonempty, and consider a basic open subset of $U$, say the set $B$ of all $0/1$-sequences extending a certain finite $0/1$-sequence $s$. Then, $mathcal Xcap B$ is a comeager subset of $B$. But then so is its image under the self-homeomorphism of $B$ that switches all $0$'s and $1$'s beyond the end of $s$. Your assumption says that this switching maps $mathcal X$ to its complement, so we have two disjoint comeager subsets of the complete metric space $B$, which is absurd. So $U$ can't be nonempty.

But if $U$ is empty, then $mathcal X$ is meager and therefore so is its image under the self-homeomorphism of $0,1^omega$ that switches $0$ with $1$ in all components. Then, by your assumption, $0,1^omega$ is covered by two meager sets, again an absurdity. This completes the proof that $mathcal X$ cannot have the Baire property.

It is consistent, relative to ZF, that all subsets of $0,1^omega$ have the Baire property (and that dependent choice holds, so that the Baire category theorem still works). So it is consistent with ZF that no $mathcal X$ as in your question exists.