Existence of a certain set of 0/1-sequences without the Axiom of Choice idު ބiki254nIt0!d92aޭ ތޓްސނގަ ގެthucacd i
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.
-
1$\\begingroup$ This looks very much like existence of a nonprincipal ultrafilter on $\\mathbb{N}$, which cannot be proven in ZF. (But is far weaker than AC of course.) $\\endgroup$ – Todd Trimble♦ 9 hours ago
-
$\\begingroup$ @Todd Yeah, had the same feeling. Especially, as $\\mathcal X$ contains always either $x$ or its complement (the sequence with entries $1-x_i$). Is it easy to make this feeling more concrete? $\\endgroup$ – M. Winter 9 hours ago
-
$\\begingroup$ Are you trying to say that this is a selector for "half" of the mod-finite relation? $\\endgroup$ – Asaf Karagila 9 hours ago
-
$\\begingroup$ @AsafKaragila Sorry, I do not know "mod-finite relation". But what I do sounds like a selector, so ... $\\endgroup$ – M. Winter 9 hours ago
-
$\\begingroup$ Two sequences are equivalent if they are equal except for finitely many points? I hoped the name would be self explanatory... like "selector". $\\endgroup$ – Asaf Karagila 9 hours ago
1 Answer
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.
