0
$\begingroup$

I have completely rewritten this question; thus, some of the comments/answers may no longer be relevant.


The elementary theory of the category of sets (hereafter, ETCS) is an axiomatic approach to the category of sets and functions. As such, it can provide a foundations for mathematics, in much the same way that ZFC can.

Now personally, I don't find sets with no additional structure to be very interesting. I'm interested in groups, posets, topological spaces etc. So I want to know if there's a way to modify ETCS such that the objects are no longer just "sets", they're "sets+additional structure."

I envision something like the following. If $Y$ is an object and $f : X \rightarrow Y$ is a function, then we can form a new object $(Y,f)$ which is essentially "$Y$ + the additional structure provided by $f$." For instance, if $Y$ is an object and $f : 1 \rightarrow Y$, then $(Y,f)$ is just like $Y$, except with a distinguished element. More generally, if $X$ is a set and $Y$ is an object, and if $f : X \rightarrow Y$ is an injection, then $(Y,f)$ is just like $Y$, except with a distinguished subset. Similarly, if $W$ is a well-ordered set and $Y$ is a structure, and if $f : W \rightarrow Y$ is a function, then $(Y,f)$ is just like $Y$, except with a distinguished sequence (possibly transfinite).

Note that $(Y,f)$ is not an ordered pair, but a new object. We could have instead denoted it $Y + f$, to emphasize that its $Y$ plus some additional structure.

So anyway, I'm after ideas for axioms and also general comments. Also, if this sort of thing has been done before, TELL ME!!! A reference would be nice.

Now, a technical question. How should we represent binary relations on an object? Observation: Given an object $Y$ and a family of functions $\{f_i : 2 \rightarrow Y\}_i$, where $2$ is a well-ordered set of two elements and $i$ is understood to range over an unordered set, the family $\{f_i\}_i$ essentially encodes a binary relation on $Y$. So $(Y,\{f_i\}_i)$ might be viewed as the structure $Y$ equipped with the binary relation $\{f_i\}_i$. But should we view this as being a valid object? Perhaps a better approach would be to consolidate the family $\{f_i\}_i$ into a single morphism $g$, and then regard $(Y,g)$ as the new object. But what is the appropriate notion of consolidation?


EDIT: It's been suggested that the question is too unfocused, so let me try to clarify. I'm looking for an axiom system for the category of structures and functions. A "structure" being a set together with some generalized elements. So I guess the novel aspect of this idea is that given a structure $Y$ and a generalized element $f : X \rightarrow Y$, we want to define a new structure $Y+f$, or $(Y,f)$ if you prefer, which is just the old structure equipped with an additional generalized element.

For instance, supposed $Y$ is a set (the simplest kind of structure), and let $f : 1 \rightarrow Y$ denote a function. Then $Y+f$ is a new kind of structure; it's a set with a distinguished element called $f$. Now suppose additionally that $g : X \rightarrow Y$ is an injection, and suppose $X$ is a set. Then $(Y+f)+g$ is again a new structure; it's $Y+f$ together with a distinguished subset called $g$.


EDIT 2: I think I finally understand what the confusion is about. The word "morphism" is typically understood to refer to a structure-preserving map. This is NOT how I'm using the word. Recall that I'm interested in a category of structures and functions. So the morphisms between two structures are precisely the functions between their underlying sets. That is, the morphisms in the category of structures and functions aren't necessarily structure-preserving. They're arbitrary functions. So if $G$ and $H$ are groups, then a morphism $f : G \rightarrow H$ is ANY FUNCTION between the underlying sets of $G$ and $H$. Of course, we can define a subcategory wherein the objects are all groups and the morphisms are all group homomorphisms, and in this subcategory the meaning of "morphism" is more restrictive.

Hopefully, that clears things up.

$\endgroup$
  • 4
    $\begingroup$ Arguably, category theory: en.wikipedia.org/wiki/Category_theory. $\endgroup$ – mjqxxxx Feb 23 '13 at 3:48
  • $\begingroup$ There are set theories inspired by category theory, such as ETCS and SEAR. But these are still set theories, and thus not really what im looking for. $\endgroup$ – goblin GONE Feb 23 '13 at 3:56
  • $\begingroup$ An elaboration of categories known as topoi might be worth looking into. There's at least a mention of them in this previous Question, How can there be alternatives for the foundations of mathematics?. $\endgroup$ – hardmath Feb 23 '13 at 5:28
  • $\begingroup$ Re: the latest edit: If you've forgotten the structure, then all you have are sets and functions; it didn't matter that you 'originally' had structures because you've forgotten about it. If you remember the structure, then you have two categories: the category of structures and morphisms, and the category of sets and functions... and you have the "forgetful" functor from the former to the latter. $\endgroup$ – user14972 Mar 24 '13 at 2:53
  • $\begingroup$ Yes thats exactly right. Note that we can view the category of sets and functions as a subcategory of the category of structures and functions. $\endgroup$ – goblin GONE Mar 24 '13 at 2:59
1
$\begingroup$

Working over ETCS is, if I recall correctly equivalent to working over a well pointed topos with choice. A good reference for topos theory is Sheaves in Geometry and Logic by Moerdijk and MacLane.

In topos theory, a binary relation on an object $X$ is just a subobject of $X \times X$, ie an object $R$ together with a monomorphism $r:R \rightarrowtail X \times X$. Based on this idea, in ETCS you can construct a set whose elements correspond to binary relations on $X$ by simply constructing the product $X \times X$ by the axiom of products and then applying the axiom of power sets to get the set of binary relations $P(X \times X)$. Since ETCS is already able to handle binary relations and in fact $n$-ary relations there isn't any need to extend it at all.

Edit: Based on the comments I'm going to extend this a bit.

In my opinion it isn't necessary to combine the two objects $X$ and $R$ into one. However it is possible to do this. In topos theory you could do this by taking the coproduct $X + R$ of $X$ and $R$.

Edit 2: On further thought, coproduct probably doesn't have all the properties you want it to. Maybe it's better to just use pairing in the "meta universe." Given any language $\mathcal{L}$ and any topos you can produce a new category of $\mathcal{L}$-models whose objects are n-tuples $\langle X, R_1,\ldots,R_n\rangle$ of objects (edit 3: as Hurkyl pointed out $R_i$ is actually an object and a monomorphism) in the topos and whose morphisms are morphisms $X \rightarrow X'$ that are homomorphisms in the internal language of the topos.

Edit 4: I think maybe the crux of the matter is that you want to take all the information from $X$ and $r : R \rightarrowtail X \times X$ and package it into one object, but this goes against the spirit of category theory because you shouldn't be thinking in terms of objects but in terms of the relationships between them.

Hope this helps.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Yes but I want to gather relations with the underlying set to obtain a new object. That new object is not a set. $\endgroup$ – goblin GONE Mar 23 '13 at 22:58
  • $\begingroup$ For example, a poset is not a set, because it is not characterised entirely by its elements. $\endgroup$ – goblin GONE Mar 23 '13 at 23:08
  • $\begingroup$ In traditional set theory, a poset is given by an ordered pair containing a set and a partial order on that set. You can do the same thing in ETCS, although it's probably most conveniently phrased in terms of sketches. $\endgroup$ – user14972 Mar 24 '13 at 0:28
  • $\begingroup$ @user: Even as aws defined it, the underlying set is already part of the relation. $R$ is not a relation. $R \to X \times X$ is a relation. And even then, that's not strictly true: it's shorthand for a (non-commuting) diagram $R \to P \rightrightarrows X$, where $P \rightrightarrows X$ is a product diagram. $\endgroup$ – user14972 Mar 24 '13 at 0:40
  • $\begingroup$ @Hurkyl I tried thinking about that but then got confused trying to work out how ordered pairs work in topos theory. In set theory ordered pairs are implemented as sets with two elements, but this means that they are all isomorphic to each other in the category of Sets. $\endgroup$ – aws Mar 24 '13 at 0:41
3
$\begingroup$

The question is not really focussed and not clear enough. There are various precise interpretations of the question, but in each case I can only offer the trivial answer: Well that's what universal algebra and categorical algebra are all about! I will not even try to summarize what has been done in these large areas of mathematics; this is not possible. The basic principle is, that for many general mathematical ideas the category of sets can be replaced by an arbitrary category with sufficiently nice properties. If these properties are ETCS, we get nothing new, since every category satisfying ETCS is equivalent to the category of sets. Typical properties are the existence of certain limits or colimits and some compatibilities between them. In order to get a fealing for this, try to read the following nlab articles.

