In descriptive set theory, the Martin measure is a

filter Filter, filtering or filters may refer to: Science and technology Computing * Filter (higher-order function), in functional programming * Filter (software), a computer program to process a data stream * Filter (video), a software component tha ...

on the set of

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 fund ...

s of sets of

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 ...

s, named after

Donald A. Martin Donald Anthony Martin (born December 24, 1940), also known as Tony Martin, is an American set theorist and philosopher of mathematics at UCLA, where he is an emeritus professor of mathematics and philosophy. Education and career Martin rece ...

. Under the

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 ...

it can be shown to be an

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 o ...

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 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 s ...

. In order-theoretic terms, the cone of

/math> is the

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 ...

/math>.

Assuming the

, 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 following result. We say that a set

A

of Turing degrees has measure 1 under the Martin measure exactly when

A

contains some cone. Since it is possible, for any

A

, to construct a game in which player I has a winning strategy exactly when

A

contains a cone and in which player II has a winning strategy exactly when the complement of

A

contains a cone, the axiom of determinacy implies that the measure-1 sets of Turing degrees form an ultrafilter.

Consequences

It is easy to show that a countable intersection of cones is itself a cone; the Martin measure is therefore a countably complete filter. This fact, combined with the fact that the Martin measure may be transferred to

\omega_1

by a simple mapping, tells us that

\omega_1

measurable In mathematics, the concept of a measure is a generalization and formalization of geometrical measures (length, area, volume) and other common notions, such as mass and probability of events. These seemingly distinct concepts have many simila ...

under the axiom of determinacy. This result shows part of the important connection between determinacy and large cardinals.

References

* {{cite book , last=Moschovakis , first= Yiannis N. , authorlink = Yiannis N. Moschovakis , title=Descriptive Set Theory , publisher=American Mathematical Society , edition = 2nd , year = 2009 , isbn = 9780821848135 , volume = 155 , series = Mathematical surveys and monographs , page=338 , url = https://books.google.com/books?id=w0GZAwAAQBAJ&pg=PA338 Descriptive set theory Determinacy Computability theory