Effectivizing Lusin's Theorem

Russell Miller

REVIEW 3 major objections 5 minor 7 references

Effectivizing Lusin's Theorem

T0 review · 3 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Lusin's theorem can be effectivized uniformly: for every Borel measurable function and every ε>0, a continuous approximant is computed from a code for the function and ε, using an oracle for its Borel level.

desk verdict New and uniform computable versions of Lusin's Theorem with a genuinely new proof strategy, but the central Lemma 5.6 has a real gap: finite-string oracle computations are not sound for all reals in the interval, so the uniform theorem as written is not established. read the letter →

arxiv 1908.06302 v2 pith:CLAPYSMH submitted 2019-08-17 math.LO

Russell Miller This is my paper · ORCID

classification math.LO MSC 03D3003D7803E15

keywords Lusin'stheoremcomputableanalysisTuringjumpnear-uniformityBorelfunctionsDedekindcutsgeneralizedlownesseffectivemeasure

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper proves Lusin's Theorem—every Borel-measurable function $f:\mathbb{R}\to\mathbb{R}$ agrees with some continuous function off a set of measure less than $\epsilon$—by a route through computability theory, and the route yields more than the classical statement. The approximation is uniform: there is a computable map $h$ such that from a Borel-code index $e$ of $f$ and a rational tolerance $\epsilon$ one obtains an index $h(\epsilon,e)$ of a Turing functional that, with an oracle coding the ordinal level of $f$, computes a continuous $g$ agreeing with $f$ off a set of measure $<\epsilon$. The key is that the iterated Turing jump is nearly uniform: a single functional $\Psi_\epsilon$ approximates $(S\oplus L_x\oplus R_x)^{(A)}$ from $S(A)\oplus L_x\oplus R_x$ except on an open error set of measure $<\epsilon$ that can be enumerated uniformly from an $S(A)$-oracle and patched by piecewise-linear functions. The proof recasts a classical 'near continuity' theorem as a statement about the jump operator, exposing a single error set that accounts for the discontinuity of every function at a given Borel level.

What carries the argument

The load-bearing mechanism is the near-uniformity of the iterated Turing jump, together with a careful 'error set' repair. For an $S$-decidable presentation $A$ of a countable ordinal $\alpha$, the $A$-jump $C(A)$ codes all lower jumps as columns. Theorem 3.4 supplies, uniformly in the rational tolerance $\epsilon$, a Turing functional $\Psi_\epsilon$ such that for every real $x$, $\Psi_\epsilon^{S(A)\oplus L_x\oplus R_x}$ is total and agrees with $(S\oplus L_x\oplus R_x)^{(A)}$ for all $x$ outside an $S(A)$-effectively open set $U_{\epsilon,S,A}$ of measure $<\epsilon$, containing all rationals; moreover the open intervals and 'buffer sets' witnessing the openness are enumerated uniformly. The proof of Theorem 5.1 then runs $\Theta = \Phi_e^{\Psi_\epsilon}$, collects upper and lower computations on rational intervals, and whenever the three approximations to the input cut fall inside an error interval, invokes a secondary step that defines $g$ piecewise-linearly, so that $g$ is total, single-valued, independent of the enumeration of the cut of $x$, and continuous by the S-computability criterion for continuity.

What would settle it

Theorem 3.4 asserts that for every $S$, every $S$-decidable presentation $A$, and every rational $\epsilon>0$, the functional $\Psi_\epsilon$ agrees with the true iterated jump $(S\oplus L_x\oplus R_x)^{(A)}$ for every real $x$ outside the enumerated open set $U_{\epsilon,S,A}$. Exhibit a single real $x\notin U_{\epsilon,S,A}$ and a coded input $\langle k,n\rangle$ for which $\Psi_\epsilon^{S(A)\oplus L_x\oplus R_x}(\langle k,n\rangle)\neq (S\oplus L_x\oplus R_x)^{(A)}(\langle k,n\rangle)$, and Theorem 3.4—and with it the uniform version of Lusin's Theorem—would be refuted; a computable search over rational intervals would suffice to look for such a disagreement.

