Is the ultraproduct concept fundamentally category-theoretic? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T07:14:51Z http://mathoverflow.net/feeds/question/11261 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/11261/is-the-ultraproduct-concept-fundamentally-category-theoretic Is the ultraproduct concept fundamentally category-theoretic? Joel David Hamkins 2010-01-09T22:12:09Z 2010-07-06T16:50:09Z <p>Once again, I would like to take advantage of the large number of knowledgable category theorists on this site for a question I have about category-theoretic aspects of a fundamental logic concept. </p> <p>My question is whether the <a href="http://en.wikipedia.org/wiki/Ultraproduct" rel="nofollow">ultraproduct</a> construction is fundamentally a category-theoretic concept. </p> <p>The ultraproduct/ultrapower construction of Łos is used pervasively in logic, particularly in model theory and also in set theory, where nearly all of the larger large cardinal axioms can be formulated in terms of the existence of certain kinds of ultrapowers of the universe.</p> <p>My question is, is the ultraproduct fundamentally a category-theoretic construction, in the sense that it is characterized by some natural category-theoretic universal property? How about the special case of ultrapowers? </p> <p>I would be very interested, if there were a natural universal characterization in terms of the usual Hom sets for these first order structures, namely, first order elementary embeddings and/or homomorphisms. (Needless to say, I would be much less interested in a characterization that amounted merely to a translation of the Łos construction or of Łos's theorem into category-theoretic language.)</p> <p><b>Background.</b> Suppose we have a collection of structures M<sub>i</sub> for i in J, all of the same first order type (e.g. groups, partial orders, graphs, fields, whatever), and U is an ultrafilter on the index set J. This means that U is a nonempty collection of nonempty subsets of J, containing every set or its complement, and closed under intersection and superset. The ultraproduct &Pi;M<sub>i</sub> /U consists of equivalence classes [f]<sub>U</sub>, where f is a function with domain J, with f(i) in M<sub>i</sub>, and f &sim;<sub>U</sub>g iff {i in J | f(i)=g(i)} in U. One imposes structure on the ultraproduct by saying that a relation holds in the product, if it holds on a set in U, and similarly for functions. Łos's theorem then states that the ultraproduct satisfies a first order formula &phi;([f]<sub>u</sub>) if and only if {i in J | M<sub>i</sub> satisfies &phi;(f(i))} is in U. That is, truth in the ultraproduct amounts to truth on a U-large set of coordinates. The special case when all M<sub>i</sub> are the same model M, we arrive at the <em>ultrapower</em> M<sup>J</sup> /U. In this case, there is a natural map from M into M<sup>J</sup> /U, defined by x maps to [c<sub>x</sub>]<sub>U</sub>, where c<sub>x</sub> is the constant function with value x. It is easy to see that this map is an elementary embedding from M into the ultrapower. </p> <p>This question is a more focused instance of a probably-too-general question I asked <a href="http://mathoverflow.net/questions/7197" rel="nofollow">here</a>, and I may have several more in the future.</p> http://mathoverflow.net/questions/11261/is-the-ultraproduct-concept-fundamentally-category-theoretic/11292#11292 Answer by Andrej Bauer for Is the ultraproduct concept fundamentally category-theoretic? Andrej Bauer 2010-01-10T07:43:39Z 2010-01-10T07:43:39Z <p>This paper comes to mind:</p> <blockquote> <p>Ultrasheaves and double negation. S. Awodey and J. Eliasson, Notre Dame Journal of Formal Logic 45(4), pp. 235--245 (2004). Available at <a href="http://www.andrew.cmu.edu/user/awodey/preprints/udn.pdf" rel="nofollow">http://www.andrew.cmu.edu/user/awodey/preprints/udn.pdf</a></p> </blockquote> <p>Perhaps this is not quite what you are asking for, because the paper takes utrafilters as given, but it certainly gives a useful category-theoretic perspective.</p> http://mathoverflow.net/questions/11261/is-the-ultraproduct-concept-fundamentally-category-theoretic/13455#13455 Answer by François G. Dorais for Is the ultraproduct concept fundamentally category-theoretic? François G. Dorais 2010-01-30T03:14:24Z 2010-01-30T03:14:24Z <p>Andrej's answer was very helpful to me, but there is yet another (perhaps not completely unrelated) category theoretic view of ultraproducts that I am aware of. I am still hopeful that more category theorists will eventually step in and sort things out...</p> <p>If $X$ is a discrete space then a sheaf $F:O(X)^{\mathrm{op}}\to Set$ must be such that $F(A) \cong \prod_{i \in A} F_i$ for some family of sets $(F_i)_{i \in X}$. This sheaf can be moved to a sheaf <code>$F':O(\beta X)^{\mathrm{op}}\to Set$</code>. Viewing $\beta X$ as the space of ultrafilters on $X$, the stalk of $F'$ at a point <code>$\mathcal{U} \in \beta X$</code> is precisely the ultraproduct <code>$\prod_{i \in X} F_i/\mathcal{U}$</code>. (There is one subtle difference which occurs when some of the components $F_i$ are empty, in which case this ultraproduct can still be nonempty when $F(A)$ is nonempty for some $A \in \mathcal{U}$.)</p> <p>From a more global point of view, the embedding $X \to \beta X$ induces a geometric morphism $Sh(X) \to Sh(\beta X)$. Similarly, a point of $\beta X$ can be identified with geometric morphism $\mathcal{U}:Set \to Sh(\beta X)$. The corresponding ultraproduct map is simply the composition $$Sh(X) \to Sh(\beta X) \xrightarrow{\mathcal{U}^*} Set,$$ where the last component is the inverse image part of $\mathcal{U}$. The corresponding ultrapower functor is the composite <code>$$Set \xrightarrow{\Delta} Sh(X) \to Sh(\beta X) \xrightarrow{\mathcal{U}^*} Set,$$</code> where $\Delta$ is the diagonal functor.</p> <p>Of course, there is nothing very special about discrete spaces in the above construction. The same construction exists for any completely regular Hausdorff space $X$ or, more generally, for a completely regular locale. (This makes sense even when the space/locale $X$ is not completely regular, but the map $X \to \beta X$ is not necessarily an embedding.) Of course, Łoś's Theorem takes a different form for this more general construction, the correct form of the theorem for a space/locale X can be found via the Kripke-Joyal semantics, for example.</p> http://mathoverflow.net/questions/11261/is-the-ultraproduct-concept-fundamentally-category-theoretic/26285#26285 Answer by Buschi Sergio for Is the ultraproduct concept fundamentally category-theoretic? Buschi Sergio 2010-05-28T16:55:05Z 2010-05-28T16:55:05Z <p>Let $\Phi$ a filter on the set $I$ and let $X_i \in C\ i\in I$, and for $U \subset I$ let $X_U:=\prod_{i\in U} X_i$ . We have a natural functor $T : P(I)^{op} \to C$ (where $P(I)$ the order of ubset onf $I$) as: $T(U):=X_U$ and for $T(V\subset U) : X_U \to X_V$ the canonical proiection induced by $V \subset U$. Being $I$ the initial object of $P(I)$ and letting $X:=X_I$ follow a "lifting" of $T$ to a functor $T': P(I)^{op} \to X \downarrow C$ as $T'(U)= (T(U\subset I), X_U)$ and $T'(V\subset U)=T(V\subset U)$. For any $U \in \Phi$ let $\alpha_U, \beta_U : K_U \to X$ the kernel pair of $T'(U)$ we obtain a diagram of all these $\alpha_U, \beta_U$ morphisms and the natural $K_{V \subset U}: K_U\to K_V$ induced by $T(V \subset U)$. The colimit of this diagram is the ultrapower of $\prod_{i\in I} X_i$ respecto to $\Phi$. This colimit is the colimits in $X\downarrow C$ of the cokers of the kernel pairs.</p> <p>But things are more simple too: observe that choise a retraction $r: I\to U$ os the inclusion $U\subset I$ we have a section $T(r): T(U)\to X$ on $T(U\subset I)$ give by $\pi_i\circ T(r) = \pi_{r(i)}$ then $T(U\subset I)$ being a retraction is a regular epimorphism (a coker of some pair), then is (well knowed fact) the coker of its Ker-pair $\alpha_U, \beta_U$. Then follow that the ultrapower is the colimit in $X\downarrow C$ of the diagram of $T(U\subset I)\ U\subset I$ as objects and $T(V\subset U)$ as morphisms.</p> http://mathoverflow.net/questions/11261/is-the-ultraproduct-concept-fundamentally-category-theoretic/30782#30782 Answer by Daniel Litt for Is the ultraproduct concept fundamentally category-theoretic? Daniel Litt 2010-07-06T15:02:33Z 2010-07-06T15:02:33Z <p>The other answers so far have generally taken ultrafilters as a given, or used the Stone-Cech compactification (which has a universal property in Top). I'd like to point out that the set of ultrafilters on a set $I$ has a categorical interpretation in Sets. In particular, consider the diagram in Sets consisting of finite partitions $X_i\subset 2^I$ of $I$, with an arrow $X_i\to X_j$ if $X_i$ is a refinement of $X_j$; the arrow sends a subset of $I$ in $X_i$ to the unique element of $X_j$ containing it. Then the set of ultrafilters on $I$ is the inverse limit of this diagram.</p> http://mathoverflow.net/questions/11261/is-the-ultraproduct-concept-fundamentally-category-theoretic/30789#30789 Answer by Peter Arndt for Is the ultraproduct concept fundamentally category-theoretic? Peter Arndt 2010-07-06T16:50:09Z 2010-07-06T16:50:09Z <p>For a short and painless description of how ultraproducts are colimits see page 6 of this article (it is equivalent, but I found it more readable than the descriptions given in the answers):</p> <p><a href="http://www.iphils.uj.edu.pl/rml/rml-42/10-mariano.pdf" rel="nofollow">H. Mariano, F. Miraglia: Profinite structures are retracts of ultraproducts of finite structures</a></p> <p>The article contains a nice application of this categorical description of ultraproducts...</p>