# Ultrafilters and Similar Structures

1. Apr 24, 2008

### 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?

2. Apr 25, 2008

### Dragonfall

Anyone?

3. Apr 25, 2008

### Hurkyl

Staff Emeritus
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?

4. Apr 25, 2008

### 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

5. Apr 25, 2008

### Hurkyl

Staff Emeritus
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.

6. Apr 26, 2008

### Dragonfall

But why do we need the ultrafilter?

7. Apr 26, 2008

### Hurkyl

Staff Emeritus
I don't understand the question.

8. Apr 26, 2008

### 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?

9. Apr 26, 2008

### lurflurf

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.

10. Apr 26, 2008

### Hurkyl

Staff Emeritus
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.

11. Apr 27, 2008

### Dragonfall

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

12. Apr 27, 2008

### Hurkyl

Staff Emeritus
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
13. Apr 27, 2008

### Dragonfall

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

14. Apr 27, 2008

### Hurkyl

Staff Emeritus
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) 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 [URL [Broken] series[/url] 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.

Last edited by a moderator: May 3, 2017
15. Apr 27, 2008

### Dragonfall

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

16. Apr 27, 2008

### Hurkyl

Staff Emeritus
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
17. Apr 27, 2008

### Dragonfall

How would I show this in the general case?

18. Apr 27, 2008

### Hurkyl

Staff Emeritus
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)

19. Apr 28, 2008

### 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.

20. Apr 28, 2008

### Hurkyl

Staff Emeritus
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.