Nonstandard Analysis

Abstract

If one wants to present the methods of nonstandard analysis in their full generality and with full rigor, then notions and tools from mathematical logic such as “first-order formula” or “elementary extension” are definitely needed. However, we believe that a gentle introduction to the basics of nonstandard methods and their use in combinatorics does not directly require any technical machinery from logic. Only at a later stage, when advanced nonstandard techniques are applied and their use must be put on firm foundations, detailed knowledge of notions from logic will be necessary.

If one wants to present the methods of nonstandard analysis in their full generality and with full rigor, then notions and tools from mathematical logic such as “first-order formula” or “elementary extension” are definitely needed. However, we believe that a gentle introduction to the basics of nonstandard methods and their use in combinatorics does not directly require any technical machinery from logic. Only at a later stage, when advanced nonstandard techniques are applied and their use must be put on firm foundations, detailed knowledge of notions from logic will be necessary.

We will begin with presenting the main properties of the nonstandard versions of the natural, integer, rational, and real numbers, which will be named by adding the prefix “hyper”. Then we will introduce the fundamental principle of nonstandard analysis, namely the transfer principle of the star map. While at this stage the treatment will still be informal, it will still be sufficient for the reader to gain a first idea of how nonstandard methods can be used in applications.

In the Appendix, we give sound and rigorous foundations to nonstandard analysis in full generality by formally introducing first order logic. The reader already familiar with nonstandard methods can proceed directly to the next chapter.

1 Warming-Up

To begin with, let us recall the following notions, which are at the very base of nonstandard analysis.

Definition 2.1

An element ε of an ordered field $\mathbb {F}$ is infinitesimal (or infinitely small) if $- \frac {1}{n}<\varepsilon <\frac {1}{n}$ for every $n\in \mathbb {N}$. A number Ω is infinite if either Ω > n for every $n\in \mathbb {N}$ or Ω < −n for every $n \in \mathbb {N}$.

In Definition 2.1 we identify a natural number n with the element of $\mathbb {F}$ obtained as the n-fold sum of 1 by itself. Clearly, a nonzero number is infinite if and only if its reciprocal is infinitesimal. We say that a number is finite or bounded if it is not infinite.

Exercise 2.2

• 1. If ξ and ζ are finite, then ξ + ζ and ξ ⋅ ζ are finite.

• 2. If ξ and ζ are infinitesimal , then ξ + ζ is infinitesimal.

• 3. If ξ is infinitesimal and ζ is finite, then ξ ⋅ ζ is infinitesimal.

• 4. If ξ is infinite and ζ is not infinitesimal, then ξ ⋅ ζ is infinite.

• 5. If ξ is infinitesimal and ζ is not infinitesimal, then ξ∕ζ is infinitesimal.

• 6. If ξ is infinite and ζ is finite, then ξ∕ζ is infinite.

Recall that an ordered field $\mathbb {F}$ is Archimedean if for every positive $x\in \mathbb {F}$ there exists $n\in \mathbb {N}$ such that nx > 1.

Exercise 2.3

The following properties are equivalent for an ordered field $\mathbb {F}$ :

• 1. $\mathbb {F}$ is non-Archimedean;

• 2. There are nonzero infinitesimal numbers in $\mathbb {F}$;

• 3. The set of natural numbers has an upper bound in $\mathbb {F}$.

We are now ready to introduce the nonstandard reals.

Definition 2.4

The hyperreal field ${ }^{\ast }\mathbb {R}$ is a proper extension of the ordered field $\mathbb {R}$ that satisfies additional properties (to be specified further on). The element of ${ }^{\ast }\mathbb {R}$ are called hyperreal numbers.

By just using the above incomplete definition, the following is proved.

Proposition 2.5

The hyperreal field ${ }^{\ast }\mathbb {R}$ is non-Archimedean, and hence it contains nonzero infinitesimals and infinite numbers .

Proof

Since ${ }^{\ast }\mathbb {R}$ is a proper extension of the real field, we can pick a number $\xi \in { }^{\ast }\mathbb {R}{\setminus }\mathbb {R}$. Without loss of generality, let us assume ξ > 0. If ξ is infinite, then we are done. Otherwise, by the completeness property of $\mathbb {R}$, we can consider the number $r=\inf \{x\in \mathbb {R}\mid x>\xi \}$. (Notice that it may be r < ξ.) It is readily checked that ξ − r is a nonzero infinitesimal number.

We remark that, as a non-Archimedean field , ${ }^{\ast }\mathbb {R}$ is not complete (e.g., the set of infinitesimals is bounded but has no least upper bound). We say that two hyperreal numbers are infinitely close if their difference is infinitesimal. The nonstandard counterpart of completeness is given by the following property.

Theorem 2.6 (Standard Part)

Every finite hyperreal number $\xi \in { }^{\ast }\mathbb {R}$ is infinitely close to a unique real number $r\in \mathbb {R}$ , called the standard part of ξ. In this case, we use the notation $r=\operatorname {st}(\xi )$.

Proof

By the completeness of $\mathbb {R}$, we can set $\operatorname {st}(\xi ):=\inf \{x\in \mathbb {R}\mid x>\xi \}=\sup \{y\in \mathbb {R}\mid y<\xi \}$. By the supremum (or infimum) property, it directly follows that $\operatorname {st}(\xi )$ is infinitely close to ξ. Moreover, $\operatorname {st}(\xi )$ is the unique real number with that property, since infinitely close real numbers are necessarily equal.

It follows that every finite hyperreal number ξ has a unique representation in the form ξ = r + ε where $r=\operatorname {st}(\xi )\in \mathbb {R}$ and ε is infinitesimal . By definition of standard part, $\xi \in { }^{\ast }\mathbb {R}$ is infinitesimal if and only if $\operatorname {st}(\xi )=0$. Given finite hyperreals ξ and ζ, it is sometimes convenient to write ξ ≳ ζ to mean $\operatorname {st}(\xi )\geq \operatorname {st}(\zeta )$.

The following are the counterparts in the nonstandard setting of the familiar properties of limits of real sequences.

Exercise 2.7

For all finite hyperreal numbers ξ, ζ:

• 1. $\operatorname {st}(\xi )<\operatorname {st}(\zeta )\Rightarrow \xi <\zeta \Rightarrow \operatorname {st}(\xi )\le \operatorname {st}(\zeta )$;

• 2. $\operatorname {st}(\xi +\zeta )=\operatorname {st}(\xi )+\operatorname {st}(\zeta )$;

• 3. $\operatorname {st}(\xi \cdot \zeta )=\operatorname {st}(\xi )\cdot \operatorname {st}(\zeta )$;

• 4. $\operatorname {st}(\frac {\xi }{\zeta })=\frac {\operatorname {st}(\xi )}{\operatorname {st}(\zeta )}$ whenever ζ is not infinitesimal .

Definition 2.8

The ring of hyperinteger numbers ${ }^{\ast }\mathbb {Z}$ is an unbounded discretely ordered subring of ${ }^{\ast }\mathbb {R}$ that satisfies special properties (to be specified further on), including the following:

• For every $\xi \in { }^{\ast }\mathbb {R}$ there exists $\zeta \in { }^{\ast }\mathbb {Z}$ with ζ ≤ ξ < ζ + 1. Such a ζ is called the hyperinteger part of ξ, denoted ζ = ⌊ξ⌋.

Since ${ }^{\ast }\mathbb {Z}$ is discretely ordered, notice that its finite part coincides with $\mathbb {Z}$. This means that for every $z\in \mathbb {Z}$ there are no hyperintegers $\zeta \in { }^{\ast }\mathbb {Z}$ such that z < ζ < z + 1.

Definition 2.9

The hypernatural numbers ${ }^{\ast }\mathbb {N}$ are the positive part of ${ }^{\ast }\mathbb {Z}$. Thus ${ }^{\ast }\mathbb {Z}=-{ }^{\ast }\mathbb {N}\cup \{0\}\cup { }^{\ast }\mathbb {N}$, where $-{ }^{\ast }\mathbb {N}=\{-\xi \mid \xi \in { }^{\ast }\mathbb {N}\}$ are the negative hyperintegers.

Definition 2.10

The field of hyperrational numbers ${ }^{\ast }\mathbb {Q}$ is the subfield of ${ }^{\ast }\mathbb {R}$ consisting of elements of the form $\frac {\xi }{\nu }$ where $\xi \in { }^{\ast }\mathbb {Z}$ and $\nu \in { }^{\ast }\mathbb {N}$.

Exercise 2.11

The hyperrational numbers ${ }^{\ast }\mathbb {Q}$ are dense in ${ }^{\ast }\mathbb {R}$, that is, for every pair ξ < ξ′ in ${ }^{\ast }\mathbb {R}$ there exists $\eta \in { }^{\ast }\mathbb {Q}$ such that ξ < η < ξ′.

We remark that, although still incomplete, our definitions suffice to get a clear picture of the order-structure of the two main nonstandard objects that we will consider here, namely the hypernatural numbers ${ }^{\ast }\mathbb {N}$ and the hyperreal line ${ }^{\ast }\mathbb {R}$. In particular, let us focus on the nonstandard natural numbers. One possible way (but certainly not the only possible way) to visualize them is the following:

• The hypernatural numbers ${ }^{\ast }\mathbb {N}$ are the extended version of the natural numbers that is obtained by allowing the use of a “mental telescope” to also see infinite numbers beyond the finite ones.

So, beyond the usual finite numbers $\mathbb {N}=\{1,2,3,\ldots \}$, one finds infinite numbers ξ > n for all $n\in \mathbb {N}$. Every $\xi \in { }^{\ast }\mathbb {N}$ has a successor ξ + 1, and every non-zero $\xi \in { }^{\ast }\mathbb {N}$ has a predecessor ξ − 1.

$$\displaystyle \begin{aligned}^{\ast}\mathbb{N}\ =\ \big\{\underbrace{1,2,3,\ldots,n,\ldots}_{\text{ finite numbers}} \quad \underbrace{\ldots, N-2, N-1, N, N+1, N+2, \ldots}_{\text{ infinite numbers}}\ \big\}\end{aligned}$$

Thus the set of finite numbers $\mathbb {N}$ does not have a greatest element and the set of infinite numbers ${ }^{\ast }\mathbb {N}{\setminus }\mathbb {N}$ does not have a least element, whence ${ }^{\ast }\mathbb {N}$ is not well-ordered. Sometimes we will write $\nu >\mathbb {N}$ to mean that $\nu \in { }^{\ast }\mathbb {N}$ is infinite.

Exercise 2.12

Consider the equivalence relation ∼_f on ${ }^{\ast }\mathbb {N}$ defined by setting ξ ∼_f ζ if ξ − ζ is finite. The corresponding equivalence classes are called galaxies. The quotient set ${ }^{\ast }\mathbb {N}/{\sim _f}$ inherits an order structure, which turns it into a dense linearly ordered set with least element $[1]=\mathbb {N}$ and with no greatest element.

2 The Star Map and the Transfer Principle

As we have seen in the previous section, corresponding to each of the sets $\mathbb {N}, \mathbb {Z}, \mathbb {Q}, \mathbb {R}$, one has a nonstandard extension, namely the sets ${ }^{\ast }\mathbb {N}, { }^{\ast }\mathbb {Z}, { }^{\ast }\mathbb {Q}, { }^{\ast }\mathbb {R}$, respectively. A defining feature of nonstandard analysis is that one has a canonical way of extending every mathematical object A under study to an object ^∗ A which inherits all “elementary” properties of the initial object.

Definition 2.13

The star map is a function that associates to each “mathematical object” A under study its hyper-extension (or nonstandard extension) ^∗ A in such a way that the following holds:

• Transfer principle: Let P(A ₁, …, A _n) be an “elementary property” of the mathematical objects A ₁, …, A _n. Then P(A ₁, …, A _n) is true if and only if P(^∗ A ₁, …,^∗ A _n) is true:

  $$\displaystyle \begin{aligned}\ \quad P(A_{1},\ldots,A_{n})\ \Longleftrightarrow\ P({}^{\ast}A_{1},\ldots,{}^{\ast}A_{n}).\end{aligned}$$

One can think of hyper-extensions as a sort of weakly isomorphic copy of the initial objects. Indeed, by the transfer principle , an object A and its hyper-extension ^∗ A are indistinguishable as far as their “elementary properties” are concerned. Of course, the crucial point here is to precisely determine which properties are “elementary” and which are not.

Let us remark that the above definition is indeed incomplete in that the notions of “mathematical object” and of “elementary property” are still to be made precise and rigorous. As anticipated in the introduction, we will do this gradually.

To begin with, it will be enough to include in our notion of “mathematical object” the following:

• 1. Real numbers and k-tuples of real numbers for every $k\in \mathbb {N}$;

• 2. All sets $A\subseteq \mathbb {R}^k$ of real tuples, and all functions f : A → B between them;

• 3. All sets made up of objects in (1) and (2), including, e.g., the families $\mathcal {F}\subseteq \bigcup _k\mathcal {P}(\mathbb {R}^k)$ of sets of real k-tuples, and the families of functions $\mathcal {G}\subseteq \text{Fun}(\mathbb {R}^k,\mathbb {R}^h)$.

