Translations of
Nonstandardly
Defined Notions

Introduction

In the introduction of the Sochor's paper concerning the metamathematics of the alternative set theory (AST) (in this Journal 1/1992, [S1992]) the reader can get some short information on this theory. It is mentioned there that AST is a suitable framework for nonstandard considerations and that AST gives some new viewpoints on some classical branches of mathematics (topology is mentioned there). Moreover, there is noticed the fact, that AST (in its basical axiomatic form) is exactly as strong as the third order arithmetic, hence much weaker than any classical axioms system of the common set theory. Even in such a weak form it gives a suitable environment for classical mathematical analysis.

In this paper we are interested in the relationship between the "classical mathematical analysis" and much more classical "Leibniz's analysis" understood here as a part of nonstandard analysis. A suitable framework for this investigation gives AST and "new" topology in it, which has brought a new light to the investigated relation. The results obtained by this method we extend for "modern" part of analysis and nonstandard analysis. We use here the more common language of nonstandard analysis (of Nelson's internal set theory and similar ones) rather than that of standard extensions in AST from where the principal ideas has arisen.

Especially we are interested in the following problems: In the works on nonstandard analysis the authors give as theorems the assertions proving the equivalence of the nonstandard and the common descriptions of different analytical notions. A question arises if there is a general theorem describing all the cases in a unified manner and if moreover all possible nonstandardly defined notions (hence not only those ones defined by "old" mathematicians and redescribed by the e - d method) have equivalents in standard mathematics. In the paper we give a precision to these two questions and we give some answers on these questions. The results described here may be (in essence) found in the paper cited at the end of the paper, but the comments given here are quite original ones. The answers on both these questions are (in essence) positive, the standard description always exists. But for the notions only a little more complicated than the classical ones (the limit, continuity, uniform continuity, etc) the standard equivalents are not comprehensive and much more complicated (concerning the syntactical form of the obtained formulas), the equivalents are substantially different from the common e - d notions. This fact points to the branches, where nonstandard methods might play an interesting role.

Another place where nonstandard analysis may play an interesting role (and somewhere this new role appears) is the creation of new interesting mathematical structures and the possibility of a better orientation in them. Here the situation is somewhat similar to the cardinal arithmetic and the infinite combinatoric investigated by the classical set theory. We are not interested in this problematic in this paper.

next page

contents

1. The translations in the framework of classical analytical notions.

By Leibniz, the infinitely small quantities are ideal objects used for solving of mathematical problems similarly as the imaginary numbers serve in algebra (for the solution of the algebraic equations).

The infinitely small quantities (and the infinitely large quantities arisen in the consequence of them) are characterized by the fact, that the same mathematical laws holding in the common mathematics (without infinitely small - here this appendix "without infinitely small" does not appear in the Leibniz's work, but it is very substantial, as it prevents a lot of misunderstandings) hold in the mathematical world extended of them. (As examples of such laws may serve the associative, commutative and distributive laws.) The absolute value of infinitely small quantities are nonzero but less than any positive number from the "real world". The last property, implicitly used by Leibniz, but (by my opinion) not explicitly expressed by him, is the fact, that if we define by the help of infinitely small quantities new relations concerning the objects of the "real" mathematical world (e.g. the notions of limit, continuity, etc), the new relations are "real" worthful mathematical relations and consequently, by the first principle, these relations may be used even for infinitely small quantities. (The limit of the sum is the sum of limits also for infinitely small arguments.)

In spite of indisputable mathematical successes (e.g. the Euler's product formula for sinus), the unclarity of the bases of the calculus using infinitely small quantities has led to some mistakes done even by good mathematicians (e.g. the Cauchy's assertion that the limit of continuous functions is continuous). This circumstance has led to the inclination of the majority of mathematicians to the e - d description of their work. Moreover, the usage of infinitely small quantities even in the intuitive considerations was found by B. Russell as unfruitful and erroneous.

Let us describe a demonstrative mistake arisen when using incorrectly nonstandard mathematics. It is well known, that if there is a natural number with a given property, then there is the least natural number with this property. Let us use this fact on the property "to be an infinitely large natural number". This usage leads either to the assertion that there is a finitely large natural number having infinitely large successor, or to the assertion that any natural number is infinitely large. Both these assertions are intuitively unacceptable. The explanation is quite easy: The property "to be an infinitely large natural number" is not expressible in the common mathematics (without infinitely small quantities) and hence the principle of the least natural number cannot be used for it. The Cauchy's misunderstanding is (in essence) of the same kind, the incorrectness of the argument is only a little more hidden. Moreover, all the incorrect considerations, I have ever met are of this kind.

previous page

next page

contents

We can obtain a mathematical structure in which infinitely small quantities (having all the three our requirements) can be modeled e.g. by the ultrapower of a suitable mathematical structure using a nontrivial ultrafilter on an infinite index set. As a suitable mathematical structure we can take the structure of real numbers with all the functions, or P _w+w (w+w-time iterated powerset on the empty set), where all the common mathematics can be done. (For the operation of ultrapower see [CH-K].) We define, that a real number r in the sense of ultrapower is infinitely small, if its absolute value is less than any positive real number of the original structure. Hence for every positive real number r of the original structure there is a subset m_r ÍI (the index set) such that m_r ÎU (the ultrafilter) and ( "i Îm_r)( r(i)<r) ( r being a real number in the sense of ultrapower is a function from the index set I to real numbers), but there is a set m ÎU, such that ( "i Îm)( r(i) ą0). As the original structure can be elementary embedded into the ultrapower, all the assertions expressible in the language of the original structure (even the parameters from the original structure may be used) hold in the both structures simultaneously. This is a realization of the first requirement for infinitely small quantities. If we take (e.g.) the set of natural numbers as the index set and if we define r(i)=1/i, we obtain a positive real number (in the sense of ultrapower) being less than any positive real number of the original structure and not being zero. (The second requirement concerning infinitely small quantities is satisfied.) If we define by considerations concerning the ultrapower structure a set of elements of P w+k, this set is an element of P _w+k+1 and hence an element of the original structure. (The third requirement is satisfied.)

From these facts we obtain a trivial translation of nonstandardly defined notions to the standard mathematics. "In the sense of the all (the all suitable) ultrapowers it holds ... ." The given "translation" is from the formal point of view a "good" solution of the translation problem. It is a formula mathematically equivalent to the nonstandard notion. But nobody of real mathematicians is satisfied with this solution, as

1) for the classical analytical notions it gives no "reasonable" equivalent, i.e. the equivalent near to the common e - d characterization,

2) it gives no "essentially new" standard information,

