Talk:Ultraproduct

Product or ultraproduct

The notation used in the equation $[a^{1}],\ldots ,[a^{n}]\in \prod M_{i}$ bothers me. The square brackets suggest we're considering equivalence classes, that is, elements of the ultraproduct, but the text claims that they're elements of the product. I feel like probably $[a^{1}],\ldots ,[a^{n}]\in M$ or $[a^{1}],\ldots ,[a^{n}]\in \prod M_{i}/U$ was meant instead. Can you verify? -lethe ^{talk +} 16:54, 11 April 2006 (UTC)

Good catch. I fixed it. --Trovatore 17:26, 11 April 2006 (UTC)

Łoś' theorem

James M. Henle and Eugene M. Kleinberg's Infinitesimal Calculus (1979, Massachusetts Institute of Technology, republished 2003 by Dover Publications) refers to this theorem as the "fundamental theorem of ultraproducts", and cites Robinson's transfer principle as an application to nonstandard analysis.

They present an inductive proof on first order formulas that uses properties of all filters,not just ultrafilters, implying that the use of a free ultrafilter is only needed so that the entire set of sequences can be used in the ultraproduct. Proper subsets of the ultrafilter, including the cofinite filter on I, would also imply the truth of the theorem as applied to models using suitably limited subsets of the entire set of sequences. Yet, this section concludes that "the fact that U is an ultrafilter (and not just a filter) is used in the negation clause." What negation clause?

If "Łoś" is pronounced "wash", shouldn't the possessive be "Łoś's"? I propose that this section be renamed "Łoś's fundamental theorem of ultraproducts".Alan R. Fisher 05:23, 30 June 2007 (UTC)

Hm, interesting point. I always hear it called "washes theorem" but it seems to me that I rarely see the apostrophe-ess in print. I don't know why. --Trovatore

On your more substantial question, I think what's being referred to is the proof of the theorem by induction on formulas. One case of the induction is when the formula being considered is the negation of a simpler formula. That case is trivial if U is an ultrafilter, but otherwise probably hopeless. --Trovatore 06:04, 30 June 2007 (UTC)

