|
Martin Measure
In descriptive set theory, the Martin measure is a filter on the set of Turing degrees of sets of natural numbers, named after Donald A. Martin. Under the axiom of determinacy it can be shown to be an ultrafilter. Definition Let D be the set of Turing degrees of sets of natural numbers. Given some equivalence class in D, we may define the ''cone'' (or ''upward cone'') of /math> as the set of all Turing degrees /math> such that X\le_T Y; that is, the set of Turing degrees that are "at least as complex" as X under Turing reduction. In order-theoretic terms, the cone of /math> is the upper set of /math>. Assuming the axiom of determinacy, the cone lemma states that if ''A'' is a set of Turing degrees, either ''A'' includes a cone or the complement of ''A'' contains a cone.D. Martin, H. G. Dales, ''Truth in Mathematics'', ch. "Mathematical Evidence", p.223. Oxford Science Publications, 1998. It is similar to Wadge's lemma for Wadge degrees, and is important for the foll ... [...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] |
Filter (mathematics)
In mathematics, a filter or order filter is a special subset of a partially ordered set (poset). Filters appear in order and lattice theory, but can also be found in topology, from which they originate. The dual notion of a filter is an order ideal. Filters on sets were introduced by Henri Cartan in 1937 and as described in the article dedicated to filters in topology, they were subsequently used by Nicolas Bourbaki in their book ''Topologie Générale'' as an alternative to the related notion of a net developed in 1922 by E. H. Moore and Herman L. Smith. Order filters are generalizations of this notion from sets to the more general setting of partially ordered sets. For information on order filters in the special case where the poset consists of the power set ordered by set inclusion, see the article Filter (set theory). Motivation 1. Intuitively, a filter in a partially ordered set (), P, is a subset of P that includes as members those elements that are large enoug ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Turing Degree
In computer science and mathematical logic the Turing degree (named after Alan Turing) or degree of unsolvability of a set of natural numbers measures the level of algorithmic unsolvability of the set. Overview The concept of Turing degree is fundamental in computability theory, where sets of natural numbers are often regarded as decision problems. The Turing degree of a set is a measure of how difficult it is to solve the decision problem associated with the set, that is, to determine whether an arbitrary number is in the given set. Two sets are Turing equivalent if they have the same level of unsolvability; each Turing degree is a collection of Turing equivalent sets, so that two sets are in different Turing degrees exactly when they are not Turing equivalent. Furthermore, the Turing degrees are partially ordered, so that if the Turing degree of a set ''X'' is less than the Turing degree of a set ''Y'', then any (noncomputable) procedure that correctly decides whether numbers a ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Natural Number
In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called ''Cardinal number, cardinal numbers'', and numbers used for ordering are called ''Ordinal number, ordinal numbers''. Natural numbers are sometimes used as labels, known as ''nominal numbers'', having none of the properties of numbers in a mathematical sense (e.g. sports Number (sports), jersey numbers). Some definitions, including the standard ISO/IEC 80000, ISO 80000-2, begin the natural numbers with , corresponding to the non-negative integers , whereas others start with , corresponding to the positive integers Texts that exclude zero from the natural numbers sometimes refer to the natural numbers together with zero as the whole numbers, while in other writings, that term is used instead for the integers (including negative integers). The natural ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Donald A
Donald is a masculine given name derived from the Gaelic name ''Dòmhnall''.. This comes from the Proto-Celtic *''Dumno-ualos'' ("world-ruler" or "world-wielder"). The final -''d'' in ''Donald'' is partly derived from a misinterpretation of the Gaelic pronunciation by English speakers, and partly associated with the spelling of similar-sounding Germanic names, such as ''Ronald''. A short form of ''Donald'' is ''Don''. Pet forms of ''Donald'' include ''Donnie'' and ''Donny''. The feminine given name ''Donella'' is derived from ''Donald''. ''Donald'' has cognates in other Celtic languages: Modern Irish ''Dónal'' (anglicised as ''Donal'' and ''Donall'');. Scottish Gaelic ''Dòmhnall'', ''Domhnull'' and ''Dòmhnull''; Welsh '' Dyfnwal'' and Cumbric ''Dumnagual''. Although the feminine given name ''Donna'' is sometimes used as a feminine form of ''Donald'', the names are not etymologically related. Variations Kings and noblemen Domnall or Domhnall is the name of many ancie ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Axiom Of Determinacy
In mathematics, the axiom of determinacy (abbreviated as AD) is a possible axiom for set theory introduced by Jan Mycielski and Hugo Steinhaus in 1962. It refers to certain two-person topological games of length ω. AD states that every game of a certain type is determined; that is, one of the two players has a winning strategy. Steinhaus and Mycielski's motivation for AD was its interesting consequences, and suggested that AD could be true in the smallest natural model L(R) of a set theory, which accepts only a weak form of the axiom of choice (AC) but contains all real and all ordinal numbers. Some consequences of AD followed from theorems proved earlier by Stefan Banach and Stanisław Mazur, and Morton Davis. Mycielski and Stanisław Świerczkowski contributed another one: AD implies that all sets of real numbers are Lebesgue measurable. Later Donald A. Martin and others proved more important consequences, especially in descriptive set theory. In 1988, John R. Steel an ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Ultrafilter
In the mathematical field of order theory, an ultrafilter on a given partially ordered set (or "poset") P is a certain subset of P, namely a maximal filter on P; that is, a proper filter on P that cannot be enlarged to a bigger proper filter on P. If X is an arbitrary set, its power set \wp(X), ordered by set inclusion, is always a Boolean algebra and hence a poset, and ultrafilters on \wp(X) are usually called X.If X happens to be partially ordered, too, particular care is needed to understand from the context whether an (ultra)filter on \wp(X) or an (ultra)filter just on X is meant; both kinds of (ultra)filters are quite different. Some authors use "(ultra)filter" ''of'' a partial ordered set" vs. "''on'' an arbitrary set"; i.e. they write "(ultra)filter on X" to abbreviate "(ultra)filter of \wp(X)". An ultrafilter on a set X may be considered as a finitely additive measure on X. In this view, every subset of X is either considered "almost everything" (has measure 1) or "almos ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Turing Reduction
In computability theory, a Turing reduction from a decision problem A to a decision problem B is an oracle machine which decides problem A given an oracle for B (Rogers 1967, Soare 1987). It can be understood as an algorithm that could be used to solve A if it had available to it a subroutine for solving ''B''. The concept can be analogously applied to function problems. If a Turing reduction from A to B exists, then every algorithm for B can be used to produce an algorithm for A, by inserting the algorithm for B at each place where the oracle machine computing A queries the oracle for B. However, because the oracle machine may query the oracle a large number of times, the resulting algorithm may require more time asymptotically than either the algorithm for B or the oracle machine computing A. A Turing reduction in which the oracle machine runs in polynomial time is known as a Cook reduction. The first formal definition of relative computability, then called relative reducibility, ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Upper Set
In mathematics, an upper set (also called an upward closed set, an upset, or an isotone set in ''X'') of a partially ordered set (X, \leq) is a subset S \subseteq X with the following property: if ''s'' is in ''S'' and if ''x'' in ''X'' is larger than ''s'' (that is, if s \leq x), then ''x'' is in ''S''. In words, this means that any ''x'' element of ''X'' that is \,\geq\, to some element of ''S'' is necessarily also an element of ''S''. The term lower set (also called a downward closed set, down set, decreasing set, initial segment, or semi-ideal) is defined similarly as being a subset ''S'' of ''X'' with the property that any element ''x'' of ''X'' that is \,\leq\, to some element of ''S'' is necessarily also an element of ''S''. Definition Let (X, \leq) be a preordered set. An in X (also called an , an , or an set) is a subset U \subseteq X that is "closed under going up", in the sense that :for all u \in U and all x \in X, if u \leq x then x \in U. The dual notion is a ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Wadge Hierarchy
In descriptive set theory, within mathematics, Wadge degrees are levels of complexity for sets of reals. Sets are compared by continuous reductions. The Wadge hierarchy is the structure of Wadge degrees. These concepts are named after William W. Wadge. Wadge degrees Suppose A and B are subsets of Baire space ωω. Then A is Wadge reducible to B or A ≤W B if there is a continuous function f on ωω with A = f^ /math>. The Wadge order is the preorder or quasiorder on the subsets of Baire space. Equivalence classes of sets under this preorder are called Wadge degrees, the degree of a set A is denoted by A.html" ;"title="math>A">math>Asub>W. The set of Wadge degrees ordered by the Wadge order is called the Wadge hierarchy. Properties of Wadge degrees include their consistency with measures of complexity stated in terms of definability. For example, if A ≤W B and B is a countable intersection of open sets, then so is A. The same works for all levels of the Borel hierarchy and th ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Ultrafilter (set Theory)
In the mathematical field of set theory, an ultrafilter is a ''maximal proper filter'': it is a filter U on a given non-empty set X which is a certain type of non-empty family of subsets of X, that is not equal to the power set \wp(X) of X (such filters are called ) and that is also "maximal" in that there does not exist any other proper filter on X that contains it as a proper subset. Said differently, a proper filter U is called an ultrafilter if there exists proper filter that contains it as a subset, that proper filter (necessarily) being U itself. More formally, an ultrafilter U on X is a proper filter that is also a maximal filter on X with respect to set inclusion, meaning that there does not exist any proper filter on X that contains U as a proper subset. Ultrafilters on sets are an important special instance of ultrafilters on partially ordered sets, where the partially ordered set consists of the power set \wp(X) and the partial order is subset inclusion \,\subsete ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Measurable Cardinal
In mathematics, a measurable cardinal is a certain kind of large cardinal number. In order to define the concept, one introduces a two-valued measure on a cardinal , or more generally on any set. For a cardinal , it can be described as a subdivision of all of its subsets into large and small sets such that itself is large, and all singletons are small, complements of small sets are large and vice versa. The intersection of fewer than large sets is again large. It turns out that uncountable cardinals endowed with a two-valued measure are large cardinals whose existence cannot be proved from ZFC. The concept of a measurable cardinal was introduced by Stanislaw Ulam in 1930. Definition Formally, a measurable cardinal is an uncountable cardinal number κ such that there exists a κ-additive, non-trivial, 0-1-valued measure on the power set of ''κ''. (Here the term ''κ-additive'' means that, for any sequence ''A''''α'', α<λ of cardinality '' ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
