VizualBusiness: A cheap version of nonstandard analysis

Thursday, April 5, 2012

A cheap version of nonstandard analysis

A cheap version of nonstandard analysis:
Nonstandard analysis is a mathematical framework in which one extends the standard mathematical universe ${{\mathfrak U}}$ of standard numbers, standard sets, standard functions, etc. into a larger nonstandard universe ${{}^* {\mathfrak U}}$ of nonstandard numbers, nonstandard sets, nonstandard functions, etc., somewhat analogously to how one places the real numbers inside the complex numbers, or the rationals inside the reals. This nonstandard universe enjoys many of the same properties as the standard one; in particular, we have the transfer principle that asserts that any statement in the language of first order logic is true in the standard universe if and only if it is true in the nonstandard one. (For instance, because Fermat’s last theorem is known to be true for standard natural numbers, it is automatically true for nonstandard natural numbers as well.) However, the nonstandard universe also enjoys some additional useful properties that the standard one does not, most notably the countable saturation property, which is a property somewhat analogous to the completeness property of a metric space; much as metric completeness allows one to assert that the intersection of a countable family of nested closed balls is non-empty, countable saturation allows one to assert that the intersection of a countable family of nested satisfiable formulae is simultaneously satisfiable. (See this previous blog post for more on the analogy between the use of nonstandard analysis and the use of metric completions.) Furthermore, by viewing both the standard and nonstandard universes externally (placing them both inside a larger metatheory, such as a model of Zermelo-Frankel-Choice (ZFC) set theory; in some more advanced set-theoretic applications one may also wish to add some large cardinal axioms), one can place some useful additional definitions and constructions on these universes, such as defining the concept of an infinitesimal nonstandard number (a number which is smaller in magnitude than any positive standard number). The ability to rigorously manipulate infinitesimals is of course one of the most well-known advantages of working with nonstandard analysis.

To build a nonstandard universe ${{}^* {\mathfrak U}}$ from a standard one ${{\mathfrak U}}$ , the most common approach is to take an ultrapower of ${{\mathfrak U}}$ with respect to some non-principal ultrafilter over the natural numbers; see e.g. this blog post for details. Once one is comfortable with ultrafilters and ultrapowers, this becomes quite a simple and elegant construction, and greatly demystifies the nature of nonstandard analysis.

On the other hand, nonprincipal ultrafilters do have some unappealing features. The most notable one is that their very existence requires the axiom of choice (or more precisely, a weaker form of this axiom known as the boolean prime ideal theorem). Closely related to this is the fact that one cannot actually write down any explicit example of a nonprincipal ultrafilter, but must instead rely on nonconstructive tools such as Zorn’s lemma, the Hahn-Banach theorem, Tychonoff’s theorem, the Stone-Cech compactification, or the boolean prime ideal theorem to locate one. As such, ultrafilters definitely belong to the “infinitary” side of mathematics, and one may feel that it is inappropriate to use such tools for “finitary” mathematical applications, such as those which arise in hard analysis. From a more practical viewpoint, because of the presence of the infinitary ultrafilter, it can be quite difficult (though usually not impossible, with sufficient patience and effort) to take a finitary result proven via nonstandard analysis and coax an effective quantitative bound from it.

