Martin measure

From Wikipedia, the free encyclopedia

In descriptive set theory, the Martin measure is a filter on the set of Turing degrees of sets of natural numbers. Under the axiom of determinacy it can be shown to be an ultrafilter.

[edit] Definition

Let $D$ be the set of Turing degrees of sets of natural numbers. Given some equivalence class $[X]\in D$ , we may define the cone (or upward cone) of $[X]$ as the set of all Turing degrees $[Y]$ such that $X\le_T Y$ ; that is, the set of Turing degrees which are "more complex" than $X$ under Turing reduction.

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.

[edit] 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 $ω 1$ by a simple mapping, tells us that $ω 1$ is measurable under the axiom of determinacy. This result shows part of the important connection between determinacy and large cardinals.