21
$\begingroup$

Let $I$ be a set and $\mathcal{U}$ an ultrafilter on $I$. Let $(X_i)_{i \in I}$ be an $I$-indexed family of sets. The ultraproduct of the family $(X_i)$ with respect to $\mathcal{U}$ is, everyone agrees, another set. But which set is it? There are two different definitions, and they sometimes give different results.

For the sake of discussion, I'll call them "Type 1" and "Type 2" ultraproducts.

Type 1 $\ $ The type 1 ultraproduct of $(X_i)_{i \in I}$ with respect to $\mathcal{U}$ is $$ \Bigl( \prod_{i \in I} X_i \Bigr) \Bigl/ \sim $$ where $$ (x_i)_{i \in I} \sim (x'_i)_{i \in I} \iff \{ i \in I: x_i = x'_i \} \in \mathcal{U}. $$

Type 2 $\ $ View the poset $(\mathcal{U}, \subseteq)$ as a category. The type 2 ultraproduct of $(X_i)_{i \in I}$ with respect to $\mathcal{U}$ is the colimit of the functor $(\mathcal{U}, \subseteq)^{\text{op}} \to \mathbf{Set}$ defined on objects by $$ J \mapsto \prod_{j \in J} X_j $$ and on maps by projection. Explicitly, then, the Type 2 ultraproduct is $$ \Bigl( \coprod_{J \in \mathcal{U}} \prod_{j \in J} X_j \Bigr) \Bigl/ \approx $$ where $$ (x_j)_{j \in J} \approx (x'_k)_{k \in K} \iff \{ i \in J \cap K: x_i = x'_i \} \in \mathcal{U}. $$

The difference $\ $ The two types of ultraproduct are the same if either none of the sets $X_i$ are empty or almost all of them are empty. But in the remaining case, where at least one $X_i$ is empty but the set of such $i$ is not large enough to belong to $\mathcal{U}$, they're different: the Type 1 ultraproduct is empty but the Type 2 ultraproduct is not.

The question $\ $ I've read in a couple of texts (both coming from the point of view of categorical logic) that the Type 2 ultraproduct is really the right one. But why? On what criteria is Type 2 judged to be better than Type 1?

A vague guess at an answer $\ $ I think I can guess very roughly what's going on. There's been a tradition in logic — maybe dying out now? — of taking all structures to be nonempty by definition. But when you move to the more general setting of categorical logic, that's no longer a satisfactory approach. Although in the category of sets, there's just a single object with no elements, in many other categories, there are lots of interesting objects with no (global) elements: e.g. there are lots of interesting sheaves with no global sections.

So categorical logic sometimes involves a recasting of classical, set-based logic, in order to handle empty sets/types satisfactorily. I imagine that something of the sort is going on here. (I only defined ultraproducts of sets, but you could of course define ultraproducts of objects of any other sufficiently complete category.) But still, I don't see clearly why Type 2 is the right choice.

See also This question of Joel David Hamkins, and its responses.

$\endgroup$
1

4 Answers 4

14
$\begingroup$

Since the question mentions texts with a categorical-logic point of view, which tends to connect with constructive logic, and since Francois's answer (with which I completely agree) adopts the viewpoint of classical logic, it seems worthwhile to add the following. As Francois said, empty domains are not very interesting, so it's natural to ignore them. But in constructive logic, it may not be decidable whether a domain is empty. That is, given a set $D$, one cannot generally assert that either $D$ is empty (and therefore safe to ignore) or $D$ has a member. To prove that the two definitions of ultraproduct give the same (i.e., canonically isomorphic) results, one needs that the domains of the structures have members (and in fact, one needs a choice function for these domains). If one is working in constructive model theory (but nevertheless managed somehow to get hold of an ultrafilter), then it's a bad idea to try to ignore empty structures, and so one must pay attention to the difference between the two definitions of ultraproduct.

$\endgroup$
2
  • $\begingroup$ Thanks, that's helpful too. I suppose I'd been subconsciously assuming that since we're working with ultrafilters, we're in a world where choice is assumed, but now that I think about it, that doesn't hold any kind of water. $\endgroup$ Aug 24, 2012 at 22:44
  • 11
    $\begingroup$ +1 for raising the idea of a black market for ultrafilters that a constructivist might furtively purchase. $\endgroup$
    – Terry Tao
    Aug 25, 2012 at 0:40
14
$\begingroup$

I once asked a logician why he insisted that algebras be non-empty. In Graetzer's book on universal algebra, he has a theorem that the intersection of any family of subalgebras of an algebra is either empty or a subalgebra. The answer the unnamed logician gave me was that it was because ultraproducts didn't work right otherwise. Specifically, it should be the case (as it is indeed with the second definition) that an ultraproduct be empty iff the set of empty factors is in the ultrafilter. The property of being empty is, I guess a first order property (is it, actually?) and should react like any other first order property. Anyway, the second definition obviously does have the desired property. So any categorist will insist on the second definition.

$\endgroup$
1
  • 2
    $\begingroup$ Being empty is first order. It means the statement there exists x is false. $\endgroup$ Aug 25, 2012 at 16:37
13
$\begingroup$

The main factor in choosing between Type 1 and Type 2 ultraproducts is whether or not empty domains make sense in the given context.

A majority of logical systems for first-order logic do not allow empty domains. This avoids a lot of technical difficulties. Since empty structures are arguably not that interesting, there is not much loss in doing that. This simplifying assumption brings a multitude of technical advantages that occur throughout the development of logic. For example, when laying the groundwork for structures and models, it is handy to always have at least one variable assignment. However, such a simplifying assumption is not at all necessary and it is possible to develop first-order logic in a way that allows empty domains.

