There are two slightly different notions of ultraproduct. Why is one said to be better than the other? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T11:42:52Z http://mathoverflow.net/feeds/question/105397 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/105397/there-are-two-slightly-different-notions-of-ultraproduct-why-is-one-said-to-be There are two slightly different notions of ultraproduct. Why is one said to be better than the other? Tom Leinster 2012-08-24T17:01:39Z 2012-08-25T13:09:27Z <p>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. </p> <p>For the sake of discussion, I'll call them "Type 1" and "Type 2" ultraproducts.</p> <p><strong>Type 1</strong> $\$ The <strong>type 1 ultraproduct</strong> of <code>$(X_i)_{i \in I}$</code> with respect to $\mathcal{U}$ is $$\Bigl( \prod_{i \in I} X_i \Bigr) \Bigl/ \sim$$ where <code>$$(x_i)_{i \in I} \sim (x'_i)_{i \in I} \iff \{ i \in I: x_i = x'_i \} \in \mathcal{U}.$$</code></p> <p><strong>Type 2</strong> $\$ View the poset $(\mathcal{U}, \subseteq)$ as a category. The <strong>type 2 ultraproduct</strong> of <code>$(X_i)_{i \in I}$</code> 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 <code>$$(x_j)_{j \in J} \approx (x'_k)_{k \in K} \iff \{ i \in J \cap K: x_i = x'_i \} \in \mathcal{U}.$$</code></p> <p><strong>The difference</strong> $\$ 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. </p> <p><strong>The question</strong> $\$ 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?</p> <p><strong>A vague guess at an answer</strong> $\$ I think I can guess <em>very</em> roughly what's going on. There's been a tradition in logic &mdash; maybe dying out now? &mdash; 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. </p> <p>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. </p> <p><strong>See also</strong> <a href="http://mathoverflow.net/questions/11261/" rel="nofollow">This question</a> of Joel David Hamkins, and its responses.</p> http://mathoverflow.net/questions/105397/there-are-two-slightly-different-notions-of-ultraproduct-why-is-one-said-to-be/105405#105405 Answer by François G. Dorais for There are two slightly different notions of ultraproduct. Why is one said to be better than the other? François G. Dorais 2012-08-24T17:46:06Z 2012-08-24T17:46:06Z <p>The main factor in choosing between Type 1 and Type 2 ultraproducts is whether or not <a href="http://en.wikipedia.org/wiki/Empty_domain" rel="nofollow">empty domains</a> make sense in the given context.</p> <p>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. </p> <p>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.</p> <p>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.</p> <p>(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.)</p> http://mathoverflow.net/questions/105397/there-are-two-slightly-different-notions-of-ultraproduct-why-is-one-said-to-be/105418#105418 Answer by Andreas Blass for There are two slightly different notions of ultraproduct. Why is one said to be better than the other? Andreas Blass 2012-08-24T20:23:14Z 2012-08-24T20:23:14Z <p>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.</p> http://mathoverflow.net/questions/105397/there-are-two-slightly-different-notions-of-ultraproduct-why-is-one-said-to-be/105437#105437 Answer by Michael Barr for There are two slightly different notions of ultraproduct. Why is one said to be better than the other? Michael Barr 2012-08-25T02:15:47Z 2012-08-25T02:15:47Z <p>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.</p> http://mathoverflow.net/questions/105397/there-are-two-slightly-different-notions-of-ultraproduct-why-is-one-said-to-be/105464#105464 Answer by Tom Leinster for There are two slightly different notions of ultraproduct. Why is one said to be better than the other? Tom Leinster 2012-08-25T13:02:24Z 2012-08-25T13:09:27Z <p>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".</p> <p>I'll use the standard notation for the ultraproduct of <code>$(X_i)_{i \in I}$</code> 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.</p> <p>(1) <em>Ultraproduct with respect to a principal ultrafilter is projection.</em> 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$.</p> <p>(2) <em>Ultraproducts preserve finite coproducts.</em> That is, writing $+$ for the coproduct (disjoint union) of sets, <code>$$\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}$$</code> 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 <em>ultra</em>$\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 &amp;\text{if } i \in J\\ \emptyset &amp;\text{otherwise} \end{cases} \qquad\ \qquad Y_i = \begin{cases} \emptyset &amp;\text{if } i \in J\\ 1 &amp;\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$.</p> <p>I guess all of these things that go wrong are intimately related to <a href="https://en.wikipedia.org/wiki/Ultraproduct" rel="nofollow">Łoś's theorem</a>, which Michael alluded to.</p>