# Sets = structured sets without structure

## Motivation

There is presumably no single and widely accepted formal definition of structured sets = sets plus structure based on sets as primitive objects, but several approaches are around. See e.g. structures (model theory), echelons (Bourbaki), frames (Moschovakis). I don't want to discuss these approaches, but for simplicity's and specifity's sake I want to pick out one especially simple definition of rather generic structured sets — graphs (which among other things are able to interpret any structured set).

When we start with the „graph“ of sets $U = \langle V,\in\rangle$, sets as primitive objects are „defined“ just by

$$\text{Set}(X) :\equiv X\ \epsilon\ V$$

with $\epsilon$ indicating class membership. Graphs (structured sets), then, are - rather sophisticatedly - defined by

$$\text{Graph}(X) :\equiv (\exists S,R\ \epsilon\ V)\ R \subseteq S^2 \wedge X = \langle S,R\rangle$$

To complete the picture we define

$$\text{Relation}(X) :\equiv (\exists S\ \epsilon\ V)\ X \subseteq S^2$$

Thus, a graph is a set plus a relation over it, usually written as $G = \langle V,E\rangle$.

## Interlude

Oppose this set-based picture to the category $\mathsf{Graph} = \langle \mathcal{O},\mathcal{M},\dots\rangle$ with $\mathcal{O}$ the class of all graphs as primitive objects, related by graph homomorphisms $\mathcal{M}$, etc. Thus graphs as primitive objects are defined by

$$\text{Graph}(X) :\equiv X\ \epsilon\ \mathcal{O}$$

To define „set“ as a now derived concept one might try to resolve the above „equation“ informally to obtain sets = structured sets minus structure. Thus, sets don't have any structure (anymore), so morphisms as structure-preserving functions don't have to preserve any structure (anymore), so every function from a set to any other graph (= structured set) is a morphism in $\mathcal{M}$. According to the standard definition of graph homomorphism, the graphs being sets are exactly the edgeless graphs (which complies with intuition).

Translating this into categorical terms we obtain:

$$\text{Set}(X) :\equiv (\forall\ Y\ \epsilon\ \mathcal{O})(\exists\ f\ \epsilon\ \mathcal{M})\ f: X \rightarrow Y$$

Making use of categorical terminology we can equivalently say: Let $\mathcal{C}/$ be the quotient category of $\mathcal{C}$ which identifies all morphisms (if present) from $A$ to $B$ as one. Then:

$$\text{Set}(X) :\equiv X\ \text{is an initial object in } \mathsf{Graph}/$$

## Question(s)

I am aware that I didn't even mention the category $\mathsf{Set}$ of sets and the notion of a concrete category (even though $\mathsf{Graph}$ is a concrete category).

What I'd like to learn is - among other things - how the above definition of being a set relates to the usual notions:

• Which concrete categories don't have sets?

• Which non-concretizable categories do have sets?

-
To whom it may concern: I'd really like to know the reason why you down-voted this question. (Even more than I'd like to know the reasons for any up-votes.) –  Hans Stricker Nov 22 '12 at 0:55
I didn't downvote, but can maybe understand why someone would, in that I didn't find the question very clear. E.g. I didn't understand the meaning of the first display, "Set$(X):\equiv X \epsilon V$", or the similar displays later. I also didn't understand what you meant by "have sets" in the actual questions. –  Tom Leinster Nov 22 '12 at 1:09
Anyway, when I saw the title of your question, what I immediately thought of was ETCS: tac.mta.ca/tac/reprints/articles/11/tr11abs.html –  Tom Leinster Nov 22 '12 at 1:10
In my opinion, this is an insightful question, at least insofar as it precipitated informative answers. Yes, as suggested in answers, one could, and I do, think that maps_among things are operationally more significant than internal structure, so, in that sense, I am not convinced that I care whether something is a set or not... nevertheless, and interesting line of thought. –  paul garrett Nov 22 '12 at 1:44
I think the definition you give of "set" in a category is not the most appropriate. I would rather go for another definition, such as: "a set object in $C$ is a coproduct of final objects". This -I think- would reflect more what is understood to be a "bare set" for example in geometry. –  Qfwfq Nov 22 '12 at 1:46

I find your approach somewhat puzzling. You seem to be saying that it useful to look at the property of "being a structure" rather than at the structure itself. What interesting mathematics do you intend to build around the property $\mathrm{Relation}$, for example? Also, note that in the definition of $\mathrm{Relation}(X)$ the domain $S$ is not determined, so you cannot recover the structure just from knowing that $X$ is a relation. And since every set is isomorphic to a set which happens to consist of pairs, your notion is not even invariant under any reasonable notion of isomorphism.

In any case, the important thing about structures are homomorphisms between them, not how they might happen to be built from sets.

In your second part you seem to be observing that a category might enjoy an adjunction to the category of sets. For example, the forgetful functor $U : \mathrm{Graph} \to \mathrm{Set}$ has both a left and a right adjoint. You noticed that the left adjoint is full and faithful. By the way, so is the right one, which assigns to each set the complete graph on the set. Once again, it is not important how objects happen to be represented as sets, but what the relations (morphisms) between them are.

If I understand your question correctly, you seem to be asking when a category embeds fully and faithfully the category of sets. Is that what you are asking?

Unless I misunderstood you completely, I think the correct answer is "this is the wrong question".

-
"this is the wrong question" - I couldn't agree more! –  David Roberts Nov 22 '12 at 1:22

(I'm not sure how much this is an answer to your question, rather it is an answer - one might say in the legal sense - to the statement in the title and the preliminary material.)

Bill Lawvere explains his philosophy behind sets (and note he invented a whole new foundation of mathematics to back this up!) in his Perugia lecture notes, available from here. Essentially he says sets are the minimally structured objects: bags of dots such that the only structure is a notion of equality. Given a set $X$, which consists of elements $x,y\in X$, all we can say is if $x=y$, or not. In particular, the notion of homomorphism between this sort of structure is a function, which is defined so as to preserve the equality structure: if $x=y$, then $f(x) = f(y)$.

Also, I refute the assertion that sets a priori form a graph, since we can define the category of sets from scratch using first-order reasoning (e.g. with ETCS, or SEAR if you want the stronger of the ZF(C) axioms - unnecessary for ordinary, non set-theory mathematics), and they don't come with a graph structure. The notion of set in ZF(C), or more generally a material set theory is actually not the minimal possible structure, as it is essentially that of a transitive well-founded graph (by results of Mostowski etc). Note then that the homomorphisms preserving the structure of a transitive well-founded graph are not what you want to think of as maps between minimally structured objects!

-
Thank you, David. That's the kind of answer I hoped for! (Not dull down-votes.) –  Hans Stricker Nov 22 '12 at 1:34

I will call source objects in a category $C$ the objects you defined in the question, that is: objects $X$ such that, for every $Y$, $\mathrm{Hom}_{C}(X,Y)$ is nonempty.

1) The category of fields is concretizable and doesn't have source objects.

2) $HoTop_{*}$ (the homotopy category of pointed topological spaces) is not concretizable and every object is a source object.

-
Thank you for these examples. That's (almost) all I wanted to ask for. –  Hans Stricker Nov 22 '12 at 1:15