Martin measure

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 <math>D</math> be the set of Turing degrees of sets of natural numbers. Given some equivalence class <math>[X]\in D</math>, we may define the cone (or upward cone) of <math>[X]</math> as the set of all Turing degrees <math>[Y]</math> such that <math>X\le_T Y</math>; that is, the set of Turing degrees that are "at least as complex" as <math>X</math> under Turing reduction. In order-theoretic terms, the cone of <math>[X]</math> is the upper set of <math>[X]</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. It is similar to Wadge's lemma for Wadge degrees, and is important for the following result.

We say that a set <math>A</math> of Turing degrees has measure 1 under the Martin measure exactly when <math>A</math> contains some cone. Since it is possible, for any <math>A</math>, to construct a game in which player I has a winning strategy exactly when <math>A</math> contains a cone and in which player II has a winning strategy exactly when the complement of <math>A</math> 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 <math>\omega_1</math> by a simple mapping, tells us that <math>\omega_1</math> is measurable under the axiom of determinacy. This result shows part of the important connection between determinacy and large cardinals.

References *