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 enumerate that base (that is, is the i^th basic open set). Now:

• Every natural number i is an ∞-Borel code. Its interpretation is .
• If c is an ∞-Borel code with interpretation A_c, then the ordered pair < 0,c > is also an ∞-Borel code, and its interpretation is the complement of A_c, that is, .
• If is a length-α sequence of ∞-Borel codes for some ordinal α (that is, if for every β<α, c_β is an ∞-Borel code, say with interpretation ), then the ordered pair is an ∞-Borel code, and its interpretation is .

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 -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 -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. B₀ 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,

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.