Of course this is just a selection and hopefully answers some of the questions. If not, please clarify the question, then I will try to improve my answer.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I have said more than "category theory". For example, I have tried to answer your question about relations. It is silly to ask unfocussed questions and expect to get exactly the answer one hopes for. Also, within a few minutes you probably haven't read the nlab links. Please take your time and clarify the question. Besides, category theory can be seen as (one of many) foundation for mathematics. $\endgroup$ – Martin Brandenburg Mar 24 '13 at 0:31
1
$\begingroup$

So, it's seems like you want a sort of category in which you can encode structures with one sort. This kind of structures usually are well encoded as models of a Lawvere's algebraic theory.

So it seems to me that what your looking for could be this sort of category, having:

  • objects: models of a Lawvere theory, i.e. some special kind of set valued functors (note that for every such model $\mathcal F \colon \mathbf T \to \mathbf {Set}$ the underlying set is the object $\mathcal F(1)$, where $1$ is the generator of the objects in the Lawvere theory;

  • morphisms: should just simply be functions (i.e. $\mathbf{Set}$ morphisms) between the underliyng sets.

Edit: I've just noted that we can do even another kind of category: the categories of algebras for monads.

You could consider a category having as objects pairs of the kind $(T(X),h)$ where $T \colon \mathbf{Set} \to \mathbf {Set}$ is a monad, $X$ is a set and $h \colon T(X) \to X$ is a function which commute with multiplication and unit of the given monad $T$. For any give pair of this sort the underlying set is the codomain of the structure map $h$. As morphisms of this category you could take the functions between the underlying sets.

I know that you can build a lot of algebraic structures, but also other ones like topological spaces, as algebras for monads. In particular there's the free group monads whose algebras are groups and (if I'm not mistaken) the ultrafilter monad having topological spaces as algebras.

You can find a lot more Googleing around.

Is this what you wanted?

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Sounds interesting. How would one go about encoding, say, a group, or a topological space? $\endgroup$ – goblin GONE Mar 25 '13 at 12:02
  • $\begingroup$ This kind of structure is well suited for the purpose of algebraic structures: you can consider the algebraic theory of groups for instance. I don't know if it well suited for all the sort of structures but I guess that with some additional structure on the theory you can build every other kind of structure. $\endgroup$ – Giorgio Mossa Mar 25 '13 at 14:02
  • $\begingroup$ About the theory of groups here (ncatlab.org/nlab/show/Lawvere+theory#the_theory_of_groups_20) you can find all the details (at least I hope so :) ) $\endgroup$ – Giorgio Mossa Mar 25 '13 at 14:06
0
$\begingroup$

$\newcommand{\map}[1]{\stackrel{#1}{\to}}$I wanted to expand briefly on mjqxxxx's comment "Arguably, category theory".

Consider a category with a terminal object $1$.

For any other object $X$, call any morphism $1\map{x}X$ an element of $X$.

If we have another morphism $X\map{f}Y$ then we can form the composition $1\map{x}X\map{f}Y$, and the resulting morphism $f\circ x$ is an element of $Y$ (that you might more often see written as $f(x)$).

So you can define the relation "is an element of" in terms of morphisms, and function evaluation in terms of composition of morphisms.

The empty set is a set with no elements - equivalently, an object which has no morphisms to it.

Similarly you can build up notions of cartesian product, images, inverse images, natural numbers, subsets etc out of the more primitive concepts of 'objects' and 'morphisms'. Tom Leinster talks more about this in this paper.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Yes I'm aware of ETCS, but I wanted "sets + additional structure" rather than "just sets". That's a good reference, though. $\endgroup$ – goblin GONE Mar 15 '13 at 9:16
  • 1
    $\begingroup$ @user: The point is, ETCS has all of the same tools that ordinary set theory does for expressing the notion of "sets with additional structure". $\endgroup$ – user14972 Mar 24 '13 at 0:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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