Watch

Extended reading notes

Core claim

The central claim is Theorem 6.1: there exists a computable total function $h:\mathbb{Q}\times\mathbb{N}\to\mathbb{N}$ such that whenever $f$ is $\alpha$-jump $S$-computable, given by $\Phi_e^{(S\oplus A\oplus B)^{(A)}}$ for all enumerations $A\oplus B$ of cuts of $x$, a continuous $g$ satisfying Lusin's Theorem for $f$ with tolerance $\epsilon$ is computed by $\Phi_{h(\epsilon,e)}^{E(A)\oplus S(A)\oplus A\oplus B}$, where $E(A)$ is the elementary diagram of the presentation $A$ of the ordinal $\alpha$. The proof builds $g$ by running a near-uniform approximation $\Psi_\epsilon$ to the iterated jump $(S\oplus L_x\oplus R_x)^{(A)}$ from an $S(A)\oplus L_x\oplus R_x$-oracle, applying the original functional $\Phi_e$ to the output, and repairing the rare failures inside the enumerated open error set $U_{\epsilon,S,A}$ by declaring $g$ piecewise linear there. Since every Borel function is $\alpha$-jump $S$-computable for some countable $\alpha$ and some $S$-decidable $A$, the uniform procedure applies to every Borel-measurable $f$. A further corollary is that the same error set $U_{\epsilon,S,A}$ works for all such $f$ at once, and that no uniform procedure can achieve agreement off a measure-zero set.

Load-bearing premise

The argument rests on the cited characterization that every Borel function $f:\mathbb{R}\to\mathbb{R}$ is $\alpha$-jump $S$-computable for some countable ordinal $\alpha$ with an $S$-decidable presentation $A$; if that bridge from analysis to computability carried hidden uniformity conditions, or failed to supply an $S$-decidable $A$, the near-uniform approximation and the uniform Lusin procedure would not get off the ground.

Editorial extensions

If this is right

There is a single computable function $h$ such that, whenever $f$ is given by an $\alpha$-jump $S$-computation with index $e$, the functional with index $h(\epsilon,e)$ and oracle $E(A)\oplus S(A)\oplus A\oplus B$ computes a continuous $g$ with $\mu(\{x: g(x)\neq f(x)\})<\epsilon$, uniformly in $\epsilon$ and independently of the Borel level $\alpha$ (Theorem 6.1).
The same open set $U_{\epsilon,S,A}$ of measure $<\epsilon$ contains the disagreement set of every $\alpha$-jump $S$-computable function at once, so each such $f$ is continuous on the complement of $U_{\epsilon,S,A}$; in this sense the failures of continuity at a fixed Borel level are confined to a single universal 'bad' set (Proposition 7.1).
Lusin's theorem cannot be pushed to equality off a measure-zero set: the characteristic function of $(0,+\infty)$ shows that no continuous $g$ can agree with it except on a set of measure 0.
The Lusin procedure need not preserve an already continuous $f$, and this is conjectured to be unavoidable for any uniform procedure; however, with one additional jump, an $S(A+1)$-oracle computes $f$ itself uniformly from its $\alpha$-jump computation (Theorem 8.1).
The same methods are claimed to yield simpler analogues with Baire category in place of Lebesgue measure and with Cantor space $2^{\mathbb{N}}$ in place of $\mathbb{R}$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Because a single error set $U_{\epsilon,S,A}$ serves every function at a fixed Borel level, one can read the paper as attaching to each countable ordinal $\alpha$ a canonical 'defect set' in $\mathbb{R}$; comparing these sets as $\alpha$ grows would give a measure-theoretic profile of the Borel hierarchy itself.
The paper notes that any dense computable set could replace $\mathbb{Q}$ in the construction; this suggests a family of variants in which the continuous approximant is forced to take prescribed values on a chosen countable dense set, which might sharpen where the error set sits.
If the conjecture of Section 8 is correct, there is an exact trade-off: no uniform Lusin operator can also leave continuous functions unchanged, and the single additional jump in Theorem 8.1 is the minimal price of correctness.
A concrete testable extension would be to instantiate the construction for $\alpha=1$ and simple functions such as characteristic functions of intervals, and verify that the computed $g$ agrees with $f$ off the predicted $U_{\epsilon,S,A}$; this would give a finite computational check of Theorem 6.1 at the lowest nontrivial Borel level.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Read the arXiv v1 carefully. The reader's conditional verdict is right, and the stress-test note is not wrong: there is a real gap at Lemma 5.6, and it is load-bearing.

