Infinity-Borel set

In set theory, a subset of a Polish space $X$ is ∞-Borel if itcan be obtained by starting with the open subsets of $X$, and transfinitely iterating the operations of complementation and wellordered union (but see the caveat below).

Formal definition

More formally: we define by simultaneous transfinite recursion the notion of ∞-Borel code, and of the interpretation of such codes. Since $X$ is Polish, it has a countable base. Let enumerate that base (that is, $mathcal\{N\}\_i$ is the $i^mathrm\{th\}$ basic open set). Now:

* Every natural number $i$ is an ∞-Borel code. Its interpretation is $mathcal\{N\}\_i$.
* If $c$ is an ∞-Borel code with interpretation $A\_c$, then the ordered pair is also an ∞-Borel code, and its interpretation is the complement of $A\_c$, that is, $Xsetminus\; A\_c$.
* If $vec\; c$ is a length-α sequence of &infin;-Borel codes for some ordinal α (that is, if for every &beta;<α, is an &infin;-Borel code, say with interpretation ), then the ordered pair is an &infin;-Borel code, and its interpretation is .

Now a set is &infin;-Borel if it is the interpretation of some &infin;-Borel code.

The axiom of choice implies that "every" set can be wellordered, and therefore that every subset of every Polish space is $infty$-Borel. Therefore the notion is interesting only in contexts where AC does not hold (or is not known to hold).

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

Incorrect definition

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

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

:# B₀ is the collection of all open subsets of $X$.:# For a given even ordinal α, B_α+1 is the union of B_α with the set of all complements of sets in B_α.:# For a given even ordinal α, B_α+2 is the set of all wellordered unions of sets in B_α+1.:# For a given limit ordinal &lambda;, B_&lambda; is the union of all B_α for α<&lambda;

: It follows from the Burali-Forti paradox that there must be some ordinal α such that B_&beta; equals B_α for every &beta;>α. For this value of α, B_α is the collection of &infin;-Borel sets.

Unfortunately, without the axiom of choice, it is not clear that the &infin;-Borel sets "are" closed under wellordered union. This is because, given a wellordered union of &infin;-Borel sets, each of the individual sets may have "many" &infin;-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.

Alternative characterization

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 &infin;-Borel just in case there is a set of ordinals "S" and a first-order formula "&phi;" of the language of set theory such that, for every "x" in Baire space,

: $xin\; Aiff\; L\; [S,x]\; modelsphi(S,x)$

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