ファイル置き場 Sendai Logic Homepage ihara

Main Results

Effectiveness for Planar Dendrites and Dendroids

Takayuki Kihara

Mathematical Institute, Tohoku University

October 29, 2010

Logic seminar in Tohoku University

Introduction Main Results

Backgrounds Preliminaries

Introduction

Every nonempty_Σ

∼ 0

1^{set inR}

n contains a computable point.

Main Results Preliminaries

Introduction

Every nonempty_Σ

∼ 0

1^{set inR}

n contains a computable point. Not every nonempty_Π⁰

1^{set inR}

ncontains a computable point.

Introduction Main Results

Backgrounds Preliminaries

Introduction

Every nonempty_Σ

∼ 0

1^{set inR}

n contains a computable point. Not every nonempty_Π⁰

1^{set inR}

ncontains a computable point. If a nonempty_Π⁰

1^{subset F ⊆ R}

1 contains no computable points, then F must bedisconnected.

Main Results Preliminaries

Introduction

Every nonempty_Σ

∼ 0

1^{set inR}

n contains a computable point. Not every nonempty_Π⁰

1^{set inR}

ncontains a computable point. If a nonempty_Π⁰

1^{subset F ⊆ R}

1 contains no computable points, then F must bedisconnected.

Does there exist a nonempty (simply)connected_Π⁰

1^{set inR} n

without computable points?

Introduction Main Results

Backgrounds Preliminaries

Introduction

Every nonempty_Σ

∼ 0

1^{set inR}

n contains a computable point. Not every nonempty_Π⁰

1^{set inR}

ncontains a computable point. If a nonempty_Π⁰

1^{subset F ⊆ R}

1 contains no computable points, then F must bedisconnected.

Does there exist a nonempty (simply)connected_Π⁰

1^{set inR} n

without computable points? The main theme of this talk is

Computability Theory for Connected Spaces.

Main Results Preliminaries

Computability Theory

Definition

S: a topological T₀space with a countable base{β_e}.

1 _{x ∈ S iscomputable}if the code of its principal filter, {e :x ∈ β_e}, isΣ⁰

1^.

Introduction Main Results

Backgrounds Preliminaries

Computability Theory

Definition

S: a topological T₀space with a countable base{β_e}.

1 _{x ∈ S iscomputable}if the code of its principal filter, {e :x ∈ β_e}, isΣ⁰

1^.

2 A closed set F ⊆ S isΠ⁰

1 ^{if F =S \}

∪e∈W^βe ^{for aΣ0}₁^{set W .}

Main Results Preliminaries

Computability Theory

Definition

S: a topological T₀space with a countable base{β_e}.

1 _{x ∈ S iscomputable}if the code of its principal filter, {e :x ∈ β_e}, isΣ⁰

1^.

2 A closed set F ⊆ S isΠ⁰

1 ^{if F =S \}

∪e∈W^βe ^{for aΣ0}₁^{set W .}

3 A closed set F ⊆ S isc.e.if{e :F ∩ β_e ,∅}isΣ⁰

1^.

Introduction Main Results

Backgrounds Preliminaries

Computability Theory

Definition

S: a topological T₀space with a countable base{β_e}.

1 _{x ∈ S iscomputable}if the code of its principal filter, {e :x ∈ β_e}, isΣ⁰

1^.

2 A closed set F ⊆ S isΠ⁰

1 ^{if F =S \}

∪e∈W^βe ^{for aΣ0}₁^{set W .}

3 A closed set F ⊆ S isc.e.if{e :F ∩ β_e ,∅}isΣ⁰

1^.

4 A closed set F ⊆ S iscomputableif it is c.e. andΠ⁰

1^.

Main Results Preliminaries

Computability Theory

Definition

S: a topological T₀space with a countable base{β_e}.

1 _{x ∈ S iscomputable}if the code of its principal filter, {e :x ∈ β_e}, isΣ⁰

1^.

2 A closed set F ⊆ S isΠ⁰

1 ^{if F =S \}

∪e∈W^βe ^{for aΣ0}₁^{set W .}

3 A closed set F ⊆ S isc.e.if{e :F ∩ β_e ,∅}isΣ⁰

1^.

4 A closed set F ⊆ S iscomputableif it is c.e. andΠ⁰

