The method used to construct an internal subset of *IR out of a sequence of subsets of lR will now be adapted to build hyperreal-valued functions out of sequences of real-valued functions. 12.1 Internal Functions Let Un : n EN) be a sequence of functions fn :Ano---+ IR, with domains An included in R Then a *JR-valued function [fn] is defined on the internal set [An] by putting Observe that if [rn] E [An], then the set J = {n EN: rn E An} belongs to F, and for each n E J, fn(rn) is defined. This is enough to make [fn]([rn]) well-defined. We have dom [fn] = [domfn]· Functions f : X ---+ *JR that are obtained by this construction are called internal. In the case that Un) is a constant sequence, with fn = f : Ao---+ lR for all n, then (fn] is just the function *f : *A ---+ *JR extending f, as defined in Section 3.13. The following result shows that we only need to specify almost all of the real functions fn in order to determine the internal function [fn]· Theorem 12.1.1 Let Un : n EN) and (gn : n EN) be sequences ofpartial functions from lR to JR. Then the internal functions [fn] and [gn] are equal 148 12. Internal Functions and Hyperfinite Sets if and only if {n EN: fn = gn} E :F. Proof. Let Jfg = {n E N : fn = gn}, and suppose Jfg E :F. Now in general, two functions are equal precisely when they have the same domain and assign the same values to all members of that domain. Thus Jfg {n EN: domnfn = domgn}, leading by 11.2(3) to the conclusion that the internal sets [dom f] and [domgn) are equal, i.e., dom (fn] = dom (gn]· But for [rn] E dom [fnJ, which leads to [fn]([rn]) = [gn)([rn]). Hence [fn] = [9n]· For the converse, suppose that Jfg :F. Now, Jjg is a subset of the union {n EN: domnfn f domgn} U {n EN: domnfn = domngn but fn f 9n}, so either {no: domfn f domgn} E :F, whence dom [fn] f dom [gn] and so [fn] f [gn], or else J = {n EN: domnfn = domgn but fn f gn} E :F. But for n E J there exists some rn with fn(rn) f gn(rn)· This leads to [fn]([rn]) f [gn]([rn]), and SO [fn] f [gn]· D 12.2 Exercises on Properties of Internal Functions (1) The image of an internal set under an internal function is internal: iff= [fn] is an internal function, and A= [An] is any internal subset of dom f, then the image set f(A) = {f(a)o: a E A} is in fact the internal set [f n (An)]. (2) The inverse image of an internal set under an internal function is internal: if f = [fn] is an internal function, and B = [Bn] is an internal set, then the inverse-image set f-1(B) ={a E domfn: f(a) E B} is the internal set [f;1( Bn) ]. 12.3 Hyperfinite Sets 149 (3) The composition of internal functions is internal: ifnf and g are internal functions, with the range ofnf included in the domain of g, then g o f is an internal function. (4) An internal function (fn] is injective iff {n EN: fn is injective} E :F. (5) The inverse of an internal function is internal: if [fn] is injective, then [fnt1 is the internal function [f,-;-1] (which is well-defined by the previous exercise and Theorem 12.1.1). (6) Ifnf and g are internal functions (with the same domain), then so are the functions f + g, f · g, and cf for any hyperreal c. (7) Let f be an internal function that takes only infinitesimal values: f(x) 0 whenever f(x) is defined. Show that the range {f(x) : x E dom f} of f has an infinitesimal least upper bound. (8) Give an alternative proof that every infinite subset of lR is external (Section 11.7), by using Exercise 1 in place of the internal set definition principle. 12.3 Hyperfini te Sets If An is finite for (almost) all n EN, then [An] may nevertheless be infinite (and then in fact uncountable!) but will have many properties that are similar to those of finite sets. Thus an internal set A = [An] is called hyperfinite if almost all An's are finite, i.e., if {n EN: An is finite} E :F. In that case, by 11.2(3) we may as well assume that all An's are finite and have finite integer size JAnl· The internal cardinality (or size) of A is then defined to be the hyperinteger IAI = [(JAnl: n EN)]n. (More succinctly, I [An] I = [ IAnJ].) For example: • Let An = {1, ... , n} N. The resulting hyperfinite set A includes N. Being internal, it must therefore be an uncountable subset of *N. To see that N A, observe that if m EN, then the set { n E N : m E An} is co finite, being equal to {m, m + 1, ... } , so belongs to :F. Hence *moE A. • Refining the previous example, we see that if B is any countable subset of JR, then there exists a hyperfinite set A with B A *B. *k E Z and 0 ::; k ::; N = 0, N, NN ' ( b *k E Z and 0 ::; k ::; N = 0, N, NN ' ( b 150 12. Internal Functions and Hyperfinite Sets For if B = {xn : n EoN}, let A= [An] where Ano= {xi, ... ,Xn}· In this case the internal size of A is w = [(1, 2, 3, ... ) ]. Later we will see that the restriction to countability here can be removed: any subset B of lR has a "hyperfinite approximation" A satisfying B A *B (cf. Sections 14.1 and 14.2). • Any finite set ofhyperreals is hyperfinite: as observed in Section 11.1, if X = {[r;], An = {r;, ... , r}. • If N = [Nn] E *N, then the set {k E *N: k::; N} = {1, 2, ... , N} discussed in Section 11.1 is hyperfinite and has internal cardinality N, since it is equal to [An], where An = {1, 2, ... , Nn} and IAnl = Nn. • If N = [Nn] E *N, then the set ... , [rl} *JR, then X is the hyperfinite set [An], where { k } { 1 is hyperfinite of internal cardinality N + 1, since it is equal to [An], where { 1 2 Nn-1 } Ano= 0'o,1 . ' , NnNn'''oNn • The last example is a special case of the fact that for any hyperreals a, b, and any N E *N, the uniform partition {a + k a) : k E *Z and 0 ::; k ::; N} is hyperfinite of internal cardinality N + 1. 12.4 Exercises on Hyperfiniteness (1) Any hyperfinite set has a greatest and a least element. (2) The union and intersection of any two hyperfinite sets X and Y are hyperfinite, with IX u Yl = lXI + IYIo-IX nYI. (3) Any internal subset of a hyperfinite set is hyperfinite. } 2 N-1 12.6 Hyperfinite Pigeonhole Principle 151 12.5 Counting a Hyperfinite Set The above results are indicative of ways in which hyperfinite sets behave like finite sets. More fundamentally, a finite set can be defined as one that has n elements for some n EN, and so is in bijective correspondence with the set {1, ... , n}. Correspondingly, for hyperfinite sets we have Theorem 12.5.1 An internal set A is hyperfinite with internal cardinality N if and only if there is an internal bijection f: {1, ... , N} A. Proof Let A = [An]· If A is hyperfinite with internal cardinality N = [Nn], then we may suppose that for each n E N, An is a finite set of cardinality Nn. Thus there is a bijection In : {1, ... , Nn} An. Let f = [fn]· Then f is an internal function with domain {1, ... , N} that is injective (12.2(4)) and has range A (12.2(1)). Conversely, suppose that f = [/n] is an internal bijection from {1, ... , N} onto A. Then [domfn] = dom [/n] = {1, ... , N} = [{1, ... , Nn}J, so for F-almost all n, domnfn = {1, ... ,Nn}· (i) Also, as A is the image of {1, ... , N} under [fn], Exercise 12.2(1) implies that A= [fn( {1, ... , Nn} )], SO (ii) for F-almost all n. Finally, by 12.2(4), In is injective (iii) for .1'-almost all n. Then the set J of those n E N satisfying (i)-(iii) must belong to .1'. But for n E J, An is finite of cardinality Nn. Hence A is hyperfinite of internal cardinality N. D An important feature of this result is that it gives a characterisation of hyperfinite sets that makes no reference to the ultrafilter .1', but requires only the hypernatural numbers *N and the notion of an internal function. This approach will be revisited in Section 13.17. 12.6 Hyperfinite Pigeonhole Principle One classical way to distinguish the finite from the infinite is to characterise the infinite sets as those that are equinumerous with a proper subset of 152 12. Internal Functions and Hyperfinite Sets themselves. Thus A is infinite iff there is an injection f: Ao---+ A whose range f(A) is a proper subset of A. Equivalently, A is finite iff every injection f : A ---+ A mapping A into itself is surjective, i.e., has f(A) = A (this latter statement is known as the pigeonhole principle). Correspondingly, we have the following characterisation of hyperfiniteness. Theorem 12.6.1 An internal set A = [An] is hyperfinite if and only if every injective internal function f whose domain includes A and has f(A) A must in fact have f(A) =A. Proof Suppose A is hyperfinite. Let f [fn] be an internal injective function with A dom f and f (A) A. Then each of the following is true for F-almost all n E .N: An is finite, Ann domfn, fn(An) An, cf. 12.2(1), 11.2(2) f n is injective. Thus the set J of those n E .N satisfying all of these conditions must belong to F. But J { n E N : f n (An) = An} by the standard pigeonhole principle, and so f(A) = [fn(An)] =o[An] =A. For the converse, suppose A is not hyperfinite. It follows that J' = {n EN: An is infinite} E F. But for each n E J' there is an injective function fn : An ---+An and some Tn E Ano-fn(An)oLet f = [fnloThis makes f an internal function with · · domain A that is injective (12.2(4)) and has f(A) = [fn(An)] nA, while [rn] E A-f(A) and so f(A) f. A. -0 Here now is an example of a noninternal function: if n EN, f(n) = { n if n rf. N. This function maps the internal set *N injectively into, but not onto, itself. Hence by the hyperfinite pigeonhole principle (Theorem 12.6.1), f cannot be internal. 12.7 Integrals as Hyperfinite Sums The operation of forming the sum of finitely many numbers can be extended to hyperfinitely many. More generally, we can define the sum over a hyperfinite set of the values of an internal function. 12.7 Integrals as Hyperfinite Sums 153 To see this, if X is a finite set, let the symbol LxEX g(x) denote the sum of the members of {g(x) : x E X}. Then if A = [An] is a hyperfinite set included in the domain of an internal function f = [fn], define LxEA f(x) to be the hyperreal number [rn] given by Tn = LxEAn fn(x). This makes sense because for F-almost all n we have An a finite subset of domnfn· Thus LxE[An][fn](x) = [LxEAn fn(x)] · This operation has many of the properties familiar from finite summations: if J, g are internal functions, A, B are hyperfinite sets, and c E *JR., then: • LxEA cf(x) = C (LxEA f(x)). • LxEA f(x) + g(x) = LxEA f(x) + LxEAg(x). • LxEAUBf(x) = LxEA f(x) + LxEB f(x) if A and Bnare disjoint. • LxEA These are analogues of familiar properties of integrals (cf. Section 9.3). We will now see that standard integrals can be realised as hyperfinite Riemann sums over hyperfinite partitions. Let f : [a, b] --+JR. be an integrable function on the closed interval [a, b] R Take a positive infinitesimal L:lx = [c:n]· Then for each n E N we inay assume that C:n is a positive real number less than b-a. Let Pn U {b} be the finite partition of [a, b] into subintervals of width C:n-Thus if Pn is of size Nn, we have the description Pn ={a+ kc:n: k E Z and 0 k < Nn}· Let P be the hyperfinite set [Pn], of internal size N = [Nn] E *N. Then in fact, P ={a+ k.Llxo: k E *Z and 0 k < N}, so PU {b} is a hyperfinite partition of [a, b] into subintervals of infinitesimal width L:lx. Now, the original function f lifts to the internal function [fn] : *[a, b] --+ *JR. determined by the constant sequence of functions f n = f. We continue to use the symbol "!" for this extended function. Its domain includes P, so the hyperfinite sum LxEPf(x) is specified as the hyperreal number [(LxEP1 f(x), LxEP2 f(x), .)] · · · 154 12. Internal Functions and Hyperfinite Sets Thus LxEP f(x) = LxEPn f(x)] [ · The ordinary Riemann sum for the real partition Pn U {b} was defined in Section 9.1 as the number But the sequence of numbers (S(f,en) : n E N) determines a hyperreal, which by definition is the extension of the function s (!, -) to the hyperreal [en]o= Llx: S(f, Llx) = [S(f,en)]. Thus we calculate S(f, Llx) [(LxEPn f(x)) en] [LxEPn f(x)] [en] (LxEP f(x)) Llx LxEPf(x)Llx, showing that the hyperreal number s (!, Llx)odefined formally by the ex ' tension process of Section 3.13, can be viewed as the (extended) ordinary Riemann sum of the hyperfinite partition P. Finally, from the analysis in Section 9.2 of the Riemann integral as a shadow of Riemann sums we get that for any positive infinitesimal Llx, 1bf(x)dx = sh (S(f, Llx)) = sh (LxEPf(x)Llx)o. Exercise 12.7.1 Verify that each member of the hyperfinite set P has the form a+kLlx for some nonnegative hyperinteger k < N.