Let $(\mathcal{A}_i)_{i \in I}$ be an infinite family of structures of the same type, such that for a cofinite set $J \subseteq I$ the structures $\mathcal{A}_j$ for all $j \in J$ are isomorphic to some finite structure $\mathcal{B}$. Let $U$ be an ultrafilter over $I$. Prove that if $U$ is not principal, then $\prod_{i \in I} \mathcal{A}_i/U$ is isomorphic to $\mathcal{B}$. \

I have used the Lemma: Ultrafilter $U$ over $I$ is principal iff $U$ is of the form $\uparrow\{ i_0 \}$ for some $i_0 \in I$. But it took me nowhere, any help is appreciated!

  • 1
    $\begingroup$ Do you know that if an ultrafilter is nonprincipal it refines the cofinite filter (aka Frechet filter) ? $\endgroup$ – Max Oct 10 '17 at 6:07
  • $\begingroup$ It may also be helpful to know that a finite structure can be classified (up to isomorphism) by a single first-order sentence. $\endgroup$ – russoo Oct 10 '17 at 10:41

As the comments have stated, the key to this problem is two important facts:

  • Any nonprincipal ultrafilter contains every cofinite set.

  • Any finite structure is characterized up to isomorphism by a single first-order sentence.

These are basic results, but can be hard to see at first, so let me give a brief sketch of what's going on here.

For the first one: "contains every cofinite set" is the same as "doesn't contain any finite set" (why?). So it will be enough to show that if $\mathcal{U}$ contains a finite set, then $\mathcal{U}$ is principal; this will follow from the following more general (and quite useful) fact:

If $A\in\mathcal{U}$ and $A=B_1\cup B_2\cup ...\cup B_n$, then some $B_i$ is in $\mathcal{U}$. (And additionally, if the $B_i$s are disjoint then exactly one is in $\mathcal{U}$.)

This is a straightforward proof by induction, and gives you some good experience with using the definition of an ultrafilter. (Interestingly, there is a characterization of ultrafilters in terms of this sort of partition rule!.)

For the second one: it's probably a good idea to first think about the way to say "There are exactly $n$ elements" (for some fixed $n$) with a first-order sentence:

$\exists x_1\exists x_2...\exists x_n[(\bigwedge_{i<j\le n}x_i\not=x_j)\quad\wedge\quad(\forall y(\bigvee_{k\le n}y=x_k))]$

(spaces added for clarity). Note how the "$\exists x_1...\exists x_n$" at the beginning essentially lets us "name" all the elements of the structure by variables, so that we can "talk" about them in the rest of the sentence. Now, think about how a structure (finite or otherwise) is characterized by its "multiplication table" (= the set of all atomic sentences (like "$1+3=4$") which are true in the structure - this is called the atomic diagram), and see if you can do a similar trick ...

It might be good first to try a specific example - say, the group $\mathbb{Z}/3\mathbb{Z}$.

Let me end by saying a bit about how to use these two results to solve the problem. The final key, of course, is Los' Theorem (without which we basically can't do anything with ultraproducts).

Suppose cofinitely many of the structures are isomorphic to some finite structure $\mathcal{B}$.

  • By the first fact, this means that $\{i: \mathcal{A}_i\cong\mathcal{B}\}$ is in $\mathcal{U}$. This doesn't immediately help though, since Los' theorem only lets us transfer sentences, not isomorphism types ...

  • ... and this is where the second fact comes in. There is some sentence $\varphi$ such that $\mathcal{C}\models\varphi \iff \mathcal{C}\cong\mathcal{B}$. Now do you see a way to re-define $\{i: \mathcal{A}_i\cong\mathcal{B}\}$ in terms of satisfying a sentence rather than being isomorphic to something?

(Incidentally, it's worth thinking about why this exercise is false if we don't assume that $\mathcal{B}$ is finite ...)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.