More generally, every other structure under study could be safely included in the list of “mathematical objects”.¹

As for the notion of “elementary property”, we will start working with a semi-formal definition. Although not fully rigorous from a logical point of view, it may nevertheless look perfectly fine to many, and we believe that it can be safely adopted to get introduced to nonstandard analysis and to familiarize oneself with its basic notions and tools.

Definition 2.14

A property P is elementary if it can be expressed by an elementary formula, that is, by a formula where:

• 1. Besides the usual logical connectives (“not”, “and”, “or”, “if … then”, “if and only if”) and the quantifiers (“there exists”, “for every”) only the basic notions of equality, membership, set, ordered k-tuple, k-ary relation, domain, range, function, value of a function at a given point, are involved;

• 2. The scope of every quantifier is bounded, that is, quantifiers always occur in the form “there exists x ∈ X” or “for every y ∈ Y ” for specified sets X, Y . More generally, also nested quantifiers “Q x ₁ ∈ x ₂ and Q x ₂ ∈ x ₃ … and Q x _n ∈ X” are allowed, where Q is either “there exists” or “for every”, x ₁, …, x _n are variables, and X is a specified set.

An immediate consequence of the transfer principle is that all fundamental mathematical constructions are preserved under the star map, with the only two relevant exceptions being powersets and function sets (see Proposition 2.49). Below we give three comprehensive lists in three distinct propositions, the first one about sets and ordered tuples, the second one about relations, and the third one about functions. Until the notion of “elementary property” has been made precise, one can take those properties as axioms for the star map.

Proposition 2.15

• 1. a = b ⇔^∗ a =^∗ b.

• 2. a ∈ A ⇔^∗ a ∈^∗ A.

• 3. A is a set if and only if ^∗ A is a set.

• 4. ^∗ ∅ = ∅.

If A, A ₁, …, A _k, B are sets:

• 5. A ⊆ B ⇔^∗ A ⊆^∗ B.

• 6. ^∗(A ∪ B) =^∗ A ∪^∗ B.

• 7. ^∗(A ∩ B) =^∗ A ∩^∗ B.

• 8. ^∗(A∖B) =^∗ A∖^∗ B.

• 9. ^∗{a ₁, …, a _k} = {^∗ a ₁, …,^∗ a _k}.

• 10. ^∗(a ₁, …, a _k) = (^∗ a ₁, …,^∗ a _k).

• 11. ^∗(A ₁ ×… × A _k) =^∗ A ₁ ×… ×^∗ A _k.

• 12. ^∗{(a, a)∣a ∈ A} = {(ξ, ξ)∣ξ ∈^∗ A}.

If $\mathcal {F}$ is a family of sets:

• 13. ${ }^*\{(x,y)\mid x\in y\in \mathcal {F}\}=\{(\xi ,\zeta )\mid \xi \in \zeta \in { }^*\mathcal {F}\}$.

• 14. ${ }^*(\bigcup _{F\in \mathcal {F}}F)=\bigcup _{G\in { }^*\mathcal {F}}G$.

Proof

Recall that by our definition, the notions of equality, membership, set, and ordered k-tuple are elementary; thus by direct applications of transfer one obtains (1), (2), (3), and (10), respectively. All other properties are easily proved by considering suitable elementary formulas. As examples, we will consider here only three of them.

• (8) The property “C = A∖B” is elementary, because it is formalized by the elementary formula:

  $$\displaystyle \begin{aligned}\text{``}\forall x\in C\ (x\in A\ \text{and}\ x\notin B)\ \text{and}\ \forall x\in A\ (x\notin B\Rightarrow x\in C)\text{''}.\end{aligned}$$

  So, by transfer, we have that C = A∖B holds if and only if

  $$\displaystyle \begin{aligned}\text{``}\forall x\in {}^{\ast}C\ (x\in {}^{\ast}A\ \text{and}\ x\notin {}^{\ast}B)\ \text{and}\ \forall x\in {}^{\ast}A\ (x\notin {}^{\ast}B\Rightarrow x\in {}^{\ast}C)\text{''},\end{aligned}$$

  that is, if and only if ^∗ C =^∗ A∖^∗ B.

• (9) The property “C = {a ₁, …, a _k}” is formalized by the elementary formula: “a ₁ ∈ C and … … and a _k ∈ C and ∀x ∈ C (x = a ₁ or … or x = a _k)”. So, we can apply transfer and obtain that ^∗ C = {^∗ a ₁, …,^∗ a _k}.

• (14) The property “$A=\bigcup _{F\in \mathcal {F}}F$” is formalized by the elementary formula: “$\forall x\in A\ (\exists y\in \mathcal {F}\ \text{with}\ x\in y)\ \text{and}\ \forall y\in \mathcal {F}\ \forall x\in y\ (x\in A)$.” Then by transfer one gets “${ }^{\ast }A=\bigcup _{y\in { }^*\mathcal {F}}y$.”

Proposition 2.16

• 1. R is a k-ary relation if and only if ^∗ R is a k-ary relation.

If R is a binary relation:

• 2. ^∗{a∣∃b R(a, b)} = {ξ∣∃ζ ^∗ R(ξ, ζ)}, that is, ^∗ domain(R) = domain(^∗ R).

• 3. ^∗{b∣∃a R(a, b)} = {ζ∣∃ξ ^∗ R(ξ, ζ)}, that is, ^∗ range(R) = range(^∗ R).

• 4. ^∗{(a, b)∣R(b, a)} = {(ξ, ζ)∣^∗ R(ζ, ξ)}.

If S is a ternary relation:

• 5. ^∗{(a, b, c)∣S(c, a, b)} = {(ξ, ζ, η)∣^∗ S(η, ξ, ζ)}.

• 6. ^∗{(a, b, c)∣S(a, c, b)} = {(ξ, ζ, η)∣^∗ S(ξ, η, ζ)}.

Proof

(1), (2), and (3) are proved by direct applications of transfer, because the notions of k-ary relation, domain, and range are elementary by definition.

(4). The property “C = {(a, b)∣R(b, a)}” is formalized by the conjunction of the elementary formula “∀z ∈ C ∃x ∈domain(R) ∃y ∈range(R) s.t. R(x, y) and z = (y, x)” and the elementary formula “∀x ∈domain(R) ∀y ∈range(R) (y, x) ∈ C”. Thus transfer applies and one obtains ^∗ C = {(ξ, ζ)∣(ζ, ξ) ∈^∗ R}.

(5) and (6) are proved by considering similar elementary formulas as in (4).

Proposition 2.17

• 1. f is a function if and only if ^∗ f is a function.

If f, g are functions and A, B are sets:

• 2. ^∗ domain(f) = domain(^∗ f).

• 3. ^∗ range(f) = range(^∗ f).

• 4. f : A → B if and only if ^∗ f :^∗ A →^∗ B. ²

• 5. ^∗ graph(f) = graph(^∗ f).

• 6. ^∗(f(a)) = (^∗ f)(^∗ a) for every a ∈domain(f).

• 7. If f : A → A is the identity, then ^∗ f :^∗ A →^∗ A is the identity, that is .

• 8. ^∗{f(a)∣a ∈ A} = {^∗ f(ξ)∣ξ ∈^∗ A}, that is ^∗(f(A)) =^∗ f(^∗ A).

• 9. ^∗{a∣f(a) ∈ B} = {ξ∣^∗ f(ξ) ∈^∗ B}, that is ^∗(f ⁻¹(B)) = (^∗ f)⁻¹(^∗ B).

• 10. ^∗(f ∘ g) =^∗ f ∘^∗ g.

• 11. ^∗{(a, b) ∈ A × B∣f(a) = g(b)} = {(ξ, ζ) ∈^∗ A ×^∗ B∣^∗ f(ξ) =^∗ g(ζ)}.

Proof

(1), (2), (3), and (6) are proved by direct applications of transfer, because the notions of function, value of a function at a given point, domain, and range, are elementary. (4) is a direct corollary of the previous properties. We only prove two of the remaining properties as all of the proofs are similar to one another.

(5). The property “C = graph(f)” is formalized by the elementary formula obtained as the conjunction of the formula “∀z ∈ C ∃x ∈domain(f) ∃y ∈range(f) such that y = f(x) and (x, y) ∈ C” with the formula “∀x ∈domain(f) ∀y ∈range(f) (y = f(x) ⇒ (x, y) ∈ C)”. The desired equality follows by transfer and by the previous properties.

(10). If f : A → B and g : B → C, then the property “h = g ∘ f” is formalized by the formula “h : A → C and ∀x ∈ A ∀y ∈ C (h(x) = y ⇔∃z ∈ B f(x) = z and g(z) = y)”.

Exercise 2.18

Prove that a function f : A → B is 1-1 if and only if ^∗ f :^∗ A →^∗ B is 1-1.

We now discuss a general result about the star map that is really useful in practice (and, in fact, several particular cases have already been included in the previous propositions): If a set is defined by means of an elementary property, then its hyper-extension is defined by the same property where one puts stars in front of the parameters.

Proposition 2.19

Let φ(x, y ₁, …, y _n) be an elementary formula. For all objects B, A ₁, …, A _n one has

$$\displaystyle \begin{aligned}^*\{x\in B\mid \varphi(x,A_1,\ldots,A_n)\}\ =\ \{x\in{}^{\ast}B\mid \varphi(x,{}^{\ast}A_1,\ldots,{}^{\ast}A_n)\}.\end{aligned}$$

Proof

Since C = {x ∈ B∣φ(x, A ₁, …, A _n)}, we have that the following formula holds:

