ファイル置き場 Sendai Logic Homepage speaker20

Relative Randomness for Martin-L¨ of random sets

NingNing Peng¹

Mathematical Institute, Tohoku University. [email protected]

February 23, 2012

Outline

1 Preliminaries

2 Γ randomness

3 Semi Γ-randomness

4 Future Study

NingNing Peng (Mathematical Institute, Tohoku University. [email protected])Relative Randomness for Martin-L¨of random sets February 23, 2012 2 / 31

Preliminaries

Notations

⊲ σ, τ,· · · denote the elements of 2^<N.

⊲ X , Y , Z · · · denote the elements of 2^N.

⊲ σ  τ (or σ  x) denotes that σ is a prefix of τ (or x).

⊲ [S]^≺= {x ∈ 2^N: ∃σ ∈ S (σ  x)} for a subset S of 2^<N.

⊲ [σ] = [{σ}]^≺ for a string σ ∈ 2^<N.

NingNing Peng (Mathematical Institute, Tohoku University. [email protected])Relative Randomness for Martin-L¨of random sets February 23, 2012 4 / 31

A c.e. open setis a set of finite stringU ⊂ 2^N such that:

⊲ U is computably enumerable.

⊲ if σ, τ ∈U then σ 6⊂ τ (the basic open sets [σ], [τ ] are disjoint).

ML-randomness

ML-randomness is a central notion of algorithmic randomness for subsets of N, which defined in the following way.

Definition (Martin-L¨of [1])

(i) AMartin-L¨of test, or ML-test for short, is a uniformly c.e. sequence (Gm)_m∈N of open sets such that ∀m ∈ N µ(Gm) ≤ 2^−m.

(ii) A set Z ⊆ Nfailsthe test if Z ∈^T_mGm, otherwise Z passes the test. (iii) Z isML-random if Z passes each ML-test.

NingNing Peng (Mathematical Institute, Tohoku University. [email protected])Relative Randomness for Martin-L¨of random sets February 23, 2012 6 / 31

weakly 2-random

Definition (Kurtz [?])

(i) Ageneralized ML-test is a uniformly c.e. sequence (G_m)_m∈N of open sets such that µ(^T_mGm) = 0.

(ii) Z isweakly 2-random if it passes every generalized ML-test.

weakly 2-random

Definition (Kurtz [?])

(i) Ageneralized ML-test is a uniformly c.e. sequence (G_m)_m∈N of open sets such that µ(^T_mGm) = 0.

(ii) Z isweakly 2-random if it passes every generalized ML-test.

Fact

(i) 2-randomness ⇒ weak 2-randomness ⇒ ML-randomness. (ii) The reverse implication fails (Kurtz, Kautz).

NingNing Peng (Mathematical Institute, Tohoku University. [email protected])Relative Randomness for Martin-L¨of random sets February 23, 2012 7 / 31

Γ randomness

Relative Randomness

These definitions are relativised: add oracle Ato tests to get A-randomness.

x is A-random if x 6∈^TU_i^A for universal oracle test Ui.

NingNing Peng (Mathematical Institute, Tohoku University. [email protected])Relative Randomness for Martin-L¨of random sets February 23, 2012 9 / 31

Relative Randomness

These definitions are relativised: add oracle Ato tests to get A-randomness.

x is A-random if x 6∈^TU_i^A for universal oracle test Ui. We study the colloection of these randomness notions.

Γ-randomness

We recall some notions in [3]. Definition

A set Z is Γ-randomif Z is ML-random relative to A for all A ∈ Γ. Any x-ML test for x ∈ Γ is called Γ-test.

NingNing Peng (Mathematical Institute, Tohoku University. [email protected])Relative Randomness for Martin-L¨of random sets February 23, 2012 10 / 31

Γ-randomness

We recall some notions in [3]. Definition

A set Z is Γ-randomif Z is ML-random relative to A for all A ∈ Γ. Any x-ML test for x ∈ Γ is called Γ-test.

Γ-randomness is called L-randomnessif Γ is the set of low sets. Obviously, any L-random set is ML-random. For any set Z , Z is not 1-random in Z . Thus, each low set is not L-random. Hence, L-randomness is strictly stronger than ML-randomness since there is a low ML-random set.

Usually, randomness notions stronger than ML-randomness are closed down- wards under Turing reducibility within the random sets. The notions we study here are not exception.

Proposition