1^.

Proposition

For a closed set F ⊆ Rⁿ let d_F(x) = inf_y∈Fd(x,y). F isΠ⁰

1 ^{⇐⇒ dF} is lower semi-computable. F is c.e. ⇐⇒ d_F is upper semi-computable.

Introduction Main Results

Backgrounds Preliminaries

Connected

1

^Sets

Observation

1 Every nonempty (simply) connected_Π⁰

1^{subset F ⊆ R} 1

contains a computable point.

Main Results Preliminaries

Connected

1

^Sets

Observation

1 Every nonempty (simply) connected_Π⁰

1^{subset F ⊆ R} 1

contains a computable point.

Observation (Le Roux-Ziegler)

1 There exists a nonempty compact connected_Π⁰

1 ^subset

F ⊆ R²without computable points.

2 There exists a nonempty compact simply connected_Π⁰

1

subset F ⊆ R³without computable points.

Introduction Main Results

Backgrounds Preliminaries

Connected

1

^Sets

Observation

1 Every nonempty (simply) connected_Π⁰

1^{subset F ⊆ R} 1

contains a computable point.

Observation (Le Roux-Ziegler)

1 There exists a nonempty compact connected_Π⁰

1 ^subset

F ⊆ R²without computable points.

2 There exists a nonempty compact simply connected_Π⁰

1

subset F ⊆ R³without computable points.

Question (Le Roux-Ziegler)

Does every nonempty compact simply connected_Π⁰

1^subset

F ⊆ R²contains a computable point?

Main Results Preliminaries

An Example of Simply-Connected Planar

1

^Sets

Example (Penrose)

The Mandelbrot set M is a compact simply-connected planar_Π⁰ set with a computable point. 1

Introduction Main Results

Backgrounds Preliminaries

An Example of Simply-Connected Planar

1

^Sets

Example (Penrose)

The Mandelbrot set M is a compact simply-connected planar_Π⁰ set with a computable point. 1

Penrose Conjecture (in “Emperor’s New Mind”) The Mandelbrot set M is not computable.

Main Results Preliminaries

An Example of Simply-Connected Planar

1

^Sets

Example (Penrose)

The Mandelbrot set M is a compact simply-connected planar_Π⁰ set with a computable point. 1

Penrose Conjecture (in “Emperor’s New Mind”) The Mandelbrot set M is not computable.

Theorem (Hertling)

The Penrose Conjecture=⇒ ¬MLC.

(Here, MLC: the Mandelbrot set is locally connected.)

Introduction Main Results

Backgrounds Preliminaries

Previous Works in Computability Theory for Continua

Definition

1 A Hausdorff distance between nonempty closed subsets A₀,A₁of a metric space(X,d)is defined by:

d_H(A₀,A₁) =max_i<2sup_x∈Aiinf_y∈B1−id(x,y).

2 _{A ∈ P}almost includesan element ofQif inf{d_H(B,A) :A ⊇B ∈ Q}= 0.

3 _{A ∈ Pis}almost computableif A almost includes a computableP. Theorem (Miller 2002; Iljazovi´c 2009)

1 Every EuclideanΠ⁰

1sphere (Jordan curve) is computable.

2 _EveryΠ⁰

1 chainable continuum (arc) is almost computable.

3 Not every computable arc almost includes an image of a computable simple curve.

Main Results Preliminaries

Observation

A closed set A is computable

=⇒A is almost computable

=⇒A has a dense subset consisting of computable points

=⇒A contains a computable point.

Thus, every arc contains many computable points. To give an answer to the Question of Le Roux-Ziegler, we need to study more general planar continua.

Introduction Main Results

Backgrounds Preliminaries

Continuum Theory

Definition

Let S be a topological space.

1 _{S isconnected}if it is not union of disjoint open sets.

2 _{S is}locally connectedif it has a base of connected sets.

3 A continuumis a connected compact metric space.

4 _{S is}uniquely arc-connectedif each two points in S is connected by a unique arc.

5 _{S is}hereditary uniquely arc-connectedif every subcontinuum of S is uniquely arc-connected.

6 _{A dendroid}is a hereditary uniquely arc-connected continuum.

7 _{A dendrite}is a locally connected dendroid.