$$\displaystyle \begin{aligned}P(A_1,\ldots,A_n,B,C):\ \forall x\left(x\in C \Leftrightarrow (x\in B\ \text{and}\ \varphi(x,A_1,\ldots,A_n)\right).\end{aligned}$$

By transfer, we have that P(^∗ A ₁, …,^∗ A _n,^∗ B,^∗ C) holds as well. This readily implies that is ^∗ C = {x ∈^∗ B∣φ(x,^∗ A ₁, …,^∗ A _n)}.

An immediate corollary is the following.

Proposition 2.20

If $(a,b)=\{x\in \mathbb {R}\mid a<x<b\}$ is an open interval of real numbers then ${ }^*(a,b)=\{\xi \in { }^{\ast }\mathbb {R}\mid a<\xi <b\}$ , and similarly for intervals of the form [a, b), (a, b], (a, b), (−∞, b] and [a, +∞). Analogous properties hold for intervals of natural, integer, or rational numbers.

2.1 Additional Assumptions

By property Proposition 2.15 (1) and (2), the hyper-extension ^∗ A of a set A contains a copy of A given by the hyper-extensions of its elements

$$\displaystyle \begin{aligned}^\sigma A\ =\ \{{}^*a\mid a\in A\}\ \subseteq{}^{\ast}A.\end{aligned}$$

Notice that, by transfer, an hyper-extension ^∗ x belongs to ^∗ A if and only if x ∈ A. Therefore, ^σ A ∩^σ B =^σ(A ∩ B) for all sets A, B.

Following the common use in nonstandard analysis, to simplify matters we will assume that ^∗ r = r for all $r\in \mathbb {R}$. This implies by transfer that ^∗(r ₁, …, r _k) = (r ₁, …, r _k) for all ordered tuples of real numbers, i.e. ${ }^\sigma (\mathbb {R}^k)=\mathbb {R}^k$. It follows that hyper-extensions of real sets and functions are actual extensions:

• A ⊆^∗ A for every $A\subseteq \mathbb {R}^k$,

• If f : A → B where $A\subseteq \mathbb {R}^k$ and $B\subseteq \mathbb {R}^h$, then ^∗ f is an extension of f, that is, ^∗ f(a) = f(a) for every a ∈ A.

In nonstandard analysis it is always assumed that the star map satisfies the following

• Properness condition: ${ }^{\ast }\mathbb {N}\ne \mathbb {N}$.

Proposition 2.21

If the properness condition ${ }^{\ast }\mathbb {N}\ne \mathbb {N}$ holds, then ^σ A≠^∗ A for every infinite A.

Proof

Suppose that there is an infinite set A such that ^σ A =^∗ A. Fix a surjective map $f:A\to \mathbb {N}$. Then also the hyper-extension ${ }^{\ast }f:{ }^{\ast }A\to { }^{\ast }\mathbb {N}$ is surjective, and

$$\displaystyle \begin{aligned} \begin{array}{rcl} {}^{\ast}\mathbb{N}\ &\displaystyle =&\displaystyle \ \{{}^{\ast}f(\alpha)\mid \alpha\in{}^{\ast}A\}\ =\ \{{}^{\ast}f({}^*a)\mid a\in A\}\ =\ \{{}^*(f(a))\mid a\in A\}\ \\ &\displaystyle =&\displaystyle \ \{{}^*n\mid n\in\mathbb{N}\}\ =\ \mathbb{N},\vspace{-3pt} \end{array} \end{aligned} $$

whence the properness condition fails.

As a first consequence of the properness condition, one gets a nonstandard characterization of finite sets as those sets that are not “extended” by hyper-extensions.

Proposition 2.22

For every set A one has the equivalence: “A is finite if and only if ^∗ A =^σ A”. (When $A\subseteq \mathbb {R}^k$ , this is the same as “A is finite if and only if ^∗ A = A”.)

Proof

If A = {a ₁, …, a _k} is finite, we already saw in Proposition 2.15 (9) that ^∗ A = {^∗ a ₁, …,^∗ a _k} = {^∗ a∣a ∈ A}. Conversely, if A is infinite, we can pick a surjective function $f:A\to \mathbb {N}$. Then also ${ }^{\ast }f:{ }^{\ast }A\to { }^{\ast }\mathbb {N}$ is onto. Now notice that for every a ∈ A, one has that $({ }^{\ast }f)({ }^*a)={ }^*(f(a))=f(a)\in \mathbb {N}$ (recall that ^∗ n = n for every $n\in \mathbb {N}$). Then if $\xi \in { }^{\ast }\mathbb {N}{\setminus }\mathbb {N}$ there exists α ∈^∗ A∖{^∗ a∣a ∈ A} with ^∗ f(α) = ξ.

One can safely extend the simplifying assumption ^∗ r = r from real numbers r to elements of any given mathematical object X under study (but of course not for all mathematical objects).

• Unless explicitly mentioned otherwise, when studying a specific mathematical object X by nonstandard analysis, we will assume that ^∗ x = x for all x ∈ X, so that X =^σ X ⊆^∗ X.

It is worth mentioning at this point that star maps satisfying the transfer principle and the properness condition do actually exist. Indeed, they can be easily constructed by means of ultrafilters, or, equivalently, by means of maximal ideals of rings of functions (see Sect. 2.4).

We end this section with an example of using properness to give a short proof of a classical fact. (This nonstandard proof was suggested by D.A. Ross.)

Theorem 2.23 (Sierpinski)

Given $a_1,\ldots ,a_n,b\in \mathbb {R}^{>0}$ , the set

$$\displaystyle \begin{aligned}E:=\left\{(x_1,\ldots,x_n)\in \mathbb{N}^n \ : \ \frac{a_1}{x_1}+\cdots +\frac{a_n}{x_n}=b\right\}\end{aligned}$$

is finite.

Proof

Suppose, towards a contradiction, that E is infinite. Then there is x = (x ₁, …, x _n) ∈^∗ E∖E. Without loss of generality, we may assume that there is k ∈{1, …, n} such that $x_1,\ldots ,x_{k}\in { }^{\ast }\mathbb {N} {\setminus } \mathbb {N}$ and $x_{k+1},\ldots ,x_n\in \mathbb {N}$. We then have

$$\displaystyle \begin{aligned}\frac{a_1}{x_1}+\cdots +\frac{a_k}{x_k}=b-\left(\frac{a_{k+1}}{x_{k+1}}+\cdots+\frac{a_n}{x_n}\right).\end{aligned}$$

We have now arrived at a contradiction for the left hand side of the equation is a positive infinitesimal element of ${ }^{\ast }\mathbb {R}$ while the right hand side of the equation is a positive standard real number.

3 The Transfer Principle, in Practice

As we already pointed out, a correct application of transfer needs a precise understanding of the notion of elementary property. Basically, a property is elementary if it talks about the elements of some given structures and not about their subsets or the functions between them.³ Indeed, in order to correctly apply the transfer principle , one must always point out the range of quantifiers, and formulate them in the forms “ ∀ x ∈ X…” and “ ∃ y ∈ Y …” for suitable specified sets X, Y . With respect to this, the following remark is particularly relevant.

Remark 2.24

Before applying transfer, all quantifications on subsets “∀ x ⊆ X…” or “∃ x ⊆ X…” must be reformulated as “$\,\forall \,x\in \mathcal {P}(X)\ldots$” and “$\,\exists \,x\in \mathcal {P}(X)\ldots$”, respectively, where $\mathcal {P}(X)=\{A\mid A\subseteq X\}$ is the powerset of X. Similarly, all quantifications on functions f : A → B must be bounded by Fun(A, B), the set of functions from A to B. We stress that doing this is crucial because in general ${ }^*\mathcal {P}(X)\ne \mathcal {P}({ }^{\ast }X)$ and ^∗Fun(A, B)≠Fun(^∗ A,^∗ B), as we will show in Proposition 2.49.

Example 2.25

Consider the property: “<  is a linear ordering on the set A”. Notice first that <  is a binary relation on A, and hence its hyper-extension is a binary relation on ^∗ A. By definition, <  is a linear ordering if and only if the following are satisfied:

• (a) $\forall x\in A\ (x\nless x)$,

• (b) ∀x, y, z ∈ A (x < y and y < z) ⇒ x < z,

• (c) ∀x, y ∈ A (x < y or y < x or x = y).

Notice that the three formulas above are elementary. Then we can apply transfer and conclude that: “ is a linear ordering on ^∗ A.”

Whenever confusion is unlikely, some asterisks will be omitted. So, for instance, we will write +  to denote both the sum operation on $\mathbb {N}$, $\mathbb {Z}$, $\mathbb {Q}$ and $\mathbb {R}$, and the corresponding operations on ${ }^{\ast }\mathbb {N}$, ${ }^{\ast }\mathbb {Z}$, ${ }^{\ast }\mathbb {Q}$ and ${ }^{\ast }\mathbb {R}$, respectively, as given by the hyper-extension ^∗ + .

Similarly as in the example above, it is readily verified that the properties of a discretely ordered ring, as well as the properties of a real-closed ordered field, are elementary because they just talk about the elements of the given structures. Thus, by a direct application of transfer, one obtain the following results, which generalize the properties presented in Sect. 2.1.

Theorem 2.26

• 1. ${ }^{\ast }\mathbb {R}$ , endowed with the hyper-extensions of the sum, product, and order on $\mathbb {R}$ , is a real-closed ordered field. ⁴

• 2. ${ }^{\ast }\mathbb {Z}$ is an unbounded discretely ordered subring of ${ }^{\ast }\mathbb {R}$ , whose positive part is ${ }^{\ast }\mathbb {N}$.

• 3. The ordered subfield ${ }^{\ast }\mathbb {Q}\subset { }^{\ast }\mathbb {R}$ is the quotient field of ${ }^{\ast }\mathbb {Z}$.

• 4. Every non-zero $\nu \in { }^{\ast }\mathbb {N}$ has a successor ν + 1 and a predecessor ν − 1.⁵

• 5. For every positive $\xi \in { }^{\ast }\mathbb {R}$ there exists a unique $\nu \in { }^{\ast }\mathbb {N}$ with ν ≤ ξ < ν + 1. As a result, ${ }^{\ast }\mathbb {N}$ is unbounded in ${ }^{\ast }\mathbb {R}$.

Proposition 2.27

$(\mathbb {N},\le )$ is an initial segment of $({ }^{\ast }\mathbb {N},\le )$ , that is, if $\nu \in { }^{\ast }\mathbb {N}{\setminus }\mathbb {N}$ , then ν > n for all $n\in \mathbb {N}$ ,

Proof

For every $n\in \mathbb {N}$, by transfer one obtains the validity of the following elementary formula: “$\forall x\in { }^{\ast }\mathbb {N}\ (x\ne 1\ \text{and}\ \ldots$ and x≠n) ⇒ x > n”, and hence the proposition holds.

To get a clearer picture of the situation, examples of non-elementary properties that are not preserved under hyper-extensions, are now in order.

Example 2.28

The property of well-ordering (that is, every nonempty subset has a least element) and of completeness of an ordered set are not elementary. Indeed, they concern the subsets of the given ordered set. Notice that these properties are not preserved by hyper-extensions. In fact, $\mathbb {N}$ is well-ordered but ${ }^{\ast }\mathbb {N}$ is not (e.g., the set of infinite hyper-natural numbers has no least element). The real line $\mathbb {R}$ is complete but ${ }^{\ast }\mathbb {R}$ is not (e.g., the set of infinitesimal numbers is bounded with no least upper bound).

Remark 2.29

Transfer applies also to the well-ordering property of $\mathbb {N}$, provided one formalizes it as: “Every nonempty element of $\mathcal {P}(\mathbb {N})$ has a least element”. (The property “X has a least element” is elementary: “there exists x ∈ X such that for every y ∈ X, x ≤ y.”) In this way, one gets: “Every nonempty element of ${ }^*\mathcal {P}(\mathbb {N})$ has a least element”. The crucial point here is that ${ }^*\mathcal {P}(\mathbb {N})$ is not equal to $\mathcal {P}({ }^{\ast }\mathbb {N})$ (see Proposition 2.49 below). So, the well-ordering property is not an elementary property of $\mathbb {N}$, but it is an elementary property of $\mathcal {P}(\mathbb {N})$. Much the same observations can be made about the completeness property. Indeed, virtually all properties of mathematical objects can be formalized by elementary formulas, provided one uses the appropriate parameters.

A much more slippery example of a non-elementary property is the following.

Example 2.30

The Archimedean property of an ordered field $\mathbb {F}$ is not elementary. Notice that to formulate it, one needs to use $\mathbb {N}\subset \mathbb {F}$ as a parameter:

$$\displaystyle \begin{aligned} \text{``}\mathit{For\ all\ positive}\ x\in\mathbb{F}\ \mathit{there\ exists}\ n\in\mathbb{N}\ \mathit{such\ that}\ nx>1.\text{''} \end{aligned}$$

While the above is an elementary property of the pair $(\mathbb {F},\mathbb {N})$ since it talks about the elements of $\mathbb {F}$ and $\mathbb {N}$ combined, it is not an elementary property of the ordered field $\mathbb {F}$ alone. In regard to this, we remark that the following expression:

$$\displaystyle \begin{aligned} \text{``}\mathit{For\ all\ positive}\ x\in\mathbb{F}\ \mathit{it\ is}\ x>1\ \mathit{or}\ 2x>1\ \mathit{or}\ 3x>1\ \mathit{or} \ \ldots\ \mathit{or}\ nx>1\ \mathit{or} \ \ldots.\text{''} \end{aligned}$$

is not a formula, because it would consist in an infinitely long string of symbols if written in full. Notice that the Archimedean property is not preserved by hyper-extensions. For instance, $\mathbb {R}$ is Archimedean, but the hyperreal line ${ }^{\ast }\mathbb {R}$ is not, being an ordered field that properly extends $\mathbb {R}$ (see Proposition 2.5).

Similarly, the properties of being infinitesimal, finite, or infinite are not elementary properties of elements in a given ordered field $\mathbb {F}$, because to formulate them one needs to also consider $\mathbb {N}\subset \mathbb {F}$ as a parameter.

4 The Ultrapower Model

It is now time to justify what we have seen in the previous sections and show that star maps that satisfy the transfer principle do actually exist. Many researchers using nonstandard methods, especially those less familiar with mathematical logic, feel more comfortable in directly working with a model. However we remark that this is not necessary. Rather, it is worth stressing that all one needs in practice is a good understanding of the transfer principle and its use, whereas the underlying construction of a specific star map does not play a crucial role.⁶ The situation is similar to what happens when working in real analysis: what really matters is that $\mathbb {R}$ is a complete Archimedean ordered field, along with the fact that such a field actually exists; whereas the specific construction of the real line (e.g., by means of Dedekind cuts or by a suitable quotient of the set of Cauchy sequences) is irrelevant when developing the theory.

4.1 The Ultrapower Construction

The ultrapower construction relies on ultrafilters and so, to begin with, let us fix an ultrafilter $\mathcal {U}$ on a set of indices I. For simplicity, in the following we will focus on ultrapowers of $\mathbb {R}$. However, the same construction can be carried out by starting with any mathematical structure.

Definition 2.31

The ultrapower of $\mathbb {R}$ modulo the ultrafilter $\mathcal {U}$, denoted $\mathbb {R}^I/\mathcal {U}$, is the quotient of the family of real I-sequences $\mathbb {R}^I=\text{Fun}(I,\mathbb {R})=\{\sigma \mid \sigma :I\to \mathbb {R}\}$ modulo the equivalence relation $\equiv _{\mathcal {U}}$ defined by setting:

$$\displaystyle \begin{aligned}\sigma\equiv_{\mathcal{U}}\tau\ \Leftrightarrow\ \{i\in I\mid\sigma(i)=\tau(i)\}\in\mathcal{U}.\end{aligned}$$

Notice that the properties of being a filter on $\mathcal {U}$ guarantee that $\equiv _{\mathcal {U}}$ is actually an equivalence relation. Equivalence classes are denoted by using square brackets: $[\sigma ]=\{\tau \in \text{Fun}(I,\mathbb {R})\mid \tau \equiv _{\mathcal {U}}\sigma \}$. The pointwise sum and product operations on the ring $\text{Fun}(I,\mathbb {R})$ are inherited by the ultrapower . Indeed, it is easily verified that the following operations are well-defined:

$$\displaystyle \begin{aligned}{}[\sigma]\boldsymbol{+}[\tau]=[\sigma+\tau]\quad \text{and}\quad [\sigma]\boldsymbol{\cdot}[\tau]=[\sigma\cdot\tau].\end{aligned}$$

The order relation < on the ultrapower is defined by putting:

$$\displaystyle \begin{aligned}{}[\sigma]\boldsymbol{<}[\tau]\ \Leftrightarrow\ \{i\in I\mid \sigma(i)<\tau(i)\}\in\mathcal{U}.\end{aligned}$$

Proposition 2.32

The ultrapower $(\mathbb {R}^I/\mathcal {U}, \boldsymbol {+},\boldsymbol {\cdot }, \boldsymbol {<},\mathbf {0},\mathbf {1})$ is an ordered field.

Proof

All properties of an ordered field are directly proved by using the properties of an ultrafilter. For example, to prove that < is a total ordering, one considers the partition I = I ₁ ∪ I ₂ ∪ I ₃ where I ₁ = {i ∈ I∣σ(i) < τ(i)}, I ₂ = {i ∈ I∣σ(i) = τ(i)} and I ₃ = {i ∈ I∣σ(i) > τ(i)}: exactly one out of the three sets belongs to $\mathcal {U}$, and hence exactly one out of [σ] < [τ], [σ] = [τ], or [σ] > [τ] holds. As another example, let us show that every [σ] ≠ 0 has a multiplicative inverse. By assumption, $A=\{i\in I\mid \sigma (i)=0\}\notin \mathcal {U}$, and so the complement $A^c=\{i\in I\mid \sigma (i)\neq 0\}\in \mathcal {U}$. Now pick any I-sequence τ such that τ(i) = 1∕σ(i) whenever i ∈ A ^c. Then $A^c\subseteq \{i\in I\mid \sigma (i)\cdot \tau (i)=1\}\in \mathcal {U}$, and hence [σ] ⋅ [τ] = 1.

There is a canonical way of embedding $\mathbb {R}$ into its ultrapower .

Definition 2.33

The diagonal embedding $d:\mathbb {R}\to \mathbb {R}^I/\mathcal {U}$ is the function that associates to every real number r the equivalence class [c _r] of the corresponding constant I-sequence c _r.

It is readily seen that d is a 1-1 map that preserves sums, products and the order relation. As a result, without loss of generality, we can identify every $r\in \mathbb {R}$ with its diagonal image d(r) = [c _r], and assume that $\mathbb {R}\subseteq \mathbb {R}^I/\mathcal {U}$ is an ordered subfield.

Notice that if $\mathcal {U}=\mathcal {U}_j$ is principal then the corresponding ultrapower $\mathbb {R}^I/\mathcal {U}_j=\mathbb {R}$ is trivial. Indeed, in this case one has $\sigma \equiv _{\mathcal {U}_j}\tau \Leftrightarrow \sigma (j)=\tau (j)$. Thus, every sequence is equivalent to the constant I-sequence with value σ(j), and the diagonal embedding $d:\mathbb {R}\to \mathbb {R}^I/\mathcal {U}_j$ is onto.⁷

Remark 2.34

Under the Continuum Hypothesis, one can show that for every pair $\mathcal {U},\mathcal {V}$ of non-principal ultrafilters on $\mathbb {N}$, the ordered fields obtained as the corresponding ultrapowers $\mathbb {R}^{\mathbb {N}}/\mathcal {U}, \mathbb {R}^{\mathbb {N}}/\mathcal {V}$ of $\mathbb {R}$ are isomorphic.⁸

4.2 Hyper-Extensions in the Ultrapower Model

In this section we will see how the ultrapower $\mathbb {R}^I/\mathcal {U}$ can be made a model of the hyperreal numbers of nonstandard analysis. Let us start by denoting

$$\displaystyle \begin{aligned}^{\ast}\mathbb{R}\ =\ \mathbb{R}^I/\mathcal{U}.\end{aligned}$$

We now have to show that the ordered field ${ }^{\ast }\mathbb {R}$ has all the special features that make it a set of hyperreal numbers . To this end, we will define a star map on the family of all sets of ordered tuples of real numbers and of all real functions, in such a way that the transfer principle holds.

Definition 2.35

Let $A\subseteq \mathbb {R}$. Then its hyper-extension ${ }^{\ast }A\subseteq { }^{\ast }\mathbb {R}$ is defined as the family of all equivalence classes of I-sequences that take values in A, that is:

$$\displaystyle \begin{aligned}^{\ast}A\ =\ A^I/\mathcal{U}\ =\ \left\{[\sigma]\mid\sigma:I\to A\right\}\ \subseteq\ {}^{\ast}\mathbb{R}.\end{aligned}$$

Similarly, if $A\subseteq \mathbb {R}^k$ is a set of real k-tuples, then its hyper-extension is defined as

$$\displaystyle \begin{aligned}^{\ast}A\ =\ \left\{([\sigma_1],\ldots,[\sigma_k])\mid (\sigma_1,\ldots,\sigma_k):I\to A\right\}\ \subseteq\ {}^{\ast}\mathbb{R}^k\end{aligned}$$

where we denote (σ ₁, …, σ _k) : i↦(σ ₁(i), …, σ _k(i)).

Notice that, by the properties of ultrafilter, for every $\sigma _1,\ldots ,\sigma _k,\tau _1,\ldots ,\tau _k:I\to \mathbb {R}$, one has

$$\displaystyle \begin{aligned} \begin{array}{rcl} &\displaystyle &\displaystyle \{i\in I\mid (\sigma_1(i),\ldots,\sigma_k(i))= (\tau_1(i),\ldots,\tau_k(i))\}\in\mathcal{U}\ \Longleftrightarrow\ \sigma_s\equiv_{\mathcal{U}}\tau_s\ \text{for every }\\ &\displaystyle &\displaystyle \quad s=1,\ldots,k. \end{array} \end{aligned} $$

In consequence, the above equivalence relation is well-defined, and one has that $([\sigma _1],\ldots ,[\sigma _n])\in { }^{\ast }A\Leftrightarrow \{i\mid (\sigma _1,\ldots ,\sigma _n)\in A\}\in \mathcal {U}$.

We also define the star map on real ordered tuples by setting

$$\displaystyle \begin{aligned}^*(r_1,\ldots,r_k)=(r_1,\ldots,r_k).\end{aligned}$$

Recall that we identified every $r\in \mathbb {R}$ with the equivalence class [c _r] of the corresponding constant sequence and so, by letting ^∗ r = r = [c _r], we have that A ⊆^∗ A for every $A\subseteq \mathbb {R}^k$.

We have already seen that ${ }^{\ast }\mathbb {R}$ is an ordered field that extends the real line. As a result, every rational function $f:\mathbb {R}\to \mathbb {R}$ is naturally extended to a function ${ }^{\ast }f:{ }^{\ast }\mathbb {R}\to { }^{\ast }\mathbb {R}$. However, here we are interested in extending all real functions f : A → B where A and B are set of real tuples, to functions ^∗ f :^∗ A →^∗ B. With ultrapowers, this can be done in a natural way.

Definition 2.36

Let f : A → B where $A,B\subseteq \mathbb {R}$. Then the hyper-extension of f is the function ^∗ f :^∗ A →^∗ B defined by setting ^∗ f([σ]) = [f ∘ σ] for every σ : I → A.

If f : A → B is a function of several variables where $A\subseteq \mathbb {R}^k$ and $B\subseteq \mathbb {R}$, then ^∗ f :^∗ A →^∗ B is defined by setting for every $\sigma _1,\ldots ,\sigma _k:I\to \mathbb {R}$:

$$\displaystyle \begin{aligned}^{\ast}f([\sigma_1],\ldots,[\sigma_k])\ =\ [\langle f(\sigma_1(i),\ldots,\sigma_k(i))\mid i\in I\rangle].\end{aligned}$$

Similarly as for hyper-extensions of sets of tuples, it is routine to check that the properties of an ultrafilter guarantee that the function ^∗ f is well-defined.

Let us now see that the ultrapower model has all the desired properties.

Theorem 2.37

The hyper-extensions of real ordered tuples, sets of ordered real tuples and real functions, as defined above, satisfy all the properties itemized in Propositions 2.15 , 2.16 , and 2.17 . For every $k,n \in \mathbb {N}$ , $a,a_1,\ldots ,a_k\in \mathbb {R} ^n$ , and $A,B\subset \mathbb {R} ^n$ :

• 1. a = b ⇔^∗ a =^∗ b.

• 2. a ∈ A if and only if ^∗ a ∈^∗ A.

• 3. A is a set if and only if ^∗ A is a set.

• 4. ^∗ ∅ = ∅.

• 5. A ⊆ B ⇔^∗ A ⊆^∗ B.

• 6. ^∗(A ∪ B) =^∗ A ∪^∗ B.

• 7. ^∗(A ∩ B) =^∗ A ∩^∗ B.

• 8. ^∗(A∖B) =^∗ A∖^∗ B.

• 9. ^∗{a ₁, …, a _k} = {a ₁, …, a _k}.

• 10. ^∗(a ₁, …, a _k) = (a ₁, …, a _k).

• 11. ^∗(A ₁ ×… × A _k) =^∗ A ₁ ×… ×^∗ A _k.

• 12. ^∗{(a, a)∣a ∈ A} = {(ξ, ξ)∣ξ ∈ A}.

• 13. R is a k-ary relation if and only if ^∗ R is a k-ary relation.

• 14. ^∗{a∣∃b R(a, b)} = {ξ∣∃ζ ^∗ R(ξ, ζ)}, that is, ^∗ domain(R) = domain(^∗ R).

• 15. ^∗{b∣∃a R(a, b)} = {ζ∣∃ξ ^∗ R(ξ, ζ)}, that is, ^∗ range(R) = range(^∗ R).

• 16. ^∗{(a, b)∣R(b, a)} = {(ξ, ζ)∣^∗ R(ζ, ξ)}.

• 17. ^∗{(a, b, c)∣S(c, a, b)} = {(ξ, ζ, η)∣^∗ S(η, ξ, ζ)}.

• 18. ^∗{(a, b, c)∣S(a, c, b)} = {(ξ, ζ, η)∣^∗ S(ξ, η, ζ)}.

• 19. f is a function if and only if ^∗ f is a function.

• 20. ^∗ domain(f) = domain(^∗ f).

• 21. ^∗ range(f) = range(^∗ f).

• 22. f : A → B if and only if ^∗ f :^∗ A →^∗ B.

• 23. ^∗ graph(f) = graph(^∗ f).

• 24. (^∗ f)(a) = f(a) for every a ∈domain(f).

• 25. If f : A → A is the identity, then ^∗ f :^∗ A →^∗ A is the identity, that is .

• 26. ^∗{f(a)∣a ∈ A} = {^∗ f(ξ)∣ξ ∈^∗ A}, that is ^∗(f(A)) =^∗ f(^∗ A).

• 27. ^∗{a∣f(a) ∈ B} = {ξ∣^∗ f(ξ) ∈^∗ B}, that is ^∗(f ⁻¹(B)) = (^∗ f)⁻¹(^∗ B).

• 28. ^∗(f ∘ g) =^∗ f ∘^∗ g.

• 29. ^∗{(a, b) ∈ A × B∣f(a) = g(b)} = {(ξ, ζ) ∈^∗ A ×^∗ B∣^∗ f(ξ) =^∗ g(ζ)}.

Proof

All proofs of the above properties are straightforward applications of the definitions and of the properties of ultrafilters. As an example, let us see here property (13) in detail. We leave the others to the reader as exercises.

Let Λ = {a∣∃b R(a, b)} and let Γ = {ξ∣∃ζ ^∗ R(ξ, ζ)}. We have to show that ^∗ Λ = Γ. If σ : I → Λ then for every i there exists an element τ(i) such that R(σ(i), τ(i)). Then ^∗ R([σ], [τ]) and so [σ] ∈ Γ. This shows the inclusion ^∗ Λ ⊆ Γ. Conversely, [σ] ∈ Γ if and only if ^∗ R([σ], [τ]) for some I-sequence τ. Since ([σ], [τ]) ∈^∗ R, the set $\varTheta =\{i\mid (\sigma (i),\tau (i))\in R\}\in \mathcal {U}$, so also the superset {i∣σ(i) ∈ Λ}⊇ Θ belongs to $\mathcal {U}$. We conclude that [σ] ∈^∗ Λ, as desired.

We disclose that the previous theorem essentially states that our defined star map satisfies the transfer principle. Indeed, once the notion of elementary property will be made fully rigorous, one can show that transfer is actually equivalent to the validity of the properties listed above.

Remark 2.38

A “strong isomorphism” between two sets of hyperreals ${ }^{\ast }\mathbb {R}$ and ${ }^\star \mathbb {R}$ is defined as a bijection $\psi :{ }^{\ast }\mathbb {R}\to { }^\star \mathbb {R}$ that it coherent with hyper-extensions, that is, (ξ ₁, …, ξ _k) ∈^∗ A ⇔ (Ψ(ξ ₁), …, Ψ(ξ _k)) ∈^⋆ A for every $A\subseteq \mathbb {R}^k$ and for every $\xi _1,\ldots ,\xi _k\in { }^{\ast }\mathbb {R}$, and ^∗ f(ξ ₁, …, ξ _k) = η ⇔^⋆ f(Ψ(ξ ₁), …, Ψ(ξ _k)) = Ψ(η) for every $f:\mathbb {R}^k\to \mathbb {R}$ and for every $\xi _1,\ldots ,\xi _k,\eta \in { }^{\ast }\mathbb {R}$. Then one can show that two ultrapower models $\mathbb {R}^{\mathbb {N}}/\mathcal {U}$ and $\mathbb {R}^{\mathbb {N}}/\mathcal {V}$ are “strongly isomorphic” if and only if the ultrafilters $\mathcal {U}\cong \mathcal {V}$ are isomorphic, that is, there exists a permutation $\sigma :\mathbb {N}\to \mathbb {N}$ such that $A\in \mathcal {U}\Leftrightarrow \sigma (A)\in \mathcal {V}$ for every $A\subseteq \mathbb {N}$. We remark that there exist plenty of non-isomorphic ultrafilters (indeed, one can show that there are $2^{\mathfrak {c}}$-many distinct classes of isomorphic ultrafilters on $\mathbb {N}$). This is to be contrasted with the previous Remark 2.34, where the notion of isomorphism between sets of hyperreals was limited to the structure of ordered field.

4.3 The Properness Condition in the Ultrapower Model

In the previous section, we observed that principal ultrafilters generate trivial ultrapowers. Below, we precisely isolate the class of those ultrafilters that produce models where the properness condition $\mathbb {N}\ne { }^{\ast }\mathbb {N}$ (as well as $\mathbb {R}\ne { }^{\ast }\mathbb {R}$) holds.

Recall that an ultrafilter $\mathcal {U}$ is called countably incomplete if it is not closed under countable intersections, that is, if there exists a countable family $\{I_n\}_{n\in \mathbb {N}}\subseteq \mathcal {U}$ such that $\bigcap _{n\in \mathbb {N}} I_n\notin \mathcal {U}$. We remark that all non-principal ultrafilters on $\mathbb {N}$ or on $\mathbb {R}$ are countably incomplete.⁹

Exercise 2.39

An ultrafilter $\mathcal {U}$ on I is countably incomplete if and only if there exists a countable partition $I=\bigcup _{n\in \mathbb {N}} J_n$ where $J_n\notin \mathcal {U}$ for every n.

Proposition 2.40

In the ultrapower model modulo the ultrafilter $\mathcal {U}$ on I, the following properties are equivalent:

• 1. Properness condition: ${ }^{\ast }\mathbb {N}\ne \mathbb {N}$ ;

• 2. $\mathcal {U}$ is countably incomplete.

Proof

Assume first that ${ }^{\ast }\mathbb {N}\ne \mathbb {N}$. Pick a sequence $\sigma :I\to \mathbb {N}$ such that $[\sigma ]\notin \mathbb {N}$. Then $I_n=\{i\in I\mid \sigma (i)\ne n\}\in \mathcal {U}$ for every $n\in \mathbb {N}$, but $\bigcap _n I_n=\emptyset \notin \mathcal {U}$. Conversely, if $\mathcal {U}$ is countably incomplete, pick a countable partition I =⋃_n J _n where $J_n\notin \mathcal {U}$ for every n, and pick the sequence $\sigma :I\to \mathbb {N}$ where σ(i) = n for i ∈ J _n. Then $[\sigma ]\in { }^{\ast }\mathbb {N}$ but [σ]≠[c _n] for every n, where c _n represents the I-sequence constantly equal to n.

In the sequel we will always assume that ultrapower models are constructed by using ultrafilters $\mathcal {U}$ that are countably incomplete.

4.4 An Algebraic Presentation

The ultrapower model can be presented in an alternative, but equivalent, purely algebraic fashion where only the notion of quotient field of a ring modulo a maximal ideal is assumed. Here are the steps of the construction, whose details can be found in [9].

• Consider $\text{Fun}(I,\mathbb {R})$, the ring of real valued sequences where the sum and product operations are defined pointwise.

• Let $\mathfrak {i}$ be the ideal of those sequences that have finite support:

  $$\displaystyle \begin{aligned}\mathfrak{i}\ =\ \{\sigma\in\text{Fun}(I,\mathbb{R})\mid \sigma(i)=0\ \text{for all but at most finitely many}\ i\}.\end{aligned}$$

• Extend $\mathfrak {i}$ to a maximal ideal $\mathfrak {m}$, and define the hyperreal numbers as the quotient field:

  $$\displaystyle \begin{aligned}^{\ast}\mathbb{R}\ =\ {\text{Fun}(I,\mathbb{R})}/\mathfrak{m}.\end{aligned}$$

• For every subset $A\subseteq \mathbb {R}$, its hyper-extension is defined by:

  $$\displaystyle \begin{aligned}^{\ast}A\ =\ \{\sigma+\mathfrak{m}\mid \sigma:I\to A\}\ \subseteq\ {}^{\ast}\mathbb{R}.\end{aligned}$$

  So, e.g., the hyper-natural numbers ${ }^{\ast }\mathbb {N}$ are the cosets $\sigma +\mathfrak {m}$ of I-sequences $\sigma :I\to \mathbb {N}$ of natural numbers.

• For every function f : A → B where $A,B\subseteq \mathbb {R}$, its hyper-extension ^∗ f :^∗ A →^∗ B is defined by setting for every σ : I → A:

  $$\displaystyle \begin{aligned}^{\ast}f(\sigma+\mathfrak{m})\ =\ (f\circ\sigma)+\mathfrak{m}.\end{aligned}$$

It can be directly verified that ${ }^{\ast }\mathbb {R}$ is an ordered field whose positive elements are ${ }^{\ast }\mathbb {R}^+=\text{Fun}(\mathbb {N},\mathbb {R}^+)/\mathfrak {m}$, where $\mathbb {R}^+$ is the set of positive reals. By identifying each $r\in \mathbb {R}$ with the coset $c_r+\mathfrak {m}$ of the corresponding constant sequence, one obtains that $\mathbb {R}$ is a proper subfield of ${ }^{\ast }\mathbb {R}$.

Notice that, as in the case of the ultrapower model, the above definitions are naturally extended to hyper-extensions of sets of real tuples and of functions between sets of real tuples.

Remark 2.41

The algebraic approach presented here is basically equivalent to the ultrapower model. Indeed, for every function $f:I\to \mathbb {R}$, let us denote by Z(f) = {i ∈ I∣f(i) = 0} its zero-set. If $\mathfrak {m}$ is a maximal ideal of the ring $\text{Fun}(I,\mathbb {R})$, then it is easily shown that the family $\mathcal {U}_{\mathfrak {m}}=\{Z(f)\mid f\in \mathfrak {m}\}$ is an ultrafilter on $\mathbb {N}$. Conversely, if $\mathcal {U}$ is an ultrafilter on $\mathbb {N}$, then $\mathfrak {m}_{\mathcal {U}}=\{f\mid Z(f)\in \mathcal {U}\}$ is a maximal ideal of the ring $\text{Fun}(I,\mathbb {R})$. The correspondence between $\mathcal {U}$-equivalence classes [σ] and cosets $\sigma +\mathfrak {m}_{\mathcal {U}}$ yields an isomorphism between the ultrapower $\mathbb {R}^I/\mathcal {U}$ and the quotient $\text{Fun}(I,\mathbb {R})/{\mathfrak {m}_{\mathcal {U}}}$.

5 Internal and External Objects

We are now ready to introduce a fundamental class of objects in nonstandard analysis, namely the internal objects. In a way, they are similar to the measurable sets in measure theory, because they are those objects that behave “nicely” in our theory. Indeed, elementary properties of subsets or of functions transfer to the corresponding internal objects (see below).

Recall that the star map does not preserve the properties of powersets and function sets. For instance, we have noticed in the previous sections that there are nonempty) sets in $\mathcal {P}({ }^{\ast }\mathbb {N})$ with no least element, and there are nonempty sets in $\mathcal {P}({ }^{\ast }\mathbb {R})$ that are bounded but have no least upper bound (see Example 2.28 and Remark 2.29). However, by the transfer principle , the family $\mathcal {P}(A)$ of all subsets of a set A and ${ }^*\mathcal {P}(A)$ satisfy the same properties. Similarly, the family Fun(A, B) of all functions f : A → B and ^∗Fun(A, B) satisfy the same properties. Let us now elaborate on this, and start with two easy observations.

