Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Nonstandard Analysis

  1. Oct 30, 2003 #1

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Anyone know much about this subject?


    I'm satisfied with my understanding of the basics of the transfer principle. My algebra text has a chapter on real closed fields, including a section on Tarski's theorem, and I see how it relates to the transfer principle. A paper I read recently, plus a revelation I had, cleared up what was the thing bugging me the most about the decidability of real arithmetic.


    However, I am now more troubled by other things. One of the key things about why real arithmetic is complete is because real arithmetic doesn't know what "integer" means.

    Yet, the hyperintegers are used in NSA!

    Also, the completeness of real arithmetic works against analysis; the algebraic numbers are also a model of the theory of real arithmetic, and transcendental functions cannot exist among the algebraic numbers... thus they also must not be a part of real arithmetic.


    So, clearly, this simle theory is not sufficient to do nonstandard analysis. I have found a little bit of information on superstructures... not nearly enough for me to feel I really understand it.

    Does anyone know of any good online resources for NSA? If not, maybe a good book or two?
     
  2. jcsd
  3. Oct 31, 2003 #2
  4. Oct 31, 2003 #3
    I'm puzzled by your puzzlements.

    One of the key things about why real arithmetic is complete is because real arithmetic doesn't know what "integer" means.
    Yet, the hyperintegers are used in NSA!


    Hyperintegers are used in NSA precisely because integers are used in SA. Therefore <0, 0, 0, ...> represents a hyperinteger. So does <1, 1, 1, ...>, and so on. These hyperintegers have standard real correspondents. But also <1, 2, 3, ...> represent a hyperinteger. But <2, 3, 4, ...> and <3, 4, 5, ...> and so on represent smaller and smaller hyperintegers. These hyperintegers have no standard real correspondents.

    Integers are known things in the reals (complete ordered field). -1, 0 and +1 are given by postulates of the field. 0, -1, +1, -1-1, +1+1 and so on are integers. Non-integers are all stuck strictly between pairs of integers i and i+1. Leave real numbers like these out and the remnant is still contains -1, 0 and +1 and it is still closed with respect to repeated additions using these elements. Everything here is still true for hyperintegers in the hyperreals. Hyper-non-integers are all stuck strictly between pairs of hyperintegers i and i+1. Because there exist hyperreal numbers strictly larger than correspondents to real numbers (represented by constant real number sequences), then there necessarily exist hyperintegers larger than any correspondents to real numbers too. Likewise, symmetrically, there necessarily exist hyperintegers smaller than any correspondents to real numbers.

    Also, the completeness of real arithmetic works against analysis; the algebraic numbers are also a model of the theory of real arithmetic, and transcendental functions cannot exist among the algebraic numbers... thus they also must not be a part of real arithmetic.

    If the system of algebraic numbers is a model for real arithmetic, what about the sequence

    1/0!, 1/0! + 1/1!, 1/0! + 1/1! + 1/2!, 1/0! + 1/1! + 1/2! + 1/3!, 1/0! + 1/1! + 1/2! + 1/3! + 1/4!, ...

    ? All of these are good algebraic numbers. All the addend terms 1/n! are monotone decreasing (well, after 1!) strictly positive elements. The sequence of sums is quite cauchy convergent. So, there must be a limit (e) somewhere in that system of numbers. I guess it isn't really true that the field of algebraic numbers is really a complete ordered field.

    You aren't perhaps confused between two senses of the word 'complete', are you?
     
    Last edited: Oct 31, 2003
  5. Oct 31, 2003 #4

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    When I was first learning about NSA, several sources mentioned that the transfer principle was based on the logical completeness of formal real arithmetic.

    I had two major misgivings when I first heard this.

    First off, how could real arithmetic be logically complete when the integers are part of the real numbers. As per Godel's theorem, integer arithmetic is incomplete, so shouldn't real arithmetic too?

    Secondly, the hyperreals clearly are not topologically complete; it seems obvious from their structure, and the theorem that the real numbers are the only complete ordered field cinch this fact. So why doesn't the transfer principle apply here?


    I've since resolved both of these issues I had. The first issue is resolved by the fact that formal real arithmetic cannot define the notion of "integer". So while the integers may be a subset of the reals, number theory is not a subtheory of formal real arithmetic. Similarly, anything that requires integers to define, such as &Sigma;n (1/n!), cannot be defined in formal real arithmetic.

    I figured out the second issue in the shower. :smile: I had read in a paper that Dedikend completeness could be proven as a theorem in formal real arithmetic... and thus must be true for any real closed field (such as algebraic numbers or the hyperreals) and that really threw me for a loop... but I realized that the theorem was only for cuts that could be defined in formal real arithmetic; more general cuts, such as what might define &pi;, cannot be defined in formal real arithmetic. Basically, the kinds of sets that would allow one to prove, say, the algebraic numbers are not topologically complete do not exist in formal real arithmetic.


    So, it's clear that NSA's fundamental underpinnings are not this simple. The key seems to be superstructures to which the transfer principle can be extended, but I can find little introductory material on these things. I can write the definition of a superstructure, and that's about it. :smile: Since we need to permit things like integers and hyperintegers, we must clearly abandon the "trick" of logical completeness, and I can't follow nor divine how to expand the transfer principle to superstructures.
     
  6. Oct 31, 2003 #5
    This all sounds like going crazy over the descriptor 'complete' again.

    I would best write everything out.

    The classical real number axioms include a postulate for 'completeness' in the order <. As usually stated, <-complete means that any non-empty subset of numbers from R with at least some upper bound number z (for ALL x in that subset x <= z) there must be a least upper bound number y (for ALL w in R w is an upper bound of the given subset -> y <= z). In other words, the subset of all upper bound numbers of a subset of R is either empty (in case the original chosen subset was unbounded above) or it contains all real numbers (in case the original chosen subset was empty) or it must have a minimum upper bound number (in case the original chosen subset was not empty and was bounded above). The 'completeness' in the order < deals with the existence of certain elements in the system.

    The completeness of integer arithmetic (ala Gödel incompleteness theorem) deals with 'completeness' in the deductive scope of its logic. If formal integer arithmetic is presumed to be a consistent system, there must be some well-formed proposition in integer arithmetic that is a true proposition, but it can't be deduced from the postulates of arithmetic if those postulates comprise a first-order relational logic system (all universal quantifiers in the logic are applied to variables that cover only the actual elements of the system). This kind of completeness deals not with existence of elements in the system but with propositions that might be deduced within the system logic.

    It is <-completeness that gets used in the development of NSA. To apply transfer to the language of real arithmetic and hyperreal arithmetic, <-completeness of the standard real number system R is used to induce a similar condition into the nonstandard real system *R. There it is restricted to so-called 'internal subsets' of *R and the least upper bounds are the standard real part components of upper bound numbers. So <-completeness in *R is a bit flaky (on purpose).


    still my only book on NSA:
    Martin Davis, Applied Nonstandard Analysis, New York, John Wiley, 1977

    A very nice book! What you probably want is in chapters 1 and 2, including superstructures, formal languages, Los and transfer theorems and the application to real numbers. But Wiley-Interscience doesn't seem to have it any more. Amazon says it is out of print and hard to get. Here is one source I found:
    http://www.countrybookshop.co.uk/cgi-bin/search.pl?searchtype=author&searchtext=Davis+Martin

    Ha! I found the following while searching Wiley:

    Hyperreal transients in transfinite RLC networks
    International Journal of Circuit Theory and Applications
    Volume 29, Issue 6, Date: November/December 2001, Pages: 591-605
    A. H. Zemanian

    That sounds far out!
     
  7. Nov 1, 2003 #6
    myself:

    But also <1, 2, 3, ...> represent a hyperinteger. But <2, 3, 4, ...> and <3, 4, 5, ...> and so on represent smaller and smaller hyperintegers

    No they don't! Better use these:

    <1, 2, 3, ...>
    <0, 1, 2, ...> - same as <1, 1, 2, 3, ...>
    <-1, 0, 1,...> - same as <1, 1, 1, 2, 3, ...>

    etc. That makes a decreasing sequence of hyperintegers.
     
  8. Nov 1, 2003 #7

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    This is, I think, the simplest part of that for what I'm looking. (Sigh, it gets annoying avoiding dangling participles)

    What I have read indicates that one has a "superstructure embedding", and an internal set is one that is the image of this embedding.

    What I have not found is what this embedding looks like, or why one would know such an embedding exists. All I can find is some semi-vague statements about what one is allowed to transfer.


    Anyways, mathworld is what indicated that the completeness of first-order logic was instrumental in how all this works.
     
  9. Nov 2, 2003 #8
    yeah, as far as i know, only first-order statements can be transferred. therefore statements like the least upper bound property for nonempty subsets of R that are bounded above don't necessarily transfer to *R. in fact, it is false that every nonempty bounded above subset of *R has a least upper bound in *R or R.
     
  10. Nov 2, 2003 #9

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    If I understand what I've read correctly, the transfer principle (the one that goes beyond first-order logic) works like this:

    We have this theorem:

    For any subset A of R, if A is nonempty and bounded above in R, then A has a least upper bound in R.

    we transfer to

    For any internal subset A of *R, if A is nonempty and bounded above in *R, then A has a least upper bound in *R.

    (A is an internal subset of *R iff there is a subset B of R such that A = *B)


    Of course, this understanding is of the "someone told me I can do this" type, not the "I know what's going on" type.
     
    Last edited: Nov 2, 2003
  11. Nov 3, 2003 #10
    Dear Hurkyl,

    I might be able to work up something of a prècis of the math part of the embedding process for NSA and to publish it here, but it is a bit difficult for me. I can't use Davis' notation consistently; I don't want to quote too much from his book; I insist on arriving at my own understanding of everything before I publish it. So I can't say when I'd be finished.

    Meanwhile, I wonder about the necessity of the hard foundational approach to NSA, when so many writers use the far easier approach with indices from the positive integers. I wrote Apps and asked him about this, and he sent a rapid reply.

    --->my request:
    Dear Dr. Apps,

    I have a question about the development of NonStandard Arithmetic.

    If nonstandard real numbers (hyperreals) can be produced easily from the ring of infinite real sequences by using a free ultrafilter that extends the filter of cofinite subsets of positive integers, then what is the purpose of all those superstructures/universes/concurrent relations/chains of mappings of concurrent relations into their own domains/ etc.,evidently just to demonstrate the existence of nonstandard numbers larger than standard numbers?

    In other words, why bother?

    Thanks for considering my question.


    --->his reply:
    Don't know if I am the best person to answer the question, but the different ways can have different logical consquences (e.g. what's the set-theoretic cardinality of the nonstandard numbers?), which can be of interest. I vaguely remember reading some papers along these lines in the Logic section of the papers I list. (The Keisler / Kunen / Leth / Miller, perhaps?). But you're right that for many purposes you don't need to pay too much attention to the foundations.

    Philip Apps
     
  12. Nov 4, 2003 #11
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?