Let X , Y be ML-random sets. If X ≤_T Y and Y is L-random, then X is L-random.

NingNing Peng (Mathematical Institute, Tohoku University. [email protected])Relative Randomness for Martin-L¨of random sets February 23, 2012 11 / 31

Usually, randomness notions stronger than ML-randomness are closed down- wards under Turing reducibility within the random sets. The notions we study here are not exception.

Proposition

Let X , Y be ML-random sets. If X ≤_T Y and Y is L-random, then X is L-random.

In fact, it turned out that L-randomness is equivalent to ∅^′-Schnorr randomness.

Theorem (Yu [4])

L-randomness is equivalent to ∅^′-Schnorr randomness.

Characterization of L-randomness

A ≤_LR B iff for any X , if X is B-random, then X is A-random. We would like to introduce another characterization of L-randomness. Then, the next lemma is useful.

Lemma

Let Γ, Γ^′ ⊂ N^N such that for any f ∈ Γ there is a function g ∈ Γ ∩ Γ^′ with f ≤LR g . Then, Γ randomness is equivalent to Γ ∩ Γ^′ randomness.

NingNing Peng (Mathematical Institute, Tohoku University. [email protected])Relative Randomness for Martin-L¨of random sets February 23, 2012 12 / 31

Characterization of L-randomness

A ≤_LR B iff for any X , if X is B-random, then X is A-random. We would like to introduce another characterization of L-randomness. Then, the next lemma is useful.

Lemma

Let Γ, Γ^′ ⊂ N^N such that for any f ∈ Γ there is a function g ∈ Γ ∩ Γ^′ with f ≤LR g . Then, Γ randomness is equivalent to Γ ∩ Γ^′ randomness.

Proof.

For any Γ-test {U_n^f}n∈N, there exists Γ ∩ Γ^′ test {Vn^g}n∈N ^{such that}

T U^f ⊆^T V^g, since f ≤ g . Then, Γ ∩ Γ^′ randomness implies Γ

1-generic

Definition

An r.e. set W ⊂ 2^<N is said to be dense alongx ∈ 2^N iff (∀n ∈ N)(∃σ ∈ W )[x ↾ n ⊂ σ]. x is said to be 1-genericiff for any r.e. set W ⊂ 2^<N

W is dense along x =⇒ (∃n ∈ N)[x ↾ n ∈ W ].

NingNing Peng (Mathematical Institute, Tohoku University. [email protected])Relative Randomness for Martin-L¨of random sets February 23, 2012 13 / 31

1-generic

Definition

An r.e. set W ⊂ 2^<N is said to be dense alongx ∈ 2^N iff (∀n ∈ N)(∃σ ∈ W )[x ↾ n ⊂ σ]. x is said to be 1-genericiff for any r.e. set W ⊂ 2^<N

W is dense along x =⇒ (∃n ∈ N)[x ↾ n ∈ W ].

Let G denote the set of 1-generic reals x such that x ≤_T ∅^′. Note that if x is 1-generic, then x is a generalized low set. Hence any G-test can be

By previous Lemma, L randomness can be also given by subsets of L as follows. PA denotes the set of reals of PA degrees.

Proposition

The following are equivalent: (i) X is L randomness, (ii) X is L ∩ G randomness, (iii) X is L ∩ PA randomness.

NingNing Peng (Mathematical Institute, Tohoku University. [email protected])Relative Randomness for Martin-L¨of random sets February 23, 2012 14 / 31

By previous Lemma, L randomness can be also given by subsets of L as follows. PA denotes the set of reals of PA degrees.

Proposition

The following are equivalent: (i) X is L randomness, (ii) X is L ∩ G randomness, (iii) X is L ∩ PA randomness.

Proof.

(ii) ⇒ (i) is proved from previous Lemma since there exsits a low g such that g is 1-generic relative to f and f ≤_T g , for any low f . (iii) ⇒ (i) is the same.

Let MLR denote the class of ML-random reals. Conjecture

L randomness is equivalent to L ∩ MLR randomness,

In other word, L randomness ⇔ {x | ∀ y : low & ML-random, x is y-random }

NingNing Peng (Mathematical Institute, Tohoku University. [email protected])Relative Randomness for Martin-L¨of random sets February 23, 2012 15 / 31

semi Γ-randomness

Motivation

The present paper is concerned with the algorithmic notion of