Proposition 2.42

• 1. Every element of the hyper-extension ${ }^*\mathcal {P}(A)$ is a subset of ^∗ A, that is, ${ }^*\mathcal {P}(A)\subseteq \mathcal {P}({ }^{\ast }A)$ ;

• 2. Every element of the hyper-extension ^∗ Fun(A, B) is a function f :^∗ A →^∗ B, that is, ^∗ Fun(A, B) ⊆Fun(^∗ A,^∗ B).

Proof

• (1) Apply transfer to the elementary property: $\forall x\in \mathcal {P}(A)\ \forall y\in x\ \,y\in A$.

• (2) Apply transfer to the elementary property: ∀x ∈Fun(A, B) “x is a function”and dom(x) = A and range(x) ⊆ B.

Consequently, it is natural to consider the elements in ${ }^*\mathcal {P}(A)$ as the “nice” subsets of ^∗ A, and the elements in ^∗Fun(A, B) as the “nice” functions from ^∗ A to ^∗ B.

Definition 2.43

Let A, B be sets. The elements of ${ }^*\mathcal {P}(A)$ are called the internal subsets of ^∗ A and the elements of ^∗Fun(A, B) are called the internal functions from ^∗ A to ^∗ B. More generally, an internal object is any element B ∈^∗ Y  that belongs to some hyper-extension.

