5. Borel ⟺ “Borel”

problem

Prove the fact, stated in class, that the family $𝑩(𝒞)$ of all Borel subsets of $𝒞$ (defined using countable Boolean circuits) is the smallest $σ$-algebra on $𝒞$ that includes every open set. ]

There are several things to show:

• $𝑩(𝒞)$ is a $σ$-algebra.
• $𝑩(𝒞)$ includes every open set.
• $𝑩(𝒞)$ is minimal: that is, for any collection of sets $𝑺$, if $𝑺$ is a $σ$-algebra that includes all open sets then $𝑩(𝒞)⊆𝑺$.

Here we go:

• To show this we need to check that $𝑩(𝒞)$ is closed under complement, countable union, and countable intersection. Yes:

  • Obtain the complement of any set by taking the corresponding circuit and attaching an additional NOT gate before the output.
  • Obtain countable unions of sets by taking each set’s circuit and combining their outputs with a disjunction/OR gate.
  • Obtain countable intersections of sets by taking each set’s circuit and combining their outputs with a conjunction/AND gate.

• Let $U∈𝒞$ be an open set.