prev

next

out of 109

View

1Download

0

Embed Size (px)

.

.

. ..

.

.

Counterexamples in Computable Continuum Theory

Takayuki Kihara

Mathematical Institute, Tohoku University

Dagstuhl Seminar, October 11, 2011

Takayuki Kihara Counterexamples in Computable Continuum Theory

.

.

Introduction

.

.

. ..

.

.

.

. .

1 Local Computability: Every nonempty open set in Rn has a computable point. Not every nonempty co-c.e. closed set in Rn has a computable point (Kleene, Kreisel, etc. 1940’s–50’s).

If a nonempty co-c.e. closed subset F ⊆ R1 has no computable points, then F must be disconnected. Does there exist a nonempty (simply) connected co-c.e. closed set in Rn without computable points?

.

.

.

2 Global Computability:

If a co-c.e. closed set is homeomorphic to an n-sphere, then it is computable (Miller 2002). If a co-c.e. closed set is homeomorphic to an arc, then it is “almost” computable, i.e., every co-c.e. arc is approximated from the inside by computable arcs.

.

.

.

3 Let us study the computable content of Continuum Theory! Here, “Continuum Theory” is a branch of topology studying connected

compact spaces.

Takayuki Kihara Counterexamples in Computable Continuum Theory

.

.

Introduction

.

.

. ..

.

.

.

. .

1 Local Computability: Every nonempty open set in Rn has a computable point. Not every nonempty co-c.e. closed set in Rn has a computable point (Kleene, Kreisel, etc. 1940’s–50’s). If a nonempty co-c.e. closed subset F ⊆ R1 has no computable points, then F must be disconnected. Does there exist a nonempty (simply) connected co-c.e. closed set in Rn without computable points?

.

.

.

2 Global Computability:

If a co-c.e. closed set is homeomorphic to an n-sphere, then it is computable (Miller 2002). If a co-c.e. closed set is homeomorphic to an arc, then it is “almost” computable, i.e., every co-c.e. arc is approximated from the inside by computable arcs.

.

.

.

3 Let us study the computable content of Continuum Theory! Here, “Continuum Theory” is a branch of topology studying connected

compact spaces.

Takayuki Kihara Counterexamples in Computable Continuum Theory

.

.

Introduction

.

.

. ..

.

.

.

. .

1 Local Computability: Every nonempty open set in Rn has a computable point. Not every nonempty co-c.e. closed set in Rn has a computable point (Kleene, Kreisel, etc. 1940’s–50’s). If a nonempty co-c.e. closed subset F ⊆ R1 has no computable points, then F must be disconnected. Does there exist a nonempty (simply) connected co-c.e. closed set in Rn without computable points?

.

.

.

2 Global Computability: If a co-c.e. closed set is homeomorphic to an n-sphere, then it is computable (Miller 2002). If a co-c.e. closed set is homeomorphic to an arc, then it is “almost” computable, i.e., every co-c.e. arc is approximated from the inside by computable arcs.

.

.

.

3 Let us study the computable content of Continuum Theory! Here, “Continuum Theory” is a branch of topology studying connected

compact spaces.

Takayuki Kihara Counterexamples in Computable Continuum Theory

.

.

Introduction

.

.

. ..

.

.

.

. .

1 Local Computability: Every nonempty open set in Rn has a computable point. Not every nonempty co-c.e. closed set in Rn has a computable point (Kleene, Kreisel, etc. 1940’s–50’s). If a nonempty co-c.e. closed subset F ⊆ R1 has no computable points, then F must be disconnected. Does there exist a nonempty (simply) connected co-c.e. closed set in Rn without computable points?

.

.

.

2 Global Computability: If a co-c.e. closed set is homeomorphic to an n-sphere, then it is computable (Miller 2002). If a co-c.e. closed set is homeomorphic to an arc, then it is “almost” computable, i.e., every co-c.e. arc is approximated from the inside by computable arcs.

.

.

.

compact spaces.

Takayuki Kihara Counterexamples in Computable Continuum Theory

.

.

Computability Theory

.

Definition

.

.

.

. ..

.

.

{Be}e∈N: an effective enumeration of all rational open balls.

.

. . 1 x ∈ Rn is computable if {e ∈ N : x ∈ Be} is c.e.

