Infinity-Borel set

We define the set of ∞-Borel codes ${\displaystyle C}$ and the interpretation function ${\displaystyle \left\|-\right\|:C\to {\mathcal {P}}(X)}$ below. A ∞-Borel set is a subset of ${\displaystyle X}$ which is in the image of the interpretation function ${\displaystyle \left\|-\right\|}$.

The set of ∞-Borel codes is an inductive type ${\displaystyle C}$ generated by functions ${\displaystyle {\mathtt {open}}:{\mathcal {O}}(X)\to C}$, ${\displaystyle {\mathtt {comp}}:C\to C}$ and ${\displaystyle {\mathtt {union}}_{\alpha }:C^{\alpha }\to C}$ for each ${\displaystyle \alpha <\Xi }$; the interpretation function is defined inductively as ${\displaystyle \left\|{\mathtt {open}}(U)\right\|=U}$, ${\displaystyle \left\|{\mathtt {comp}}(c)\right\|=X\setminus \left\|c\right\|}$ and ${\displaystyle \left\|{\mathtt {union}}_{\alpha }({\vec {c}})\right\|=\cup _{\beta <\alpha }\left\|c_{\beta }\right\|}$. Here ${\displaystyle \Xi }$ denotes the Hartogs number of ${\displaystyle {\mathcal {P}}(X)}$: a sufficiently large ordinal such that there is no injection from ${\displaystyle \Xi }$ to ${\displaystyle {\mathcal {P}}(X)}$. Restricting to unions of length below ${\displaystyle \Xi }$ doesn't affect the possible unions (as any union of length ${\displaystyle \geq \Xi }$ can be replaced by one of length ${\displaystyle <\Xi }$ by removing duplicates), but ensures that the ∞-Borel codes form a set, not a proper class.

This can be phrased more set-theoretically as a definition by transfinite recursion as follows:

• For every open subset ${\displaystyle U\subseteq X}$, the ordered pair ${\displaystyle \left\langle 0,U\right\rangle }$ is an ∞-Borel code; its interpretation is ${\displaystyle U}$.
• If ${\displaystyle c}$ is an ∞-Borel code, then the ordered pair ${\displaystyle \left\langle 1,c\right\rangle }$ is also an ∞-Borel code; its interpretation is the complement of ${\displaystyle \left\|c\right\|}$, that is, ${\displaystyle X\setminus \left\|c\right\|}$.
• If ${\displaystyle {\vec {c}}}$ is a length-α sequence of ∞-Borel codes for some ordinal α < Ξ (that is, if for every β<α, ${\displaystyle c_{\beta }}$ is an ∞-Borel code), then the ordered pair ${\displaystyle \left\langle 2,{\vec {c}}\right\rangle }$ is an ∞-Borel code; its interpretation is ${\displaystyle \bigcup _{\beta <\alpha }\left\|c_{\beta }\right\|}$.

The axiom of choice implies that every set can be wellordered, and therefore that every subset of every Polish space is ∞-Borel. Therefore, the notion is interesting only in contexts where AC does not hold (or is not known to hold). Unfortunately, without the axiom of choice, it is not clear that the ∞-Borel sets are closed under wellordered union. This is because, given a wellordered union of ∞-Borel sets, each of the individual sets may have many ∞-Borel codes, and there may be no way to choose one code for each of the sets, with which to form the code for the union.

The assumption that every set of reals is ∞-Borel is part of AD+, an extension of the axiom of determinacy studied by Woodin.

It is very tempting to read the informal description at the top of this article as claiming that the ∞-Borel sets are the smallest class of subsets of ${\displaystyle X}$ containing all the open sets and closed under complementation and wellordered union. That is, one might wish to dispense with the ∞-Borel codes altogether and try a definition like this:

For each ordinal α define by transfinite recursion B_α as follows:

1. B₀ is the collection of all open subsets of ${\displaystyle X}$.
2. For a given even ordinal α, B_α+1 is the union of B_α with the set of all complements of sets in B_α.
3. For a given even ordinal α, B_α+2 is the set of all wellordered unions of sets in B_α+1.
4. For a given limit ordinal λ, B_λ is the union of all B_α for α<λ

B_β equals B_Ξ for every β>Ξ; B_Ξ would then be the collection of "∞-Borel sets".

This set is manifestly closed under well-ordered unions, but without AC it cannot be proved equal to the ∞-Borel sets (as defined in the previous section). Specifically, this set may contain unions of sequences ${\displaystyle {\vec {b}}}$ of ∞-Borel sets for which it is not possible to choose a code for each ${\displaystyle b_{\beta }}$; it is the closure of the ∞-Borel sets under all well-ordered unions (and complements), even those for which a choice of codes cannot be made.

For subsets of Baire space or Cantor space, there is a more concise (if less transparent) alternative definition, which turns out to be equivalent. A subset A of Baire space is ∞-Borel just in case there is a set of ordinals S and a first-order formula φ of the language of set theory such that, for every x in Baire space,

${\displaystyle x\in A\iff L[S,x]\models \phi (S,x)}$

where L[S,x] is Gödel's constructible universe relativized to S and x. When using this definition, the ∞-Borel code is made up of the set S and the formula φ, taken together.

• Woodin, W. Hugh (1999). The Axiom of Determinacy, Forcing Axioms, and the Nonstationary Ideal. De Gruyter Series in Logic and Its Applications. Vol. 1. Berlin: Walter de Gruyter. p. 618. ISBN 3-11-015708-X. ISSN 1438-1893.