What's genuinely new: the uniform effective Lusin Theorem 6.1 (h computable in ε and the index e), the function-independent error set of Prop 7.1, and the continuous-function recovery Theorem 8.1. The method—deriving Lusin from near-uniformity of iterated Turing jumps, with an error set uniform in f—is a new route to a classical theorem. The construction in Section 5 is explicit, and the use of Kechris's Theorem 4.2 as an external bridge is standard and not circular.

The gap is exactly the one the stress test identifies. Definition 5.2 accepts any halting computation of Θ on S(A)⊕λ⊕ρ, with finite strings extended by zeros in the usual oracle convention. For a good interval (c,c'), the first rational q_l inside lies beyond the strings' length, so the zero-extension puts q_l in neither L nor R—matching only the rational x=q_l, not the continuum-many other x in (c,c'). A computation that queries q_l or anything past the string is therefore not sound for those x. The Main Step applies every listed computation whose interval contains x, and Lemma 5.6 proves only the forward direction (genuine bounds eventually appear), never the converse (every listed computation is genuine). Without a use-boundedness condition—say, requiring the halting computation's use to stay entirely within the finite string, so it never queries the ambiguous rational—g(x) can be driven by spurious bounds. The parenthetical about a later error interval does not rescue x outside U; no error interval contains such x. Theorem 6.1 inherits the gap. This is not obviously fatal: adding an explicit use bound to Definition 5.2 and rechecking the Main Step looks like a plausible repair. But as written, the proof doesn't go through.

Smaller issue: the abstract promises Baire-category and Cantor-space versions; those are absent from this v1. The abstract should be trimmed or the versions supplied.

For whom: computability theorists and descriptive set theorists interested in effective measure and uniform versions of classical theorems. This deserves peer review: the ideas are substantial, the results are new, and the gap is concrete and likely repairable. I'd send it out with a request for major revision focused on the use-boundedness issue.

Referee Report

3 major / 5 minor

Summary. The paper presents a computability-theoretic proof of Lusin's Theorem: every Borel function f:R->R agrees with some continuous g except on a set of measure less than epsilon. The proof strategy is to represent a Borel f as an alpha-jump S-computable function via a cited characterization (Theorem 4.2, from Kechris), prove a near-uniform approximation theorem for the iterated jump on Dedekind cuts (Theorem 3.4), and then construct a Turing functional Gamma that computes g from the oracle S(A) plus an enumeration of the cut of x. The main claimed output is Theorem 6.1, a uniform effective version: an index for g is computed uniformly from the index of f and from epsilon, independently of the Borel level of f, once an oracle coding the presentation A is supplied. The paper also states an extended-valued version (Theorem 6.2) and a variant for continuous functions (Theorem 8.1). The abstract additionally promises Baire-category and Cantor-space versions, but the body of the submitted text does not contain those sections.

Significance. If the main proof can be repaired, this is a genuinely striking paper. It connects a classical theorem of real analysis to the near-uniformity of the transfinite Turing jump, and it yields a concrete, falsifiable uniformity statement: the approximating continuous function is obtained uniformly from epsilon and the index of f. The proof is not circular: it does not assume Lusin's Theorem, and the reliance on the external Borel-computability characterization Theorem 4.2 is declared. Theorem 3.4 is the main technical engine and is largely explicit, and the uniformity in epsilon is a real feature. However, the gap detailed below in the soundness of finite-string oracle computations is load-bearing for Lemma 5.6 and therefore for Theorem 5.1 and Theorem 6.1. The missing Baire-category and Cantor-space sections announced in the abstract are also a completeness problem for this version.

major comments (3)

[§5, Definition 5.2 and Lemma 5.6] The finite-string oracle computations defined in Definition 5.2 are not sound for every x in the interval (c,c'), and Lemma 5.6 never proves the converse direction needed for the Main Step. Definition 5.2 declares (c,c',u) to be an upper computation if Theta^{S(A) xor lambda_{c,c'} xor rho_{c,c'}}(<u,2n+1>) halts and outputs 1. Under the standard convention, the finite strings lambda and rho are padded with zeros beyond their length l. For every x in (c,c'), the rational q_l inside (c,c') is a member of L_x or R_x, so the padded oracle gives the wrong answer at that position to any computation that queries beyond l. Such a computation can therefore halt with an output that is true for no x in (c,c'). The Main Step then applies every listed computation once the three shrinking intervals lie inside (c,c'), without checking that the computation's use is contained in the finite string. Lemma 5.6 proves, in the forward direction, that genuine upper and lower bounds for x outside U appear in the enumeration, but it does not prove that every listed computation applied to x outside U is genuine. The parenthetical in the Main Step that a contradiction would generate an error interval containing x is not established: x outside U has no error interval around it. Without a use-boundedness condition on accepted computations, the identity g(x)=f(x) outside U is unsupported, and Theorem 6.1 inherits the gap.
[Abstract] The abstract states that 'Easier results, which we prove by the same methods, include versions of Lusin's Theorem with Baire category in place of Lebesgue measure and also with Cantor space 2^N in place of R,' but the submitted body contains no such theorems and no sections devoted to Baire category or Cantor space; the text ends after Section 8. Since the abstract and introduction advertise these variants as part of the paper's contribution, this is not a mere wording issue. Either these results and their proofs must be added, or the abstract and introduction must be revised to state accurately what the paper contains.
[§5, Theorem 4.2 / proof of Theorem 5.1] Theorem 4.2 is the bridge from Borel measurability to alpha-jump S-computability, and Theorem 5.1 uses it in a strong form: a single oracle S and a single S-decidable presentation A must work for every enumeration A xor B of the cut of every x in R, with the successor and limit relations of the presentation computable from S. This theorem is cited from [2] without a specific theorem number. Please supply the exact statement and location in Kechris, and verify that it indeed gives the uniformity and decidability properties required by Definition 3.2 and Corollary 3.5. If Theorem 4.2 provides only a presentation that is merely S-computable in the weaker atomic-diagram sense, or if the uniformity over enumerations is not explicit, then the subsequent application of Corollary 3.5 and the construction of Gamma do not follow as written.

minor comments (5)

[§6, Theorem 6.1] There is a notational clash in Theorem 6.1: A denotes both the presentation of the ordinal alpha and the left Dedekind cut in the join A xor B. Please use different symbols, for example P for the presentation and A xor B for the cut enumeration.
[§3, Lemma 3.3 / Theorem 3.4] The paper never states its convention for using a finite string as an oracle. In Lemma 3.3 and Definition 5.2, expressions of the form Phi^{sigma}(e) downarrow and Theta^{S(A) xor lambda xor rho} are used; please state explicitly whether finite strings are padded with zeros, identified with arbitrary extensions, or treated as finite partial functions, and explain how the convergence notion depends on that convention.
[§5] There are several typos in the final paragraph of Section 5: 'whcih', 'a dn', and 'end poitnts' should be corrected. The same paragraph's final sentence is extremely long and would benefit from being split for readability.
[§5, Lemma 5.4] Lemma 5.4 is stated with proof omitted (the proof is marked only by a square). It is used in the soundness of the main construction, so a short proof or at least a clear justification of the three-string claim should be included.
[§8, Theorem 8.1] The proof of Theorem 8.1 says the cuts L_q and R_q are 'computable uniformly in Q'; this should read 'uniformly in q'. The decision procedure for the set D is plausible but deserves one more sentence explaining why the additional jump A+1 suffices to decide a universal quantification over infinitely many rationals in [a,b].

Circularity Check

0 steps flagged · score 0.0 of 10

No circular derivation: Lusin's Theorem is proved from independent computability facts, not assumed or fitted.

full rationale

The paper's derivation chain is not circular. Lusin's Theorem (Theorem 5.1) is proved, not presupposed: the target conclusion appears only as the statement to be established, and the proof builds a continuous g from a Turing functional Γ using the near-uniformity of the iterated jump (Theorem 3.4) and a cited external characterization of Borel functions (Theorem 4.2 from Kechris). The Kechris result is independent support: it does not assume Lusin's Theorem, and it is cited as a background theorem from a different field, not as a premise containing the conclusion. The Weihrauch theorem (Theorem 2.4) is likewise external and states only that S-computable real functions are continuous, which is logically much weaker than Lusin's Theorem and carries no fitted parameters. Stillwell's work is used for the measure-one near-uniformity of the jump, again independent of the conclusion. No self-citations occur, and no parameter is fitted to a subset of data and then renamed as a prediction: the uniform function h in Theorem 6.1 is obtained uniformly from the index e and tolerance epsilon via the construction, not by tuning. The error set U_{epsilon,S,A} is defined from computability-theoretic data and is independent of f, so the equality g=f outside U is not engineered by using the desired approximation as an input. Even if the skeptical concern about Definition 5.2's finite-string oracle soundness reveals an internal gap in the proof, that is a correctness issue, not circularity: the contested step is an unproved implication inside a constructive argument, not a reduction of the conclusion to an assumption equivalent to it. Accordingly, the paper earns a circularity score of 0.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

No fitted parameters or new postulated entities. The 'presentation' and 'A-jump' constructions are internal definitions, not independent empirical assumptions.

assumptions (5)

standard math Weihrauch's characterization: f:R to R is continuous iff it is S-computable for some oracle S (Theorem 2.4).
Used in Theorem 5.1 to conclude the Gamma-computed g is continuous; cited from Weihrauch's book without proof.
standard math Every Borel function f:R to R is alpha-jump S-computable for some countable ordinal alpha, oracle S, and S-decidable presentation A (Theorem 4.2).
Bridge from analytic Borel functions to jump computations; invoked at the start of the proof of Theorem 5.1 and cited to Kechris, not proved in the paper.
standard math Transparency Lemma: jump-computable functions are exactly limits of computable functions (Lemma 4.3).
Used to motivate the choice of jump over limit operations; folklore and not needed for the main proof.
standard math Basic facts about the Turing jump and iterated jumps: A is strictly below A', and S-decidable presentations exist for all ordinals below omega_1^S.
Background from Soare assumed for Definition 3.2 and Theorem 3.4.
domain assumption Lebesgue measure on R is compatible with the interval measure on Dedekind cuts used in Corollary 3.5.
The proof converts measure estimates on [0,1] to all of R by summing over unit intervals; standard measure theory.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Effectivizing Lusin's Theorem." pith.science (2026). https://pith.science/paper/CLAPYSMH

@misc{pith2026190806302,
  author       = {Pith},
  title        = {Pith review of: Effectivizing Lusin's Theorem},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/CLAPYSMH}},
  note         = {Machine review of arXiv:1908.06302}
}

abstract

Lusin's Theorem states that, for every Borel-measurable function $\bf{f}$ on $\mathbb R$ and every $\epsilon>0$, there exists a continuous function $\bf{g}$ on $\mathbb R$ which is equal to $\bf{f}$ except on a set of measure $<\epsilon$. We give a proof of this result using computability theory, relating it to the near-uniformity of the Turing jump operator, and use this proof to derive several uniform computable versions. Easier results, which we prove by the same methods, include versions of Lusin's Theorem with Baire category in place of Lebesgue measure and also with Cantor space $2^{\mathbb N}$ in place of $\mathbb R$. The distinct processes showing generalized lowness for generic sets and for a set of full measure are seen to explain the differences between versions of Lusin's Theorem.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

7 extracted references · 7 canonical work pages

[2]

Kechris; Classical Descriptive Set Theory (New York: Springer-Verlag, 1995)

A. Kechris; Classical Descriptive Set Theory (New York: Springer-Verlag, 1995)

work page 1995
[1]

C.J. Ash & J. Knight; Computable structures and the hyperarithmetical hierarch y (Amsterdam: North-Holland Publishing Co., 2000)

work page 2000
[3]

Royden; Real Analysis, third edition (Englewood Cliﬀs, NJ: Pearson, 1988)

H. Royden; Real Analysis, third edition (Englewood Cliﬀs, NJ: Pearson, 1988)

work page 1988
[4]

Rudin; Real and Complex Analysis (New York: McGraw Hill Book Company, 1987)

W. Rudin; Real and Complex Analysis (New York: McGraw Hill Book Company, 1987)

work page 1987
[5]

Soare; Recursively Enumerable Sets and Degrees (New York: Springer-Verlag, 1987)

R.I. Soare; Recursively Enumerable Sets and Degrees (New York: Springer-Verlag, 1987)

work page 1987
[6]

almost all

John Stillwell; Decidability of the “almost all” theory of degrees. Journal of Symbolic Logic 37 (3) 1972, 501–506

work page 1972
[7]

Weihrauch; Computable Analysis: An Introduction (Berlin: Springer, 2000)

K. Weihrauch; Computable Analysis: An Introduction (Berlin: Springer, 2000). Dept. of Mathematics, Queens College, & Ph.D. Programs in Ma thematics & Com- puter Science, Graduate Center, City University of New York , USA E-mail address : Russell.Miller@qc.cuny.edu URL: http://qcpages.qc.cuny.edu/∼rmiller/

work page 2000

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [2]

Kechris; Classical Descriptive Set Theory (New York: Springer-Verlag, 1995)

A. Kechris; Classical Descriptive Set Theory (New York: Springer-Verlag, 1995)

work page 1995

[2] [1]

C.J. Ash & J. Knight; Computable structures and the hyperarithmetical hierarch y (Amsterdam: North-Holland Publishing Co., 2000)

work page 2000

[3] [3]

Royden; Real Analysis, third edition (Englewood Cliﬀs, NJ: Pearson, 1988)

H. Royden; Real Analysis, third edition (Englewood Cliﬀs, NJ: Pearson, 1988)

work page 1988

[4] [4]

Rudin; Real and Complex Analysis (New York: McGraw Hill Book Company, 1987)

W. Rudin; Real and Complex Analysis (New York: McGraw Hill Book Company, 1987)

work page 1987

[5] [5]

Soare; Recursively Enumerable Sets and Degrees (New York: Springer-Verlag, 1987)

R.I. Soare; Recursively Enumerable Sets and Degrees (New York: Springer-Verlag, 1987)

work page 1987

[6] [6]

almost all

John Stillwell; Decidability of the “almost all” theory of degrees. Journal of Symbolic Logic 37 (3) 1972, 501–506

work page 1972

[7] [7]

Weihrauch; Computable Analysis: An Introduction (Berlin: Springer, 2000)

K. Weihrauch; Computable Analysis: An Introduction (Berlin: Springer, 2000). Dept. of Mathematics, Queens College, & Ph.D. Programs in Ma thematics & Com- puter Science, Graduate Center, City University of New York , USA E-mail address : Russell.Miller@qc.cuny.edu URL: http://qcpages.qc.cuny.edu/∼rmiller/

work page 2000