0
$\begingroup$

As a step in proving that the union of intervals $B_E \subset [0,1]$ (where $E$ is the set of infinite Bernoulli sequences, e.g. 0.0110...., such that some finite pattern repeats infinitely often) is a Borel set, the authors in this book build the set as follows. First, they define $E_n$ as the set of sequences where the pattern occurs beginning at position $n$ and $B_{E_n}$ to be the corresponding union of intervals. Then they state without proof that \begin{align} B_E = \bigcap^\infty_{k=1} \; \bigcup_{n \geq k} \; B_{E_n} \end{align}

After thinking about this statement for a few days, I have now convinced myself that this does indeed represent the set of Bernoulli sequences (and the corresponding intervals) where a given finite pattern repeats infinitely often.

On the other hand, if someone asked me to prove that this infinite intersection of infinite unions does represent $B_E$, I'm not sure where I should start (I think I could do a hand waving argument, though). So my question is, how do you formally prove equivalence between the LHS and RHS?

  • 1
    See h$t$$t$p://ma$t$hoverflow.net/questions/12462/limsup-and-liminf-for-a-sequence-of-sets, for example.2011-02-23

1 Answers 1

3

If you can understand that "the pattern appears infinitely often in the sequence $x$" is the same as the formal mathematical sentence "$\forall k, \exists n \ge k$ such that the pattern appears at index $n$ in the sequence $x$", then the RHS is just a traduction in terms of sets of this sentence : $ x \in \bigcap^\infty_{k=1} \; \bigcup_{n \geq k} \; B_{E_n} \Leftrightarrow \forall k, \; x \in \bigcup_{n \geq k} \; B_{E_n} \Leftrightarrow \forall k \; \exists n \ge k, \; x \in B_{E_n}$

If you need to formally prove equivalence between the LHS and the RHS, you need a formal description of what the LHS is. In fact, if $B_E$ isn't formally defined before, this equality is its definition.

If you have a predicate $\phi$ that depends on an integer parameter $n$ (like $\phi(n)$ = $x_n$ is even, or $\phi(n)$ = the pattern appears at index $n$ in the sequence $x$), we mean that :

  • "$\phi$ is sometime true" means "$\exists n \phi(n)$"
  • "$\phi$ is always true" means "$\forall n \phi(n)$"
  • "$\phi$ is eventually true" means "$\exists k, \forall n \ge k, \phi(n)$"
  • "$\phi$ is true infinitely many times (or infinitely often)" means "$\forall k, \exists n \ge k, \phi(n)$"

In order to see why it is the right translation, it's best to understand that "$\phi$ is true infinitely often", is the same as "$\phi$ is not eventually false", since the translation of "eventually true" is easier to understand.

If $\phi$ is true infinitely often and eventually false, you have a contradiction. If it's not the case that $\phi$ is true infinitely often, then it is eventually false.

  • 0
    Thanks! The part about "true infinitely often" and "eventually true" really cleared things up.2011-02-23