The following facts about functions are easily verified, and the proofs are left as exercises.

Proposition 2.44

• 1. A function F is internal if and only if it belongs to the hyper-extension ${ }^*\mathcal {F}$ of some set of functions $\mathcal {F}$ ;

• 2. A function F : A → B is internal if and only if there exist sets X, Y  such that $A\in { }^*\mathcal {P}(X)$ , $B\in { }^*\mathcal {P}(Y)$ , and F ∈^∗{f function∣domain(f) ⊆ X and range(f) ⊆ Y }.

In consequence, domain and range of an internal function are internal sets.

The first natural examples of internal objects are given by the hyperreal numbers $\xi \in { }^{\ast }\mathbb {R}$, and also by all ordered tuples of hyperreal numbers $(\xi _1,\ldots ,\xi _k)\in { }^{\ast }\mathbb {R}^k$. Notice that the hyper-extension ^∗ X of a standard object X is an internal object, since ^∗ X ∈^∗{X} = {^∗ X}.

• Rule of thumb. Properties about subsets of a set A transfer to the internal subsets of ^∗ A, and properties about functions f : A → B transfer to the internal functions from ^∗ A to ^∗ B.

For instance, the well-ordering property of $\mathbb {N}$ is transferred to: “Every nonempty internal subset of ${ }^{\ast }\mathbb {N}$ has a least element”, and the completeness property of $\mathbb {R}$ transfers to: “Every nonempty internal subset of ${ }^{\ast }\mathbb {R}$ that is bounded above has a least upper bound”.

The following is a useful closure property of the class of internal objects .

Theorem 2.45 (Internal Definition Principle)

Let φ(x, y ₁, …, y _k) be an elementary formula. If A is an internal set and B ₁, …, B _n are internal objects, then the set {x ∈ A∣φ(x, B ₁, …, B _n)} is also internal.

Proof

By assumption, there exists a family of sets $\mathcal {F}$ and sets Y _i such that $A\in { }^*\mathcal {F}$ and B _i ∈^∗ Y _i for i = 1, …, n. Pick any family $\mathcal {G}\supseteq \mathcal {F}$ that is closed under subsets, that is, $C'\subseteq C\in \mathcal {G}\Rightarrow C'\in \mathcal {G}$. (For example, one can take $\mathcal {G}=\bigcup \{\mathcal {P}(C)\mid C\in \mathcal {F}\}$.) Then the following is a true elementary property of the objects $\mathcal {G},Y_1,\ldots ,Y_n$ ¹⁰:

$$\displaystyle \begin{aligned} &P(\mathcal{G},Y_1,\ldots,Y_n):\quad \forall x\in\mathcal{G}\,\forall y_1\in Y_1\,\ldots\,\forall y_n\in Y_n\ \exists z\in\mathcal{G}\ \text{such that}\ \\ &\quad ``z=\{t\in x\mid \varphi(t,y_1,\ldots,y_n)\}.\text{''} \end{aligned} $$

By transfer, the property $P({ }^*\mathcal {G},{ }^{\ast }Y_1,\ldots ,{ }^{\ast }Y_n)$ is also true, and since $A\in { }^*\mathcal {G}, B_i\in { }^{\ast }Y_i$, we obtain the existence of an internal set $C\in { }^*\mathcal {G}$ such that C = {t ∈ A∣φ(x, B ₁, …, B _n)}, as desired.

As direct applications of the above principle, one obtains the following properties for the class of internal objects .

Proposition 2.46

• 1. The class $\mathcal {I}$ of internal sets is closed under unions, intersections, set-differences, finite sets and tuples, Cartesian products, and under images and preimages of internal functions.