Equivalently, x = (x1, . . . , xn) ∈ Rn is computable iff x i is computable for each i ≤ n.

.

.

.

2 F ⊆ Rn is co-c.e. if F = Rn \∪e∈W Be for a c.e. set W .

.

.

.

3 A co-c.e. closed set F ⊆ Rn is computable if {e : F ∩ Be , ∅} is c.e.

.

Remark

.

.

.

. ..

.

.

F is co-c.e. closed ⇐⇒ F is a computable point in the hyperspaceA−(Rn) of closed subsets of Rn under lower Fell topology.

F is computable closed ⇐⇒ F is a computable point in the hyperspaceA(Rn) of closed subsets of Rn under Fell topology.

Takayuki Kihara Counterexamples in Computable Continuum Theory

.

.

Computability Theory

.

Definition

.

.

.

. ..

.

.

{Be}e∈N: an effective enumeration of all rational open balls.

.

. . 1 x ∈ Rn is computable if {e ∈ N : x ∈ Be} is c.e.

Equivalently, x = (x1, . . . , xn) ∈ Rn is computable iff x i is computable for each i ≤ n.

.

.

.

2 F ⊆ Rn is co-c.e. if F = Rn \∪e∈W Be for a c.e. set W .

.

.

.

3 A co-c.e. closed set F ⊆ Rn is computable if {e : F ∩ Be , ∅} is c.e.

.

Remark

.

.

.

. ..

.

.

F is co-c.e. closed ⇐⇒ F is a computable point in the hyperspaceA−(Rn) of closed subsets of Rn under lower Fell topology.

F is computable closed ⇐⇒ F is a computable point in the hyperspaceA(Rn) of closed subsets of Rn under Fell topology.

Takayuki Kihara Counterexamples in Computable Continuum Theory

.

.

Computability Theory

.

Definition

.

.

.

. ..

.

.

{Be}e∈N: an effective enumeration of all rational open balls.

.

. . 1 x ∈ Rn is computable if {e ∈ N : x ∈ Be} is c.e.

Equivalently, x = (x1, . . . , xn) ∈ Rn is computable iff x i is computable for each i ≤ n.

.

.

.

2 F ⊆ Rn is co-c.e. if F = Rn \∪e∈W Be for a c.e. set W .

.

.

.

3 A co-c.e. closed set F ⊆ Rn is computable if {e : F ∩ Be , ∅} is c.e.

.

Remark

.

.

.

. ..

.

.

F is co-c.e. closed ⇐⇒ F is a computable point in the hyperspaceA−(Rn) of closed subsets of Rn under lower Fell topology.

F is computable closed ⇐⇒ F is a computable point in the hyperspaceA(Rn) of closed subsets of Rn under Fell topology.

Takayuki Kihara Counterexamples in Computable Continuum Theory

.

.

Computability Theory

.

Definition

.

.

.

. ..

.

.

{Be}e∈N: an effective enumeration of all rational open balls.

.

. . 1 x ∈ Rn is computable if {e ∈ N : x ∈ Be} is c.e.

Equivalently, x = (x1, . . . , xn) ∈ Rn is computable iff x i is computable for each i ≤ n.

.

.

.

2 F ⊆ Rn is co-c.e. if F = Rn \∪e∈W Be for a c.e. set W .

.

.

.

3 A co-c.e. closed set F ⊆ Rn is computable if {e : F ∩ Be , ∅} is c.e.

.

Remark

.

.

.

. ..

.

.

Takayuki Kihara Counterexamples in Computable Continuum Theory

.

.

Connected co-c.e. closed Sets

.

Fact

.

.

.

. ..

.

.

.

. . 1 (Kleene, Kreisel, etc.) There exists a nonempty co-c.e. closedset P ⊆ R1 which has no computable point.

.

.

.

2 Every nonempty connected co-c.e. closed subset P ⊆ R1 contains a computable point.

.

Fact

.

.

.

. ..

.

.

.

.

.

1 There exists a nonempty connected co-c.e. closed subset P(2) ⊆ R2 which has no computable point.

.

.

.

2 There exists a nonempty simply connected co-c.e. closed subset P(3) ⊆ R3 which has no computable point.

Takayuki Kihara Counterexamples in Computable Continuum Theory

.

.

Connected co-c.e. closed Sets

.

Fact

.

.

.

. ..