8 _{A tree}is a dendrite with finitely many ramification points.

Main Results Preliminaries

✓ ✏

arc

tree

dendrite

dendroid

∞-connected 1-dimensional

simply connected

locally connected

✒ ✑

Introduction Main Results

Backgrounds Preliminaries

Example

We plot a tree T ⊆2^<Non the Euclidean plane^R2. Then the plotted pictureΨ(T) ⊆ R²is a dendrite.

✓ ✏

Protting 2^<Non^R2. Ψ(2^<N)

✒ ✑

Ψ(T)is a tree if T is finite.

HoweverΨ(T)is not a tree if T is infinite. Thus,Ψ(2^<N)is a dendrite which is not a tree.

Main Results Preliminaries

Π⁰₁

^Dendroids

Example

A Cantor fananda harmonic combare dendroids, but not dendrites.

✓ ✏

Cantor set

Cantor fan Harmonic comb

✒ ✑

Here a harmonic comb is defined by:

([0,1] × {0}⁾∪⁽({0} ∪ {1/n :n ∈ N}) × [0,1]⁾.

Introduction Main Results

Not EveryΠ⁰₁Dendrite is Almost Computable

Not Every Computable Dendroid Almost Includes aΠ⁰₁Dendrite

Effectiveness for Tree-Like Continua

Main Theorem

Introduction Main Results

Not EveryΠ₁Dendrite is Almost Computable

Not Every Computable Dendroid Almost Includes aΠ⁰₁Dendrite

Effectiveness for Tree-Like Continua

Main Theorem

1 _EveryΠ⁰

1 tree is almost computable.

Introduction Main Results

Not EveryΠ⁰₁Dendrite is Almost Computable

Not Every Computable Dendroid Almost Includes aΠ⁰₁Dendrite

Effectiveness for Tree-Like Continua

Main Theorem

1 _EveryΠ⁰

1 tree is almost computable.

2 Not every computable dendrite almost includes aΠ⁰

1 ^tree.

Introduction Main Results

Not EveryΠ₁Dendrite is Almost Computable

Not Every Computable Dendroid Almost Includes aΠ⁰₁Dendrite

Effectiveness for Tree-Like Continua

Main Theorem

1 _EveryΠ⁰

1 tree is almost computable.

2 Not every computable dendrite almost includes aΠ⁰

1 ^tree.

3 _{Not everyΠ}⁰

1dendrite is almost computable.

Introduction Main Results

Not EveryΠ⁰₁Dendrite is Almost Computable

Not Every Computable Dendroid Almost Includes aΠ⁰₁Dendrite

Effectiveness for Tree-Like Continua

Main Theorem

1 _EveryΠ⁰

1 tree is almost computable.

2 Not every computable dendrite almost includes aΠ⁰

1 ^tree.

3 _{Not everyΠ}⁰

1dendrite is almost computable.

4 Not every computable dendroid almost includes aΠ⁰

1^dendrite.

Introduction Main Results

Not EveryΠ₁Dendrite is Almost Computable

Not Every Computable Dendroid Almost Includes aΠ⁰₁Dendrite

Effectiveness for Tree-Like Continua

Main Theorem

1 _EveryΠ⁰

1 tree is almost computable.

2 Not every computable dendrite almost includes aΠ⁰

1 ^tree.

3 _{Not everyΠ}⁰

1dendrite is almost computable.

4 Not every computable dendroid almost includes aΠ⁰

1^dendrite.

5 _{Not everyΠ}⁰

1dendroid is almost computable.

Introduction Main Results

Not EveryΠ⁰₁Dendrite is Almost Computable

Not Every Computable Dendroid Almost Includes aΠ⁰₁Dendrite

Effectiveness for Tree-Like Continua

Main Theorem

1 _EveryΠ⁰

1 tree is almost computable.

2 Not every computable dendrite almost includes aΠ⁰

1 ^tree.

3 _{Not everyΠ}⁰

1dendrite is almost computable.

4 Not every computable dendroid almost includes aΠ⁰

1^dendrite.

5 _{Not everyΠ}⁰

1dendroid is almost computable.

6 _{Not everyΠ}⁰

1dendroid contains a computable point.

Introduction Main Results

Not EveryΠ₁Dendrite is Almost Computable

Not Every Computable Dendroid Almost Includes aΠ⁰₁Dendrite

Effectiveness for Tree-Like Continua

Main Theorem

1 _EveryΠ⁰

1 tree is almost computable.

2 Not every computable dendrite almost includes aΠ⁰

1 ^tree.

3 _{Not everyΠ}⁰

1dendrite is almost computable.

4 Not every computable dendroid almost includes aΠ⁰

1^dendrite.

5 _{Not everyΠ}⁰

1dendroid is almost computable.

6 _{Not everyΠ}⁰

1dendroid contains a computable point. This is the solution tothe question of Le Roux, and Ziegler.

Introduction Main Results

Not EveryΠ⁰₁Dendrite is Almost Computable

Not Every Computable Dendroid Almost Includes aΠ⁰₁Dendrite

Effectiveness for Tree-Like Continua

Main Theorem

1 _EveryΠ⁰

1 tree is almost computable.

2 Not every computable dendrite almost includes aΠ⁰

1 ^tree.

3 _{Not everyΠ}⁰

1dendrite is almost computable.

4 Not every computable dendroid almost includes aΠ⁰

1^dendrite.

5 _{Not everyΠ}⁰

1dendroid is almost computable.

6 _{Not everyΠ}⁰

1dendroid contains a computable point. This is the solution to the question of Le Roux, and Ziegler.

Introduction Main Results

Not EveryΠ₁Dendrite is Almost Computable

Not Every Computable Dendroid Almost Includes aΠ⁰₁Dendrite

Theorem Not everyΠ⁰

1dendrite is almost computable.

✓ ✏

Basic Dendrite Approximation of Basic Dendrite

0-rising 1-rising 1-rising

✒ ✑

Basic Dendritehas 2ⁿmanyn-risingsof height 2⁻ⁿ.

Introduction Main Results

Not EveryΠ⁰₁Dendrite is Almost Computable

Not Every Computable Dendroid Almost Includes aΠ⁰₁Dendrite

Fix a non-computableΣ⁰

1^{set A ⊆ N.}

The Basic construction around an n-risingis following:

✓ ✏

n ∈A

n ^<A n-rising

✒ ✑

n ∈A =⇒an n-rising will bea cut point.

n <A =⇒an n-rising will bea ramification point.

Introduction Main Results

Not EveryΠ₁Dendrite is Almost Computable

Not Every Computable Dendroid Almost Includes aΠ⁰₁Dendrite

To prove the theorem, we need to prepare some tools.

Introduction Main Results

Not EveryΠ⁰₁Dendrite is Almost Computable

Not Every Computable Dendroid Almost Includes aΠ⁰₁Dendrite

To prove the theorem, we need to prepare some tools.

Lemma

1 Every subdendrite ofΨ(2^<N)is homeomorphic toΨ(T) for a subtree T ⊆2^<N.

2 _{T ⊆2}^<N_isΠ⁰

1(c.e., computable, resp.) tree iffΨ(T) ⊆ R² isΠ⁰

1(c.e., computable, resp.) dendrite.

3 Every computable subdendrite D ⊆ Ψ(2^<N)

there exists a computable subtree T ⊆ 2^<Nsuch that D ⊆Ψ(T)holds, and D andΨ(T)has same paths.

Introduction Main Results

Not EveryΠ₁Dendrite is Almost Computable

Not Every Computable Dendroid Almost Includes aΠ⁰₁Dendrite

Definition (Cenzer, Kihara, Weber and Wu 2009) AΠ⁰

1 subset P of Cantor space istree-immuneif aΠ⁰

1^{tree TPhas}

no infinite computable subtree.

Here T_P = {σ ∈ 2^<N: (∃f ⊃ σ)f ∈ P}

Example

The set ofall consistent complete extensions of Peano Arithmetic is tree-immune.

Lemma

Let P be a tree-immuneΠ⁰

1 subset of Cantor space, and D ⊆Ψ(T_P)be any computable subdendrite. Then D contains no path.

Introduction Main Results

Not EveryΠ⁰₁Dendrite is Almost Computable

Not Every Computable Dendroid Almost Includes aΠ⁰₁Dendrite

Now we startTrue Construction.

✓ ✏

Approximating basic n-rising Basic n-rising Tree-immuneΠ⁰

1^set

✒ ✑

An n-rising has a copy ofa tree-immuneΠ⁰

1 ^{setof scale 2}

−n_.

Introduction Main Results

Not EveryΠ₁Dendrite is Almost Computable

Not Every Computable Dendroid Almost Includes aΠ⁰₁Dendrite

Fix a non-computableΣ⁰

1^{set A ⊆ N.}

The True Construction around an n-risingis following:

✓ ✏

Tree-immuneΠ⁰

1^set

n ∈ A

n < A

✒ ✑

n ∈A =⇒any top of an n-rising will bea cut point. n ^<A =⇒any top of an n-rising will be

inaccessibleby computable dendrites.

Introduction Main Results

Not EveryΠ⁰₁Dendrite is Almost Computable

Not Every Computable Dendroid Almost Includes aΠ⁰₁Dendrite

Fix a non-computableΣ⁰

1^{set A ⊆ N.}

The True Construction around an n-risingis following:

✓ ✏

Tree-immuneΠ⁰

1^set

n ∈ A

n < A

✒ ✑

n ∈A =⇒If a dendrite D passes this n-rising, then Dcontains a topof this n-rising.

n <A =⇒Any computable dendritecontains no topof n-rising.

Introduction Main Results

Not EveryΠ₁Dendrite is Almost Computable

Not Every Computable Dendroid Almost Includes aΠ⁰₁Dendrite

Theorem (Restated) Not everyΠ⁰

1dendrite is almost computable.

The construction of theΠ⁰

1dendrite H is completed.

Introduction Main Results

Not EveryΠ⁰₁Dendrite is Almost Computable

Not Every Computable Dendroid Almost Includes aΠ⁰₁Dendrite

Theorem (Restated) Not everyΠ⁰

1dendrite is almost computable.

The construction of theΠ⁰

1dendrite H is completed. Let D ⊆H be any computable dendrite.

Introduction Main Results

Not EveryΠ₁Dendrite is Almost Computable

Not Every Computable Dendroid Almost Includes aΠ⁰₁Dendrite

Theorem (Restated) Not everyΠ⁰

1dendrite is almost computable.

The construction of theΠ⁰

1dendrite H is completed. Let D ⊆H be any computable dendrite.

It suffices to show thatD cannot pass 2 distinct risings.

Introduction Main Results

Not EveryΠ⁰₁Dendrite is Almost Computable

Not Every Computable Dendroid Almost Includes aΠ⁰₁Dendrite

Theorem (Restated) Not everyΠ⁰

1dendrite is almost computable.

The construction of theΠ⁰

1dendrite H is completed. Let D ⊆H be any computable dendrite.

It suffices to show thatD cannot pass 2 distinct risings. If D passes m,n-risings, then D passes a k -rising for all k ≥min{m,n}.

Introduction Main Results

Not EveryΠ₁Dendrite is Almost Computable

Not Every Computable Dendroid Almost Includes aΠ⁰₁Dendrite

Theorem (Restated) Not everyΠ⁰

1dendrite is almost computable.

The construction of theΠ⁰

1dendrite H is completed. Let D ⊆H be any computable dendrite.

It suffices to show thatD cannot pass 2 distinct risings. If D passes m,n-risings, then D passes a k -rising for all k ≥min{m,n}.

Since D isΠ⁰

1, we can enumerate all k such that D contains no top of any k -rising.

Introduction Main Results

Not EveryΠ⁰₁Dendrite is Almost Computable

Not Every Computable Dendroid Almost Includes aΠ⁰₁Dendrite

Theorem (Restated) Not everyΠ⁰

1dendrite is almost computable.

The construction of theΠ⁰

1dendrite H is completed. Let D ⊆H be any computable dendrite.

It suffices to show thatD cannot pass 2 distinct risings. If D passes m,n-risings, then D passes a k -rising for all k ≥min{m,n}.

Since D isΠ⁰

1, we can enumerate all k such that D contains no top of any k -rising.

This enumeration yields the complement of aΣ⁰

1^{set A .}

Introduction Main Results

Not EveryΠ₁Dendrite is Almost Computable

Not Every Computable Dendroid Almost Includes aΠ⁰₁Dendrite

Theorem (Restated) Not everyΠ⁰

1dendrite is almost computable.

The construction of theΠ⁰

1dendrite H is completed. Let D ⊆H be any computable dendrite.

It suffices to show thatD cannot pass 2 distinct risings. If D passes m,n-risings, then D passes a k -rising for all k ≥min{m,n}.

Since D isΠ⁰

1, we can enumerate all k such that D contains no top of any k -rising.

This enumeration yields the complement of aΣ⁰

1^{set A .}

This contradicts non-computability of A .

Introduction Main Results

Not EveryΠ⁰₁Dendrite is Almost Computable

Not Every Computable Dendroid Almost Includes aΠ⁰₁Dendrite

Theorem

Not every computable dendroid almost includes aΠ⁰

1^dendrite.

Introduction Main Results

Not EveryΠ₁Dendrite is Almost Computable

Not Every Computable Dendroid Almost Includes aΠ⁰₁Dendrite

Theorem

Not every computable dendroid almost includes aΠ⁰

1^dendrite.

We will useharmonic combsin place of the Basic Dendrite.

Introduction Main Results

Not EveryΠ⁰₁Dendrite is Almost Computable

Not Every Computable Dendroid Almost Includes aΠ⁰₁Dendrite

Theorem

Not every computable dendroid almost includes aΠ⁰

1^dendrite.

We will useharmonic combsin place of the Basic Dendrite. Before starting the construction, we take account of the fact thattopologist’s sine curveis not path-connected.

Introduction Main Results

Not EveryΠ₁Dendrite is Almost Computable

Not Every Computable Dendroid Almost Includes aΠ⁰₁Dendrite

Theorem

Not every computable dendroid almost includes aΠ⁰

1^dendrite.

We will useharmonic combsin place of the Basic Dendrite. Before starting the construction, we take account of the fact thattopologist’s sine curveis not path-connected.

It means that we cannot cut-pointize infinite many risings, on one harmonic comb.

Introduction Main Results

Not EveryΠ⁰₁Dendrite is Almost Computable

Not Every Computable Dendroid Almost Includes aΠ⁰₁Dendrite

Theorem

Not every computable dendroid almost includes aΠ⁰

1^dendrite.

We will useharmonic combsin place of the Basic Dendrite. Before starting the construction, we take account of the fact thattopologist’s sine curveis not path-connected.

It means that we cannot cut-pointize infinite many risings, on one harmonic comb.

Our idea is using a computable approximation of a certain limit computable function.

Introduction Main Results

Not EveryΠ₁Dendrite is Almost Computable

Not Every Computable Dendroid Almost Includes aΠ⁰₁Dendrite

Theorem

Not every computable dendroid almost includes aΠ⁰

1^dendrite.

We will useharmonic combsin place of the Basic Dendrite. Before starting the construction, we take account of the fact thattopologist’s sine curveis not path-connected.

It means that we cannot cut-pointize infinite many risings, on one harmonic comb.

Our idea is using a computable approximation of a certain limit computable function.

One harmonic comb replaces one rising.

Introduction Main Results

Not EveryΠ⁰₁Dendrite is Almost Computable

Not Every Computable Dendroid Almost Includes aΠ⁰₁Dendrite

Theorem

Not every computable dendroid almost includes aΠ⁰

1^dendrite.

We will useharmonic combsin place of the Basic Dendrite. Before starting the construction, we take account of the fact thattopologist’s sine curveis not path-connected.

It means that we cannot cut-pointize infinite many risings, on one harmonic comb.

Our idea is using a computable approximation of a certain limit computable function.

One harmonic comb replaces one rising.

The Basic Dendroidwill be constructed by connecting infinitely many harmonic combs.

Introduction Main Results

Not EveryΠ₁Dendrite is Almost Computable

Not Every Computable Dendroid Almost Includes aΠ⁰₁Dendrite

✓ ✏

Basic Dendroid 0-harmonic comb

1-h.c. 1-h.c.

✒ ✑

Basic Dendroidhas 2ⁿ manyn-harmonic combsof height 2⁻ⁿ. Eachn-harmonic combhas infinitely manyrisings.

Introduction Main Results

Not EveryΠ⁰₁Dendrite is Almost Computable

Not Every Computable Dendroid Almost Includes aΠ⁰₁Dendrite

✓ ✏

n-harmonic comb (n,0)-rising

(n,1)-rising

(n,2)-rising

(n, ω)-rising

✒ ✑

Basic Dendroidhas 2ⁿ manyn-harmonic combsof height 2⁻ⁿ. Eachn-harmonic combhas(ω +1)-many risings;

They are(n, α)-risings forα < ω+1.

Introduction Main Results

Not EveryΠ₁Dendrite is Almost Computable

Not Every Computable Dendroid Almost Includes aΠ⁰₁Dendrite

To prove the theorem, we need the following lemma.

Introduction Main Results

Not EveryΠ⁰₁Dendrite is Almost Computable

Not Every Computable Dendroid Almost Includes aΠ⁰₁Dendrite

To prove the theorem, we need the following lemma.

Lemma

There exists a limit computable function p such that, for every uniformly c.e. sequence{U_n}of cofinite c.e. sets, it holds that p(n) ∈U_nfor almost all n.

Introduction Main Results

Not EveryΠ₁Dendrite is Almost Computable

Not Every Computable Dendroid Almost Includes aΠ⁰₁Dendrite

To prove the theorem, we need the following lemma.

Lemma

There exists a limit computable function p such that, for every uniformly c.e. sequence{U_n}of cofinite c.e. sets, it holds that p(n) ∈U_nfor almost all n.

Proof

{V_e}: an effective enumeration of uniformly c.e. decreasing sequence of c.e. sets.

σ(e,x) = {i ≤ e: x ∈(V_i)_e}: The e-state of x. p(e)chooses x to maximize the e-state.

Introduction Main Results

Not EveryΠ⁰₁Dendrite is Almost Computable

Not Every Computable Dendroid Almost Includes aΠ⁰₁Dendrite

p =lim_sp_s: a limit computable function in the previous lemma. The construction on an n-harmonic combis following:

✓ ✏

p_s(n) = m

p_s(n) , m (n,m)-rising

✒ ✑

(∃s)p_s(n) =m=⇒an(n,m)-rising will bea cut point.

(∀s)p_s(n) ,m=⇒an(n,m)-rising will bea ramification point.

Introduction Main Results

Not EveryΠ₁Dendrite is Almost Computable

Not Every Computable Dendroid Almost Includes aΠ⁰₁Dendrite

p =lim_sp_s: a limit computable function in the previous lemma. The construction on an n-harmonic combis following:

✓ ✏

p_s(n) = m

p_s(n) , m (n,m)-rising

✒ ✑

Since p(n) =lim_sp_s(n)changes his mind at most finitely often, hecut-pointizes only finitely many risingson an n-harmonic comb.

Introduction Main Results

Not EveryΠ⁰₁Dendrite is Almost Computable

Not Every Computable Dendroid Almost Includes aΠ⁰₁Dendrite

p =lim_sp_s: a limit computable function in the previous lemma. The construction on an n-harmonic combis following:

✓ ✏

p_s(n) = m

p_s(n) , m (n,m)-rising

✒ ✑

Thus each n-harmonic comb, actually, will be homeomorphic to a harmonic comb. The construction yieldscomputable dendroid K.

Introduction Main Results

Not EveryΠ₁Dendrite is Almost Computable

Not Every Computable Dendroid Almost Includes aΠ⁰₁Dendrite

Recall that a dendrite is a locally connected dendroid. On a harmonic comb, any top of almost all rising must be inaccessibleby a dendrite.

✓ ✏

⊇

Locally connected D n-harmonic comb

D contains tops of only three risings; (n,1)-rising;(n,4)-rising;(n, ω)-rising

✒ ✑

Introduction Main Results

Not EveryΠ⁰₁Dendrite is Almost Computable

Not Every Computable Dendroid Almost Includes aΠ⁰₁Dendrite

✓ ✏

p_s(n) = m

p_s(n) , m (n,m)-rising

✒ ✑

(∃s)p_s(n) =m=⇒any top of an(n,m)-rising will be a cut point.

Meanwhile, any top of almost all risings will beinaccessibleby a given dendrite.

Introduction Main Results

Not EveryΠ₁Dendrite is Almost Computable

Not Every Computable Dendroid Almost Includes aΠ⁰₁Dendrite

✓ ✏

p_s(n) = m

p_s(n) , m (n,m)-rising

✒ ✑

(∃s)p_s(n) =m=⇒If a dendrite D passes an(n,m)-rising, then Dcontains a topof an(n,m)-rising. Meanwhile, any dendritecontains no topof almost all risings.

Introduction Main Results

Not EveryΠ⁰₁Dendrite is Almost Computable

Not Every Computable Dendroid Almost Includes aΠ⁰₁Dendrite

✓ ✏

p_s(n) = m

p_s(n) , m (n,m)-rising

✒ ✑

U^D_n: the set of all(n,m)-risings whose top is not accessed by a dendrite D. Then U_n^D iscofinitefor all n.

If D passes n-harmonic comb thenp(n) <U_n^D.

Introduction Main Results

Not EveryΠ₁Dendrite is Almost Computable

Not Every Computable Dendroid Almost Includes aΠ⁰₁Dendrite

Theorem (Restated)

Not every computable dendroid almost includes aΠ⁰

1^dendrite.

K : the computable dendroid in the construction.

Introduction Main Results

Not EveryΠ⁰₁Dendrite is Almost Computable

Not Every Computable Dendroid Almost Includes aΠ⁰₁Dendrite

Theorem (Restated)

Not every computable dendroid almost includes aΠ⁰

1^dendrite.

K : the computable dendroid in the construction. D: aΠ⁰

1 subdendrite of K .

Introduction Main Results

Not EveryΠ₁Dendrite is Almost Computable

Not Every Computable Dendroid Almost Includes aΠ⁰₁Dendrite

Theorem (Restated)

Not every computable dendroid almost includes aΠ⁰

1^dendrite.

K : the computable dendroid in the construction. D: aΠ⁰

1 subdendrite of K .

U_n: the set of all(n,m)-risings whose top is not accessed by a dendrite D.

Introduction Main Results

Not EveryΠ⁰₁Dendrite is Almost Computable

Not Every Computable Dendroid Almost Includes aΠ⁰₁Dendrite

Theorem (Restated)

Not every computable dendroid almost includes aΠ⁰

1^dendrite.

K : the computable dendroid in the construction. D: aΠ⁰

1 subdendrite of K .

U_n: the set of all(n,m)-risings whose top is not accessed by a dendrite D.

U_n is cofinite by previous observation.

Introduction Main Results

Not EveryΠ₁Dendrite is Almost Computable

Not Every Computable Dendroid Almost Includes aΠ⁰₁Dendrite

Theorem (Restated)

Not every computable dendroid almost includes aΠ⁰

1^dendrite.

K : the computable dendroid in the construction. D: aΠ⁰

1 subdendrite of K .

U_n: the set of all(n,m)-risings whose top is not accessed by a dendrite D.

U_n is cofinite by previous observation. {U_n}is uniformly c.e., since D isΠ⁰

1^.

Introduction Main Results

Not EveryΠ⁰₁Dendrite is Almost Computable

Not Every Computable Dendroid Almost Includes aΠ⁰₁Dendrite

Theorem (Restated)

Not every computable dendroid almost includes aΠ⁰

1^dendrite.

K : the computable dendroid in the construction. D: aΠ⁰

1 subdendrite of K .

U_n: the set of all(n,m)-risings whose top is not accessed by a dendrite D.

U_n is cofinite by previous observation. {U_n}is uniformly c.e., since D isΠ⁰

1^.

It suffices to show thatD cannot pass 2 distinct combs.

Introduction Main Results

Not EveryΠ₁Dendrite is Almost Computable

Not Every Computable Dendroid Almost Includes aΠ⁰₁Dendrite

Theorem (Restated)

Not every computable dendroid almost includes aΠ⁰

1^dendrite.

K : the computable dendroid in the construction. D: aΠ⁰

1 subdendrite of K .

U_n: the set of all(n,m)-risings whose top is not accessed by a dendrite D.

U_n is cofinite by previous observation. {U_n}is uniformly c.e., since D isΠ⁰

1^.

It suffices to show thatD cannot pass 2 distinct combs.