• 2. If $A\in \mathcal {I}$ is an internal set, then the set of its internal subsets $\mathcal {P}(A)\cap \mathcal {I}\in \mathcal {I}$ is itself internal.

• 3. If A, B are internal sets, then the set $\mathit{\text{Fun}}(A,B)\cap \mathcal {I}\in \mathcal {I}$ of internal functions between them is itself internal.

Proof

• (1) If A and B are internal sets, say $A\in { }^*\mathcal {P}(X)$ and $B\in { }^*\mathcal {P}(Y)$, then A ∪ B = {t ∈^∗ X ∪^∗ Y ∣t ∈ A or t ∈ B} is internal by the Internal Definition Principle. The other properties are easily proved in the same fashion.

• (2) Let X be such that $A\in { }^*\mathcal {P}(X)$. It is easily verified that $\mathcal {P}(A)\cap \mathcal {I}=\{B\in { }^*\mathcal {P}(X)\mid B\subseteq A\}$, and so the Internal Definition Principle applies.

• (3) Pick X, Y  such that $A\in { }^*\mathcal {P}(X)$ and $B\in { }^*\mathcal {P}(Y)$. By Proposition 2.44, we know that

  $$\displaystyle \begin{aligned}\text{Fun}(A,B)\cap\mathcal{I}= \{F\in{}^*\mathcal{F}\mid \text{domain}(F)=A\ \text{and}\ \text{range}(F)\subseteq B\}\end{aligned}$$

  where $\mathcal {F}=\{f\ \text{function}\mid \text{domain}(f)\subseteq X\ \text{and}\ \text{range}(f)\subseteq Y\}$, and so $\text{Fun}(A,B)\cap \mathcal {I}$ is internal by the Internal Definition Principle.

Definition 2.47

An object that is not internal is called external.

Although they might not satisfy the same first-order properties as standard sets, external sets are useful in a number of application of nonstandard methods.

Example 2.48

• 1. The set of infinitesimal hyperreal numbers is external. Indeed, it is a bounded subset of ${ }^{\ast }\mathbb {R}$ without least upper bound.

• 2. The set of infinite hypernatural numbers is external. Indeed, it is a nonempty subset of ${ }^{\ast }\mathbb {N}$ without a least element.

• 3. The set $\mathbb {N}$ of finite hypernatural numbers is external, as its complement ${ }^{\ast }\mathbb {N}{\setminus }\mathbb {N}$ inside ${ }^{\ast }\mathbb {N}$ is external.

The above examples shows that ${ }^*\mathcal {P}(\mathbb {N})\ne \mathcal {P}({ }^{\ast }\mathbb {N})$ and ${ }^*\mathcal {P}(\mathbb {R})\ne \mathcal {P}({ }^{\ast }\mathbb {R})$. More generally, we have

Proposition 2.49

• 1. For every infinite set A, the set ^σ A = {^∗ a∣a ∈ A} is external.

• 2. Every infinite hyperextension ^∗ A has external subsets, that is, the inclusion ${ }^*\mathcal {P}(A)\subset \mathcal {P}({ }^{\ast }A)$ is proper.

• 3. If the set A is infinite and B contains at least two elements, then the inclusion ^∗ Fun(A, B) ⊂Fun(^∗ A,^∗ B) is proper.

Proof

• (1) Pick a surjective map $\psi :A\to \mathbb {N}$. Then also the hyper-extension ${ }^*\psi :{ }^{\ast }A\to { }^{\ast }\mathbb {N}$ is surjective. If by contradiction ^σ A was internal, its image under ^∗ ψ would also be, and this is not possible, since

  $$\displaystyle \begin{aligned}^*\psi\left({}^\sigma A\right)\ =\ \left\{{}^*\psi({}^*a)\mid a\in A\right\}\ =\ \left\{{}^*(\psi(a))\mid a\in A\right\}\ =\ \left\{\psi(a)\mid a\in A\right\}\ =\ \mathbb{N}.\end{aligned}$$

• (2) Notice first that A is infinite, because if A = {a ₁, …, a _n} were finite, then also ^∗ A = {^∗ a ₁, …,^∗ a _n} would be finite. Recall that ${ }^*\mathcal {P}(A)$ is the set of all internal subsets of ^∗ A. Since ^σ A ⊂^∗ A is external by (1), ${ }^\sigma A\in \mathcal {P}({ }^{\ast }A){\setminus {}}^*\mathcal {P}(A)$.

• (3) Recall that ^∗Fun(A, B) is the set of all internal functions f :^∗ A →^∗ B. Pick an external subset X ⊂ A, pick b ₁≠b ₂ in B, and let f :^∗ A →^∗ B be the function where f(a) =^∗ b ₁ if a ∈ X and f(a) =^∗ b ₂ if a∉X. Then f is external, as the preimage f ⁻¹(^∗{b ₁}) = X is external.

We warn the reader that becoming familiar with the distinction between internal and external objects is probably the hardest part of learning nonstandard analysis.

5.1 Internal Objects in the Ultrapower Model

The ultrapower model ${ }^{\ast }\mathbb {R}=\mathbb {R}^I/\mathcal {U}$ that we introduced in Sect. 2.4 can be naturally extended so as to include also hyper-extensions of families of sets of real tuples, and of families of functions.

Let us start by observing that every I-sequence T = 〈T _i∣i ∈ I〉 of sets of real numbers $T_i\subseteq \mathbb {R}$ determines a set $\widehat {T}\subseteq { }^{\ast }\mathbb {R}$ of hyperreal numbers in a natural way, by letting

$$\displaystyle \begin{aligned}\widehat{T}\ =\ \left\{[\sigma]\in{}^{\ast}\mathbb{R}\,\bigm|\{i\in I\mid \sigma(i)\in T_i\}\in\mathcal{U}\right\}.\end{aligned}$$

Definition 2.50

If $\mathcal {F}\subseteq \mathcal {P}(\mathbb {R})$, then its hyper-extension ${ }^*\mathcal {F}\subseteq { }^*\mathcal {P}(\mathbb {R})$ is defined as

$$\displaystyle \begin{aligned}^*\mathcal{F}\ =\ \left\{\widehat{T}\bigm| T:I\to\mathcal{F}\right\}.\end{aligned}$$

We remark that the same definition above also applies to families $\mathcal {F}\subseteq \mathcal {P}(\mathbb {R}^k)$ of sets of k-tuples, where for I-sequences $T:I\to \mathcal {P}(\mathbb {R}^k)$ one defines $\widehat {T}=\left \{([\sigma _1],\ldots ,[\sigma _k])\in { }^{\ast }\mathbb {R}^k\bigm | \{i\in I\mid (\sigma _1(i),\ldots ,\sigma _k(i))\in T(i)\}\in \mathcal {U}\right \}$.

According to Definition 2.43, $A\subseteq { }^{\ast }\mathbb {R}$ is internal if and only if $A\in { }^*\mathcal {P}(\mathbb {R})$. So, in the ultrapower model, $A\subseteq { }^{\ast }\mathbb {R}$ is internal if and only if $A=\widehat {T}$ for some I-sequence $T:I\to \mathcal {P}(\mathbb {R})$.

Analogously as above, every I-sequence F = 〈F _i∣i ∈ I〉 of real functions $F_i:\mathbb {R}\to \mathbb {R}$ determines a function $\widehat {F}:{ }^{\ast }\mathbb {R}\to { }^{\ast }\mathbb {R}$ on the hyperreal numbers by letting for every $\sigma :I\to \mathbb {R}$:

$$\displaystyle \begin{aligned}\widehat{F}([\sigma])\ =\ [\langle F_i(\sigma(i))\mid i\in I\rangle].\end{aligned}$$

The internal functions from ${ }^{\ast }\mathbb {R}$ to ${ }^{\ast }\mathbb {R}$ in the ultrapower model are precisely those that are determined by some I-sequence $F:I\to \text{Fun}(\mathbb {R},\mathbb {R})$.

Definition 2.51

If $\mathcal {G}\subseteq \text{Fun}(\mathbb {R},\mathbb {R})$, then its hyper-extension ${ }^*\mathcal {G}\subseteq { }^*\text{Fun}(\mathbb {R},\mathbb {R})$ is defined as

$$\displaystyle \begin{aligned}^*\mathcal{G}\ =\ \left\{\widehat{F}\bigm| F:I\to\mathcal{G}\right\}.\end{aligned}$$

If F = 〈F _i∣i ∈ I〉 is an I-sequence of functions $F_i:\mathbb {R}^k\to \mathbb {R}$ of several variables, one extends the above definition by letting $\widehat {F}:{ }^{\ast }\mathbb {R}^k\to { }^{\ast }\mathbb {R}$ be the function where for every $\sigma _1,\ldots ,\sigma _k:I\to \mathbb {R}$:

$$\displaystyle \begin{aligned}\widehat{F}([\sigma_1],\ldots,[\sigma_k])\ =\ [\langle F_i(\sigma_1(i),\ldots ,\sigma_k(i))\mid i\in I\rangle].\end{aligned}$$

Indeed, also in this case, if $\mathcal {G}\subseteq \text{Fun}(\mathbb {R}^k,\mathbb {R})$ then one sets ${ }^*\mathcal {G}=\left \{\widehat {F}\bigm | F:I\to \mathcal {G}\right \}$.

6 Hyperfinite Sets

In this section we introduce a fundamental tool in nonstandard analysis, namely the class of hyperfinite sets . Although they may contain infinitely many elements, hyperfinite sets satisfy the same “elementary properties” as finite sets. For this reason they are useful in applications as a convenient bridge between finitary statements and infinitary notions.

Definition 2.52

A hyperfinite set A is an element of the hyper-extension ${ }^*\mathcal {F}$ of a family $\mathcal {F}$ of finite sets.

In particular, hyperfinite sets are internal objects.

Remark 2.53

In the ultrapower model, the hyperfinite subsets of ${ }^{\ast }\mathbb {R}$ are defined according to Definition 2.50. Precisely, $A\subseteq { }^{\ast }\mathbb {R}$ is hyperfinite if and only if there exists a sequence 〈T _i∣i ∈ I〉 of finite sets $T_i\subset \mathbb {R}$ such that $A=\widehat {T}$, that is, for every $\sigma :I\to \mathbb {R}$, $[\sigma ]\in A\Leftrightarrow \{i\in I\mid \sigma (i)\in T_i\}\in \mathcal {U}$.

Let us start with the simplest properties of hyperfinite sets.

Proposition 2.54

• 1. A subset A ⊆^∗ X is hyperfinite if and only if A ∈^∗ Fin(X), where Fin(X) = {A ⊆ X∣A is finite}.

• 2. Every finite set of internal objects is hyperfinite.

• 3. A set of the form ^∗ X for some standard set X is hyperfinite if and only if X is finite.

• 4. If f : A → B is an internal function , and Ω ⊆ A is a hyperfinite set, then its image f(Ω) = {^∗ f(ξ)∣ξ ∈ Ω} is hyperfinite as well. In particular, internal subsets of hyperfinite sets are hyperfinite.

Proof

• (1) If A is a hyperfinite subset of ^∗ X, then A is internal, and hence $A\in { }^*\mathcal {P}(X)$. So, if $\mathcal {F}$ is a family of finite sets with $A\in { }^*\mathcal {F}$, then $A\in { }^*\mathcal {P}(X)\cap { }^*\mathcal {F}= { }^*(\mathcal {P}(X)\cap \mathcal {F})\subseteq { }^*\text{Fin}(X)$. The converse implication is trivial.

• (2) Let A = {a ₁, …, a _k}, and pick X _i such that a _i ∈^∗ X _i. If $X=\bigcup _{i=1}^n X_i$, then A ∈^∗Fin(X), as it is easily shown by applying transfer to the elementary property: “∀x ₁, …, x _k ∈ X {x ₁, …, x _k}∈Fin(X)”.

• (3) This is a direct consequence of transfer and the definition of hyperfinite set.

• (4) Pick X and Y  with $A\in { }^*\mathcal {P}(X)$ and $B\in { }^*\mathcal {P}(Y)$. Then apply transfer to the property: “For every $C\in \mathcal {P}(X)$, for every $D\in \mathcal {P}(Y)$, for every f ∈Fun(C, D) and for every F ∈Fin(X) with F ⊆ C, the image f(F) is in Fin(Y )”.

Example 2.55

For every pair N < M of (possibly infinite) hypernatural numbers , the interval

$$\displaystyle \begin{aligned}{}[N,M]_{{}^{\ast}\mathbb{N}}\ =\ \{\alpha\in{}^{\ast}\mathbb{N}\mid N\le\alpha\le M\}\end{aligned}$$

is hyperfinite. Indeed, applying transfer to the property: “For every $x,y\in \mathbb {N}$ with x < y, the set $[x,y]_{\mathbb {N}}=\{a\in \mathbb {N}\mid x\le a\le y\}\in \text{Fin}(\mathbb {N})$”, one obtains that $[N,M]_{{ }^{\ast }\mathbb {N}}\in { }^*\text{Fin}(\mathbb {N})$.¹¹ More generally, it follows from transfer that every bounded internal set of hyperintegers is hyperfinite.

