The non-normal abyss in Kleene’s Computability
TheorySam Sanders (jww Dag Normann)
Department of Philosophy II, RUB Bochum, Germany

CiE2023, Batumi, Georgia, July 28, 2023

A logical abyss
In a nutshell, this talk reports on my joint project with Dag Normann (U.
of Oslo) on the computability theory of the uncountable.

A logical abyss
In a nutshell, this talk reports on my joint project with Dag Normann (U.
of Oslo) on the computability theory of the uncountable.

Kleene’s higher-order computability theory based on S1-S9 and its
recent lambda calculus formulation due to the authors.

A logical abyss
In a nutshell, this talk reports on my joint project with Dag Normann (U.
of Oslo) on the computability theory of the uncountable.

Kleene’s higher-order computability theory based on S1-S9 and its
recent lambda calculus formulation due to the authors.
The main message: there are computational operations that aremathematically extremely close but logically extremely different.

A logical abyss
In a nutshell, this talk reports on my joint project with Dag Normann (U.
of Oslo) on the computability theory of the uncountable.

Kleene’s higher-order computability theory based on S1-S9 and its
recent lambda calculus formulation due to the authors.
The main message: there are computational operations that aremathematically extremely close but logically extremely different.
How different? Computable in Kleene’s quantifier ∃2 (≈ Turingjump) versus computable in Kleene’s ∃3 (≈ SOA) but not in
weaker oracles.

A logical abyss
In a nutshell, this talk reports on my joint project with Dag Normann (U.
of Oslo) on the computability theory of the uncountable.

Kleene’s higher-order computability theory based on S1-S9 and its
recent lambda calculus formulation due to the authors.
The main message: there are computational operations that aremathematically extremely close but logically extremely different.
How different? Computable in Kleene’s quantifier ∃2 (≈ Turingjump) versus computable in Kleene’s ∃3 (≈ SOA) but not in
weaker oracles.
Why? The ‘∃2 -side’ deals (exactly) with function classes that havea built-in approximation-device for function values

Kleene computability theory

Turing

Exploring the abyss

Kleene computability theory

Exploring the abyss

TuringTuring’s ‘machine’ framework (1936): first intuitively convincing
notion of computing with real numbers (Entscheidungsproblem).

Kleene computability theory

Exploring the abyss

TuringTuring’s ‘machine’ framework (1936): first intuitively convincing
notion of computing with real numbers (Entscheidungsproblem).
Complexity theory studies computation with restricted resources.

Kleene computability theory

Exploring the abyss

TuringTuring’s ‘machine’ framework (1936): first intuitively convincing
notion of computing with real numbers (Entscheidungsproblem).
Complexity theory studies computation with restricted resources.
Turing machines may or may not produce an output after finitely
many steps: partiality and the Halting problem.

Kleene computability theory

Turing and Kleene

Exploring the abyss

Kleene computability theory

Exploring the abyss

Turing and Kleene

Kleene’s S1-S9 are computation schemes that formalise
X is computable in Y
for objects X , Y of finite type (essentially most of ordinary math).

Kleene computability theory

Exploring the abyss

Turing and Kleene

Kleene’s S1-S9 are computation schemes that formalise
X is computable in Y
for objects X , Y of finite type (essentially most of ordinary math).
S1-S9-computability extends Turing computability; the latter isrestricted to X , Y being real numbers.

Kleene computability theory

Exploring the abyss

Turing and Kleene

Kleene’s S1-S9 are computation schemes that formalise
X is computable in Y
for objects X , Y of finite type (essentially most of ordinary math).
S1-S9-computability extends Turing computability; the latter isrestricted to X , Y being real numbers.
S1-S8 merely provide a kind of primitive recursion while S9
hard-codes the recursion theorem in an ad hoc way.

Kleene computability theory

For details, consult:

Exploring the abyss

Kleene computability theory

A lambda calculus capturing S1-S9

Exploring the abyss

Kleene computability theory

Exploring the abyss

A lambda calculus capturing S1-S9
Computation can be based on fixed point operators (Moschovakis).

Kleene computability theory

Exploring the abyss

A lambda calculus capturing S1-S9
Computation can be based on fixed point operators (Moschovakis).
For Kleene’s S1-S9, the ‘is less partial than’-order is essential:

Kleene computability theory

Exploring the abyss

A lambda calculus capturing S1-S9
Computation can be based on fixed point operators (Moschovakis).
For Kleene’s S1-S9, the ‘is less partial than’-order is essential:x σ ⪯σ y σ means: the graph of x is included in the graph of y .

Kleene computability theory

Exploring the abyss

A lambda calculus capturing S1-S9
Computation can be based on fixed point operators (Moschovakis).
For Kleene’s S1-S9, the ‘is less partial than’-order is essential:x σ ⪯σ y σ means: the graph of x is included in the graph of y .
s σ→τ is monotone if: x ⪯σ y implies s(x) ⪯τ s(y ) for all x σ , y σ .

Kleene computability theory

Exploring the abyss

A lambda calculus capturing S1-S9
Computation can be based on fixed point operators (Moschovakis).
For Kleene’s S1-S9, the ‘is less partial than’-order is essential:x σ ⪯σ y σ means: the graph of x is included in the graph of y .
s σ→τ is monotone if: x ⪯σ y implies s(x) ⪯τ s(y ) for all x σ , y σ .
For monotone s σ→σ , µx σ .s(x) is the least fixed point of s, i.e.