There is however a “cheap” version of nonstandard analysis which is less powerful than the full version, but is not as infinitary in that it is constructive (in the sense of not requiring any sort of choice-type axiom), and which can be translated into standard analysis somewhat more easily than a fully nonstandard argument; indeed, a cheap nonstandard argument can often be presented (by judicious use of asymptotic notation) in a way which is nearly indistinguishable from a standard one. It is obtained by replacing the nonprincipal ultrafilter in fully nonstandard analysis with the more classical Fréchet filter of cofinite subsets of the natural numbers, which is the filter that implicitly underlies the concept of the classical limit ${\lim_{{\bf n} \rightarrow \infty} a_{\bf n}}$ of a sequence when the underlying asymptotic parameter ${{\bf n}}$ goes off to infinity. As such, “cheap nonstandard analysis” aligns very well with traditional mathematics, in which one often allows one’s objects to be parameterised by some external parameter such as ${{\bf n}}$ , which is then allowed to approach some limit such as ${\infty}$ . The catch is that the Fréchet filter is merely a filter and not an ultrafilter, and as such some of the key features of fully nonstandard analysis are lost. Most notably, the law of the excluded middle does not transfer over perfectly from standard analysis to cheap nonstandard analysis; much as there exist bounded sequences of real numbers (such as ${0,1,0,1,\ldots}$ ) which do not converge to a (classical) limit, there exist statements in cheap nonstandard analysis which are neither true nor false (at least without passing to a subsequence, see below). The loss of such a fundamental law of mathematical reasoning may seem like a major disadvantage for cheap nonstandard analysis, and it does indeed make cheap nonstandard analysis somewhat weaker than fully nonstandard analysis. But in some situations (particularly when one is reasoning in a “constructivist” or “intuitionistic” fashion, and in particular if one is avoiding too much reliance on set theory) it turns out that one can survive the loss of this law; and furthermore, the law of the excluded middle is still available for standard analysis, and so one can often proceed by working from time to time in the standard universe to temporarily take advantage of this law, and then transferring the results obtained there back to the cheap nonstandard universe once one no longer needs to invoke the law of the excluded middle. Furthermore, the law of the excluded middle can be recovered by adopting the freedom to pass to subsequences with regards to the asymptotic parameter ${{\bf n}}$ ; this technique is already in widespread use in the analysis of partial differential equations, although it is generally referred to by names such as “the compactness method” rather than as “cheap nonstandard analysis”.

Below the fold, I would like to describe this cheap version of nonstandard analysis, which I think can serve as a pedagogical stepping stone towards fully nonstandard analysis, as it is formally similar to (though weaker than) fully nonstandard analysis, but on the other hand is closer in practice to standard analysis. As we shall see below, the relation between cheap nonstandard analysis and standard analysis is analogous in many ways to the relation between probabilistic reasoning and deterministic reasoning; it also resembles somewhat the preference in much of modern mathematics for viewing mathematical objects as belonging to families (or to categories) to be manipulated en masse, rather than treating each object individually. (For instance, nonstandard analysis can be used as a partial substitute for scheme theory in order to obtain uniformly quantitative results in algebraic geometry, as discussed for instance in this previous blog post.)

— 1. Details —

To set up cheap nonstandard analysis, we will need an asymptotic parameter ${{\bf n}}$ , which we will take to initially lie in the natural numbers ${{\bf N}}$ (though it is certainly possible to set up cheap nonstandard analysis on other non-compact spaces than ${{\bf N}}$ if one wishes). However, we reserve the right in the future to restrict the parameter space from ${{\bf N}}$ to a smaller infinite subset ${\Sigma}$ (which corresponds to the familiar operation of passing from a sequence ${x_{\bf n}}$ to a subsequence, except that we do not bother to relabel the subsequence to be indexed by ${{\bf N}}$ again). The dynamic nature of the parameter space ${\Sigma}$ makes it a little tricky to properly formalise cheap nonstandard analysis in the usual static framework of mathematical logic, but it turns out not to make much difference in practice, because in cheap nonstandard analysis one only works with statements which remain valid under the operation of restricting the underlying domain of the asymptotic parameter. (This is analogous to how in probability theory one only works with statements which remain valid under the operation of extending the underlying probability space, as discussed in this blog post.)

We then distinguish two types of mathematical objects:

Standard objects ${x}$ , which do not depend on the asymptotic parameter ${{\bf n}}$ ; and
Nonstandard objects ${x = x_{\bf n}}$ , which are allowed to depend on the asymptotic parameter ${{\bf n}}$ .

Similarly with “object” replaced by other mathematical concepts such as “number”, “point”, “set”, “function”, etc. Thus, for instance, a nonstandard real is a real number ${x = x_{\bf n}}$ that depends on the asymptotic parameter ${{\bf n}}$ ; a nonstandard function is a function ${f = f_{\bf n}: X_{\bf n} \rightarrow Y_{\bf n}}$ from a domain ${X = X_{\bf n}}$ to a range ${Y = Y_{\bf n}}$ , which are all allowed to depend on the asymptotic parameter ${{\bf n}}$ ; and so forth.

