46 1. Logic and foundations N, the sum of the lengths of Iε,1,...,1ε,N remains less than ε, and secondly that after selecting any real number x, that if x lies in E but not in Eε or vice versa, that x indeed lies in I ε,N(x) . In principle, if one performed this verification procedure an uncountable number of times (once for each choice of ε,N,x) one would fully demonstrate the measurability of E but if one instead only had access to finite or countable computational resources, then one could only verify measurability on an “as needed” basis. So, in the oracle model, a measurable set is not simply a membership oracle E() it must also be supplemented with an additional measurability oracle M() that “witnesses” the measurability. This is analogous to how sets must be augmented with (say) topological structure if one wants to perform topology on that set, or algebraic structure if one wants to perform algebra on that set, etc. If one possesses a measurability oracle M() for a set E (or more precisely, a membership oracle E()), then one can estimate the Lebesgue measure of E to within accuracy ε by calling M(ε) to obtain an approximant Eε, and then computing the measure |Eε| of Eε (which can be done in a finite amount of time, as Eε is simply a finite union of intervals). A key fact (which, not coincidentally, is crucial in the standard construction of Lebesgue measure) is that these approximations to the Lebesgue measure of E are compatible with each other in the following sense: if one calls one measurability oracle M(ε) for E() at accuracy ε 0 to get one estimate |Eε| for the Lebesgue measure of E(), and if one then calls another (possibly different) measura- bility oracle M (ε ) for the same set E() at another accuracy ε 0 to get another estimate |E ε | for E(), then these two estimates can only differ by at most ε + ε in particular, sending ε → 0, one obtains a Cauchy sequence and (after a countable number of operations) one can then compute the Lebesgue measure of E to infinite precision. This key fact boils down (after some standard manipulations) to the fact that an interval such as [a,b] has outer measure at least b − a in our oracle based model, this means that if one is given an interval oracle I() that generates open intervals I(n) for each natural number n, in such a way that the total length ∑ n |I(n)| of these intervals is less than b − a, then one can find a point in [a,b] which is not covered by any of the I(n). This can be done using a countable amount of computational power (basically, the ability to run a single infinite loop this is roughly equivalent to the theory RCA0 that is used in reverse mathematics). The point is that for each finite N, the set SN := [a,b]\ N n=1 I(n) is a computable non-empty finite union of closed intervals in [a,b], which decreases in N. The infimum inf(SN) can be computed infinite times for each N, and increases in N the limit limN→∞ inf(SN) is then an element in N SN that lies in [a,b] but is

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2013 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.