randomness such as originally introduced by P. Martin-L¨of [1] in 1966. One approach is to generalize the Martin-L¨of-test by giving the m-th component (a c.e. set of measure at most 2^−m) via a function in some function class Γ.

A main purpose of this paper is to give a general framework for such randomness notions.

To do this, we introduce the notion of semi Γ-randomness.

NingNing Peng (Mathematical Institute, Tohoku University. [email protected])Relative Randomness for Martin-L¨of random sets February 23, 2012 17 / 31

Semi Γ-random

In this section, we investigate a new randomness notion weaker than Γ-random. We concentrate on index function for the componets of a test. Definition

Let Γ ⊆ N^N:

1 We say that a sequence {Gn}n∈N of c.e open sets is a Γ-indexed test if and only if there exists f ∈ Γ such that G_n = W_f(n) for all n ∈ N and µ(Gn) ≤ 2⁻ⁿ.

2 A set Z ⊆ Nfails the test if Z ∈^T_nGn, otherwise Z passes the test.

3 _{A is}semi Γ-randomif it passes every Γ-indexed test.

Note that, there is no semi N^N-random set. It is straightforward from the

Theorem

A set is semi ∆⁰₂-random if and only if it is weakly 2-random.

Proposition

Every L-random real is semi L-random.

NingNing Peng (Mathematical Institute, Tohoku University. [email protected])Relative Randomness for Martin-L¨of random sets February 23, 2012 19 / 31

Theorem

A set is semi ∆⁰₂-random if and only if it is weakly 2-random.

Proposition

Every L-random real is semi L-random.

Theorem

For any Γ ⊂ N^N, there is no universal Γ indexed Martin-L¨of test unless any Martin-L¨of random set is semi Γ-random.

Separation between random notions

The following lemma is for separation between weak randomness and semi Γ-randomness.

Lemma

For any Γ, Γ^′ ⊂ N^Nsuch that Γ randomness is not equivalent to Martin-L¨of randomness and Γ^′ is countable, there exists a semi Γ^′ random real which is not Γ random.

NingNing Peng (Mathematical Institute, Tohoku University. [email protected])Relative Randomness for Martin-L¨of random sets February 23, 2012 20 / 31

Proof of Lemma

Choose a Martin-L¨of random f which is in ^T_{i ∈N}V_i, where {V_i}i ∈N ^{is a}

universal g -Martin-L¨of test for some g ∈ Γ.

Let {{U_gi(j)}j ∈N}i ∈N be a sequence of all Γ^′ indexed test.

Proof of Lemma

Choose a Martin-L¨of random f which is in ^T_{i ∈N}V_i, where {V_i}i ∈N ^{is a}

universal g -Martin-L¨of test for some g ∈ Γ.

Let {{U_gi(j)}j ∈N}i ∈N be a sequence of all Γ^′ indexed test.

We construct a function h and a ⊂-increasing sequence {σi}i ∈N such that [σi] ⊂ Vi and (limj →∞^σj) 6∈ U_gi(h(i)) for any i ∈ N.

Then a semi Γ^′-random ^Sσ_i is not Γ-random.

NingNing Peng (Mathematical Institute, Tohoku University. [email protected])Relative Randomness for Martin-L¨of random sets February 23, 2012 21 / 31

How to construct h and σ

^?

Stage s: Let σ =^S_{i <s}σ_i. As the inductive hypothesis, we suppose that µ([σ] \^S_{i <s}U_gi(h(i))) > 0.

How to construct h and σ

^?

Stage s: Let σ =^S_{i <s}σ_i. As the inductive hypothesis, we suppose that µ([σ] \^S_{i <s}U_gi(h(i))) > 0.