3) it is doubtful, if every enlarging (with infinitely small quantities) structure must be an ultrapower.

Let us try to solve the problem of the translation only on the basis of the three properties which we require for all the enlarging structures. The three properties we express in a mathematical theory similar to the set theory. The axioms system of this theory is (in essence) due to P. Vopěnka (see [Č 1976]) and it is very near to the independently created axioms system of the Nelson's Internal set theory (see [N 1977]). This theory is an extension of the G.B. theory

previous page

next page

contents

of classes (i.e. it uses class variables and the schema of normal definitions for classes holds). A new class constant K is added with the meaning of the unenlarged world (i.e. the mathematical world without infinitely small quantities). Contrariwise the universal class V has the meaning of the mathematical world after the enlargement of the infinitely small quantities. The theory is the common G.B. set theory (hence the common mathematics) concerning the formulas without the new class constant K. The subset axiom (and hence the replacement axiom, too) does not hold for formulas with K. (This fact solves the mentioned "paradox" of the nonexistence of the least infinitely large natural number.) The three given properties are expressed in the following way.

TP (Transfer Principle): For every set formula j(a₁,...,a_k) (i.e. no class variables occurs in j and every free set variable of j occurs in the list a₁,...,a_k), the following formula is an axiom:

( "a₁ ÎK,...,a_k ÎK)( j(a₁,...,a_k) ş j^K(a₁,...,a_k)) (where j^K denotes the formula obtained from j by the restriction of the all quantifiers to the class K - i.e. ( "x),( $x) are replaced by ( "x ÎK),( $x ÎK), respectively).

Hence every set formula with parameters of unenlarged world holds simultaneously in the enlarged and unenlarged world.

ID (Idealization): ( $ a)(a ÎN-K), where N denotes the set of natural numbers. It can be proved (in the theory) that all natural numbers of N-K are larger than natural numbers of N ÇK and hence they may be called infinitely large. 1/ a is then an example of infinitely small real number.

ST (Standardization): ( "a ÎK)( "X Ía ÇK)( $b ÎPower(a) ÇK)(X=b ÇK).

   Hence even nonstandardly described system of standard elements of a standard set a determines a standard subset b of a. This standard set b is determined uniquely, as, by the extensionality, two sets with equal elements are equal and by TP two standard sets with equal standard elements are equal.

As an example of the work in the described theory let us prove the following lemma.

Lemma 1.1:( " a ÎN-K)( "n ÎN ÇK)(n< a).

   Hence we are right when calling a ÎN-K infinitely large.

Proof: Let a ÎN & a<n & n ÎN ÇK. We may suppose that a ą0, as 0 ÎK can be easily proved. Let X={t ÎK ÇN; t<a} and by ST let x ÎPower(N) ÇK be such that x ÇK=X. Then by TP we have ( "t Îx)(t<n) and hence x is a bounded (from above) nonempty standard ( ÎK) set of

previous page

next page

contents

natural numbers and it has a maximum. We put m=max(x). As m is the only element being the maximum of the standard set x, by TP we have that m is standard. As m ÎK Çx=X, we have that mŁa. By TP we have m+1 ÎK. The assumption m+1Ła leads to m+1 ÎX=x ÇK in contradiction to the maximality of m. Hence m+1> a and m=a ÎK.

During the proof the reader may noticed that the standard world K is closed on the definitions by set formulas.

   Using the distributive laws for quantifiers (( "x)(A ş B) ® (( "x) A ş ( "x) B) and ( "x)(A ş B) ® (( $x)A ş ( $x)B)) we can immediately extend the equivalence expressed in TP to the following theorem.

Theorem 1.2: ( "a ÎK)((Qx) j(x,a) ş (Q^Kx) j(x,a) ş (Q^Kx) j^K(x,a), where Q_i is a shortcut for " or $ and the vector notation is self-explanatory.

   Hence the set formulas with standard parameters are valid simultaneously in the standard world, enlarged world or we can restrict some quantifiers of the beginning of the prefix to the standard world and the rest of the formula understand in the enlarged world. This circumstance gives a strategy for the proving of formulas. If we need to find an element proving the existence it suffices to find such element in the enlarged world. To prove something for all elements, it suffices to prove it only for all standard elements.

   Now if we have modelled infinitely large natural numbers as the nonstandard natural numbers and finitely large natural numbers as the standard ones, we can naturally define the infinitely large natural numbers and the infinitely small real numbers.

Definition 1.3: 1) IL(a) ş a ÎN-K (the infinitely large natural number).

2) IS(x) ş x ÎE&( "n ÎN ÇK)(1/x<1/n) (the infinitely small real number).

   The fact, that there is no largest finitely large natural number (or the smallest infinitely large natural number), leads to the fact, that every set containing all the infinitely large natural numbers contains all the natural numbers larger than a finitely large natural number and as a corollary we obtain the possibility to substitute the quantification for all infinitely large natural numbers by the quantification for all sufficiently large natural numbers (and similarly for the existence). This is the leading idea of the reformulation of the notions of Leibniz's analysis of infinitely small quantities to the e - d methods. The translation theorem for one quantification of infinitely large natural numbers follows.

Theorem 1.4: Let j(a,a) be a set formula. Then

( "a,IL( a)) j(a,a) ş( $n ÎN ÇK)( " a>n) j( a,a) and dually

( $a,IL( a)) j(a,a) ş( "n ÎN ÇK)( $a>n) j(a,a).

previous page

next page

contents

Moreover, if the parameters a are standard then we obtain even

( "a ÎK)(( "a,IL( a)) j(a,a) ş( $n ÎN)( "a>n) j(a,a)) and

( "a ÎK)(( $a,IL( a)) j(a,a) ş( "n ÎN)( $a>n) j(a,a)).

   In the formulas on the righthand side of the second case the class K does not occurs and hence they are standard assertions - assertions of the common mathematics.

Proof: Both the sides of the first equivalence are equivalent to the assertion, that the set {n;n ÎN & ( "a>n) j(a,a)} contains a standard natural number. The second equivalence is only the dual version of the first one. The third equivalence is an immediate corollary of the first one and Th.1.2., the forth one is the dual version of the third one.

   Note that the translation of formulas containing at the beginning of the prefix a block of quantifiers of the same kind is quite analogous.

   Th.1.4. we use to prove the following lemma.

Lemma 1.5: IS(x) ş( $ aIL(a))(x<1/ a).

Proof: By Th.1.4. ( $ aIL(a))(x<1/ a) ş ( "n ÎN ÇK)( $a>n)(x<1/ a).

   Now we define that two real numbers are infinitely close iff their difference is infinitely small.

Definition 1.6: xy ş IS(x-y).

As another application of Th.1.4. we prove that a standard sequence of real numbers {a_n; n ÎN} has a standard real number a as its limit point iff ( $a IL( a))(a _a a).

Theorem 1.7:Let { a_n;n ÎN} ÎK and a ÎK be a standard sequence of real numbers and a real number. Then a is a limit point of {a_n;n ÎN} is equivalent to ( $ a IL(a))(a a a).

Proof: ( $ aIL( a))(a _a a) ş ( $ aIL( a))IS(a a - a) ş ( $ aIL(a))( $ bIL(b))(a _a - a<1/b). This is equivalent by the forth equivalence of Th.1.4. to ( "n)( $a>n)( $ b>n)(a a - a<1/b) which is equivalent to the common definition.

   Now let us prove the translation for two quantifiers (one change of quantifiers), proved (in essence) by P.Vopěnka (see [Č 1977]). We prove this theorem in the general vector version.

Theorem 1.8: Let j(a,x, b,y,a) be a set formula then

( " aIL( a))( "x)( $ bIL(b))( $y) j( a,x,b,y,a) ş

( "n ÎN ÇK)( $m ÎN ÇK)( "a>m)( "x)( $b>n)( $y) j(a,x, b,y,a) and dually.

If moreover a ÎK, then the formula on the lefthand side of the equivalence is equivalent to the standard formula

( "n ÎN)( $m ÎN)( "a>m)( "x)( $b>n)( $y) j(a,x, b,y,a).

previous page

next page

contents

Proof: By Theorem 1.4. the formula ( $ b IL(b))( $y) j(a,x, b,y,a) is equivalent to ( "n ÎN ÇK)( $b>n)( $y) j( a,x,b,y,a). Changing the universal quantifiers we obtain the formula ( "n ÎN ÇK)( " aIL( a))( "x)( $b>n)( $y) j(a,x, b,y,a) understanding n as a new parame-ter and using once more Th.1.4. on the formula ( " aIL(a))( "x)( $b>n)( $y) j(a,x, b,y,a) we obtain the required equivalent ( "n ÎN ÇK)( $m ÎN ÇK)( "a>m)( "x)( $b>n)( $y) j(a,x, b,y,a)

The second case (this one with standard parameters) we prove similarly as in the proof of Th.1.4. using the first case and Th.1.2.

   As an application of the theorem we prove the equivalence of standard and nonstandard notions for the pointwise limit and the uniform limit of sequences of functions.

Theorem 1.9: Let {f_n;n ÎN} ÎK be a standard sequence of real functions defined on a standard set m, let f be a standard real function defined on m. Then f is the pointwise limit of {f_n;n ÎN} on m iff ( "x ÎM ÇK)( " aIL( a))(f a(x) f(x)) and f is the uniform limit of {f_n;n ÎN} on m iff ( "x ÎM)( " aIL(a))(f a(x) f(x)).

Proof: ( "x ÎM ÇK)( " aIL( a))(f a(x) f(x)) ş ( "x ÎM ÇK)( " aIL( a))( $ bIL( b))(f a(x)-f(x)<1/ b). Using Theorem 1.8. we obtain ( " a IL(a))( $b IL( b))(f a(x) - f(x) < 1/b) ş ( "n ÎN)( $m ÎN)( "a>m)( $ b>n)(f a(x)-f(x)<1/ b) hence we obtain the equivalent ( "x ÎM ÇK)( "n ÎN)( $m ÎN)( "a>m)( $ b>n)(f a(x)-f(x)<1/ b) which is by Th.1.2. equivalent to ( "x ÎM)( "n ÎN)( $m ÎN)( " a>m)( $ b>n)(f a(x)-f(x)<1/ b) which is equivalent to the common standard definition.

Concerning the uniform convergence we have: ( "x Î M)( " a IL(a))(f a(x) f(x)) ş ( "x ÎM)( " aIL( a))( $ bIL( b))(f a(x)-f(x)<1/ b). By Th.1.8. we obtain the equivalent ( "n ÎN)( $m ÎN)( "x ÎM)( "a>m)( $ b>n)(f _a(x)-f(x)<1/ b) which is equivalent to the common standard definition of the uniform limit.

   From Th.1.9. you may see that the Cauchy's misunderstanding was in its essence the same as the formerly (in §0) given example "of the existence of the minimal infinitely large natural number".

   Theorem 1.8. may serve for direct (algorithmical) finding standard equivalents of nonstandardly described classical analytical notions as continuity, uniform continuity, derivation, etc in the similar way as in the proof of Th.1.9. For internal parameters it gives equivalent formulations of some nonstandard notions e.g. microcontinuity.

previous page

next page

contents

2. Comments to the basic translation.

   In this section we describe the extension of the basic translation described in Th.1.8. for modern branches of mathematics (e.g. topology). Furthermore we give examples of more complicated notions, where the given translation does not succeed.

   For modern branches of mathematics we can generalize the notion of being infinitely large, as it is given in the following definition.

Definition 2.1: Let a ÎK be an infinite set. An internal (i.e. an element of V but not necessarily of K) set b ÎPower_fin(a) is called a-infinitely large (a-IL) iff a ÇK Ěb. (In words: iff any standard element of a is an element of b.) By Power_fin(a) we mean here the standard set of all internally finite subsets of a (^*(Power_fin(a)) in the asterisk notation of the enlargements' language).

   The existence of a-IL elements is not implied by the axiom ID given in §1, but it is implied by (even equivalent to) the common requirement of enlargements - the existence of ideal elements for concurrent relations.

   If U is e.g. the neighbourhoods filter of the point x in a topological space, then the nonstandard notion y is near to x may be described as there is a U-infinitely large element f such that y Î Çf. Similarly we proceed in the case of a uniformity.

   When working with e.g. general topological notions we must strengthen the axiom ID to the assumption that for any standard a there is an a-infinitely large element. This assumption is satisfied e.g. in Nelson's internal set theory (see [N 1977]).

   But even this strengthening does not suffice for proving the analogons of Th.1.4. and Th.1.8. The proof of these theorems is based on the assertion that every internal set containing all a-IL elements contain all supersets (elements of Power_fin(a)) of a suitable standard element of Power_fin(a). If we add this assumption (this is equivalent to so-called compactness of enlargement) then we prove analogons of Th.1.4. and Th.1.8. in the same way as in the given basic case. Let us call this assumption the a-compact enlargement property (a-CE). The assumption is e.g. satisfied for a standard set a if the enlargement is k⁺-saturated, where k is the cardinality of a.

Definition 2.2: a-CE property (for a standard infinite) is the property that for every internal set m containing all a-IL set there is a standard set b Î Power_fin(a) such that m É{c;c ÎPower_fin(a)&b Ěc}.

   H.J.Keisler has found an example of an enlargement where the a-CE property does not hold (see [L 1969]). We give here a modification being easier but not so strong. If a is a standard set of the cardinality larger than continuum and M is an enlargement then the ultrapower of M (denote it by U) having the set of natural numbers as its index set is an enlargement, too. Let a denote the natural number in the sense of U represented by the identity function (a(n)=n).

previous page

next page

contents

Consider the internal set m={b ÎPower_fin(a); b>a} (where b is the number of elements of b in the internal sense). m does not contain any standard element of Power_fin(a) but m contains every a-IL element (as, if bŁa then the external cardinality of b may be maximal continuum contradicting the fact, that it contains all the standard elements of Power_fin(a).)

   Note that if b Ěa then a-CE property implies b-CE property. Let us give now the formulation of the analogon of Th.1.8. for a-IL.

Theorem 2.3: Let a, b be standard sets and let a-CE and b-CE properties hold. Let j( a₁,a₂, b₁,b₂,x,y,p) be a set formula. Then

( "a₁a-IL( a₁))( " b₁b-IL(b₁))( "x)( $ a₂a-IL(a₂))( $b₂b-IL( b₂))( $y) j(a₁, a₂, b₁,b₂,x,y,p) ş

( "c₂ ÎPower_fin(a) ÇK)( "d₂ ÎPower_fin(b) ÇK)( $c₁ ÎPower_fin(a) ÇK)( $d₁ ÎPower_fin(b) ÇK)

( "a₁ Éc₁)( "b₁ É d₁)( "x)( $ a₂ É c₂)( $ b₂ Éd₂)( $y) j(a₁, a₂,b₁, b₂,x,y,p) and dually.

Moreover, if p is standard then the restriction to standard in the quantification in the righthandside formula can be omitted and we obtain a standard equivalent.

   Let us consider the following notion which seems to be "quite analytical". Let {f_n;n ÎN} be a standard sequence of real functions defined in a neighbourhood of a standard real number x and let a be a standard real number. a is said to be a limit point in touch to x of the sequence {f_n;n ÎN} iff ( $y,y x)( "a IL( a))(f _a(y) a).   If we try to find a standard equivalent of this notion we can try to generalize the given method and make an attempt with the formula

( "n)( $m)( "k)( $y,y-x<1/k)( "m₁>m)( $n₁>n)(f_m1(y)-a<1/n)

or, with the formula "In every neighbourhood of x there is y such that lim_{n ®Ą}f_n(y)=a." But no one of these formulas is equivalent to the original one (see [Č 1977]). Moreover, the satisfactory relation for standard (formal) arithmetical formulas on N ÇK may be described by a formula of the type ( $a)( "b IL(b))( $ gIL( g))(...) and by e.g. Tarski's theorem (on the nondescribility of true arithmetical formulas by an arithmetical formula) this formula cannot be equivalent to the formula using only natural numbers and, as you can see bellow, only natural numbers can be used in the nonstandard description.

   Now we give the description. But the arguments are quite unpleasant from the formal point of view. For a better orientation in the formal description we use overlining for Gödel's numbers of formulas. Remember also, that every countable standard set (e.g. the satisfactory relation Sat) may be "embedded" into a formally finite internal set (Sat ÇK = y ÇK&Fin(y)). In the following description we use At(B) for "the formula B is atomary", GenSeq(A) for the generating sequence of the formula A, NumVar(A) for the number of variables of A, ^j a for the internal set of ordered j-tuples of elements of a . Remember, moreover, that we may suppose that variables are "clean" (every variable is quantified at most one time and free and bounded variables are disjoint), and

previous page

next page

contents

atomary formulas are only of the type x_i=C, x_i=x_j, x_i<x_j, x_i=x_j+x_k, x_i=x_j.x_k, where C denotes constants for suitable natural numbers, 0,1 suffices.

Theorem 2.4: If A is an arithmetical formula and x₁,...,x_j are variables of A, then <n₁,...,n_j> ÎSat"{A} ş ( $a)( " b IL(b))( $ gIL(g))B( a,b,g,A,<n₁,... ,n_j>,j) for a suitable arithmetical formula B.

Proof: Let us give, at first, a formula describing the satisfactory relation.

<n₁,... ,n_j> Î Sat"{A} ş ( $y)(dom(y)=GenSeq(A) & <n₁,... ,n_j> Îy"{A} &

j=NumVar(A) & ( "B₁&B₂} Î dom(y)) (y"{B₁&B₂} = y"{B₁} Ç y"{B₂}) &

( $ aIL( a))(( "B Îdom(y))(At(B) ®<x₁,...,x_j> Îy"{B} ş

(B(x₁,...,x_j) & ( "iŁj)(x_i< a))) & ( " ŘB Îdom(y))(y"{ ŘB} = ^j a-y"{B})) &

( "( $x_i)B Îdom(y))( "n Î N ÇK)( "x₁,...,x_j)(( "kŁj)(x_k<n) ® (<x₁,...,x_j> Î y"{( $x_i)B} ş ( $m ÎN ÇK)(<x₁,...,x_i-1,m,x_i+1,...,x_j> Î y"{B})))).

This formula consists of three parts. The first one without any quantification restricted to IL, the second one concerning atomary formulas and the negation of formulas and the third one concerning the quantification. To describe a suitable equivalent for the part concerning the quantification we use underlining for the codes of functions from j-tuples of natural numbers to natural numbers (e.g. the Gödel's b -function can be used).

( "n ÎN ÇK)( "x₁,...,x_j)(( "kŁj)(x_k<n) ® (<x₁,...,x_j> Îy"{( $x_i)B} ş

( $m ÎN ÇK)(<x₁,...,x_i-1,m,x_i+1,...,x_j> Î y"{B}))) ş ( "n Î N ÇK)( "m Î N ÇK)( $ l Î N ÇK)

( $ f)(Fcn(f) & l = f & f: ^jn ® n & f constant in i-th coordinate &

( "x₁,...,x_j)(( "kŁj)(x_k<n) ® ((<x₁,...,x_i-1,m,x_i+1,...,x_j> Î y"{B} ® <x₁,...,x_j> Îy"{( $x_i)B}) & (<x₁,...,x_j> Îy"{( $x_i)B} ® <x₁,...,x_i-1,f(<x₁,...,x_j>),x_i+1,...,x_j> Î y"{B})))).

Hence we obtain an equivalent of the form

( $y)(A₁ & ( $ aIL(a))A₂ & ( "n ÎN ÇK)( "m ÎN ÇK)( "t)( $l ÎN ÇK)A₃) which is equivalent to ( $y)(A₁ & ( $ aIL( a))A₂ & ( " bIL(b))( $ gIL(g))( "n<g)( "m<g)( "t)( $ l < b)A₃).

Using prenex operations we obtain ( $y)( " bIL( b))( $ gIL( g))( $ aIL( a))(...). By a coding of y and a small modification we obtain the required form.

   Some doubts concerning the description of the given formula may appear relating to the usage of the metamathematical notation <x₁,...,x_j>, but the usage of e.g. functions instead of j-tupples is less readable.

   Hence we have proved that for finding equivalents of nonstandardly (by the usage of infinitely large numbers) defined notions the usage of auxiliary variables for natural numbers ( e - d methodic can be replaced by n - m methodic) does not suffice. In the third section we prove that the usage of one auxiliary variable for real numbers and a suitable set of real numbers as a parameter (the

previous page

next page

contents

complexity of this set is connected with the complexity of the prefix of the translated formula) does suffice in compact enlargements.

   Let us consider now the standard set Ul( a) (see [CH-H 1972]) defined for natural number a by ( "x ÎPower(N) ÇK)(x ÎUl(a) ş a Îx). For infinitely large a the set Ul( a) is a proper ultrafilter. (This definition can be applied not only for the set of natural numbers N).

   In the case, that the enlarging structure is obtained by an ultrapower using the ultrafilter U, you can see (considering the ultrapower construction), that every Ul( a) is less than U in the Rudin-Keisler ordering of ultrafilters. If U is an ultrafilter on N then we have ( "x ÎU ÇK)( $ aIL( a))(a Îx) (a being represented by the identity function in the ultrapower construction - a(n)=n). Hence the set A of all ultrafilters less than U in R-K ordering of ultrafilters may be defined by ( "M ÎB)(M ÎA ÇK ş ( $a IL(a))( "x ÎM ÇK)( a Îx), where B denotes the set of all ultrafilters on N. As A depends on U and hence on the enlarging structure, there is no standard formula equivalent to ( $ aIL(a))( "x ÎM ÇK)(a Îx). As subsets of natural numbers may be coded by real numbers in the segment <0,1> and hence ultrafilters (being subsets of Power(N)) may be coded by real functions on <0,1>, the assertion can be reformulated to the following theorem (see [S 1977]).

Theorem 2.5. (Sochor): There is a property of standard real functions of the form ( $ aIL( a))( "x ÎE ÇK) j(f,a,x) which is not equivalent to any standard formula.

   Thus we can look for standard equivalents only for suitable enlarging structures. Compact enlargements are a good tip. We describe a translating algorithm for these structures in the third section.

   In enlargements, where every ultrafilter is of the type Ul(x) for a suitable internal x (ultrafilter can be "embedded" into its formally finite internal part and x can be taken from the intersection of this part), the compactness of a standard set M of real numbers is expressed by the formula ( "x ÎM( $y ÎM ÇK)(x y) hence ( "x ÎM)( $ aIL(a))( $y ÎM ÇK)(x-y<1/a) being quite similar to the Sochor's one. Hence Sochor's formula is a quite natural one.

   Note that the equivalence of the given description of compactness to the standard one is not proved by the formerly described "universal" way.

3. The translation of more complicated notions.

   In this section we mention the relatively easy translating algorithms due to Nelson (see [N 1977], [N 1988]). But these algorithms have a disadvantage, that they use auxiliary variables of higher and higher powersets in the dependence of the complexity of the prefix of the translated

previous page

next page

contents

formula. (By auxiliary variables we mean variables occurring newly in the prefix after the translation.)

   Much more attention is devoted to the description of another algorithm (see [Č 1980], [Č 1982], [Č 1984]) using only one auxiliary variable of Power(N) and auxiliary variables for natural numbers. As the description of the satisfactory relation (see Th.2.4.) proves, the usage of the auxiliary variable of Power(N) is necessary.

   Both the Nelson's (reduction) algorithms and the described one have only a theoretical importance, as the obtained standard equivalent is incomprehensive. From the practical point of view they may be useful for finding of interesting nonstandard notions (those ones having the complicated translations).

   As you can noticed the strategy of translation consists of putting forward the quantifiers restricted to standard elements in the prefix of the formula and then using the theorem Th.1.2. To this purpose we must be able to change the quantifiers of different kind. As

( "x)( $n ÎN ÇK) j(n,x,p) ş ( $n ÎN ÇK)( "x) j(n,x,p)

(for a set formula j) and similarly for other variables restricted to standard world (using the CE property), it suffices to note that

( "x ÎK)( $y ÎK) j(x,y,p) ş ( $f ÎK)( "x ÎK) j(x,f(x),p)

(for a set formula j) using "the Skolem's function". But the change of quantifiers we have payed by the appearance of a new more complicated object - a function. Iterating the two mentioned procedures (and the dual ones) we can obtain an equivalent of the required form (with the restricted quantifiers on the beginning of the formula). Just described procedure is the leading idea of the both Nelson's algorithms. As functions may be usually coded by elements of powerset, we have roughly expressed the appearance of more and more complicated functions by the usage of auxiliary variables from higher and higher powersets.

   In our algorithm the principal role plays the following lemma.

Quantifier changing lemma 3.1: Let a be an internally finite set and let X Ěa be a class (external set in the enlargements' language). Let j(a,p) be a set formula then

( "a ÎX) j(a,p) ş ( $b Î(Power_fin(a) - Power_fin(a - X)))( "a Îb) j( a,p) and dually.

Proof: Put b={ a Îa; j( a,p)}.

   Note that the formula y( b,b)=( " a Îb) j(a,p) is a set formula, too.

   Remember that in accordance with our notation Power_fin(x) means the class of all internally finite internal subsets of the class x (hence an external set in the enlargements' terminology). Note, moreover, that our way of changing quantifiers leads only to new (auxiliary) variables of Power_fin(a) hence of "the same level" (e.g. finite subsets of natural numbers may be coded by

previous page

next page

contents

natural numbers). But our auxiliary variables stay in the internal world in the difference with Nelson's algorithms where the auxiliary variables (being standard functions) range in the standard world.

   Using ( $b ÎX)( $g ÎY) j( b, g,p) ş ( $ d ÎX ´Y)( $b)( $g)( d=< b,g> & j(b,g,p)) (and dually) and choosing an infinitely large a, we can find an equivalent of the form ( $aIL( a))( $b ÎX) y( a, b,p) to every normal (i.e. only internal sets are quantified) formula j(N ÇK,p), where x is constructed from a and N ÇK only by the use of the operations Power_fin(Y), complement and cartesian product. We express this fact as the following assertion.

Theorem 3.2: For every normal formula j(N ÇK,p) there is a set formula y(a,b,p) and a parametrical construction of a class X(a) (a subclass of an internally finite set), such that for every a, such that IL(a), we have that j(N ÇK,p) ş ( $b ÎX(a)) y(a, b,p). Moreover the new (auxiliary) variables in y are restricted to sets obtained by the iterated Power_fin operation on a.

   In the case of j(a ÇK,p) where a denotes another standard set (different from N) we proceed quite analogously using only a-IL( a) instead of IL(a).

   To obtain the standard equivalent (if the parameters p are standard) we use topological methods developed in AST.

   Remember that in nonstandard topological considerations the relations of nearness play a substantial role.

Definition 3.3: Let T be a standard topological space and x ÎT ÇK be a standard point in T. A point y ÎT is said to be near to x (notation y Î m(x)) if ( "U ÎU(x) ÇK)(y ÎU), where U(x) is the neighbourhoods filter of x. m(x)= Ç(U(x) ÇK) is called the monad of x.

   Remember that if T is compact, then ( "y ÎT)( $x ÎT ÇK)(y Î m(x)) (all points of T are near-standard). Remember, moreover, that if T is Hausdorff then ( "x,y ÎT ÇK)(x ąy ® m(x) Ç m (y)=0). Hence if T is compact Hausdorff then the system of monads creates a partition and we may consider the relation of nearness as an equivalence relation and we use for it "=" with subscripts and superscripts. In the following text we are interested only in compact Hausdorff spaces.

Definition 3.4: Let T be a standard compact Hausdorff topological space and =_T the corresponding nearness equivalence relation.

1) For X ÍT we put Fig(x) = (=_T)"X (the figure of X)

2) FIG(X) ş X=Fig(X) (X is a figure).

   The following theorem remembers that figures are in one-one correspondence with standard subsets of the topological space.

Theorem 3.5: FIG(X) ş (X=Fig(X ÇK)).

previous page

next page

contents

Proof: Obvious, due to the fact, that every point is near to a standard one.

   Now we can connect the operations used in the construction of the class X in Th.3.2. with operations on compact Hausdorff spaces. By this connection X can be understood as a figure in a suitable space (being metrized in the N ÇK case) and using A for the corresponding standard set we can substitute ( $ b ÎX)(...) by ( $t ÎA ÇK)( $ gIL( g))( $b, r(b,t)<1/g) (...), where r denotes the metric on the corresponding space. Then it suffices only to note the equivalence of ( $ aIL(a)( $t ÎA ÇK)( $gIL( g))(...) ş ( $t ÎA ÇK)( "n ÎN ÇK)( $a>n)( $g>n)(...) and use Th.1.2. for the finishing of finding of the required standard equivalent. Moreover, the spaces in the construction are totally disconnected ones. Hence they may be embedded into real numbers and the set A may be understood as a suitable set of real numbers.

   The operations of complement and cartesian product correspond to the same operations. But the operation Power_fin leads to the Vietoris topology on the hyperspace. To prove this we need some more advanced assertions of nonstandard topology (e.g. that figures of internal sets correspond to closed sets). Hence we choose a more direct elementary way.

Definition 3.6: For aŁ b ÎN we define ^aprd ^b (projection degree function) by the following inductive manner.

1) ^aprd b: b ® a is defined by ^aprd ^b( g)=g for g< a and ^aprd ^b( g)= a -1 for g ła.

2) if ^aprd ^b: x _b ® x _a and ^aprd ^b:y _b ® y _a are defined, then ^aprd ^b:x _b ´y _b ® x _a ´y _a is defined by ^aprd ^b(<t,u>)=< ^aprd ^b(t), ^aprd ^b(u)>.

3) if ^aprd ^b: x _b ® x _a is defined, then ^aprd ^b:Power_fin(x _b) ® Power_fin(x _a) is defined by ^aprd ^b(t)=( ^aprd ^b)"t={ ^aprd ^b(u);u Ît}.

   The definition is not quite correct as the equalities <x,y>={{x},{x,y}} and a+1=a Č {a} may lead to confusions. But I prefer here the easy way of description avoiding the index concerning the level of operations. (For more details see [Č 1984].)

   It is easy to prove that ^aprd ^{b b}prd ^g= ^aprd ^g.

   Now to the levels of operations and to the function prd w-trees may be assigned in such a way that the successors of <t,a> are such vertices <u, a+1> that t = ^a+1prd ^a+2(u). Hence in the first level the successors of <a,a> are <a,a+1> and <a+1,a+1> and for b<a the successor of <b,a> is <b,a+1>.

   On the set of branches of an w-tree a compact totally disconnected Hausdorff topology can be described by the way, that for a branch b the neighbourhoods filter is generated by sets of branches having in the given level (of the tree) the same vertice.

previous page

next page

contents

   In the first level of our construction we obtain the space homeomorphic to the one point compactification of N with the discrete topology. N ÇK forms a figure in the one point compactification and infinitely large natural numbers lay in the monad of the added point.

   The operations used for the creation of the class X( a) in Th.3.2 have counterparts in the corresponding trees and X( a) is obtained as the class of vertices of the level a (in the sense of tree) lieing on branches in the corresponding figure. The described considerations lead to the following theorem.

Theorem 3.7: For every normal formula j(N ÇK,p) a set formula y(x, a,p), a standard w-tree and a standard subset M of the set of branches of the tree can be found in such a way that j(N ÇK,p) ş ( $u ÎM ÇK)( "n ÎN ÇK)( $b>n)( $a>b)( $t)(t( b)=u(b)& y(t( a),a,p)).

Proof: By Theorem 3.2. we can found X( a) and a formula y₁ such that j(N ÇK,p) ş( $v ÎX( a)) y(a,v,p) for every infinitely large a. By the above considerations we can express X(a) as the figure corresponding to a standard set M of branches in the canonical topology of a suitable w-tree. Hence v ÎX( a) ş( $u ÎM ÇK)( $t,a branch) ( $ bIL(b))(u( b)=t(b)&v=t( a)) as u=_T t is expressed by ( $ bIL( b))(u(b)=t( b)) (T denotes the topological space on branches). We can suppose a>b as b> a ®(u(b)=t( b) ®u(a)=t( a)). As ( $ bIL(b))(...) ş ( "n ÎN ÇK)( $b>n)(...) by Theorem 1.4., we obtain j(N ÇK,p) ş ( $u ÎM ÇK)( "n ÎN ÇK)( $b>n)( $a>b)( $t)(t( b)=u(b)& y₁( a,t(a),p)).

   The set M can be defined using only projective operations. The complexity of M (in the projective hierarchy) depends only on the complexity of the prefix of j (after the expression in the prenex form).

   The method can be generalized for a ÇK (instead of N ÇK). For more details see [Č 1984].

References

CMUC=Commentationes Mathematicae Universitatis Carolinae (Prague)

[CH-H1972] G.Cherlin, J.Hirschfeld, Ultrafilters and ultraproducts in non-standard analysis, Contributions to Non-Standard Analysis, Studies in Logic 69, North-Holl. Publ. Comp. 1972, 261-280

[CH-K] C.C.Chang, H.J.Keisler, Model Theory, Studies in Logic 73, North-Holl. Publ. Comp. 1973

[Č1976] K.Čuda, A nonstandard set theory, CMUC 17 (1976), 647-663

previous page

next page

contents

[Č1977] K.Čuda, The relation between e - d procedures and the infinitely small in nonstandard methods, Set theory and hierarchy theory V, Lecture notes in mathematics 619, pp.143-152, Springer-Verlag 1977

[Č1980] K.Čuda, An elimination of infinitely small quantities and infinitely large numbers (within the framework of AST), CMUC 21 (1980), 433-445

[Č1982] K.Čuda, An elimination of the predicate "To be a standard number" in nonstandard models of arithmetic, CMUC 23 (1982), 785-803

[Č1984] K.Čuda, Translation of nonstandard definitions to standard ones, CMUC 25 (1984), 615-634

[L1969] W.A.J.Luxemburg, A general theory of monads, Applications of Model Theory to Algebra, Analysis, and Probability, Holt, Rinehart and Winston, Inc. 1969, 18-86

[N1977] E.Nelson, Internal set theory: A new approach to nonstandard analysis, BAMS 83 (1977), 1165-1198

[N1988] E.Nelson, The syntax of nonstandard analysis, Annals of Pure and Applied Logic 38 (1988), North-Holl. Publ. Comp., 123-134

[S1977] A.Sochor, Differential calculus in the alternative set theory, Set theory and hierarchy theory V, Lecture notes in mathematics 619, pp.273-284, Springer-Verlag 1977

[S1992] A.Sochor, Metamathematics of alternative set theory, From the Logical Point of View 1/92, FU AV Prague 1992.

previous page

contents