Another routine simplifying assumption is that there is only one sort of object. Indeed, multiple sorts can always be simulated using unary predicates to distinguish different domains. However, there are many contexts where multiple sorts make a lot of sense and this unary predicate "hack" is undesirable. Categorical logic is such a context.

The use of multiple sorts amplifies the empty domain problem. Indeed, each sort has its own domain and a structure is not necessarily uninteresting when some of these domains are empty. When all domains are nonempty, there is no difference between Type 1 and Type 2 ultraproducts. However, if only one of the domains is empty in the structures involved in a Type 1 ultraproduct, then the corresponding domain of the ultraproduct will also be empty. This violates the basic idea that the ultraproduct captures what happens "almost always" in the collection of structures. This problem is fixed with Type 2 ultraproducts where the ultraproduct domain will be nonempty precisely when "almost all" of the corresponding domains in the structures involved in the ultraproduct are nonempty.

(Note that if unary predicates are used to distinguish sorts using the "hack" described above, then the Type 1 ultraproduct does do the right thing and the end result is the "hacked" version of what would be the Type 2 ultraproduct of the structures.)

$\endgroup$
15
  • 3
    $\begingroup$ Related: See the Appendix (pdf p. 14/16) in archive.numdam.org/ARCHIVE/CTGDC/CTGDC_1986__27_2/… $\endgroup$ Aug 24, 2012 at 17:49
  • 3
    $\begingroup$ You could of course get a modified version 1' by allowing partial functions, as long as their domain is in the ultrafilter. This type 1' ultraproduct is then canonically isomorphic to the type 1 ultraproduct iff all structures are non-empty, but it will never be empty (unless most of the base structures are empty, of course). $\endgroup$
    – Goldstern
    Aug 24, 2012 at 18:56
  • 4
    $\begingroup$ Yes, this is exactly what the Type 2 ultraproduct is. (Tom's 'explicit' definition is the usual one, I think.) $\endgroup$ Aug 24, 2012 at 19:13
  • 5
    $\begingroup$ <flame>I strongly disagree with "avoidance of the empty domain is a good thing". It is a very bad thing, it promotes ad-hoc hacks and definitions, it makes it harder to generalize constructions and proofs. Along the same lines, requiring non-empty metric spaces, non-empty topological spaces, non-trivial rings, etc., is a big mistake. It builds in classical logic, so people have to then rework everything when they pass to sheaves, computability and more generally intuitionistic logic. Bad idea.</flame> $\endgroup$ Aug 25, 2012 at 8:34
  • 3
    $\begingroup$ The criterion is very simple: the correct definition is the one that generalizes to other settings (filter-quotient construction in toposes comes to mind), and it is the one that enjoys a universal property which does not involve ad-hoc side conditions and special cases. $\endgroup$ Aug 25, 2012 at 8:38
7
$\begingroup$

Michael Barr pointed out one thing that goes wrong if you try to use the type 1 definition when some of the sets involved are empty. Now that I understand this issue better, I'll point out a couple of other things that go wrong. They're both of the form "this theorem holds cleanly for type 2 ultraproducts, but for type 1 you have to make exceptions".

I'll use the standard notation for the ultraproduct of $(X_i)_{i \in I}$ with respect to an ultrafilter $\mathcal{U}$ on $I$: $$ \Bigl( \prod_{i \in I} X_i \Bigr) \bigl/ \mathcal{U} $$ (for either of the two definitions). The notation makes more sense for type 1 than type 2, but never mind.

(1) Ultraproduct with respect to a principal ultrafilter is projection. That is, if $k \in I$ and $\mathcal{U}$ is the principal ultrafilter on $k$ then $(\prod X_i)/\mathcal{U} = X_k$. This is true without exception for type 2 ultraproducts. It is almost true for type 1, but fails if $X_k \neq \emptyset$ and $X_i = \emptyset$ for some $i \neq k$.

(2) Ultraproducts preserve finite coproducts. That is, writing $+$ for the coproduct (disjoint union) of sets, $$ \Bigl( \prod_{i \in I} (X_i + Y_i) \Bigr) \bigl/ \mathcal{U} \cong \Bigl( \prod_{i \in I} X_i \Bigr) \bigl/ \mathcal{U} + \Bigl( \prod_{i \in I} Y_i \Bigr) \bigl/ \mathcal{U} $$ for any families of sets $(X_i)$ and $(Y_i)$. This is true without exception for type 2 ultraproducts (using the fact that these are *ultra*$\mbox{}$filters). But again, it isn't quite true for type 1: it can fail when some of the sets are empty. For example, let $I$ be a set, choose any nonempty proper subset $J$ of $I$, and put $$ X_i = \begin{cases} 1 &\text{if } i \in J\\\ \emptyset &\text{otherwise} \end{cases} \qquad\ \qquad Y_i = \begin{cases} \emptyset &\text{if } i \in J\\\ 1 &\text{otherwise,} \end{cases} $$ where $1$ denotes a one-element set. Then according to the type 1 definition, $(\prod(X_i + Y_i))/\mathcal{U} = 1$ but $(\prod X_i)/\mathcal{U} + (\prod Y_i)/\mathcal{U} = \emptyset$.

I guess all of these things that go wrong are intimately related to Łoś's theorem, which Michael alluded to.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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