Kleene computability theory

Exploring the abyss

A lambda calculus capturing S1-S9
Computation can be based on fixed point operators (Moschovakis).
For Kleene’s S1-S9, the ‘is less partial than’-order is essential:x σ ⪯σ y σ means: the graph of x is included in the graph of y .
s σ→τ is monotone if: x ⪯σ y implies s(x) ⪯τ s(y ) for all x σ , y σ .
For monotone s σ→σ , µx σ .s(x) is the least fixed point of s, i.e.
s(µx σ .s(x)) = µx σ .s(x) and s(y ) = y → µx σ .s(x) ⪯σ y ,Kleene computability theory

Exploring the abyss

A lambda calculus capturing S1-S9
Computation can be based on fixed point operators (Moschovakis).
For Kleene’s S1-S9, the ‘is less partial than’-order is essential:x σ ⪯σ y σ means: the graph of x is included in the graph of y .
s σ→τ is monotone if: x ⪯σ y implies s(x) ⪯τ s(y ) for all x σ , y σ .
For monotone s σ→σ , µx σ .s(x) is the least fixed point of s, i.e.
s(µx σ .s(x)) = µx σ .s(x) and s(y ) = y → µx σ .s(x) ⪯σ y ,Kleene’s S1-S9 is captured by: S1-S8 (primitive recursion) plus
λ-abstraction plus the µσ -operator for all finite types.

Kleene computability theory

Exploring the abyss

A lambda calculus capturing S1-S9
Computation can be based on fixed point operators (Moschovakis).
For Kleene’s S1-S9, the ‘is less partial than’-order is essential:x σ ⪯σ y σ means: the graph of x is included in the graph of y .
s σ→τ is monotone if: x ⪯σ y implies s(x) ⪯τ s(y ) for all x σ , y σ .
For monotone s σ→σ , µx σ .s(x) is the least fixed point of s, i.e.
s(µx σ .s(x)) = µx σ .s(x) and s(y ) = y → µx σ .s(x) ⪯σ y ,Kleene’s S1-S9 is captured by: S1-S8 (primitive recursion) plus
λ-abstraction plus the µσ -operator for all finite types.
Many functionals that ‘occur in nature’ are partial but take totalarguments; our lambda calculus is designed for the study of those.

Kleene computability theory

Exploring the abyss

A lambda calculus capturing S1-S9
Computation can be based on fixed point operators (Moschovakis).
For Kleene’s S1-S9, the ‘is less partial than’-order is essential:x σ ⪯σ y σ means: the graph of x is included in the graph of y .
s σ→τ is monotone if: x ⪯σ y implies s(x) ⪯τ s(y ) for all x σ , y σ .
For monotone s σ→σ , µx σ .s(x) is the least fixed point of s, i.e.
s(µx σ .s(x)) = µx σ .s(x) and s(y ) = y → µx σ .s(x) ⪯σ y ,Kleene’s S1-S9 is captured by: S1-S8 (primitive recursion) plus
λ-abstraction plus the µσ -operator for all finite types.
Many functionals that ‘occur in nature’ are partial but take totalarguments; our lambda calculus is designed for the study of those.

Normann-Sanders, JLC22, https://arxiv.org/abs/2203.05250.

Kleene computability theory

Why study Kleene’s computability theory?

Exploring the abyss

Kleene computability theory

Exploring the abyss

Why study Kleene’s computability theory?
Kleene’s S1-S9 provides a/the most general model of computationfor objects of finite type.

Kleene computability theory

Exploring the abyss

Why study Kleene’s computability theory?
Kleene’s S1-S9 provides a/the most general model of computationfor objects of finite type.
It also has a unique closure property called Gandy selection,
essentially a computational version of the Axiom of Choice.

Kleene computability theory

Exploring the abyss

Why study Kleene’s computability theory?
Kleene’s S1-S9 provides a/the most general model of computationfor objects of finite type.
It also has a unique closure property called Gandy selection,
essentially a computational version of the Axiom of Choice.
(∀x σ )(∃y τ )A(x, y ) → (∃F σ→τ ) (∀x σ )A(x, F (x)).
| {z }
choice function

Kleene computability theory

Exploring the abyss

Why study Kleene’s computability theory?
Kleene’s S1-S9 provides a/the most general model of computationfor objects of finite type.
It also has a unique closure property called Gandy selection,
essentially a computational version of the Axiom of Choice.
(∀x σ )(∃y τ )A(x, y ) → (∃F σ→τ ) (∀x σ )A(x, F (x)).
| {z }
choice function

Under certain restrictions, Gandy selection (and variations) guarantees:

Kleene computability theory

Exploring the abyss

Why study Kleene’s computability theory?
Kleene’s S1-S9 provides a/the most general model of computationfor objects of finite type.
It also has a unique closure property called Gandy selection,
essentially a computational version of the Axiom of Choice.
(∀x σ )(∃y τ )A(x, y ) → (∃F σ→τ ) (∀x σ )A(x, F (x)).
| {z }
choice function

Under certain restrictions, Gandy selection (and variations) guarantees:(∀ computable x σ )(∃ computable y τ ) A(x, y )| {z }
decidable

Kleene computability theory

