Ultrafilters and Similar Structures

[Dragonfall]

M\equiv N means M and N are elementarily equivalent, that is, for any setence S in the language of M and N, M\models S \Leftrightarrow N\models S.

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 M\models t(y) \Rightarrow n\models t(f(y))

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

How do I do that?

[Dragonfall]

Anyone?

[Hurkyl]

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?

[Dragonfall]

I is any set. And U is an ultrafilter on the subsets of I. M^U is the ultraproduct (\prod_{i\in I}M)/U. That is, the cartesian product of M indexed by the elements of I, modulo U.

(MxMxMxMx...) / U

[Hurkyl]

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.

[Dragonfall]

But why do we need the ultrafilter?

[Hurkyl]

I don't understand the question.

[Dragonfall]

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 \{j\in I:j\supseteq i\}. How does this help?

[lurflurf]

But why do we need the ultrafilter?

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.

[Hurkyl]

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 \{j\in I:j\supseteq i\}. How does this help?
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.

[Dragonfall]

I don't understand the QUESTION itself. What is it asking?

[Hurkyl]

I don't understand the QUESTION itself. What is it asking?
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.

[Dragonfall]

If N and M are elementarily equivalent, then does there exist an elementary embedding N -> M?

[Hurkyl]

If N and M are elementarily equivalent, then does there exist an elementary embedding N -> M?
There doesn't have to be.

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

I can do better -- the reals R and the set of Puiseux series (http://en.wikipedia.org/wiki/Puiseux's_theorem) with coefficients from \mathbb{Q}^r 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.

[Dragonfall]

Then I don't understand why the taking of ultraproducts is going to change that fact.

[Hurkyl]

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,+,*,<)

[Dragonfall]

How would I show this in the general case?

[Hurkyl]

How would I show this in the general case?
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)

[Dragonfall]

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
\{j\in I:j\supseteq i\}
. Is there an injective function N->M^U, at least? I'm having hard time picturing these kinds of things.

[Hurkyl]

So first we have to find a right I such that you can at least map N into M^U injectively.
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,
\{j\in I:j\supseteq i\}
doesn't make sense, because you haven't defined i.

[Dragonfall]

i = arbitrary element of I.

Ok so if I just want an injective function N->M^I, then I can just take N=I. Provided M has at least 2 elements (say, 0 and 1) by sending n from N to (0,0,..,1,0,0,...) where the index of 1 is n. But what does this give me?