Hopeless? The case for negation of a simpler formula is the easiest part of the entire proof: The agreement set of indices for which the negation holds is the complement of the agreement set of the original formula. Complements of filter members are nonmembers of the filter (and members of the filter's dual ideal). (If the filter is cofinite (Fréchet), its dual is the set of finite sets of indices.) The agreement set of a negation is the complement of the agreement set of the original formula, and the negation in the constructed model has the opposite truth value of the formula in the source model. disjunctions, conjunctions, and implications are only slightly more complex. Henle and Keinberg show the proof for disjunctions and existential quantifications, and challenge the reader to complete the proof for the other cases.

I'll take your comment that you've always heard the theorem called "washes theorem" as an approval to change the possessive in the main article, and add a line crediting "fundamental theorem of ultraproducts" to Henle and Kleinberg. Alan R. Fisher 20:12, 30 June 2007 (UTC)

Last things first: You mean crediting the theorem to them, or just the phrase? Either way, I'm skeptical. If you just want to use them as a reference, then of course that should be fine.

On to negations: Suppose we know the theorem holds for a formula φ and we want to show it holds for ¬φ. Your argument works fine if φ is true in the ultraproduct. But what if it's false? All the induction hypothesis tells us, in that case, is that the set of indices for which φ holds is not in the filter. We can't conclude, just from that, that the set of indices for which ¬φ holds, is in the filter, which is what we need.

In fact, honestly, I don't even know how you interpret atomic formulas, if you don't have an ultrafilter. What if the set of indices on which the atomic formula is true is not in the filter, and neither is its complement? --Trovatore 20:30, 30 June 2007 (UTC)

Just the phrase "fundamental theorem of ultraproducts." Is this single citation sufficient for Wikipedia, or should the phrase be removed as insufficiently cited? Are there any other citable uses of this phrase for Łoś's theorem?

Paraphrasing Henle & Kleinberg, an atomic formula is relation of a finite number of terms, each of which is a particular element, a variable standing for such an element, or a function of a finite number of terms.

Limiting the set of sequences in the constructed model M_i, where M is the source model (I use the "rational function" sequences of reals to construct a set of hyperreals), allows one to use the cofinite filter, the subset common to all free ultrafilters on the index set, the positive integers N im my case. The agreement set of indices i for which the formula φ holds for the ith terms of the sequences holds is cofinite when and only when φ holds in the source model, and its complement, the agreement set for ¬φ is cofinite iff φ does not hold in the source, and nonfinite sets of indices with nonfinite complements are never encountered.

Ultrafilters can define when higher order formulae hold, but may disagree with other ultrafilters. This shows that the formula cannot be rephrased in first order terms within the source model. Example: The natural sequence of positive integers (1, 2, ..., n, ...) is clearly a nonstandard integer, and all integers are either odd or even but not both. Is this sequence odd or even? One ultrafilter that includes to odd terms, say the sequence is odd. Another filter, with the even terms, says the sequence is even. Conclusion: Parity of integers is not a first order property within the reals. (I'm not even sure that "x is an integer" is first order within the real numbers!)Alan R. Fisher 00:13, 1 July 2007 (UTC)

"x is an integer" is equivalent to "∃Z Z⊂R ∧ x∈Z ∧ (y∈Z ∧ y≠1 → 1/y∉Z," which quantizes sets rather than real numbers, and is thus not first order within that set. Alan R. Fisher 08:19, 1 July 2007 (UTC)

You're correct that the property of being an integer is not first-order definable in the reals (with plus and times as the only nonlogical symbols). But I'm afraid the argument you give is not a correct way to prove that. Consider a similar case: Every real number is either negative or nonnegative, and the property of being negative is certainly first-order definable within the real numbers (with plus and times). So consider the element of the ultraproduct represented by the sequence <1, −1, 1, −1, 1, −1, ...>. Is it negative, or nonnegative? --Trovatore 10:35, 1 July 2007 (UTC)

The sequence <1, −1, 1, −1, 1, −1, ...>. Is it negative, or nonnegative? The smart-ass in me wants to answer, "Yes!" The correct answer is that this sequence does indeed require an ultrafilter to decide. But this sequence would never appear in a suitably limited subset of the set of all sequences like my polynomial ratio sequences.

I still do not see any "negation clause" that requires an ultrafilter. Ultrafilters are only needed for cases where nonfinite agreement sets have nonfinite complements, as in this sequence.

The polynomial ratio functions of real numbers serve as a formal model and justification of Leibnizian calculus even without the full transfer principle. (Why did no one between Weierstrass and Robinson point out this model, and show the formalists were too hasty in throwing out the infinitesimals?) By making these functions of the positive integers, and thus a subset of the ultraproduct model with all the first-order properties of the reals, it should be much easier to introduce students already familiar with the infinitesimal approach to calculus to the wider implications of nonstandard analysis. More advanced model theory including ultrafilters and the Axiom of Choice can be introduced afterward.

I should give credit to Eric Schecter's page on defining the real numbers as my source for the "rational functions" as an example of a field with infinitesimals. Go to http://www.math.vanderbilt.edu/~schectex/courses/thereals/ and search the file for infinitesimals. He told me by email that he was introduced to the idea by fellow mathematicians a few years earlier at a meeting, but he no longer had the names of his sources. Alan R. Fisher 09:49, 2 July 2007 (UTC)

So I'm not too sure what you mean by "polynomial ratio sequences". Do you mean that the sequence can only be of the form <r(0),r(1),r(2),...>, where r is a rational function? That might possibly work, for the specific case of the structure <R,0,1,+,*>. At least I don't immediately know a counterexample.

However: (1) the proof would be somewhat involved, as it would rely on the limited expressive power of first-order logic in that structure (e.g. the fact that all functions first-order definable over the structure are rational functions oops--that's not actually a "fact"; you can define the square-root function, for example), and (2) it would fall apart as soon as you made the expressive power a little stronger. For example, as soon as you can define the trig functions, you'll have the same problem with the cosine of the element represented by <0,π,2π,3π...>. So it seems rather limiting as a way of introducing the calculus.

Still, it does seem like an interesting avenue to explore. --Trovatore 17:44, 2 July 2007 (UTC)

(Thanks for helping me clarify my ideas. A lot of this extended discussion will be reflected in the paper I am still working on.)

I use "polynomial ratio" as an alternative name for "rational function" to avoid confusing these functions with functions from Q to Q. (The constant function f(x) = √2 is a "rational function" even though it's an irrational number.) A "polynomial ratio sequence" is a sequence derived from such a function, say f(x), with the nth term being f(n). The advantage of using sequences rather than functions of real numbers for a nonstandard model is that it is easier to extend the meanings of standard formulae from the standard model to the nonstandard one.

Ultraproduct models of the hyperreals numbers contain sequences (e.g., exponential sequences) that make infinitesimals and unlimited elements of what traditional calculus refers to as "higher order" (infinitely smaller or larger) than any polynomial ratio, but they are not essential to actual problems in analysis.

In science, it frequently takes powerful methods or tools to make important discoveries that lesser tools may confirm. I think my polynomial ratios are an example of more modest tools that merely confirm the discovery Robinson made with model theory and ultraproducts, the most powerful tools at his command. Alan R. Fisher 18:16, 3 July 2007 (UTC)

While (as you've alluded to) this isn't really the proper use of this talk page, it's so interesting that I'll indulge myself one more time and make a few more remarks. We should really quit here, though.

1. "Rational function" is completely standard terminology and is not ambiguous. It's rarely a good idea to reinvent the wheel on nomenclature just because you can think of another possible meaning of the standard term.
2. Rational functions aren't actually going to do it. For example, you need to be able to take the square root of the element represented by <0,1,2,...>, and there is no sequence induced by a rational function whose square gives you that sequence cofinitely often. You'll have to extend the possible sequences (say, to all functions first-order definable over <R,+,*>).
3. The reason you don't see any problem with the "negation" step of the induction is that you're effectively using an ultrafilter -- it's just that it's not an ultrafilter on the Boolean algebra of all subsets of the naturals. It's an ultrafilter on a different Boolean algebra; namely, all finite and cofinite subsets of the naturals. That choice does make the negation step trivial. The hard part now becomes proving that the set of all indices where the proposition holds, is actually an element of that Boolean algebra. That will require a harder and more delicate argument than I think you've come to terms with (if, that is, it's even true).

Good luck with your research! While your hope of using this to simplify the introduction to calculus is in my opinion extremely unlikely to work, it's not impossible that the mathematics as a whole will work, and it does sound like a fun question to investigate. --Trovatore 01:27, 4 July 2007 (UTC)

As one can see by some of my work on Wikipedia this year, I have some ideas about hyperreal numbers and nonstandard analysis that are still unpublished, and therefore are not yet ready for entry in this encyclopedia. They need some kicking around in an open forum. Does anyone know an internet discussion group on this topic that would be more suitable than these discussion pages? Alan R. Fisher 02:10, 1 July 2007 (UTC)

"the axiom of choice is needed at the existential quantifier step" The ultrafilter lemma suffices and is, in ZF, strictly weaker than the axiom of choice. ---Dagme (talk) 18:47, 2 May 2012 (UTC)

Hyperreal example - bad statement?

In the examples section, this is stated:
"The hyperreal numbers are the ultraproduct of one copy of the real numbers for every natural number, with regard to an ultrafilter over the natural numbers containing all cofinite sets."
But that is wrong, since a filter containing all cofinite sets is not an ultrafilter:
let F={cofinite subsets of N}={A in N such that N\A is finite} when N is the set of natural numbers and N\A={n in N and not in A}
let A be the subset of even natural numbers and B the subset of odd natural numbers,
then N\A=B and N\B=A, therefore A and B are not cofinite and therefore A and N\A are not in F and therefore F is not an ultrafilter but simply a filter. Rockyrackoon (talk) 15:54, 16 June 2009 (UTC)

There's nothing wrong with the statement. It does not state that the ultrafilter contains only cofinite sets. The ultrafiter can (and indeed must) contain also other sets. — Emil J. 16:00, 16 June 2009 (UTC)

Wrong statement in the proof of Los's Theorem

The following statement is in the proof, I think it is wrong:

The fact that $U$ is an ultrafilter (and not just a filter) is used in the negation clause, and the axiom of choice is needed at the existential quantifier step.

I'm quite rusty, but, it seems to me AOC is not required. Only requires that U be a set closed for contain. The Compactness theorem is proved using this one and the Boolean Ulrafilter Axiom, which is weaker than AOC. It says the Compactness Theorem is equivalent to boolean Ultrafilter Axiom (over ZF) - both are weaker than AOC. Itaj Sherman (talk) 02:58, 24 May 2020 (UTC)