Whenever confusion is unlikely, we will omit the subscript, and write directly [N, M] to denote the interval of hypernatural numbers determined by $N,M\in { }^{\ast }\mathbb {N}$.

Definition 2.56

A hyperfinite sequence is an internal function whose domain is a hyperfinite set A.

Typical examples of hyperfinite sequences are defined on initial segments $[1,N]\subset { }^{\ast }\mathbb {N}$ of the hypernatural numbers. In this case we use notation 〈ξ _ν∣ν = 1, …, N〉.

By transfer from the property: “For every nonempty finite set A there exists a unique $n\in \mathbb {N}$ such that A is in bijection with the segment {1, …, n},” one obtains that there is a well-posed definition of cardinality for hyperfinite sets.

Definition 2.57

The internal cardinality |A|_h of a nonempty hyperfinite set A is the unique hypernatural number α such that there exists an internal bijection f : [1, α] → A.

Proposition 2.58

The internal cardinality satisfies the following properties:

• 1. If the hyperfinite set A is finite, then |A|_h = |A|.

• 2. For any $\nu \in { }^{\ast }\mathbb {N}$ , we have |[1, ν]|_h = ν. More generally, we have |[α, β]|_h = β − α + 1.

Proof

• (1) If A is a finite internal set of cardinality n, then every bijection f : [1, n] → A is internal by Proposition 2.44.

• (2) The map f : [1, β − α + 1] → [α, β] where f(i) = α + i − 1 is an internal bijection.

When confusion is unlikely, we will drop the subscript and directly write |A| to also denote the internal cardinality of a hyperfinite set A.

The following is a typical example of a property that hyperfinite sets inherit from finite sets. It is obtained by a straightforward application of transfer, and its proof is left as an exercise.

Proposition 2.59

Every nonempty hyperfinite subset of ${ }^{\ast }\mathbb {R}$ has a least element and a greatest element.

A relevant example of a hyperfinite set which is useful in applications is the following.

Definition 2.60

Fix an infinite $N\in { }^{\ast }\mathbb {N}$. The corresponding hyperfinite grid $\mathbb {H}_N\subset { }^{\ast }\mathbb {Q}$ is the hyperfinite set that determines a partition of the interval $[1,N]\subset { }^{\ast }\mathbb {R}$ of hyperreals into N-many intervals of equal infinitesimal length 1∕N. Precisely:

$$\displaystyle \begin{aligned}\mathbb{H}_N\ =\ \left\{ [1+\frac{i -1}{N}, 1+(N-1)\frac{i}{N}]\, \Bigm|\,i=1,2, \ldots, N\right\}.\end{aligned}$$

We close this section with a couple of result about the (infinite) cardinalities of hyperfinite sets.

Proposition 2.61

If $\alpha \in { }^{\ast }\mathbb {N}$ is infinite, then the corresponding interval $[1,\alpha ]\subset { }^{\ast }\mathbb {N}$ has cardinality at least the cardinality of the continuum .

Proof

For every real number r ∈ (0, 1), let

$$\displaystyle \begin{aligned}\psi(r)\ = \min\{\beta\in[1,\alpha]\mid r<\beta/\alpha\}.\end{aligned}$$

Notice that the above definition is well-posed, because $\{\beta \in { }^{\ast }\mathbb {N}\mid r<\beta /\alpha \}$ is an internal bounded set of hypernatural numbers , and hence a hyperfinite set. The map $\psi :(0,1)_{\mathbb {R}}\to [1,\alpha ]_{{ }^{\ast }\mathbb {N}}$ is 1-1. Indeed, ψ(r) = ψ(s) ⇒|r − s| < 1∕α ⇒ r ∼ s ⇒ r = s (recall that two real numbers that are infinitely close are necessarily equal). Thus, we obtain the desired inequality $\mathfrak {c}=|(0,1)_{\mathbb {R}}|\le |[1,\alpha ]_{{ }^{\ast }\mathbb {N}}|$.

Corollary 2.62

If A is internal, then either A is finite or A has at least the cardinality of the continuum . In consequence, every countably infinite set is external.

Proof

It is easily seen by transfer that an internal set A is either hyperfinite , and hence there is an internal bijection with an interval $[1,\alpha ]\subset { }^{\ast }\mathbb {N}$, or there exists an internal 1-1 function $f:{ }^{\ast }\mathbb {N}\to A$. In the first case, if $\alpha \in \mathbb {N}$ is finite, then trivially A is finite. Otherwise $|A|=[1,\alpha ]\ge \mathfrak {c}$ by the previous proposition. In the second case, if α is any infinite hypernatural number , then $|A|\ge |{ }^{\ast }\mathbb {N}|\ge |[1,\alpha ]|\ge \mathfrak {c}$.

6.1 Hyperfinite Sums

Similarly to finite sums of real numbers, one can consider hyperfinite sums of hyperfinite sets of hyperreal numbers .

Definition 2.63

If $f:A\to \mathbb {R}$ then for every nonempty hyperfinite subset Ω ⊂^∗ A, one defines the corresponding hyperfinite sum by setting:

$$\displaystyle \begin{aligned}\sum_{\xi\in \varOmega}\,{}^{\ast}f(\xi)\ :=\ {}^*S_f(\varOmega),\end{aligned}$$

where $S_f:\text{Fin}(A){\setminus }\{\emptyset \}\to \mathbb {R}$ is the function {r ₁, …, r _k}↦f(r ₁) + … + f(r _k).

As a particular case, if $a=\langle a_n\mid n\in \mathbb {N}\rangle$ is a sequence of real numbers and $\alpha \in { }^{\ast }\mathbb {N}$ is a hypernatural number , then the corresponding hyperfinitely long sum is defined as

$$\displaystyle \begin{aligned}\sum_{i=1}^\alpha a_i\ =\ {}^*S_a(\alpha)\end{aligned}$$

where $S_a:\mathbb {N}\to \mathbb {R}$ is the function n↦a ₁ + … + a _n.

Remark 2.64

More generally, the above definition can be extended to hyperfinite sums ∑_{ξ ∈ Ω} F(ξ) where $F:{ }^{\ast }A\to { }^{\ast }\mathbb {R}$ is an internal function, and Ω ⊆^∗ A is a nonempty hyperfinite subset. Precisely, in this case one sets $\sum _{\xi \in \varOmega }F(\xi )={ }^*\mathcal {S}(F,\varOmega )$, where $\mathcal {S}:\text{Fun}(A,\mathbb {R})\times (\text{Fin}(A){\setminus }\{\emptyset \})\to \mathbb {R}$ is the function (f, G)↦∑_{x ∈ G} f(x).

Let us mention in passing that hyperfinite sums can be used to directly define integrals. Indeed, if $N\in { }^{\ast }\mathbb {N}$ is any infinite hypernatural number and $\mathbb {H}$ is the corresponding hyperfinite grid (see Definition 2.60), then for every $f:\mathbb {R}\to \mathbb {R}$ and for every $A\subseteq \mathbb {R}$, one defines the grid integral by putting:

$$\displaystyle \begin{aligned}\int_A f(x)d_{\mathbb{H}}(x)\ =\ \operatorname{st}\left(\frac{1}{N}\sum_{\xi\in\mathbb{H}\cap{}^{\ast}A}{}^*f(\xi) \right).\end{aligned}$$

Notice that the above definition applies to every real function f and to every subset A. Moreover, it can be shown that if $f:[a,b]\to \mathbb {R}$ is a Riemann integrable function defined on an interval, then the grid integral coincides with the usual Riemann integral.

7 Overflow and Underflow Principles

Proposition 2.65 (Overflow Principles)

• 1. $A\subseteq \mathbb {N}$ is infinite if and only if its hyper-extension ^∗ A contains an infinite number.

• 2. If $B\subseteq { }^{\ast }\mathbb {N}$ is internal and $B\cap \mathbb {N}$ is infinite then B contains an infinite number.

• 3. If $B\subseteq { }^{\ast }\mathbb {N}$ is internal and $\mathbb {N}\subseteq B$ then [1, α] ⊆ B for some infinite $\alpha \in { }^{\ast }\mathbb {N}$.

Proof

Item (1) follows from Propositions 2.22 and 2.27. For Item (2), suppose that B does not contain an infinite number. Then B is bounded above in ${ }^{\ast }\mathbb {N}$. By transfer, B has a maximum, which is necessarily an element of $\mathbb {N}$, contradicting that $B\cap \mathbb {N}$ is infinite. For Item (3), let $C:=\{\alpha \in { }^{\ast }\mathbb {N} \ : \ [1,\alpha ]\subseteq B\}$. Then C is internal and $\mathbb {N}\subseteq C$ by assumption. By Item (2) applied to C, there is α ∈ C that is infinite. This α is as desired.

Proposition 2.66 (Underflow Principles)

• 1. If $B\subseteq { }^{\ast }\mathbb {N}$ is internal and B contains arbitrarily small infinite numbers, then B contains a finite number.

• 2. If $B\subseteq { }^{\ast }\mathbb {N}$ is internal and [α, +∞) ⊆ B for every infinite $\alpha \in { }^{\ast }\mathbb {N}$ then [n, +∞) ⊆ B for some finite $n\in \mathbb {N}$.

Proof

For Item (1), suppose that B does not contain a finite number. Then the minimum of B is necessarily infinite, contradicting the assumption that B contains arbitrarily small infinite numbers. Item (2) follows by applying Item (1) to the internal set $C:=\{\alpha \in { }^{\ast }\mathbb {N} \ : \ [\alpha ,+\infty )\subseteq B\}$.

In practice, one often says they are using overflow when they are using any of the items in Proposition 2.65 and likewise for underflow. Below we will present a use of overflow in graph theory.

7.1 An Application to Graph Theory

Recall that a graph is a set V  (the set of vertices) endowed with an anti-reflexive and symmetric binary relation E (the set of edges). Notice that if G = (V, E) is a graph then also its hyper-extension ^∗ G = (^∗ V,^∗ E) is a graph. By assuming as usual that ^∗ v = v for all v ∈ V , one has that G is a sub-graph of ^∗ G. A graph G = (V, E) is locally finite if for every vertex v ∈ V , its set of neighbors N _G(v) = {u ∈ V ∣{u, v}∈ E} is finite. One has the following simple nonstandard characterization.

Proposition 2.67

A graph G = (V, E) is locally finite if and only if ^∗(N _G(v)) ⊆ V  for every v ∈ V .

Proof

If G is locally finite then for every v ∈ V  the set of its neighbors N _G(v) = {u ₁, …, u _n} is finite, and so ^∗ N _G(v) = {^∗ u ₁, …,^∗ u _n} = {u ₁, …, u _n}⊆ V . Conversely, if G is not locally finite, then there exists a vertex v ∈ V  such that N _G(v) is infinite, and we can pick an element τ ∈^∗(N _G(v))∖N _G(v). Now, τ∉V , as otherwise τ ∈^∗(N _G(v)) ∩ V = N _G(v), a contradiction.

Recall that a finite path in a graph G = (V, E) is a finite sequence 〈v _i∣i = 1, …, n〉 of pairwise distinct vertexes such that {v _i, v _i+1}∈ E for every i < n. A graph is connected if for every pair of distinct vertices u, u′ there exists a finite path 〈v _i∣i = 1, …, n〉 where v ₁ = u and v _n = u′. A hyperfinite path ^∗ G is a hyperfinite sequence 〈v _i∣i = 1, …, N〉 for $N\in { }^{\ast }\mathbb {N}$ of pairwise distinct vertexes v _i ∈^∗ V  such that {v _i, v _i+1}∈^∗ E for every i < n. An infinite path is a sequence $\langle v_i\mid i\in \mathbb {N}\rangle$ of pairwise distinct vertexes such that {v _i, v _i+1}∈ E for every $i\in \mathbb {N}$.

Theorem 2.68 (König’s Lemma - I)

Every infinite connected graph that is locally finite contains an infinite path.

Proof

Given a locally finite connected graph G = (V, E) where V  is infinite, pick u ∈ V  and τ ∈^∗ V ∖V . Since G is connected, by transfer there exists a hyperfinite sequence 〈v _i∣i = 1, …, μ〉 for some $\mu \in { }^{\ast }\mathbb {N}$ where v ₁ = u and {v _i, v _i+1}∈^∗ E for every i < μ. By local finiteness, ^∗(N _G(v ₁)) ⊆ V  and so v ₂ ∈ V  and {v ₁, v ₂}∈ E. Then, by induction, it is easily verified that the restriction $\langle v_i\mid i\in \mathbb {N}\rangle$ of the above sequence to the finite indexes is an infinite path in G.

A simple but relevant application of overflow proves the following equivalent formulation in terms of trees. A graph is a tree if between any pair of distinct vertices u, u′ there exists a unique finite path 〈v _i∣i = 1, …, n〉 where v ₁ = u and v _n = u′. A rooted tree is a tree with a distinguished vertex, called the root. The vertices of a tree are also called nodes. The height of a node (other than the root) in a rooted tree is the length of the unique finite path that connects is to the root. A branch of a rooted tree is an infinite path $\langle v_i\mid i\in \mathbb {N}$ such that v ₁ is equal to the root.