Exploring the abyss

Why study Kleene’s computability theory?
Kleene’s S1-S9 provides a/the most general model of computationfor objects of finite type.
It also has a unique closure property called Gandy selection,
essentially a computational version of the Axiom of Choice.
(∀x σ )(∃y τ )A(x, y ) → (∃F σ→τ ) (∀x σ )A(x, F (x)).
| {z }
choice function

Under certain restrictions, Gandy selection (and variations) guarantees:(∀ computable x σ )(∃ computable y τ ) A(x, y )| {z }↓
decidable(∃ computable F σ→τ )(∀ computable x σ )A(x, F (x)).

Kleene computability theory

Exploring the abyss

Some oracles
The Halting problem/Turing jump has the following counterpart:Kleene computability theory

Exploring the abyss

Some oracles
The Halting problem/Turing jump has the following counterpart:(∀f : N → N)(∃2 (f ) = 0 ↔ (∃n ∈ N)(f (n) = 0)).

Kleene computability theory

Exploring the abyss

Some oracles
The Halting problem/Turing jump has the following counterpart:(∀f : N → N)(∃2 (f ) = 0 ↔ (∃n ∈ N)(f (n) = 0)).
Kleene’s quantifier ∃2 is discontinuous at f = 11 . . . .

Kleene computability theory

Exploring the abyss

Some oracles
The Halting problem/Turing jump has the following counterpart:(∀f : N → N)(∃2 (f ) = 0 ↔ (∃n ∈ N)(f (n) = 0)).
Kleene’s quantifier ∃2 is discontinuous at f = 11 . . . .
Similarly: S2k decides the truth of φ ∈ Π1k (Sieg-Feferman).

Kleene computability theory

Exploring the abyss

Some oracles
The Halting problem/Turing jump has the following counterpart:(∀f : N → N)(∃2 (f ) = 0 ↔ (∃n ∈ N)(f (n) = 0)).
Kleene’s quantifier ∃2 is discontinuous at f = 11 . . . .
Similarly: S2k decides the truth of φ ∈ Π1k (Sieg-Feferman).
The ‘hyperjump’ functional S21 is called the Suslin functional.

Kleene computability theory

Exploring the abyss

Some oracles
The Halting problem/Turing jump has the following counterpart:(∀f : N → N)(∃2 (f ) = 0 ↔ (∃n ∈ N)(f (n) = 0)).
Kleene’s quantifier ∃2 is discontinuous at f = 11 . . . .
Similarly: S2k decides the truth of φ ∈ Π1k (Sieg-Feferman).
The ‘hyperjump’ functional S21 is called the Suslin functional.
Everything we do is computable in Kleene’s quantifier ∃3 :(∀Y : NN → N)(∃3 (Y ) = 0 ↔ (∃f ∈ NN )(Y (f ) = 0)).
which yields full second-order arithmetic.

Kleene computability theory

Exploring the abyss

Some oracles
The Halting problem/Turing jump has the following counterpart:(∀f : N → N)(∃2 (f ) = 0 ↔ (∃n ∈ N)(f (n) = 0)).
Kleene’s quantifier ∃2 is discontinuous at f = 11 . . . .
Similarly: S2k decides the truth of φ ∈ Π1k (Sieg-Feferman).
The ‘hyperjump’ functional S21 is called the Suslin functional.
Everything we do is computable in Kleene’s quantifier ∃3 :(∀Y : NN → N)(∃3 (Y ) = 0 ↔ (∃f ∈ NN )(Y (f ) = 0)).
which yields full second-order arithmetic.
Historically, the focus of Kleene’s computability theory was normal
functionals (which compute ∃2 or ∃3 ).

Kleene computability theory

Exploring the abyss

Some oracles
The Halting problem/Turing jump has the following counterpart:(∀f : N → N)(∃2 (f ) = 0 ↔ (∃n ∈ N)(f (n) = 0)).
Kleene’s quantifier ∃2 is discontinuous at f = 11 . . . .
Similarly: S2k decides the truth of φ ∈ Π1k (Sieg-Feferman).
The ‘hyperjump’ functional S21 is called the Suslin functional.
Everything we do is computable in Kleene’s quantifier ∃3 :(∀Y : NN → N)(∃3 (Y ) = 0 ↔ (∃f ∈ NN )(Y (f ) = 0)).
which yields full second-order arithmetic.
Historically, the focus of Kleene’s computability theory was normal
functionals (which compute ∃2 or ∃3 ). (Hilbert-Bernays, Tait)Kleene computability theory

Exploring the abyss

The non-normal abyss
Kleene’s quantifiers ∃2 and ∃3 :(∀f : N → N)(∃2 (f ) = 0 ↔ (∃n ∈ N)(f (n) = 0)).
(∀Y : NN → N)(∃3 (Y ) = 0 ↔ (∃f ∈ NN )(Y (f ) = 0)).

Kleene computability theory

Exploring the abyss

The non-normal abyss
Kleene’s quantifiers ∃2 and ∃3 :(∀f : N → N)(∃2 (f ) = 0 ↔ (∃n ∈ N)(f (n) = 0)).
(∀Y : NN → N)(∃3 (Y ) = 0 ↔ (∃f ∈ NN )(Y (f ) = 0)).
Huge abyss between ∃2 and ∃3 in terms of computational strength.

