8
$\begingroup$

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.

Improve this question
$\endgroup$
7
  • 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
    Commented Aug 17, 2019 at 19:03
  • $\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
    Commented Aug 17, 2019 at 19:07
  • $\begingroup$ Are you trying to say that this is a selector for "half" of the mod-finite relation? $\endgroup$
    – Asaf Karagila ♦
    Commented Aug 17, 2019 at 19:09
  • $\begingroup$ @AsafKaragila Sorry, I do not know "mod-finite relation". But what I do sounds like a selector, so ... $\endgroup$
    – M. Winter
    Commented Aug 17, 2019 at 19:10
  • $\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 ♦
    Commented Aug 17, 2019 at 19:11

1 Answer 1

Reset to default
14
$\begingroup$

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.

Improve this answer
$\endgroup$
8
  • $\begingroup$ While I agree that the statement of BCT makes more sense when assuming DC (which is equivalent to BCT, as we know), to make sense of BCT for separable spaces, such as the Cantor space, you don't need more than ZF. $\endgroup$
    – Asaf Karagila ♦
    Commented Aug 18, 2019 at 8:34
  • $\begingroup$ @AsafKaragila You're right that the separable case doesn't need any choice at all; I was just too lazy to check that and say it. $\endgroup$
    – Andreas Blass
    Commented Aug 18, 2019 at 11:44
  • $\begingroup$ But certainly the notion of having the Baire property doesn't make sense if every set is meager. So to that end, DC is certainly helpful. $\endgroup$
    – Asaf Karagila ♦
    Commented Aug 18, 2019 at 12:33
  • $\begingroup$ @AsafKaragila If one defines, as usual, "meager" to mean "covered by countably many closed sets with empty interior", then I think there's no danger of all sets (in Cantor space, say) being meager even without choice --- even when the reals are the union of countably many countable sets. The danger seems to be rather that the union of countably many meager sets need not be meager. $\endgroup$
    – Andreas Blass
    Commented Aug 18, 2019 at 19:56
  • 1
    $\begingroup$ @AsafKaragila Avoiding large cardinals was my reason for using the Baire property here. An $\mathcal X$ as in the question can't be Lebesgue measurable either, but then I'd need an inaccessible cardinal, which somebody might not trust. $\endgroup$
    – Andreas Blass
    Commented Aug 18, 2019 at 20:08

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .