# Union of a object (a set) in the Elementary Theory of the Category of Sets

I see the Todd Trimble article "Elementary Theory of the Category of Sets" on catlab.

I ask: how make (in the categorical setting) the usual union of a set $\cup X=${$y |\exists x\in X: y\in x$}?

This object is (strongly) no natural (no amenable to a functor and natural transformation).

I ask this because the "Union axiom" is one of the ZF theory of sets.

-

There are several articles that I wrote on ETCS, which had originally appeared on the (currently inactive) blog Topological Musings. The nLab articles are nothing more than transcriptions of what I had written into MathML, which is what we use at the nLab. They stop a little short of what you are asking for specifically, so perhaps I can fill the gap now, and say how I think I might have proceeded.

As already mentioned by David and Sridhar, ETCS differs from traditional set theories that are based on a global membership relation (theories whose underlying signature consists of a single binary relation $\in$). Instead, ETCS spells out axioms that one expects to hold for a category of sets and functions. For those who speak the language, the axioms amount to saying that a model of ETCS is a topos with a natural numbers object, such that the terminal set is a generator and the axiom of choice ("epis split") holds.

In this framework, one treats "union" as an operation which internalizes the external operation of taking joins in subset lattices. Thus, if $X$ is a set (or an object if you like), the union operation relative to $X$ is an appropriate morphism

$$\bigcup: PPX \to PX$$

where $PX$ denotes the power set/object of $X$. By the universal property of power objects, this morphism corresponds to a subobject of $X \times PPX$. This subobject is specified by the formula (of an internal language for toposes)

$$\exists_{A: PX} (x \in_X A) \wedge (A \in_{PX} C)$$

where $x$ is of type $X$ and $C$ is of type $PPX$.

There are several ways of doing this, even if one is not familiar with the internal language of a topos. One way, which works for general toposes, proceeds by interpreting the quantifier $\exists_{A: PX}$ directly in terms of image factorizations. Namely, consider the image factorization of the composite

$$[(x \in_X A) \wedge (A \in_{PX} C)] \hookrightarrow X \times PX \times PPX \stackrel{proj}{\to} X \times PPX$$

to get the desired subobject $I \hookrightarrow X \times PPX$. (Of course, this requires that one construct image factorizations in a topos, as treated in any standard text.) The subobject described in brackets is, in turn, a pullback of the form

$$(1_X \times \delta \times 1_{PPX})^\ast(\in_X \times \in_{PX})$$

where $\in_X \hookrightarrow X \times PX$ and $\in_{PX} \hookrightarrow PX \times PPX$ are the canonical subobjects, and where $\delta: PX \to PX \times PX$ is the diagonal. Then, as said before, the map $PPX \to PX$ which classifies this image $I \hookrightarrow X \times PPX$ is the desired internal union relative to $X$.

The second way to go is to realize that a model of ETCS is in particular a Boolean topos. Then, if one has already constructed universal quantification (see for instance the second of the three articles in the ETCS series), one can easily interpret the formula

$$\neg \forall_{A: PX} (x \in_X A) \Rightarrow \neg(A \in_{PX} C)$$

once one has defined internal negation, which is not difficult. This circumvents the need to first construct images, but only works in the Boolean case.

However one spells out the details, the larger point is that in ETCS, membership relations are local and relative to objects $X$, in the form of universal subobjects $\in_X \hookrightarrow X \times PX$, as opposed to being given by a single global relation $\in$ that obtains on the class of objects. Correspondingly, set-theoretic operations like union and intersection are also local and relative in this sense. Otherwise, the first-order formulas that specify such operations -- the ones we all know and love -- work pretty much the same way; in ETCS, the relevant operations may be constructed by clever exploitation of universal properties of relations $\in_X$, and not just asserted to exist by way of a comprehension or separation axiom scheme.

-
thank you very much for your reply Mr. Trimble. I just know a little of categorical logic, and internal logic of a topos, but I have to improve a lot of this large deep aspect of mathematic. I see that after Godel theorems we know that mathematics cannot have a foundation that ensure its consistency, and after category theory (and topos theory) we see the mathematic world no as a single "planet" but a system of different world, each totally different from the other, but "Set teory " keep its role of milestone of all mathematics, any structure, category is in last analysis a set (continue). –  Buschi Sergio Nov 21 '11 at 12:30
Not only, but set theory provides essential technical elements for the various demonstrations in various fields (transfinite induction, ordinal regular irraggiongibili, universes, etc. .. Vopenka). Then I think that today mathematic need a new foundation. –  Buschi Sergio Nov 21 '11 at 12:33
One such "new foundations" is currently being developed by Voevodsky and others who are working at the interface between $\infty$-category theory and intensional type theory, under the rubric "homotopy type theory". But generally, we've moved past the point where we actively need to shoehorn mathematical concepts (like homotopy type) into a specifically set-theoretic framework, and doing so often introduces irrelevancies and complications. Let's just say it's nice, for purposes of relative consistency, that this can be done. (Cf. Conway's call for a "Mathematicians' Liberation Movement"!) –  Todd Trimble Nov 21 '11 at 15:26
thank you Trimble. –  Buschi Sergio Nov 21 '11 at 18:41

The elements of sets in the theory ETCS are not other sets, they are functions $\ast \to X$. In particular, elements to not themselves have elements, so you cannot discuss the union as you have described it. In essence, this is one of the main difference between ETCS (a structural set theory) and ZF(C) (a material set theory).

The translation from ETCS is not simplistic. One has to take certain well-founded trees where the nodes are ETCS-sets to recover ZF(C)-sets. Actually, since ETCS is really of the strength of bounded Zermelo set theory with Choice you get this instead (see http://ncatlab.org/nlab/show/pure+set). Such a tree is actually a diagram $\mathcal{T} \to Set$ where $Set$ is given by ETCS, and represents a membership tree.

Then given a rooted tree (with root $T_0$) representing a material set, the union is (roughly) the tree with root the disjoint union of sets at the next level up from the original root and the union of all the branches above that.

-
thank you very much for your reply. I seems that that naive set was a natural very large place for make mathematic bulding in past, now (axiomatic set theory) become no so natural (when two set $X$ and $Y$ are equal? Or it is a "ontological" property or because have equal elements, but how two elements of these two sets could be equal? If they have equal elements.... ecc. ). –  Buschi Sergio Nov 21 '11 at 12:18
If we admit colimits the union of two abject $X,\ Y$ the union $X\cup Y$ is the colimit $F: I\to Set$ where $I$ is the (small) category of alla monomorphism of type $(m,n): A\to X\times Y$ with $m$ and $n$ monomorphisms, (see as a subcategory of the comma $Set\downarrow X\times Y$ and $F: (A, m, n)\mapsto A$ is the forgetfull functor. –  Buschi Sergio Nov 21 '11 at 20:28
@Buschi Sergio: I don't understand your last comment. Your preorder $I$ contains all such instances where $A$ is restricted to the terminal object (where it is automatic that $m$ and $n$ are monic for any $m$, $n$), and the colimit over just that subpreorder is all of $X \times Y$, not "$X \cup Y$". In fact, the only categorical meaning of union $X \cup Y$ that is stable under categorical equivalence is the disjoint union. –  Todd Trimble Nov 21 '11 at 20:47
@Trimble. sorry, I realized too late get a mistake. But the colimit above define the intersection $X\cap Y$ (is roughtly the maximal common subobject), then the union is the pushout of $X\leftarrow X\cap Y\to Y$. A object of $I$ is simply a span $X\leftarrow A\to Y$ where the two arrow are monomorphism isnt true that if $(m, n)$ is mono then $m$ and $n$ are mono (this is true about $m\times n$) viceversa is enough that just one of these is Mono, consider the graph of a function. The terminal object $(X\times Y, \pi_1, \pi_2)$ isnt in $I$ just because $\pi_1$ and $\pi_2$ aren't mono. –  Buschi Sergio Nov 21 '11 at 23:19
You misunderstood me entirely. I was considering $A = 1$, the terminal object in $Set$. In other words, let $J$ be the subpreorder of $I$ given by full subcategory of $Set/X \times Y$ whose objects are $(m, n): 1 \to X \times Y$ where $m: 1 \to X$ and $n: 1 \to Y$ are monic. Well, any morphism out of $1$ is monic! So, this $J$ is equivalent to the discrete category whose objects are indexed by elements of $X \times Y$. The colimit of the restriction of $F$ to $J$ is the union of all elements of $X \times Y$, i.e., is $X \times Y$. It follows easily that the colimit of $F$ is also $X \times Y$. –  Todd Trimble Nov 22 '11 at 0:54

There are several nice answers already, but François's answer makes me think that the following point might also be relevant.

It's a known fact that the ETCS axioms do not imply the existence of a coproduct $$\mathbb{N} + P(\mathbb{N}) + P(P(\mathbb{N})) + \cdots$$ where $P$ means power set. (At least, they don't unless they're inconsistent.) So if that's the kind of "union" you had in mind, it's not always provided by ETCS.

However, you can add the following axiom scheme to ETCS (and indeed, ETCS plus this axiom scheme is equivalent to ZFC). I'll say it a bit informally; a precise statement is in Section 8 of

Colin McLarty, Exploring categorical structuralism, Philosophia Mathematica 12 (2004), 37-53.

So: suppose you have a set $I$ and a family $(X_i)_{i \in I}$ of sets specified by a first-order formula. The axiom states that the coproduct $\sum_{i \in I} X_i$ exists. How does it state this? By saying that there are a set $X$ (to be thought of as $\sum_{i \in I} X_i$) and a map $p: X \to I$ (to be thought of as the evident projection) such that for each $i \in I$, the fibre $p^{-1}(i)$ is isomorphic to $X_i$.

One moral of the variation between our answers: "union" and "disjoint union" are more different concepts than they might at first appear.

-

There is a sense in which there is a (trivial, tautological) axiom of (disjoint) union in the elementary theory of the category of sets. In any category with pullbacks, one can think of a slice above an object X (that is, a map into X) as representing an X-indexed set (the idea being that the set associated to any particular point in X is the fiber of that point under that map; pullback then acts as reindexing). One might then ask what the disjoint union of an indexed set is. Well, it will simply be the domain of the representing slice! (Since the domain of a map amounts to the same as the union of all its fibers).

(Of course, this does not touch upon the traditional idea of set theory as about "sets of sets of sets of sets...". To model such a theory within a theory of unstructured collections, you must use membership trees, as David notes.)

-
thank you for your considerations. –  Buschi Sergio Nov 21 '11 at 18:42

After reading your other question, I think I understand what you're looking for.

In ZF, one of the key purposes of the Union Axiom is to prove that the universe of sets (viewed as a topos) is closed under internal coproducts, i.e., that one can always form the disjoint union of a set-indexed family of sets.

Any elementary topos $\mathcal{E}$ is closed under internal coproducts and internal products: for any morphism $f:A \to B$, the functor $f^*:\mathcal{E}/B \to \mathcal{E}/A$ has both a left adjoint $\sum_f:\mathcal{E}/A\to\mathcal{E}/B$ (internal coproduct) and a right adjoint $\prod_f:\mathcal{E}/A\to\mathcal{E}/B$ (internal product). Note that internal coproducts are conceptually stronger than internal unions, though the existence proof for either in elementary toposes is essentially the same.

One can also formulate this in terms of indexed categories, where the topos $\mathcal{E}$ is used to index itself. This is closer to the usual notion of (set-indexed) coproduct, but working with slice categories is equivalent and technically simpler.

-
thank you Dorais, and excuse me for the no too understable English. Of course the importance of the union is to allow the coproduct in Set. But the union is much more subdle (see the good reply of David Roberts above) it involve the trees of elements, is like a colimits of the inclusions of the union members in the maximal universe class. THis is the result of a bad generalization of the boolean operation on subsets (of a fixed set) to a general sets context, I seems is amost bad as the "axiom of class formation" that has led to Russel paradox. –  Buschi Sergio Nov 21 '11 at 20:23
David is talking about the interpretation of the Union Axiom in a topos. I'm doing the reverse: what does the Union Axiom say about the universe of sets seen as a topos. Well, it corresponds exactly to the existence of internal coproducts (modulo some elementary combinatorics). Note that these coproducts are significantly different from unions of subobjects, which is the literal translation of the union operation but lacks its full power. –  François G. Dorais Nov 21 '11 at 22:55
This is really a different topic, but the Union Axiom does not entail any typing violations, as Frege's Rule V did -- leading to Russell's Paradox, so it is really hard to compare the two. What do you mean that the Union Axiom is bad? –  François G. Dorais Nov 21 '11 at 22:58
I should add that my answer describes very roughly how to recover the concept of union for the material set theory extracted from a structural set theory. It doesn't describe 'union' in the structural set theory itself, where it is a meaningless construct. –  David Roberts Nov 22 '11 at 1:12