Kleene computability theory

Exploring the abyss

The non-normal abyss
Kleene’s quantifiers ∃2 and ∃3 :(∀f : N → N)(∃2 (f ) = 0 ↔ (∃n ∈ N)(f (n) = 0)).
(∀Y : NN → N)(∃3 (Y ) = 0 ↔ (∃f ∈ NN )(Y (f ) = 0)).
Huge abyss between ∃2 and ∃3 in terms of computational strength.
This talk:(a) we identify basic (non-normal) functionals that are computable in ∃2

Kleene computability theory

Exploring the abyss

The non-normal abyss
Kleene’s quantifiers ∃2 and ∃3 :(∀f : N → N)(∃2 (f ) = 0 ↔ (∃n ∈ N)(f (n) = 0)).
(∀Y : NN → N)(∃3 (Y ) = 0 ↔ (∃f ∈ NN )(Y (f ) = 0)).
Huge abyss between ∃2 and ∃3 in terms of computational strength.
This talk:(a) we identify basic (non-normal) functionals that are computable in ∃2(b) and for which slight variations are computable in ∃3 but notcomputable in any functional S2k (which decides Π1k -formulas).

Kleene computability theory

Exploring the abyss

The non-normal abyss
Kleene’s quantifiers ∃2 and ∃3 :(∀f : N → N)(∃2 (f ) = 0 ↔ (∃n ∈ N)(f (n) = 0)).
(∀Y : NN → N)(∃3 (Y ) = 0 ↔ (∃f ∈ NN )(Y (f ) = 0)).
Huge abyss between ∃2 and ∃3 in terms of computational strength.
This talk:(a) we identify basic (non-normal) functionals that are computable in ∃2(b) and for which slight variations are computable in ∃3 but notcomputable in any functional S2k (which decides Π1k -formulas).

Item (a) deals (exactly) with definitions that have a built-in
approximation-device for function values.

Kleene computability theory

Exploring the abyss

A regular abyss just beyond the continuous
We always study f : [0, 1] → R for well-known function classes.

Kleene computability theory

Exploring the abyss

A regular abyss just beyond the continuous
We always study f : [0, 1] → R for well-known function classes.
f is regulated (aka regular) if the left and right limits f (x−) andf (x+) exist everywhere.

Kleene computability theory

Exploring the abyss

A regular abyss just beyond the continuous
We always study f : [0, 1] → R for well-known function classes.
f is regulated (aka regular) if the left and right limits f (x−) andf (x+) exist everywhere.
f is cadlag if it is regulated and right-continuous, i.e.
f (x) = f (x+) everywhere.

Kleene computability theory

Exploring the abyss

A regular abyss just beyond the continuous
We always study f : [0, 1] → R for well-known function classes.
f is regulated (aka regular) if the left and right limits f (x−) andf (x+) exist everywhere.
f is cadlag if it is regulated and right-continuous, i.e.
f (x) = f (x+) everywhere.
Both have (at most) countably many points of discontinuity and arich history (PDE, probability, Bourbaki, Scheeffer, . . . ).

Kleene computability theory

Exploring the abyss

A regular abyss just beyond the continuous
We always study f : [0, 1] → R for well-known function classes.
f is regulated (aka regular) if the left and right limits f (x−) andf (x+) exist everywhere.
f is cadlag if it is regulated and right-continuous, i.e.
f (x) = f (x+) everywhere.
∃2 computes supx∈[p,q] f (x) for any cadlag f : [0, 1] → R andp, q ∈ [0, 1].

Kleene computability theory

Exploring the abyss

A regular abyss just beyond the continuous
We always study f : [0, 1] → R for well-known function classes.
f is regulated (aka regular) if the left and right limits f (x−) andf (x+) exist everywhere.
f is cadlag if it is regulated and right-continuous, i.e.
f (x) = f (x+) everywhere.
∃2 computes supx∈[p,q] f (x) for any cadlag f : [0, 1] → R andp, q ∈ [0, 1].
∃3 computes supx∈[p,q] f (x) for any regulated f : [0, 1] → R andp, q ∈ [0, 1].

Kleene computability theory

Exploring the abyss

A regular abyss just beyond the continuous
We always study f : [0, 1] → R for well-known function classes.
f is regulated (aka regular) if the left and right limits f (x−) andf (x+) exist everywhere.
f is cadlag if it is regulated and right-continuous, i.e.
f (x) = f (x+) everywhere.
∃2 computes supx∈[p,q] f (x) for any cadlag f : [0, 1] → R andp, q ∈ [0, 1].
∃3 computes supx∈[p,q] f (x) for any regulated f : [0, 1] → R andp, q ∈ [0, 1].
Sharp: the functional S2k , which decides Π1k -formulas, cannot ingeneral compute suprema for regulated functions (holds for any k).

Kleene computability theory

Exploring the abyss

A regular abyss just beyond the continuous
We always study f : [0, 1] → R for well-known function classes.
f is regulated (aka regular) if the left and right limits f (x−) andf (x+) exist everywhere.
f is cadlag if it is regulated and right-continuous, i.e.
f (x) = f (x+) everywhere.
∃2 computes supx∈[p,q] f (x) for any cadlag f : [0, 1] → R andp, q ∈ [0, 1].
∃3 computes supx∈[p,q] f (x) for any regulated f : [0, 1] → R andp, q ∈ [0, 1].
Sharp: the functional S2k , which decides Π1k -formulas, cannot ingeneral compute suprema for regulated functions (holds for any k).
NB: right-continuity as in f (x) = f (x−) allows us to approximate f (x)given only f (q) for all q ∈ Q ∩ [0, 1].

