Infinity-Borel set

From Wikipedia, the free encyclopedia

In set theory, a subset of a Polish space X is ∞-Borel if it can 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).

[edit] 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 <\mathcal{N}_i|i<\omega> enumerate that base (that is, \mathcal{N}_i is the ith 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 Ac, then the ordered pair < 0,c > is also an ∞-Borel code, and its interpretation is the complement of Ac, that is, X\setminus A_c.
  • If \vec c is a length-α sequence of ∞-Borel codes for some ordinal α (that is, if for every β<α, cβ is an ∞-Borel code, say with interpretation A_{c_{\beta}}), then the ordered pair <1,\vec c> is an ∞-Borel code, and its interpretation is \bigcup_{\beta<\alpha}A_{c_{\beta}}.

Now a set is ∞-Borel if it is the interpretation of some ∞-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.

[edit] Incorrect definition

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 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. B0 is the collection of all open subsets of 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 α<λ
It follows from the Burali-Forti paradox that there must be some ordinal α such that Bβ equals Bα for every β>α. For this value of α, Bα is the collection of ∞-Borel sets.

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.

[edit] 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 ∞-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,

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.