Of course, with these conventions, every standard object is automatically also a nonstandard object. (One can use the terminology strictly nonstandard object to refer to a nonstandard object which is not a standard object.) This will lead to the following slight abuse of notation: if ${X}$ is a standard set, we consider a cheap nonstandard element of ${X}$ to be a nonstandard object ${x = x_{\bf n}}$ , such that each ${x_{\bf n}}$ is an element of ${X}$ . In the strict set-theoretic sense, this is not an actual element of ${X}$ , which consists only of standard objects, but we will abuse notation and consider it as a nonstandard element of ${X}$ . (This is analogous to how, in probability theory, a real-valued random variable is not actually a (deterministic) element of ${{\bf R}}$ , but can be considered as a probabilistic element of ${{\bf R}}$ instead.) If one wants to be more pedantic, one can use the notation ${{}^* X}$ to denote the collection of all nonstandard elements of ${X}$ , which is what one usually does in fully nonstandard analysis (after quotienting by equivalence with respect to a non-principal ultrafilter), but we will avoid trying to collect cheap nonstandard elements into a set here because it interferes with the freedom to pass to subsequences. Because of this, though, it is best not to combine cheap nonstandard analysis with any advanced set theory unless one knows exactly what one is doing, as one can get quite confused if one is not already experienced in both set theory and nonstandard analysis. (In such circumstances, it is best to instead use fully nonstandard analysis, which can treat the nonstandard universe as an actual set rather than a “potential” one.)

Example 1 Suppose ${x_1, x_2, \ldots}$ is a bounded sequence of real numbers, with the uniform upper bound ${|x_{\bf n}| \leq M}$ for all ${{\bf n}}$ . Then one can interpret ${x = x_{\bf n}}$ as a single nonstandard real, while the bound ${M}$ remains a standard real. Note the slight conceptual distinction between the cheap nonstandard approach of treating ${x}$ as a single nonstandard object, and the classical approach of treating ${x}$ as a sequence of standard objects. This distinction is analogous the distinction between treating a random variable as a single probabilistic object (as is done in probability theory), as opposed to a measurable function mapping the underlying measure space to a deterministic range space (which is the viewpoint taken in measure theory). The two viewpoints are mathematically equivalent, but can lead to somewhat different ways of thinking about such objects.