Kleene computability theory

Exploring the abyss

An abyss among the Baire functions
Baire 1 means: pointwise limit of sequence of continuous functions.

Kleene computability theory

Exploring the abyss

An abyss among the Baire functions
Baire 1 means: pointwise limit of sequence of continuous functions.
Baire 2 means: pointwise limit of sequence of Baire 1 functions.

Kleene computability theory

Exploring the abyss

An abyss among the Baire functions
Baire 1 means: pointwise limit of sequence of continuous functions.
Baire 2 means: pointwise limit of sequence of Baire 1 functions.
Effectively Baire 2 means: iterated limit of double sequence ofcontinuous functions (≈ second-order codes for Baire 2).

Kleene computability theory

Exploring the abyss

An abyss among the Baire functions
Baire 1 means: pointwise limit of sequence of continuous functions.
Baire 2 means: pointwise limit of sequence of Baire 1 functions.
Effectively Baire 2 means: iterated limit of double sequence ofcontinuous functions (≈ second-order codes for Baire 2).
Baire (1905) notes that Baire 2 functions can be represented as
iterated limits.

Kleene computability theory

Exploring the abyss

An abyss among the Baire functions
Baire 1 means: pointwise limit of sequence of continuous functions.
Baire 2 means: pointwise limit of sequence of Baire 1 functions.
Effectively Baire 2 means: iterated limit of double sequence ofcontinuous functions (≈ second-order codes for Baire 2).
∃2 computes supx∈[p,q] f (x) given Baire 1 f : [0, 1] → [0, 1],p, q ∈ [0, 1], and the associated sequence of continuous functions.

Kleene computability theory

Exploring the abyss

An abyss among the Baire functions
Baire 1 means: pointwise limit of sequence of continuous functions.
Baire 2 means: pointwise limit of sequence of Baire 1 functions.
Effectively Baire 2 means: iterated limit of double sequence ofcontinuous functions (≈ second-order codes for Baire 2).
∃2 computes supx∈[p,q] f (x) given Baire 1 f : [0, 1] → [0, 1],p, q ∈ [0, 1], and the associated sequence of continuous functions.
∃3 computes supx∈[p,q] f (x) given Baire 2 f : [0, 1] → [0, 1],p, q ∈ [0, 1], and the associated sequence of Baire 1 functions.

Kleene computability theory

Exploring the abyss

An abyss among the Baire functions
Baire 1 means: pointwise limit of sequence of continuous functions.
Baire 2 means: pointwise limit of sequence of Baire 1 functions.
Effectively Baire 2 means: iterated limit of double sequence ofcontinuous functions (≈ second-order codes for Baire 2).
∃2 computes supx∈[p,q] f (x) given Baire 1 f : [0, 1] → [0, 1],p, q ∈ [0, 1], and the associated sequence of continuous functions.
∃3 computes supx∈[p,q] f (x) given Baire 2 f : [0, 1] → [0, 1],p, q ∈ [0, 1], and the associated sequence of Baire 1 functions.
Sharp: the functional S2k , which decides Π1k -formulas, cannot ingeneral compute suprema for Baire 2 functions (holds for any k).

Kleene computability theory

Exploring the abyss

An abyss among the Baire functions
Baire 1 means: pointwise limit of sequence of continuous functions.
Baire 2 means: pointwise limit of sequence of Baire 1 functions.
Effectively Baire 2 means: iterated limit of double sequence ofcontinuous functions (≈ second-order codes for Baire 2).
∃2 computes supx∈[p,q] f (x) given Baire 1 f : [0, 1] → [0, 1],p, q ∈ [0, 1], and the associated sequence of continuous functions.
∃3 computes supx∈[p,q] f (x) given Baire 2 f : [0, 1] → [0, 1],p, q ∈ [0, 1], and the associated sequence of Baire 1 functions.
Sharp: the functional S2k , which decides Π1k -formulas, cannot ingeneral compute suprema for Baire 2 functions (holds for any k).
Borderline: the Suslin functional S21 computes supx∈[p,q] f (x) given
effectively Baire 2 f : [0, 1] → [0, 1], p, q ∈ [0, 1], and theassociated double sequence of continuous functions.

Kleene computability theory

Out there: quasi-continuity and around

Exploring the abyss

Kleene computability theory

Exploring the abyss

Out there: quasi-continuity and aroundf is quasi-continuous if for all ϵ > 0, N ∈ N, x ∈ [0, 1], there is(a, b) ⊂ B(x, 21N ) with (∀y ∈ (a, b))(|f (x) − f (y )| < ϵ).

Kleene computability theory

Exploring the abyss

Out there: quasi-continuity and aroundf is quasi-continuous if for all ϵ > 0, N ∈ N, x ∈ [0, 1], there is(a, b) ⊂ B(x, 21N ) with (∀y ∈ (a, b))(|f (x) − f (y )| < ϵ).
f is cliquish if for all ϵ > 0, N ∈ N, x ∈ [0, 1], there is(a, b) ⊂ B(x, 21N ) such that (∀y , z ∈ (a, b))(|f (z) − f (y )| < ϵ).

