Infinity-Borel set
Encyclopedia
In set theory
, a subset of a Polish space
is ∞-Borel if it
can be obtained by starting with the open subsets
of
, and transfinitely iterating the operations of complementation
and wellordered union
. Note that the set of ∞-Borel sets may not actually be closed under wellordered union; see below.
is Polish, it has a countable
base
. Let
enumerate that base (that is, 
is the 
basic open set). Now:
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). 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
.
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:
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, it is instead the closure of the ∞-Borel sets under all well-ordered unions, even those for which a choice of codes cannot be made.
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.
Set theory
Set theory is the branch of mathematics that studies sets, which are collections of objects. Although any type of object can be collected into a set, set theory is applied most often to objects that are relevant to mathematics...
, a subset of a Polish space
Polish space
In the mathematical discipline of general topology, a Polish space is a separable completely metrizable topological space; that is, a space homeomorphic to a complete metric space that has a countable dense subset. Polish spaces are so named because they were first extensively studied by Polish...
is ∞-Borel if itcan be obtained by starting with the open subsets
Open set
The concept of an open set is fundamental to many areas of mathematics, especially point-set topology and metric topology. Intuitively speaking, a set U is open if any point x in U can be "moved" a small amount in any direction and still be in the set U...
of
, and transfinitely iterating the operations of complementationComplement (set theory)
In set theory, a complement of a set A refers to things not in , A. The relative complement of A with respect to a set B, is the set of elements in B but not in A...
and wellordered union
Union (set theory)
In set theory, the union of a collection of sets is the set of all distinct elements in the collection. The union of a collection of sets S_1, S_2, S_3, \dots , S_n\,\! gives a set S_1 \cup S_2 \cup S_3 \cup \dots \cup S_n.- Definition :...
. Note that the set of ∞-Borel sets may not actually be closed under wellordered union; see below.
Formal definition
More formally: we define by simultaneous transfinite recursion the notion of ∞-Borel code, and of the interpretation of such codes. Since is Polish, it has a countableCountable set
In mathematics, a countable set is a set with the same cardinality as some subset of the set of natural numbers. A set that is not countable is called uncountable. The term was originated by Georg Cantor...
base
Base (topology)
In mathematics, a base B for a topological space X with topology T is a collection of open sets in T such that every open set in T can be written as a union of elements of B. We say that the base generates the topology T...
. Let
enumerate that base (that is, is the basic open set). Now:- Every natural numberNatural numberIn mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...
is an ∞-Borel code. Its interpretation is 
. - If
is an ∞-Borel code with interpretation 
, then the ordered pairOrdered pairIn mathematics, an ordered pair is a pair of mathematical objects. In the ordered pair , the object a is called the first entry, and the object b the second entry of the pair...
is also an ∞-Borel code, and its interpretation is the complement of 
, that is, 
. - If
is a length-α sequenceSequenceIn mathematics, a sequence is an ordered list of objects . Like a set, it contains members , and the number of terms is called the length of the sequence. Unlike a set, order matters, and exactly the same elements can appear multiple times at different positions in the sequence...
of ∞-Borel codes for some ordinalOrdinal numberIn set theory, an ordinal number, or just ordinal, is the order type of a well-ordered set. They are usually identified with hereditarily transitive sets. Ordinals are an extension of the natural numbers different from integers and from cardinals...
α (that is, if for every β<α,
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). 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+
AD plus
In set theory, AD+ is an extension, proposed by W. Hugh Woodin, to the axiom of determinacy. The axiom, which is to be understood in the context of ZF plus DCR , states two things:# Every set of reals is ∞-Borel....
, an extension of the axiom of determinacy
Axiom of determinacy
The axiom of determinacy is a possible axiom for set theory introduced by Jan Mycielski and Hugo Steinhaus in 1962. It refers to certain two-person games of length ω with perfect information...
studied by Woodin
W. Hugh Woodin
William Hugh Woodin is an American mathematician and set theorist at University of California, Berkeley. He has made many notable contributions to the theory of inner models and determinacy. A type of large cardinal, the Woodin cardinal, bears his name.-Biography:Born in Tucson, Arizona, Woodin...
.
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 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:
-
- B0 is the collection of all open subsetsOpen setThe concept of an open set is fundamental to many areas of mathematics, especially point-set topology and metric topology. Intuitively speaking, a set U is open if any point x in U can be "moved" a small amount in any direction and still be in the set U...
of
. - For a given even ordinal α, Bα+1 is the union of Bα with the set of all complementsComplement (set theory)In set theory, a complement of a set A refers to things not in , A. The relative complement of A with respect to a set B, is the set of elements in B but not in A...
of sets in Bα. - For a given even ordinal α, Bα+2 is the set of all wellordered unionsUnion (set theory)In set theory, the union of a collection of sets is the set of all distinct elements in the collection. The union of a collection of sets S_1, S_2, S_3, \dots , S_n\,\! gives a set S_1 \cup S_2 \cup S_3 \cup \dots \cup S_n.- Definition :...
of sets in Bα+1. - For a given limit ordinal λ, Bλ is the union of all Bα for α<λ
- B0 is the collection of all open subsets
- It follows from the Burali-Forti paradoxBurali-Forti paradoxIn set theory, a field of mathematics, the Burali-Forti paradox demonstrates that naively constructing "the set of all ordinal numbers" leads to a contradiction and therefore shows an antinomy in a system that allows its construction...
that there must be some ordinal α such that Bβ equals Bα for every β>α. For this value of α, Bα is 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, it is instead the closure of the ∞-Borel sets under all well-ordered unions, even those for which a choice of codes cannot be made.
Alternative characterization
For subsets of Baire spaceBaire space (set theory)
In set theory, the Baire space is the set of all infinite sequences of natural numbers with a certain topology. This space is commonly used in descriptive set theory, to the extent that its elements are often called “reals.” It is often denoted B, N'N, or ωω...
or Cantor space
Cantor space
In mathematics, a Cantor space, named for Georg Cantor, is a topological abstraction of the classical Cantor set: a topological space is a Cantor space if it is homeomorphic to the Cantor set. In set theory, the topological space 2ω is called "the" 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.