Example 2 In graph theory, an expander family is a sequence of finite graphs ${G_{\bf n} = (V_{\bf n}, E_{\bf n})}$ which have uniform edge expansion in the following sense: there exists an ${\epsilon>0}$ independent of ${{\bf n}}$ , such that for any ${{\bf n}}$ and any subset ${A_{\bf n}}$ of ${V_{\bf n}}$ of size at most ${|V_{\bf n}|/2}$ is adjacent to at least ${\epsilon |A_{\bf n}|}$ other vertices in ${V_{\bf n}}$ . Adopting a cheap nonstandard analysis perspective, one can view this expander family as a single cheap nonstandard graph ${G = (V,E)}$ (with a cheap nonstandard finite vertex set ${V = V_{\bf n}}$ and edge set ${E = E_{\bf n}}$ , while the expansion constant ${\epsilon}$ remains a standard real number.

Example 3 In the above two examples, the asymptotic parameter ${{\bf n}}$ was already inherent in the mathematical structure being studied. In other situations, there is initially no asymptotic parameter present, but one can be created by arguing by contradiction and selecting a sequence of counterexamples (in some cases, this requires countable version of the axiom of choice). For instance, suppose one has a (standard) function ${F: X \rightarrow {\bf R}}$ on some domain ${X}$ , and one wishes to show that ${F}$ is bounded. If ${F}$ were not bounded, then for each natural number ${{\bf n}}$ one could find a point ${x_{\bf n}}$ in the domain with ${|F(x_{\bf n})| \geq {\bf n}}$ ; one can then collect all of these standard points ${x_{\bf n}}$ together to form a cheap nonstandard point ${x}$ , with the property that ${F(x)}$ is unbounded (we will define what this means shortly). Taking contrapositives, we see that to show that ${F}$ is a bounded function, it suffices to show that ${F(x)}$ is bounded for each cheap nonstandard point ${x}$ in ${X}$ .

We will only be interested in the behaviour of cheap nonstandard mathematical objects ${x = x_{\bf n}}$ in the asymptotic limit ${{\bf n} \rightarrow \infty}$ . To this end, we will reserve the right to delete an arbitrary finite number of values from the domain ${\Sigma}$ of the parameter ${{\bf n}}$ , and work only with sufficiently large choices of this parameter. In particular, two nonstandard objects ${x = x_{\bf n}}$ , ${y = y_{\bf n}}$ will be considered equal if one has ${x_{\bf n} = y_{\bf n}}$ for all sufficiently large ${{\bf n}}$ . (This is where the Frechet filter is implicitly coming into play.)

Any operation which can be applied to standard objects ${x}$ , can also be applied to cheap nonstandard objects ${x = x_{\bf n}}$ by applying the standard operation separately for each choice of asymptotic parameter ${{\bf n}}$ in the current domain ${\Sigma}$ , with no interaction between different values of the asymptotic parameter. For instance, the sum ${x+y}$ of two cheap nonstandard reals ${x = x_{\bf n}}$ and ${y = y_{\bf n}}$ is given by ${(x+y)_{\bf n} := x_{\bf n} + y_{\bf n}}$ . Similarly, if ${f = f_{\bf n}: X_{\bf n} \rightarrow Y_{\bf n}}$ is a cheap nonstandard function from a cheap nonstandard set ${X = X_{\bf n}}$ to another cheap nonstandard set ${Y = Y_{\bf n}}$ , and ${x = x_{\bf n}}$ is a cheap nonstandard element of ${X}$ (thus ${x_{\bf n}}$ is an element of ${X_{\bf n}}$ for all ${{\bf n}}$ in the current parameter space ${\Sigma}$ ), then ${f(x)}$ is the cheap nonstandard element defined by ${f(x)_{\bf n} := f_{\bf n}(x_{\bf n})}$ . Since every standard function is also a nonstandard function, this also defines ${f(x)}$ when ${f}$ is standard and ${x}$ is nonstandard, and also vice versa.

(Again, one should note the analogy here with probability theory; any operation that can be applied to deterministic objects, can also be applied to probabilistic objects, by applying the deterministic operation to each individual point in the event space separately. For instance, the sum of two random variables ${X+Y}$ is defined by the formula ${(X+Y)(\omega) := X(\omega)+Y(\omega)}$ for all points ${\omega}$ in the event space. Because of things like this, the event parameter ${\omega}$ can usually be suppressed entirely from view when doing probability, and similarly the parameter ${{\bf n}}$ can also usually be suppressed from view when performing cheap nonstandard analysis.)

Similarly, any relation or predicate which can be applied to standard objects, can be applied to cheap nonstandard objects, with the relation or predicate considered to be true for some cheap nonstandard objects if it is true for all sufficiently large values of the asymptotic parameter (in the current domain ${\Sigma}$ ). For instance, given two nonstandard real numbers ${x = x_{\bf n}}$ and ${y = y_{\bf n}}$ , we say that ${x>y}$ if one has ${x_{\bf n} > y_{\bf n}}$ for all sufficiently large ${{\bf n}}$ . Similarly, we say that the relation is false if it is false for all sufficiently large values of the asymptotic parameter.

It is here that we run into the main defect of the cheap version of nonstandard analysis: it is possible for a statement concerning cheap nonstandard objects to neither be fully true nor fully false, but instead merely being both potentially true and potentially false. (Again, this is in analogy with probability theory, in which a probabilistic statement need not be almost surely true or almost surely false, but could instead be true with positive probability and also false with positive probability.) For instance, using the natural numbers ${{\bf N}}$ as the initial domain of the asymptotic parameter, the nonstandard real number ${x = x_{\bf n} := (-1)^{\bf n}}$ is neither positive, negative, nor zero, because none of the three statements ${(-1)^{\bf n} > 0}$ , ${(-1)^{\bf n} < 0}$ , or ${(-1)^{\bf n} = 0}$ are true for all sufficiently large ${{\bf n}}$ . However, if one restricts the asymptotic parameter to the even integers, then this real number ${x}$ becomes positive, while if one restricts the asymptotic parameter instead to the odd integers, then the real number becomes negative. Until we make such a restriction, though, we cannot assign a definite truth value to statements such as “ ${x}$ is positive”, and so we must accept the existence of statements in cheap nonstandard analysis whose truth value is currently indeterminate, although once the truth value does become determinate, it remains that way under any further refinement of the underlying domain ${\Sigma}$ . (This problem is precisely what is rectified by the use of an ultrafilter in fully nonstandard analysis, as ultrafilters always contain exactly one of a given subset of ${{\bf N}}$ and its complement.) But there is certainly substantial precedent in mathematics for reasoning with statements with an indeterminate truth value: probability theory, intuitionistic logic, and modal logic, for instance, all contain this issue in some shape or form.

Despite this indeterminacy, we still largely retain the fundamental transfer principle of nonstandard analysis: many statements of first-order logic which are true (resp. false) when quantified over standard objects, remain true (resp. false) when quantified over nonstandard objects, regardless of what the current value of the domain ${\Sigma}$ of the asymptotic parameter is. For instance, addition and multiplication are commutative and associative for the standard real numbers, and thus for the cheap nonstandard real numbers also, as can be easily verified after a moment’s thought. Because of the lack of the law of excluded middle, though, sometimes one has to take some care in phrasing statements properly before they will transfer. For instance, the statement “If ${xy=0}$ , then either ${x=0}$ or ${y=0}$ ” is of course true for standard reals, but not for nonstandard reals; a counterexample can be given for instance by ${x_{\bf n} := 1 + (-1)^{\bf n}}$ and ${y_{\bf n} := 1 - (-1)^{\bf n}}$ . However, the rephrasing “If ${x \neq 0}$ and ${y \neq 0}$ , then ${xy \neq 0}$ ” is true for nonstandard reals (why?). As a rough rule of thumb, as long as the logical connectives “or” and “not” are avoided, one can transfer standard statements to cheap nonstandard ones, but otherwise one may need to reformulate the statement first before transfer becomes possible. Even when one’s statements do contain an “or” or a “not”, one can often still recover a nonstandard formulation after invoking the freedom to pass to a subsequence. For instance, “If ${xy=0}$ , then after passing to a subsequence if necessary, either ${x=0}$ or ${y=0}$ ” is a true statement in cheap nonstandard analysis (why? this is basically the infinite pigeonhole principle). Note that for fully nonstandard analysis, one does not need to be so careful with transfer, as all first-order statements transfer properly (this fact is known as Los’s theorem).

We also retain a version of the equally fundamental countable saturation property of nonstandard analysis, although the cheap version is often referred to instead as the Arzelá-Ascoli diagonalisation argument. Let us call a nonstandard property ${P(x)}$ pertaining to a nonstandard object ${x}$ satisfiable if, no matter how one restricts the domain ${\Sigma}$ from its current value, one can find an ${x}$ for which ${P(x)}$ becomes true, possibly after a further restriction of the domain ${\Sigma}$ . The countable saturation property is then the assertion that if one has a countable sequence ${P_1, P_2, \ldots}$ of properties, such that ${P_1(x),\ldots,P_n(x)}$ is jointly satisfiable for any finite ${n}$ , then the entire sequence ${P_1(x), P_2(x), \ldots}$ is simultaneously satisfiable. The proof proceeds by mimicking the diagonalisation component of the proof of the Arzelá-Ascoli theorem, which explains the above terminology.

— 2. Asymptotic notation —

Thus far, there has been essentially no interaction between different choices of the parameter ${{\bf n}}$ . In classical analysis, such an interaction is obtained by the device of introducing the limit ${\lim_{{\bf n} \rightarrow \infty} x_{\bf n}}$ of a convergent sequence, and also by introducing asymptotic notation such as ${O()}$ and ${o()}$ which tracks the dependence of various bounds on the parameter ${{\bf n}}$ . These devices can be easily translated to the cheap nonstandard analysis setting without much difficulty, as follows.

Firstly, given two cheap nonstandard numbers ${X = X_{\bf n}}$ and ${Y = Y_{\bf n}}$ , we may write ${X = O(Y)}$ (or ${X \ll Y}$ , or ${Y \gg X}$ ) if one has ${|X| \leq CY}$ for some standard real number ${C>0}$ (or equivalently, if ${|X_{\bf n}| \leq C Y_{\bf n}}$ for all sufficiently large ${n}$ ). Similarly, we write ${X = o(Y)}$ if one has ${|X| \leq \epsilon Y}$ for every standard real number ${\epsilon>0}$ (or equivalently, if ${|X_{\bf n}| \leq c({\bf n}) Y_{\bf n}}$ for all ${{\bf n}}$ and some quantity ${c({\bf n})}$ that goes to zero as ${{\bf n} \rightarrow \infty}$ ). Note that these conventions are essentially the same as the usual asymptotic notation (except that sometimes the bound for the ${O()}$ notation is required to hold for all ${{\bf n}}$ , rather than merely for sufficiently large ${{\bf n}}$ ).

A cheap nonstandard quantity ${X}$ is said to be bounded if one has ${X=O(1)}$ , and infinitesimal if ${X=o(1)}$ .

Many quantitative statements about standard objects can be converted into equivalent qualitative statements about cheap nonstandard objects. We illustrate this with some simple examples.

Exercise 1 (Boundedness) Let ${f: X \rightarrow {\bf R}}$ be a standard function. Show that the following are equivalent:

(Quantitative standard version) There exists a standard ${M>0}$ such that ${|f(x)| \leq M}$ for all standard ${x \in X}$ .

(Quantitative nonstandard version) There exists a standard ${M>0}$ such that ${|f(x)| \leq M}$ for all nonstandard elements ${x}$ of ${X}$ .

(Qualitative nonstandard version) ${f(x)}$ is bounded for each nonstandard element ${x}$ of ${X}$ .

(Qualitative subsequential nonstandard version) For each nonstandard element ${x}$ of ${X}$ , ${f(x)}$ is bounded after passing to a subsequence.

Call two nonstandard elements ${x, y}$ of a standard metric space ${(X,d)}$ infinitesimally close if ${d(x,y)=o(1)}$ .

Exercise 2 (Continuity) Let ${f: X \rightarrow {\bf R}}$ be a standard function on a standard metric space ${X = (X,d)}$ . Show that the following are equivalent:

(Standard version) ${f}$ is continuous.

(Nonstandard version) If ${x}$ is a standard element of ${X}$ and ${y}$ is a cheap nonstandard element that is infinitesimally close to ${x}$ , then ${f(y)}$ is infinitesimally close to ${x}$ .

(Subsequential nonstandard version) If ${x}$ is a standard element of ${X}$ and ${y}$ is a cheap nonstandard element that is infinitesimally close to ${f(x)}$ , then ${f(y)}$ is infinitesimally close to ${f(x)}$ after passing to a subsequence.

Exercise 3 (Uniform continuity) Let ${f: X \rightarrow {\bf R}}$ be a standard function on a standard metric space ${X = (X,d)}$ . Show that the following are equivalent:

(Standard version) ${f}$ is uniformly continuous.

(Nonstandard version) If ${x}$ is a nonstandard element of ${X}$ and ${y}$ is a cheap nonstandard element that is infinitesimally close to ${x}$ , then ${f(y)}$ is infinitesimally close to ${x}$ .

(Subsequential nonstandard version) If ${x}$ is a nonstandard element of ${X}$ and ${y}$ is a cheap nonstandard element that is infinitesimally close to ${x}$ , then ${f(y)}$ is infinitesimally close to ${x}$ after passing to a subsequence.

Exercise 4 (Differentiability) Let ${f: {\bf R} \rightarrow {\bf R}}$ and ${f': {\bf R} \rightarrow {\bf R}}$ be standard functions. Show that the following are equivalent:

(Standard version) ${f}$ is everywhere differentiable, with derivative ${f'}$ .

(Nonstandard version) If ${x}$ is a standard real and ${h}$ is infinitesimal, then ${f(x+h) = f(x)+hf'(x) + o(h)}$ .

(Subsequential nonstandard version) If ${x}$ is a standard real and ${h}$ is infinitesimal, then ${f(x+h) = f(x)+hf'(x) + o(h)}$ after passing to a subsequence.

One nice feature about nonstandard analysis is that it tends to automatically perform “epsilon management”, in that it tends to correctly figure out on its own what parameters are allowed to depend on what other parameters. Let us illustrate this with an simple example:

Exercise 5 Let ${P(d,n,m)}$ be a predicate depending on three natural numbers ${d,n,m}$ . Show that the following are equivalent:

(Standard version) For every standard ${d \in {\bf N}}$ , there exists a standard constant ${C_d>0}$ , such that for every ${n \in {\bf N}}$ , there exists ${m}$ with ${m \leq C_d n}$ such that ${P(d,n,m)}$ holds.

(Nonstandard version) For every standard natural number ${d}$ and cheap nonstandard natural number ${n}$ , there exists a cheap nonstandard natural number ${m = O(n)}$ such that ${P(d,n,m)}$ holds.

Furthermore, show that requiring in the standard version that the constant ${C_d}$ is actually uniform in ${d}$ is equivalent to allowing ${d}$ to be nonstandard rather than standard in the nonstandard version.

As a consequence, the asymptotic notation in a nonstandard argument tends to be slightly simpler than in a standard counterpart; whereas in the standard world one usually has to subscript the asymptotic notation by various parameters (e.g. the bound ${m \leq C_d n}$ in the above exercise could be written instead as ${m=O_d(n)}$ ), the subscripting is done automatically once one decides which variables are standard and which ones are nonstandard.

If a nonstandard real ${x}$ is of the form ${y+o(1)}$ for some standard real ${y}$ , we call ${y}$ the standard part of ${x}$ and write ${y = \hbox{st}(x)}$ ; viewing ${x}$ as a sequence ${x_{\bf n}}$ , we see that this occurs precisely when the sequence ${x_{\bf n}}$ converges to ${y}$ as ${{\bf n} \rightarrow \infty}$ . But because not all sequences are convergent, not all cheap nonstandard reals have a standard part. However, thanks to the Bolzano-Weierstrass theorem, we know that any bounded nonstandard number ${x}$ will have a standard part after passing to a subsequence; more generally, we can extract a standard part from any nonstandard object lying in a sequentially compact set by passing to a subsequence.

We can then reformulate many basic compactness arguments in analysis using this observation (at least if the topologies involved are sufficiently non-pathological that they can be accurately probed by sequences). For instance, let us give the cheap non-standard proof that a continuous function ${f: X \rightarrow {\bf R}}$ on a compact metric space is bounded. By Exercise 1, it suffices to show that ${f(x)}$ is bounded for every nonstandard element ${x}$ of ${X}$ after passing to a subsequence. But by the Bolzano-Weierstrass theorem, ${x}$ has a standard part ${y}$ ; by continuity, ${f(x)}$ is then infinitesimally close to ${f(y)}$ . But ${f(y)}$ is standard, and so ${f(x)}$ is bounded as well.

Exercise 6 Give a cheap nonstandard analysis proof of the fact that on a compact domain, every continuous function is uniformly continuous.

Readers who are familiar with traditional real analysis will note that the above proofs are basically just very lightly disguised versions of the usual sequence-based traditional proofs. Indeed, cheap nonstandard analysis is very close to sequence-based analysis (much as probability theory is very close to measure theory), and it is easy to translate from one to the other. (Fully nonstandard analysis is a bit different in this regard, because it relies on ultralimits rather than classical limits, but it is still analogous in many ways to sequence-based analysis.)

Filed under: expository, math.CA, math.LO Tagged: Bolzano-Weierstrass theorem, nonstandard analysis, sequential compactness