Kleene computability theory

Exploring the abyss

Out there: quasi-continuity and aroundf is quasi-continuous if for all ϵ > 0, N ∈ N, x ∈ [0, 1], there is(a, b) ⊂ B(x, 21N ) with (∀y ∈ (a, b))(|f (x) − f (y )| < ϵ).
f is cliquish if for all ϵ > 0, N ∈ N, x ∈ [0, 1], there is(a, b) ⊂ B(x, 21N ) such that (∀y , z ∈ (a, b))(|f (z) − f (y )| < ϵ).
Some properties:
Studied by Baire, Volterra, Hankel, . . . starting ca 1870.

Kleene computability theory

Exploring the abyss

Out there: quasi-continuity and aroundf is quasi-continuous if for all ϵ > 0, N ∈ N, x ∈ [0, 1], there is(a, b) ⊂ B(x, 21N ) with (∀y ∈ (a, b))(|f (x) − f (y )| < ϵ).
f is cliquish if for all ϵ > 0, N ∈ N, x ∈ [0, 1], there is(a, b) ⊂ B(x, 21N ) such that (∀y , z ∈ (a, b))(|f (z) − f (y )| < ϵ).
Some properties:
Studied by Baire, Volterra, Hankel, . . . starting ca 1870.
Cliquish = continuity points are dense = pointwise discontinuous.

Kleene computability theory

Exploring the abyss

Out there: quasi-continuity and aroundf is quasi-continuous if for all ϵ > 0, N ∈ N, x ∈ [0, 1], there is(a, b) ⊂ B(x, 21N ) with (∀y ∈ (a, b))(|f (x) − f (y )| < ϵ).
f is cliquish if for all ϵ > 0, N ∈ N, x ∈ [0, 1], there is(a, b) ⊂ B(x, 21N ) such that (∀y , z ∈ (a, b))(|f (z) − f (y )| < ϵ).
Some properties:
Studied by Baire, Volterra, Hankel, . . . starting ca 1870.
Cliquish = continuity points are dense = pointwise discontinuous.

There are 2|R| non-measurable quasi-cont. functions and 2|R|
non-Borel measurable quasi-cont. functions.

Kleene computability theory

Exploring the abyss

Out there: quasi-continuity and aroundf is quasi-continuous if for all ϵ > 0, N ∈ N, x ∈ [0, 1], there is(a, b) ⊂ B(x, 21N ) with (∀y ∈ (a, b))(|f (x) − f (y )| < ϵ).
f is cliquish if for all ϵ > 0, N ∈ N, x ∈ [0, 1], there is(a, b) ⊂ B(x, 21N ) such that (∀y , z ∈ (a, b))(|f (z) − f (y )| < ϵ).
Some properties:
Studied by Baire, Volterra, Hankel, . . . starting ca 1870.
Cliquish = continuity points are dense = pointwise discontinuous.

There are 2|R| non-measurable quasi-cont. functions and 2|R|
non-Borel measurable quasi-cont. functions.
Closely related: every cliquish function is the sum of two
quasi-continuous functions (on the reals).

Kleene computability theory

Exploring the abyss

Quasi-continuity and aroundf is quasi-continuous if for all ϵ > 0, N ∈ N, x ∈ [0, 1], there is(a, b) ⊂ B(x, 21N ) with (∀y ∈ (a, b))(|f (x) − f (y )| < ϵ).
f is cliquish if for all ϵ > 0, N ∈ N, x ∈ [0, 1], there is(a, b) ⊂ B(x, 21N ) such that (∀y , z ∈ (a, b))(|f (z) − f (y )| < ϵ).
Closely related: every cliquish function is the sum of two
quasi-continuous functions (on the reals).

Kleene computability theory

Exploring the abyss

Quasi-continuity and aroundf is quasi-continuous if for all ϵ > 0, N ∈ N, x ∈ [0, 1], there is(a, b) ⊂ B(x, 21N ) with (∀y ∈ (a, b))(|f (x) − f (y )| < ϵ).
f is cliquish if for all ϵ > 0, N ∈ N, x ∈ [0, 1], there is(a, b) ⊂ B(x, 21N ) such that (∀y , z ∈ (a, b))(|f (z) − f (y )| < ϵ).
Closely related: every cliquish function is the sum of two
quasi-continuous functions (on the reals).
∃2 computes supx∈[p,q] f (x) given quasi-continuous
f : [0, 1] → [0, 1], p, q ∈ [0, 1].

Kleene computability theory

Exploring the abyss

Quasi-continuity and aroundf is quasi-continuous if for all ϵ > 0, N ∈ N, x ∈ [0, 1], there is(a, b) ⊂ B(x, 21N ) with (∀y ∈ (a, b))(|f (x) − f (y )| < ϵ).
f is cliquish if for all ϵ > 0, N ∈ N, x ∈ [0, 1], there is(a, b) ⊂ B(x, 21N ) such that (∀y , z ∈ (a, b))(|f (z) − f (y )| < ϵ).
Closely related: every cliquish function is the sum of two
quasi-continuous functions (on the reals).
∃2 computes supx∈[p,q] f (x) given quasi-continuous
f : [0, 1] → [0, 1], p, q ∈ [0, 1].
∃3 computes supx∈[p,q] f (x) given cliquish f : [0, 1] → [0, 1],p, q ∈ [0, 1].

