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

Ultrafilters and Similar Structures

  1. Apr 24, 2008 #1
    [tex]M\equiv N[/tex] means M and N are elementarily equivalent, that is, for any setence S in the language of M and N, [tex]M\models S \Leftrightarrow N\models S[/tex].

    An elementary embedding f:M->N is a mapping f:|M|->|N| between the underlying sets such that, for any formula t(x) and matching tuple y of elements of M, we have that [tex]M\models t(y) \Rightarrow n\models t(f(y))[/tex]

    Assume that [tex]M\equiv N[/tex]. Show that there is an ultrafilter U=(I, U) and an elementary embedding [tex]g:N\rightarrow M^U[/tex].

    How do I do that?
     
  2. jcsd
  3. Apr 25, 2008 #2
    Anyone?
     
  4. Apr 25, 2008 #3

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Some notational questions...

    When you say U = (I, U), what exactly are I and U?
    What do you mean by M^U?
    Upon what poset is U an ultrafilter?
     
  5. Apr 25, 2008 #4
    I is any set. And U is an ultrafilter on the subsets of I. M^U is the ultraproduct [tex](\prod_{i\in I}M)/U[/tex]. That is, the cartesian product of M indexed by the elements of I, modulo U.

    (MxMxMxMx...) / U
     
  6. Apr 25, 2008 #5

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Well, the obvious special cases (N is an ultrapower of M, or M is an ultrapower of N) are too esay, they don't give any insight.

    Looking at it set-theoretically, it seems clear that I has to 'know' something about N, which might suggest some things to try.

    However, looking at it formally seems to give the most obvious way to proceed. Your goal is to define g(n) for every n in N... so an obvious starting point is to simply add each "g(n)" as a formal symbol to your language and work from there.
     
  7. Apr 26, 2008 #6
    But why do we need the ultrafilter?
     
  8. Apr 26, 2008 #7

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    I don't understand the question.
     
  9. Apr 26, 2008 #8
    Nevermind the question. Suppose D = the set of sentences true in N. Let I but the set of finite subsets of D. Let U be an ultrafilter containing each subset [tex]\{j\in I:j\supseteq i\}[/tex]. How does this help?
     
  10. Apr 26, 2008 #9

    lurflurf

    User Avatar
    Homework Helper

    I am not sure I understand you.

    The reason we like ultrafilters is say we have a sequence of truth values

    TFTTFTTFFFTTFFTTTFFFFTTTTFFF.....

    we would like a consistent way to assign the seqence a truth value many methods we might consider would be defined only on a subset of all sequences, by using ultrafilters we can decide any sequence.
     
  11. Apr 26, 2008 #10

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    I don't (yet) see how that particular choice of I helps -- I expect this to be the sort of thing that, once you figure out the right I, it's immediately obvious how to map from N into M^U.
     
  12. Apr 27, 2008 #11
    I don't understand the QUESTION itself. What is it asking?
     
  13. Apr 27, 2008 #12

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    For any two elementarily equivalent structures, prove there is an elementary embedding of the first one into an ultrapower of the second one.

    At least, that's the question you asked.
     
    Last edited: Apr 27, 2008
  14. Apr 27, 2008 #13
    If N and M are elementarily equivalent, then does there exist an elementary embedding N -> M?
     
  15. Apr 27, 2008 #14

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    There doesn't have to be.

    For example, in the language of 'ordered rings' (0, 1, +, *, <), the reals and the set [itex]\mathbb{Q}^r[/itex] of real algebraic numbers are elementarily equivalent. (Tarski's theorem) However, there is obviously no injective function [itex]\mathbb{R} \to \mathbb{Q}^r[/itex], and an elementary embedding must be injective....

    I can do better -- the reals R and the set of Puiseux series with coefficients from [itex]\mathbb{Q}^r[/itex] are elementarily equivalent, and I'm pretty sure there cannot be an elementary embedding between them in either direction.

    Yes, I can prove it.

    Assume there is an embedding t from Puiseux series to the reals. The field of Puiseux series has an infinitessimal number x, which satisfies 0 < x, and the (infinitely many) statements x < 1/n, for each natural number n. However, t(x) is a real number, and cannot satisfy all of these formulae.

    Now, suppose there is an embedding t of the real numbers into the field of Puiseaux series. The real numbers contains an element (pi) satisfying each of the infinitely many formulas
    3 < x < 4
    3.1 < x < 3.2
    3.14 < x < 3.15
    ...

    However, every finite Puiseux series is infinitessimally close to an algebraic number, and thus t(x) cannot satisfy all of these formulae.
     
    Last edited: Apr 27, 2008
  16. Apr 27, 2008 #15
    Then I don't understand why the taking of ultraproducts is going to change that fact.
     
  17. Apr 27, 2008 #16

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Well, the reason I identified that the field of Puiseaux series (over the real algebraic numbers) couldn't be embedded into the reals was because it contained a positive infinitessimal element.

    So, if we take a free, countable ultrapower of R -- i.e. we consider the field *R of hyperreals -- we get a bigger structure that does contain an infinitessimal element, into which we can embed the field of Puiseaux series.

    (Incidentally, you should note that "x is an infinitessimal" cannot be expressed as a first-order formula)

    If it helps you work with the Puiseaux series... it has an operational definition as the smallest field that satisfies the properties:
    (1) It contains the rational numbers.
    (2) It contains an infinitessimal number x.
    (3) It is elementarily equivalent to the reals. (In the language of 0,1,+,*,<)
     
    Last edited: Apr 27, 2008
  18. Apr 27, 2008 #17
    How would I show this in the general case?
     
  19. Apr 27, 2008 #18

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    And that's where the fun part of the exercise lies. :tongue:

    The point I was hinting at in the beginning is that given arbitrary sets N and M, there simply isn't any natural way to produce a map N --> M... so the plan is to choose your set I precisely so that it suggests how one might sensibly define a map N --> M^U. Then once we know how to produce sensible maps, then we can spend effort trying to find one that really is a morphism of structures, and then an elementary embedding.


    If you want to study this particular example to see if you can generalize it, note that the point here is that the field of Puiseux series had essentially only one free object x, in terms of which everything else is representable. We mapped it to an infinitessimal element of the hyperreals, one such example is the class of the element
    (1, 1/2, 1/3, 1/4, 1/5, ...)​
    of R^U. So we've found a sequences of putative images for the value of x, and each statement that x satisfies is actually satisfied by almost every term in that sequence. (And is thus satisfied by that element of R^U)
     
  20. Apr 28, 2008 #19
    So first we have to find a right I such that you can at least map N into M^U injectively. Going back to a previous post, if D= set of true setences in N, and I = finite subsets of D, U=ultrafilter containing [tex]
    \{j\in I:j\supseteq i\}
    [/tex]. Is there an injective function N->M^U, at least? I'm having hard time picturing these kinds of things.
     
  21. Apr 28, 2008 #20

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    But it might be too difficult to try and do that all at once -- why not first think about mapping N into M^I? (or into the set of functions I-->M that are defined on 'most' I)

    And one thing to keep in mind: the notion of a function N --> M^I is roughly the same thing as a function N x I --> M.


    Incidentally, [itex]
    \{j\in I:j\supseteq i\}
    [/itex] doesn't make sense, because you haven't defined i.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Ultrafilters and Similar Structures
  1. Similar Quadrilaterals (Replies: 2)

  2. Exact self-similarity? (Replies: 7)

Loading...