Borel Determinacy
In descriptive set theory, the Borel determinacy theorem states that any Gale–Stewart game whose payoff set is a Borel set is determined, meaning that one of the two players will have a winning strategy for the game. A Gale-Stewart game is a possibly infinite two-player game, where both players have perfect information and no randomness is involved. The theorem is a far reaching generalization of Zermelo's Theorem about the determinacy of finite games. It was proved by Donald A. Martin in 1975, and is applied in descriptive set theory to show that Borel sets in Polish spaces have regularity properties such as the perfect set property and the property of Baire. The theorem is also known for its metamathematical properties. In 1971, before the theorem was proved, Harvey Friedman showed that any proof of the theorem in Zermelo–Fraenkel set theory must make repeated use of the axiom of replacement. Later results showed that stronger determinacy theorems cannot be proven in Zermel ... [...More Info...]       [...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]   |
|
Descriptive Set Theory
In mathematical logic, descriptive set theory (DST) is the study of certain classes of "well-behaved" subsets of the real line and other Polish spaces. As well as being one of the primary areas of research in set theory, it has applications to other areas of mathematics such as functional analysis, ergodic theory, the study of operator algebras and group actions, and mathematical logic. Polish spaces Descriptive set theory begins with the study of Polish spaces and their Borel sets. A Polish space is a second-countable topological space that is metrizable with a complete metric. Heuristically, it is a complete separable metric space whose metric has been "forgotten". Examples include the real line \mathbb, the Baire space \mathcal, the Cantor space \mathcal, and the Hilbert cube I^. Universality properties The class of Polish spaces has several universality properties, which show that there is no loss of generality in considering Polish spaces of certain restricted form ... [...More Info...]       [...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]   |
|
Game Tree
In the context of Combinatorial game theory, which typically studies sequential games with perfect information, a game tree is a graph representing all possible game states within such a game. Such games include well-known ones such as chess, checkers, Go, and tic-tac-toe. This can be used to measure the complexity of a game, as it represents all the possible ways a game can pan out. Due to the large game trees of complex games such as chess, algorithms that are designed to play this class of games will use partial game trees, which makes computation feasible on modern computers. Various methods exist to solve game trees. If a complete game tree can be generated, a deterministic algorithm, such as backward induction or retrograde analysis can be used. Randomized algorithms and minimax algorithms such as MCTS can be used in cases where a complete game tree is not feasible. Understanding the game tree To better understand the game tree, it can be thought of as a technique for an ... [...More Info...]       [...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]   |
|
Borel Hierarchy
In mathematical logic, the Borel hierarchy is a stratification of the Borel algebra generated by the open subsets of a Polish space; elements of this algebra are called Borel sets. Each Borel set is assigned a unique countable ordinal number called the rank of the Borel set. The Borel hierarchy is of particular interest in descriptive set theory. One common use of the Borel hierarchy is to prove facts about the Borel sets using transfinite induction on rank. Properties of sets of small finite ranks are important in measure theory and analysis. Borel sets The Borel algebra in an arbitrary topological space is the smallest collection of subsets of the space that contains the open sets and is closed under countable unions and complementation. It can be shown that the Borel algebra is closed under countable intersections as well. A short proof that the Borel algebra is well defined proceeds by showing that the entire powerset of the space is closed under complements and count ... [...More Info...]       [...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]   |
|
Closed Set
In geometry, topology, and related branches of mathematics, a closed set is a set whose complement is an open set. In a topological space, a closed set can be defined as a set which contains all its limit points. In a complete metric space, a closed set is a set which is closed under the limit operation. This should not be confused with a closed manifold. Equivalent definitions By definition, a subset A of a topological space (X, \tau) is called if its complement X \setminus A is an open subset of (X, \tau); that is, if X \setminus A \in \tau. A set is closed in X if and only if it is equal to its closure in X. Equivalently, a set is closed if and only if it contains all of its limit points. Yet another equivalent definition is that a set is closed if and only if it contains all of its boundary points. Every subset A \subseteq X is always contained in its (topological) closure in X, which is denoted by \operatorname_X A; that is, if A \subseteq X then A \subseteq \oper ... [...More Info...]       [...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]   |
|
Open Set
In mathematics, open sets are a generalization of open intervals in the real line. In a metric space (a set along with a distance defined between any two points), open sets are the sets that, with every point , contain all points that are sufficiently near to (that is, all points whose distance to is less than some value depending on ). More generally, one defines open sets as the members of a given collection of subsets of a given set, a collection that has the property of containing every union of its members, every finite intersection of its members, the empty set, and the whole set itself. A set in which such a collection is given is called a topological space, and the collection is called a topology. These conditions are very loose, and allow enormous flexibility in the choice of open sets. For example, ''every'' subset can be open (the discrete topology), or no set can be open except the space itself and the empty set (the indiscrete topology). In practice, however, ... [...More Info...]       [...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]   |
|
Basis (topology)
In mathematics, a base (or basis) for the topology of a topological space is a family \mathcal of open subsets of such that every open set of the topology is equal to the union of some sub-family of \mathcal. For example, the set of all open intervals in the real number line \R is a basis for the Euclidean topology on \R because every open interval is an open set, and also every open subset of \R can be written as a union of some family of open intervals. Bases are ubiquitous throughout topology. The sets in a base for a topology, which are called , are often easier to describe and use than arbitrary open sets. Many important topological definitions such as continuity and convergence can be checked using only basic open sets instead of arbitrary open sets. Some topologies have a base of open sets with specific useful properties that may make checking such topological definitions easier. Not all families of subsets of a set X form a base for a topology on X. Under some cond ... [...More Info...]       [...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]   |
|
Tree (descriptive Set Theory)
In descriptive set theory, a tree on a set X is a collection of finite sequences of elements of X such that every prefix of a sequence in the collection also belongs to the collection. Definitions Trees The collection of all finite sequences of elements of a set X is denoted X^. With this notation, a tree is a nonempty subset T of X^, such that if \langle x_0,x_1,\ldots,x_\rangle is a sequence of length n in T, and if 0\le m and called the ''body'' of the tree T. A tree that has no branches is called ''wellfounded''; a tree with at least one branch is ''illfounded''. By Kőnig's lemma, a tree on a finite set with an infinite number of sequences must necessarily be illfounded. Terminal nodes A finite sequence that belongs to a tree T is called a terminal node if it is not a prefix of a longer sequence in T. Equivalently, \langle x_0,x_1,\ldots,x_\rangle \in T is terminal if there is no element x of X such that that \langle x_0,x_1,\ldots,x_,x\rangle \in T. A tree that does not h ... [...More Info...]       [...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]   |
|
Baire Space
In mathematics, a topological space X is said to be a Baire space if countable unions of closed sets with empty interior also have empty interior. According to the Baire category theorem, compact Hausdorff spaces and complete metric spaces are examples of Baire spaces. The Baire category theorem combined with the properties of Baire spaces has numerous applications in topology, geometry, analysis, in particular functional analysis. Bourbaki introduced the term "Baire space" in honor of René Baire, who investigated the Baire category theorem in the context of Euclidean space \R^n in his 1899 thesis. Definition The definition that follows is based on the notions of meagre (or first category) set (namely, a set that is a countable union of sets whose closure has empty interior) and nonmeagre (or second category) set (namely, a set that is not meagre). See the corresponding article for details. A topological space X is called a Baire space if it satisfies any of the follo ... [...More Info...]       [...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]   |
|
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. Examples The Cantor set itself is a Cantor space. But the canonical example of a Cantor space is the countably infinite topological product of the discrete 2-point space . This is usually written as 2^\mathbb or 2ω (where 2 denotes the 2-element set with the discrete topology). A point in 2ω is an infinite binary sequence, that is a sequence which assumes only the values 0 or 1. Given such a sequence ''a''0, ''a''1, ''a''2,..., one can map it to the real number :\sum_^\infty \frac. This mapping gives a homeomorphism from 2ω onto the Cantor set, demonstrating that 2ω is indeed a Cantor space. Cantor spaces occur abundantly in real analysis. For example, they exist as subspaces in every perfect, complete metric ... [...More Info...]       [...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]   |
|
Topological Product
In topology and related areas of mathematics, a product space is the Cartesian product of a family of topological spaces equipped with a natural topology called the product topology. This topology differs from another, perhaps more natural-seeming, topology called the box topology, which can also be given to a product space and which agrees with the product topology when the product is over only finitely many spaces. However, the product topology is "correct" in that it makes the product space a categorical product of its factors, whereas the box topology is too fine; in that sense the product topology is the natural topology on the Cartesian product. Definition Throughout, I will be some non-empty index set and for every index i \in I, let X_i be a topological space. Denote the Cartesian product of the sets X_i by X := \prod X_ := \prod_ X_i and for every index i \in I, denote the i-th by \begin p_i :\;&& \prod_ X_j &&\;\to\; & X_i \\ .3ex && \left( ... [...More Info...]       [...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]   |
|
Countably Infinite
In mathematics, a set is countable if either it is finite or it can be made in one to one correspondence with the set of natural numbers. Equivalently, a set is ''countable'' if there exists an injective function from it into the natural numbers; this means that each element in the set may be associated to a unique natural number, or that the elements of the set can be counted one at a time, although the counting may never finish due to an infinite number of elements. In more technical terms, assuming the axiom of countable choice, a set is ''countable'' if its cardinality (its number of elements) is not greater than that of the natural numbers. A countable set that is not finite is said countably infinite. The concept is attributed to Georg Cantor, who proved the existence of uncountable sets, that is, sets that are not countable; for example the set of the real numbers. A note on terminology Although the terms "countable" and "countably infinite" as defined here are quite com ... [...More Info...]       [...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]   |