Kleene computability theory

Exploring the abyss

Quasi-continuity and aroundf is quasi-continuous if for all ϵ > 0, N ∈ N, x ∈ [0, 1], there is(a, b) ⊂ B(x, 21N ) with (∀y ∈ (a, b))(|f (x) − f (y )| < ϵ).
f is cliquish if for all ϵ > 0, N ∈ N, x ∈ [0, 1], there is(a, b) ⊂ B(x, 21N ) such that (∀y , z ∈ (a, b))(|f (z) − f (y )| < ϵ).
Closely related: every cliquish function is the sum of two
quasi-continuous functions (on the reals).
∃2 computes supx∈[p,q] f (x) given quasi-continuous
f : [0, 1] → [0, 1], p, q ∈ [0, 1].
∃3 computes supx∈[p,q] f (x) given cliquish f : [0, 1] → [0, 1],p, q ∈ [0, 1].
Sharp: the functional S2k , which decides Π1k -formulas, cannot ingeneral compute suprema for cliquish functions (holds for any k).

Kleene computability theory

Exploring the abyss

Quasi-continuity and aroundf is quasi-continuous if for all ϵ > 0, N ∈ N, x ∈ [0, 1], there is(a, b) ⊂ B(x, 21N ) with (∀y ∈ (a, b))(|f (x) − f (y )| < ϵ).
f is cliquish if for all ϵ > 0, N ∈ N, x ∈ [0, 1], there is(a, b) ⊂ B(x, 21N ) such that (∀y , z ∈ (a, b))(|f (z) − f (y )| < ϵ).
Closely related: every cliquish function is the sum of two
quasi-continuous functions (on the reals).
∃2 computes supx∈[p,q] f (x) given quasi-continuous
f : [0, 1] → [0, 1], p, q ∈ [0, 1].
∃3 computes supx∈[p,q] f (x) given cliquish f : [0, 1] → [0, 1],p, q ∈ [0, 1].
Sharp: the functional S2k , which decides Π1k -formulas, cannot ingeneral compute suprema for cliquish functions (holds for any k).
Note that quasi-continuity allows us to approximate f (x) given
only f (q) for all q ∈ Q ∩ [0, 1].

Kleene computability theory

Exploring the abyss

Similar theorems
The supremum principle is not special; the same abyss is observedfor other basic properties.

Kleene computability theory

Exploring the abyss

Similar theorems
The supremum principle is not special; the same abyss is observedfor other basic properties.
Coverings lemmas (Cousin, Vitali, Heine-Borel, . . . ) forcoverings ∪x∈[0,1] B(x, Ψ(x)) and Ψ : [0, 1] → R+ .

Kleene computability theory

Exploring the abyss

Similar theorems
The supremum principle is not special; the same abyss is observedfor other basic properties.
Coverings lemmas (Cousin, Vitali, Heine-Borel, . . . ) forcoverings ∪x∈[0,1] B(x, Ψ(x)) and Ψ : [0, 1] → R+ .
Finding an RM-code for the set of continuity points Cf .

Kleene computability theory

Exploring the abyss

Similar theorems
The supremum principle is not special; the same abyss is observedfor other basic properties.
Coverings lemmas (Cousin, Vitali, Heine-Borel, . . . ) forcoverings ∪x∈[0,1] B(x, Ψ(x)) and Ψ : [0, 1] → R+ .
Finding an RM-code for the set of continuity points Cf .
Deciding whether f is continuous at a given real x ∈ [0, 1].

Kleene computability theory

Exploring the abyss

Similar theorems
The supremum principle is not special; the same abyss is observedfor other basic properties.
Coverings lemmas (Cousin, Vitali, Heine-Borel, . . . ) forcoverings ∪x∈[0,1] B(x, Ψ(x)) and Ψ : [0, 1] → R+ .
Finding an RM-code for the set of continuity points Cf .
Deciding whether f is continuous at a given real x ∈ [0, 1].
Jordan decomposition theorem.

Kleene computability theory

Exploring the abyss

Similar theorems
The supremum principle is not special; the same abyss is observedfor other basic properties.
Coverings lemmas (Cousin, Vitali, Heine-Borel, . . . ) forcoverings ∪x∈[0,1] B(x, Ψ(x)) and Ψ : [0, 1] → R+ .
Finding an RM-code for the set of continuity points Cf .
Deciding whether f is continuous at a given real x ∈ [0, 1].
Jordan decomposition theorem.
For a Riemann integrable f : [0, 1] → [0, 1] with
R1
0 f (x)dx = 0, find x ∈ [0, 1] such that f (x) = 0.
...

Kleene computability theory

Exploring the abyss

Similar theorems
The supremum principle is not special; the same abyss is observedfor other basic properties.
Coverings lemmas (Cousin, Vitali, Heine-Borel, . . . ) forcoverings ∪x∈[0,1] B(x, Ψ(x)) and Ψ : [0, 1] → R+ .
Finding an RM-code for the set of continuity points Cf .
Deciding whether f is continuous at a given real x ∈ [0, 1].
Jordan decomposition theorem.
For a Riemann integrable f : [0, 1] → [0, 1] with
R1
0 f (x)dx = 0, find x ∈ [0, 1] such that f (x) = 0.
...
Finally, how do we prove our negative results?

