Sets = structured sets without structure - MathOverflow

Sets = structured sets without structure

2012-11-22T00:18:51Z

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?

Answer by Qfwfq for Sets = structured sets without structure

2012-11-22T01:09:45Z

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.

Answer by Andrej Bauer for Sets = structured sets without structure

2012-11-22T01:15:10Z

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".

Answer by David Roberts for Sets = structured sets without structure

2012-11-22T01:22:12Z

(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!