Theorem 2.69 (König’s Lemma - II)

Every infinite, finitely branching tree has an infinite path.

Proof

Let T _n denote the nodes of the tree of height n. Since T is finitely branching, each T _n is finite. Since T is infinite, each T _n ≠ ∅. By overflow , there is $N>\mathbb {N}$ such that T _N ≠ ∅. Fix x ∈ T _N. Then

$$\displaystyle \begin{aligned} &\{y\in T \mid \text{ either }y\text{ is the root of }T\text{ or }y\text{ is connected to }x\text{ by a hyperfinite path} \\ &\quad \text{that does not pass from the root of }T\} \end{aligned} $$

is an infinite branch in T.

Exercise 2.70

Prove the last assertion in the proof of Theorem 2.69.

8 The Saturation Principle

The transfer principle is all that one needs to develop the machinery of nonstandard analysis, but for advanced applications another property is also necessary, namely:

Definition 2.71

Countable Saturation Principle: Suppose $\{B_n\}_{n\in \mathbb {N}}\subseteq { }^{\ast }A$ is a countable family of internal sets with the finite intersection property. Then $\bigcap _{n\in \mathbb {N}}B_n\neq \emptyset$.

Exercise 2.72

Assume countable saturation. Then every sequence $\langle B_n\mid n\in \mathbb {N}\rangle$ of internal elements can be extended to an internal sequence $\langle B_n\mid n\in { }^{\ast }\mathbb {N}\rangle$, that is, there exists an internal function σ with domain ${ }^{\ast }\mathbb {N}$ and such that σ(n) = B _n for every $n\in \mathbb {N}$.

Countable saturation will be instrumental in the definition of Loeb measures. In several contexts, stronger saturation principles are assumed where also families of larger size are allowed. Precisely, if κ is a given uncountable cardinal, then one considers the following.

Definition 2.73

κ-saturation property : If $\mathcal {B}$ is a family of internal subsets of ^∗ A of cardinality less than κ, and if $\mathcal {B}$ has the finite intersection property, then $\,\bigcap _{B\in \mathcal {B}} B\neq \emptyset$.

Notice that, in this terminology, countable saturation is ℵ ₁-saturation.

In addition to countable saturation, in the applications presented in this book, we will only use the following weakened version of κ-saturation , where only families of hyper-extensions are considered.

Definition 2.74

κ-enlarging property: Suppose $\mathcal {F}\subseteq \mathcal {P}(A)$ has cardinality $|\mathcal {F}|<\kappa$. If $\mathcal {F}$ has the finite intersection property, then $\bigcap _{F\in \mathcal {F}}{ }^*F\neq \emptyset$.¹²

As a first important application of the enlarging property, one obtains that sets are included in a hyperfinite subset of their hyper-extension.

Proposition 2.75

If the κ-enlarging property holds, then for every set X of cardinality |X| < κ there exists a hyperfinite subset H ⊆^∗ X such that X ⊆ H.

Proof

For each a ∈ X, let $\mathcal {X}_a:=\{Y\subseteq X \ : \ Y \text{ is finite and }a\in Y\}$. One then applies the κ-enlarging property to the family $\mathcal {F}:=\{\mathcal {X}_a \ : \ a\in X\}$ to obtain $H\in \bigcap _{a\in X}{ }^{\ast }\mathcal {X}_a$. Such H is as desired.

The saturation property plays a key role in the application of nonstandard methods to topology, as the next example shows.

Example 2.76

Let (X, τ) be a topological space with character < κ, that is, such that each point x ∈ X has a base of neighborhoods $\mathcal {N}_x$ of cardinality less than κ. If we assume the κ-enlarging property, the intersection $\mu (x)=\bigcap _{U\in \mathcal {N}_x}{ }^*U$ is nonempty. In the literature, μ(x) is called the monad of x. Monads are the basic ingredient in applying nonstandard analysis to topology, starting with the following characterizations (see, e.g., [91, Ch.III]):

• X is Hausdorff if and only if distinct points of x have disjoint monads;

• A ⊆ X is open if and only if for every x ∈ A, μ(a) ⊆^∗ A;

• C ⊆ X is closed if and only if for every x∉C, μ(x) ∩^∗ C = ∅;

• K ⊆ X is compact if and only if ^∗ K ⊆⋃_{x ∈ K} μ(x).

8.1 Saturation in the Ultrapower Model

We now show that the ultrapower model ${ }^{\ast }\mathbb {R}=\mathbb {R}^I/\mathcal {U}$ introduced in Sect. 2.4 provides an example of nonstandard map that satisfies saturation. Let us start with a direct combinatorial proof in the case of ultrapowers modulo ultrafilters on $\mathbb {N}$.

Theorem 2.77

For every non-principal ultrafilter $\mathcal {U}$ on $\mathbb {N}$ , the corresponding ultrapower model satisfies countable saturation.

Proof

Let {B _n} be a countable family of internal subsets of ${ }^{\ast }\mathbb {R}$ with the finite intersection property. For every n, pick a function $T_n:\mathbb {N}\to \mathcal {P}(\mathbb {R}){\setminus } \emptyset$ such that

$$\displaystyle \begin{aligned}B_n\ =\ \widehat{T}_n\ =\ \left\{[\sigma]\in{}^{\ast}\mathbb{R}\mid \{i\in \mathbb{N}\mid \sigma(i)\in T_n(i)\}\in\mathcal{U}\right\}.\end{aligned}$$

For any fixed n, pick an element τ(n) ∈ T ₁(n) ∩⋯ ∩ T _n(n) if that intersection is nonempty. Otherwise, pick an element τ(n) ∈ T ₁(n) ∩⋯ ∩ T _n−1(n) if that intersection is nonempty, and so forth until τ(n) is defined. By the definition of τ, one has the following property:

• If T ₁(n) ∩⋯ ∩ T _k(n) ≠ ∅ and n ≥ k then τ(n) ∈ T ₁(n) ∩… ∩ T _k(n).

Now let k be fixed. By the finite intersection property, $\widehat {T}_1\cap \ldots \cap \widehat {T}_k\ne \emptyset$, so there exists $\sigma :\mathbb {N}\to \mathbb {R}$ such that $\varLambda _j=\{i\in \mathbb {N}\mid \sigma (i)\in T_j(i)\}\in \mathcal {U}$ for every j = 1, …, k. In particular, the set of indexes $\varGamma (k)=\{i\in \mathbb {N}\mid T_1(i)\cap \ldots \cap T_k(i)\ne \emptyset \}\in \mathcal {U}$ because it is a superset of $\varLambda _1\cap \ldots \cap \varLambda _k\in \mathcal {U}$. But then the set $\{i\in \mathbb {N}\mid \tau (i)\in T_1(i)\cap \ldots \cap T_k(i)\}\in \mathcal {U}$ because it is a superset of $\{i\in \varGamma (k)\mid i\ge k\}\in \mathcal {U}$. We conclude that $[\tau ]\in \widehat {T}_1\cap \ldots \cap \widehat {T}_k$. As this holds for every k, the proof is completed.

The above result can be extended to all ultrapower models where the ultrafilter $\mathcal {U}$ on I is countably incomplete (recall that every non-principal ultrafilter on $\mathbb {N}$ is countably incomplete).

Theorem 2.78

For every infinite cardinal κ there exist ultrafilters $\mathcal {U}$ on the set I = Fin(κ) of finite parts of κ such that the corresponding ultrapower model satisfies the κ ⁺ -enlarging property.

Proof

For every x ∈ κ, let $\widehat {x}=\{a\in I\mid x\in a\}$. Then trivially the family $\mathcal {X}=\{\widehat {x}\mid x\in \kappa \}$ has the finite intersection property. We claim that every ultrafilter $\mathcal {U}$ that extends $\mathcal {X}$ has the desired property.

Suppose that the family $\mathcal {F}=\{B_x\mid x\in \kappa \}\subseteq \mathcal {P}(A)$ satisfies the finite intersection property. Then we can pick a sequence σ : I → A such that σ(a) ∈⋂_{x ∈ a} A _x for every a ∈ I. The proof is completed by noticing that [σ] ∈^∗ A _x for every x ∈ κ, since $\{a\in I\mid \sigma (a)\in A_x\}\supseteq \widehat {x}\in \mathcal {U}$.

A stronger result holds, but we will not prove it here because it takes a rather technical proof, and we do not need that result in the applications presented in this book. The proof can be found in [25, §6.1].

Theorem 2.79

For every infinite cardinal κ there exist ultrafilters $\mathcal {U}$ on κ (named κ ⁺ -good ultrafilters ) such that the corresponding ultrapower models satisfy the κ ⁺ -saturation property.

9 Hyperfinite Approximation

As established in Proposition 2.75, in sufficiently saturated structures, hyperfinite sets can be conveniently used as “approximations” of infinite structure. The fact that they behave as finite sets makes them particularly useful objects in applications of nonstandard analysis. In this section we will see a few examples to illustrate this. We assume that the nonstandard extension satisfies the κ-enlarging property, where κ is larger than the cardinality of the objects under consideration.

Theorem 2.80

Every infinite set can be linearly ordered.

Proof

Let X be an infinite set, and let κ be the cardinality of X. We can assume that the nonstandard map satisfies the κ ⁺-enlargement property. By Proposition 2.75 there exists a hyperfinite H ⊆^∗ X such that {^∗ x∣x ∈ X}⊆ H. By transfer applied to the corresponding property of finite sets, H can be linearly ordered, whence so can {^∗ x∣x ∈ X}, and hence X.

The next theorem is a generalization of the previous one:

Theorem 2.81

Every partial order on a set can be extended to a linear order.

Proof

We leave it as an easy exercise by induction to show that every partial order on a finite set can be extended to a linear order. Thus, we may precede as in the previous theorem. This time, H is endowed with the partial order it inherits from ^∗ X, whence, by transfer, this partial order can be extended to a linear order. This linear order restricted to X extends the original partial order on X.

Recall that a k-coloring of a graph G for some $k\in \mathbb {N}$ is a function that assigns to each vertex of G and element of {1, …, k} (its color) in such a way that vertices connected by an edge are given different colors. A graph is k-colorable if and only if it admits a k-coloring.

Theorem 2.82

A graph is k-colorable if and only if every finite subgraph is k-colorable.

Proof

Suppose that G is a graph such that every finite subgraph is k-colorable. Embed G into a hyperfinite subgraph H of ^∗ G. By transfer, H can be k-colored. The restriction of this k-coloring to G is a k-coloring of G.

The next result plays an important role in the application of ultrafilter and nonstandard methods. Let S be a set. Say that f : S → S is fixed-point free if f(x) ≠ x for all x ∈ S.

Theorem 2.83

Suppose that f : S → S is fixed-point free. Then there is a function c : S →{1, 2, 3} (that is, a 3-coloring of S) such that c(f(x)) ≠ c(x) for all x ∈ S.

Proof

In order to use hyperfinite approximation , we first need a finitary version of the theorem:

Claim

For every finite subset $F\subseteq \mathbb {N}$, there is a 3-coloring c _F of F such that c(f(n)) ≠ c(n) whenever n, f(n) ∈ F.

Proof of Claim

We prove the claim by induction on the cardinality of F, the case |F| = 1 being trivial since F never contains both n and f(n). Now suppose that |F| > 1. Fix m ∈ F such that |f ⁻¹(m) ∩ F|≤ 1. Such an m clearly exists by the Pigeonhole principle. Let G := F∖{m}. By the induction assumption, there is a 3-coloring c _G of G such that c(f(n)) ≠ c(n) whenever n, f(n) ∈ G. One extends c _G to a 3-coloring c _F of F by choosing c _F(m) different from c _G(f(m)) (if f(m) ∈ G) and different from c _G(k) if k ∈ G is such that f(k) = m (if there is such k). Since we have three colors to choose from, this is clearly possible. The coloring c _F is as desired.

Now that the claim has been proven, let H ⊆^∗ S be hyperfinite such that S ⊆ H. By transfer, there is an internal 3-coloring c _H of H such that c(f(x)) ≠ c(x) whenever x, f(x) ∈ H. Since x ∈ S implies n, f(n) ∈ H, we see that the restriction of c _H to S is a 3-coloring of S as desired.

Notes and References

Nonstandard analysis was introduced by Robinson in the 1960s [112]. Robinson’s original approach was based on model theory. Shortly after, Luxemburg proposed an alternative approach based on the ultrapower construction [99], which helped to further popularize nonstandard methods. Indeed, the ultrapower construction is still one of the most common ways to present nonstandard methods. This is the approach followed in [53], which is an accessible introduction to nonstandard analysis, including a rigorous formulation and a detailed proof of the transfer principle . The foundations of nonstandard analysis are also presented in detail in §4.4 of [25]. A survey of several different possible approaches to nonstandard methods is given in [11]. A nice introduction to nonstandard methods for number theorists, including many examples, is presented in [80] (see also [76]). Finally, a full development of nonstandard analysis can be found in several monographs in the existing literature; see e.g. Keisler’s classical book [83], or the comprehensive collection of surveys in [3].