Kleene computability theory

The uncountability of R
Cantor’s first set theory paper (1874): uncountability of R.

Exploring the abyss

Kleene computability theory

Exploring the abyss

The uncountability of R
Cantor’s first set theory paper (1874): uncountability of R.

Cantor realisers (CR) perform the following associated operation:

Kleene computability theory

Exploring the abyss

The uncountability of R
Cantor’s first set theory paper (1874): uncountability of R.

Cantor realisers (CR) perform the following associated operation:
on input a countable set X ⊂ R, output an element y ∈ R \ X .

Kleene computability theory

Exploring the abyss

The uncountability of R
Cantor’s first set theory paper (1874): uncountability of R.

Cantor realisers (CR) perform the following associated operation:
on input a countable set X ⊂ R, output an element y ∈ R \ X .
A countable set X ⊂ R is a pair (X , Y ) where Y : R → N is
assumed to be injective (or even bijective) on X .

Kleene computability theory

Exploring the abyss

The uncountability of R
Cantor’s first set theory paper (1874): uncountability of R.

Cantor realisers (CR) perform the following associated operation:
on input a countable set X ⊂ R, output an element y ∈ R \ X .
A countable set X ⊂ R is a pair (X , Y ) where Y : R → N is
assumed to be injective (or even bijective) on X .
∃3 can compute a CR, but S2k cannot compute a CR (hold for any k).

Kleene computability theory

Exploring the abyss

Cantor realisers
Cantor realisers (CR) perform the following operation:
on input a countable set A ⊂ R, output an element y ∈ R \ X .
A countable set X ⊂ R is a pair (X , Y ) where Y : R → N is
injective (or even bijective) on X .
∃3 can compute a CR, but no S2k can compute a CR.

Kleene computability theory

Exploring the abyss

Cantor realisers
Cantor realisers (CR) perform the following operation:
on input a countable set A ⊂ R, output an element y ∈ R \ X .
A countable set X ⊂ R is a pair (X , Y ) where Y : R → N is
injective (or even bijective) on X .
∃3 can compute a CR, but no S2k can compute a CR.
Our negative results are obtained by computing a CR from thefunctionals at handKleene computability theory

Exploring the abyss

Cantor realisers
Cantor realisers (CR) perform the following operation:
on input a countable set A ⊂ R, output an element y ∈ R \ X .
A countable set X ⊂ R is a pair (X , Y ) where Y : R → N is
injective (or even bijective) on X .
∃3 can compute a CR, but no S2k can compute a CR.
Our negative results are obtained by computing a CR from thefunctionals at hand using:(1
if x ∈ X
f (x) := 2Y (x)+10
otherwise
which is BV , semi-continuous, cliquish, . . . and is found in theliterature.

Kleene computability theory

Exploring the abyss

The abyss and its origin
The abyss:(a) there are basic (non-normal) functionals that are computable in ∃2 .
(b) and for which slight variations are computable in ∃3 , but notcomputable in S2k .

Kleene computability theory

Exploring the abyss

The abyss and its origin
The abyss:(a) there are basic (non-normal) functionals that are computable in ∃2 .
(b) and for which slight variations are computable in ∃3 , but notcomputable in S2k .

Its origin: item (a) deals exactly with definitions that have abuilt-in approximation-device for function values.

Kleene computability theory

Exploring the abyss

The abyss and its origin
The abyss:(a) there are basic (non-normal) functionals that are computable in ∃2 .
(b) and for which slight variations are computable in ∃3 , but notcomputable in S2k .

Its origin: item (a) deals exactly with definitions that have abuilt-in approximation-device for function values.
Like item (a): Baire 1, effectively Baire n, normalised bounded(x+)
variation, regulated such that f (x) = f (x−)+f
everywhere.
2

Kleene computability theory

Exploring the abyss

The abyss and its origin
The abyss:(a) there are basic (non-normal) functionals that are computable in ∃2 .
(b) and for which slight variations are computable in ∃3 , but notcomputable in S2k .

Its origin: item (a) deals exactly with definitions that have abuilt-in approximation-device for function values.
Like item (a): Baire 1, effectively Baire n, normalised bounded(x+)
variation, regulated such that f (x) = f (x−)+f
everywhere.
2
Like item (b): simple continuity, semi-continuity, fragmented,
bounded variation, Baire 1∗ , Fσ -measurable.

Kleene computability theory

Exploring the abyss

The abyss and its origin
The abyss:(a) there are basic (non-normal) functionals that are computable in ∃2 .
(b) and for which slight variations are computable in ∃3 , but notcomputable in S2k .

Its origin: item (a) deals exactly with definitions that have abuilt-in approximation-device for function values.
Like item (a): Baire 1, effectively Baire n, normalised bounded(x+)
variation, regulated such that f (x) = f (x−)+f
everywhere.
2
Like item (b): simple continuity, semi-continuity, fragmented,
bounded variation, Baire 1∗ , Fσ -measurable.
Mathematically close (or equivalent) notions can land on eitherside of the abyss!

Kleene computability theory

Exploring the abyss

Thanks!
Questions?
Funded by the Klaus Tschira Foundation, German DFG, and RUB
Bochum.