Ultraproducts & Ultrafilters

Ultrafilters

Definition: A filter $U$ on a set $S$ is an ultrafilter if for every $X\subset S$, then either $X\in U$ or it’s complement $S/X\in U$.

Definition: A filter $F$ on a set $S$ is maximal if there is no filter $F^{\prime }$ on $S$ such that $F\subset F^{\prime }$.

A filter $F$ on a set $S$ is maximal if and only if $F$ is an ultrafilter.

Theorem: Every filter can be extended to an ultrafilter. Proof: Let $F_0$ be a filter on a set $S$. Let $P$ be the set of all filters $F$ on $S$ such that $F\supset F_0$ and partially ordered set $(P,\subset )$. If $\mathcal{C}$ is a chain in $P$, then from Forcing, $\bigcup \mathcal{C}$ is a filter and so an upper bound of $\mathcal{C}$ on $P$. By Zorn’s lemma there exists a maximal element $U\in P$. From the above, $U$ is an ultrafilter.

Ultraproducts

Let $U$ be an ultrafilter on a set $X$, $\tau$ a vocabulary, and $({\mathcal{M}}_{\alpha }{)}_{\alpha \in X}$

An ultraproduct is defined as $\mathcal{M}=\left({\prod }_{\alpha \in X}{\mathcal{M}}_{\alpha }\right)/U$

Domain: $M=\{g:X\to \bigcup _{\alpha \in X}{M}_{\alpha }|g(\alpha )\in M_{\alpha }\text{ for all }\alpha \in X\}/\sim$ For $\sim$ is an equivalence relation obtained from the ultrafilter.

$g\sim g^{\prime }⟺\{\alpha \in X|g(\alpha )=g^{\prime }(\alpha )\}\in U$, i.e., two functions $g$ and $g^{\prime }$ are equivalent if and only if the set of indices such that $g(\alpha )=g^{\prime }(\alpha )$ is in the ultrafilter $U$

For a constant symbol $c\in \tau$, then $c^{\mathcal{M}}:=[\alpha \mapsto c^{{\mathcal{M}}_{\alpha }}{]}_{\sim }$, i.e., the ultraproducts interpretation of a constant symbol is defined as the equivalence class (for the relation $\sim$) of the function which maps and index $\alpha$ to the interpretation of the constant symbol in ${\mathcal{M}}_{\alpha }$

For a relation symbol $R\in \tau$ of arity $k$, then $R^{\mathcal{M}}([g_1{]}_{\sim },\dots ,[g_k{]}_{\sim })⟺\{\alpha \in X|R^{{\mathcal{M}}_{\alpha }}[g_1(\alpha )],\dots ,[g_k(\alpha )]\}\in U$

For a function symbol $f\in \tau$ of arity $k$, then $f^{\mathcal{M}}([g_1{]}_{\sim },\dots ,[g_k{]}_{\sim })=[g_0{]}_{\sim }⟺\{\alpha \in X|f^{{\mathcal{M}}_{\alpha }}(g_1(\alpha ),\dots ,g_k(\alpha ))=g_0(\alpha )\}\in U$ $\to$ The atomic formula is true in the ultraproduct if it is true in ‘almost’ all factors ${\mathcal{M}}_{\alpha }$ $\to$ This can also be applied to other filters (not just ultrafilters) although the product is a ‘reduced’ product and not an ultraproduct.

Łoś Theorem (ultraproducts): For a formula $\phi (x_1,\dots ,x_n)$ of vocabulary $\tau$ (in the language $\mathcal{L}$, which we are working in) and elements $[g_1],\dots ,[g_k]\in \mathcal{M}:=\prod _{\alpha \in X}{\mathcal{M}}_{\alpha }/U$, then $\mathcal{M}\models \phi ([g_1],\dots ,[g_k])⟺\{\alpha \in X|{\mathcal{M}}_{\alpha }\models \phi (g_1,\dots ,g_k)\}\in U$

Proof: Induction over the ‘shape’ of the formula $\phi$. $\phi$ of the form $R(x_1,\dots ,x_k)$ for $R\in \tau$:

• $\mathcal{M}\models (\phi \wedge \psi )(\overline{[g]})⟺\mathcal{M}\models \phi (\overline{[g]})$ and $\mathcal{M}\models \psi (\overline{[g]})$ (i.e., $⟺\{\alpha \in X|{\mathcal{M}}_{\alpha }\models (\phi \wedge \psi )(\overline{g(\alpha )})\}\in U$

• $\mathcal{M}\models \neg \phi (\overline{[g]})⟺\mathcal{M}\models \phi (\overline{[g]})$ (i.e., $⟺\{\alpha \in X|{\mathcal{M}}_{\alpha }\models \phi (\overline{g(\alpha )})\}\notin U$ or equivalently, $⟺\{\alpha \in X|{\mathcal{M}}_{\alpha }/\models \phi (\overline{g(\alpha )})\}\in U$)

• $\mathcal{M}\models (\exists x.\phi )(\overline{[g]})⟺$ there is $[f]\in \mathcal{M}$ w/ $\mathcal{M}\models \phi ([f],\overline{[g]})$

• Special case: $A^X:=\prod _{\alpha \in X}A$ and $A^X/U:=\prod _{\alpha \in X}{A}^X/U$

Corollary: Th($A^X/U$) = Th($A$)

Interesting case: Let $U$ be a non principal ultrafilter on $\omega$, then the arithmetic structure $\mathcal{N}=\{\mathbb{N},+,\cdot ,<,0,1{\}}^{\omega }/U$ has infinitely large members (larger than other integers)

Ultraproducts can be used to give an alternate proof of the compactness theorem.

References

Forcing [Ultrafilter](Ultrafilter - Wikipedia) jech_03