Is there a set $\mathcal X\subset\{0,1\}^{\Bbb N}$ of 0/1-sequences, so that


* For any two 0/1-sequences $x,y\in\{0,1\}^{\Bbb N}$ for which there is an $N\in\Bbb N$ with
$$x\_i=y\_i,\;\;\text{for all $i< N$},\qquad x\_i\not=y\_i,\;\;\text{for all $i\ge N$},$$
*exactly one* of these belongs to $\mathcal X$.
* $\mathcal X$ can be proven to exist without using the Axiom of Choice.



Existence of a certain set of 0/1-sequences without 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 X\cap 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.