Defineh(s) by the least number x such that µ([σ] \ (^[

i <s

U_gi(h(i))∪ U_gs(x))) > 0.

Choose a tail f^′ of f such that

σf^′ ∈ [σ] \^[

i ≤s

U_gi(h(i))

Note that σf^′∈^T_{i ∈N}V_i. Thus, we can chooseσ_s ) σsuch that σ_s ⊂ σf^′ and [σs] ⊂ Vs.

NingNing Peng (Mathematical Institute, Tohoku University. [email protected])Relative Randomness for Martin-L¨of random sets February 23, 2012 22 / 31

Theorem

If n > 2, then weakly n randomness is strictly stronger than semi

∆⁰_n-randomness.

Theorem

If n > 2, then weakly n randomness is strictly stronger than semi

∆⁰_n-randomness.

Proof.

It is clear that weakly n randomness is stronger than semi ∆⁰_n randomness. This relation is strict since weakly n randomness is stronger that n − 1 randomness which contains some Martin-L¨of random set so that we can apply to the previous Lemma.

NingNing Peng (Mathematical Institute, Tohoku University. [email protected])Relative Randomness for Martin-L¨of random sets February 23, 2012 23 / 31

Finally, we consider the case around n = 2. Lemma

There exists a Π⁰₁(∅^′) null set P containing a semi L random element.

Proof sketch:

Let f be a strictly increasing ∅^′-computable function such that no low function dominates f and 2f (x) ≤ 2^f(x)−f (x−1)_.

Let F refer to the set

{σ ∈ N^<N| (∀i < lh(σ))[σ(i) < f (i)]}.

We define a ∅^′-computable function A : F → Pf(N) as follows: A(σ) = {i ≤ lh(σ) | µ([W^σ(i)^{]) ≤ 2−i −f(i)}.}

NingNing Peng (Mathematical Institute, Tohoku University. [email protected])Relative Randomness for Martin-L¨of random sets February 23, 2012 25 / 31

Let B(σ) be an element τ ∈ 2^f(lh(σ)) such that µ([τ ] \ ( ^[

i ∈A(σ)

[W_σ(i)])) ≥ 2^{−lh(στ )−1}

for all σ ∈ F . Define a Π⁰₁(∅^′) null set P by P = [B(F )].

Let {{W_hi(x)}x ∈N}i ∈N be a sequence of all L indexed test. (Indeed, we gives some technical assumption to hi’s.) Then we can construct a

⊂-increasing sequence {σi}i ∈N of elements of F and a function h : N → N such that lim_{i →∞}B(σ_i) 6∈ [W_hj(h(j))]. So^SB(σ_i) ∈ P is semi L random.

The following is straightfoward from Lemma 13. Theorem

Weakly 2 randomness is strictly stronger than semi L-randomness

NingNing Peng (Mathematical Institute, Tohoku University. [email protected])Relative Randomness for Martin-L¨of random sets February 23, 2012 27 / 31

The following is straightfoward from Lemma 13. Theorem

Weakly 2 randomness is strictly stronger than semi L-randomness

Proof.

This is because for any Π⁰₁(∅^′) null set P there exists a generalized Martin-L¨of test {Ui}i ∈N such that P =^T_{i ∈N}Ui.

Proposition

2-randomness does not imply semi ∆⁰₃-randomness.

NingNing Peng (Mathematical Institute, Tohoku University. [email protected])Relative Randomness for Martin-L¨of random sets February 23, 2012 28 / 31

Proposition

2-randomness does not imply semi ∆⁰₃-randomness.

Proof.

Since there is a ∆⁰₃ 2 random set, we show that there is no ∆⁰₃ semi

∆⁰₃-random set. Let A be a ∆⁰₃ set, then there is a ∆⁰₃ function f such that W_f(n)= {Akn}. Note that W_f(n) is a singleton set where only element is Akn and µ(W_f(n)) ≤ 2⁻ⁿ. So, {W_f(n)}n∈N is a semi ∆⁰₃-test. But A ∈^T_n∈NW_f(n). Hence, A is not semi ∆⁰₃-random.

Future Study

Conjecture

L randomness is equivalent to L ∩ MLR randomness, Conjecture

smei L-randomness and Demuth randomness are incompareble.

Question

Is the a characterization of ∅^′-computable randomness via ML randomness?

NingNing Peng (Mathematical Institute, Tohoku University. [email protected])Relative Randomness for Martin-L¨of random sets February 23, 2012 29 / 31

References

Per. Martin-L¨of: The definition of random sequences. Information and Control, vol. 9, no. 6, pp. 602-619 (1966)

Andr´e Nies: Computability and Randomness. Oxford University Press (2009)

NingNing Peng: The notions between Martin L¨of randomness and 2-randomness. RIMS Kˆokyˆuroku, No. 1792, pp. 117-122 (2010) Liang Yu: Characterizing strong randomness via Martin-L¨of

randomness. Annals of Pure and Applied Logic, vol. 163, no. 3, pp. 214-224 (2012)

Thank you very much!

NingNing Peng (Mathematical Institute, Tohoku University. [email protected])Relative Randomness for Martin-L¨of random sets February 23, 2012 31 / 31