Sets = structured sets without structure - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T21:29:40Z http://mathoverflow.net/feeds/question/114117 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/114117/sets-structured-sets-without-structure Sets = structured sets without structure Hans Stricker 2012-11-22T00:18:51Z 2012-11-22T01:51:25Z <h2>Motivation</h2> <p>There is presumably no single and widely accepted formal definition of <strong>structured sets = sets <em>plus</em> structure</strong> based on sets as primitive objects, but several approaches are around. See e.g. <a href="http://en.wikipedia.org/wiki/Structure_%28mathematical_logic%29" rel="nofollow">structures</a> (model theory), <a href="http://books.google.de/books?id=IL-SI67hjI4C&amp;pg=PA289&amp;lpg=PA289&amp;dq=echelon%20bourbaki&amp;source=bl&amp;ots=nbgnz98aNL&amp;sig=qsJnl4NV_bRxRn-buNgRUuXfSCs&amp;hl=de&amp;sa=X&amp;ei=NkerUMbbOIWHswahkIH4Cw&amp;ved=0CDgQ6AEwAg#v=onepage&amp;q=echelon%20bourbaki&amp;f=false" rel="nofollow">echelons</a> (Bourbaki), <a href="ftp://210.45.114.81/math/2007_07_06/UTM/Y.Moschovakis%20Notes%20on%20Set%20Theory.pdf#page=56" rel="nofollow">frames</a> (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 &mdash; <strong>graphs</strong> (which among other things are able to <a href="http://books.google.de/books?id=Rf6GWut4D30C&amp;pg=PA228&amp;dq=%22classes+which+interpret+any+structure%22&amp;hl=de#v=onepage&amp;q=%22classes%20which%20interpret%20any%20structure%22&amp;f=false" rel="nofollow">interpret <em>any</em> structured set</a>).</p> <p>When we start with the &bdquo;graph&ldquo; of <strong>sets</strong> $U = \langle V,\in\rangle$, sets as primitive objects are &bdquo;defined&ldquo; just by</p> <p>$$\text{Set}(X) :\equiv X\ \epsilon\ V$$</p> <p>with $\epsilon$ indicating class membership. Graphs (structured sets), then, are - rather sophisticatedly - defined by</p> <p>$$\text{Graph}(X) :\equiv (\exists S,R\ \epsilon\ V)\ R \subseteq S^2 \wedge X = \langle S,R\rangle$$</p> <p>To complete the picture we define</p> <p>$$\text{Relation}(X) :\equiv (\exists S\ \epsilon\ V)\ X \subseteq S^2$$</p> <p>Thus, a graph is a set <em>plus</em> a relation over it, usually written as $G = \langle V,E\rangle$.</p> <h2>Interlude</h2> <p>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 <a href="http://en.wikipedia.org/wiki/Graph_homomorphism" rel="nofollow">graph homomorphisms</a> $\mathcal{M}$, etc. Thus graphs as primitive objects are defined by</p> <p>$$\text{Graph}(X) :\equiv X\ \epsilon\ \mathcal{O}$$</p> <p>To define &bdquo;set&ldquo; as a now <em>derived</em> concept one might try to resolve the above &bdquo;equation&ldquo; informally to obtain <strong>sets = structured sets <em>minus</em> structure</strong>. Thus, sets don't have any structure (anymore), so morphisms as structure-<em>preserving</em> functions don't have to preserve any structure (anymore), so <em>every</em> function from a set to any other graph (= structured set) is a morphism in $\mathcal{M}$. According to the standard definition of <a href="http://en.wikipedia.org/wiki/Graph_homomorphism" rel="nofollow">graph homomorphism</a>, the graphs being sets are exactly the edgeless graphs (which complies with intuition). </p> <p>Translating this into categorical terms we obtain:</p> <p>$$\text{Set}(X) :\equiv (\forall\ Y\ \epsilon\ \mathcal{O})(\exists\ f\ \epsilon\ \mathcal{M})\ f: X \rightarrow Y$$</p> <p>Making use of categorical terminology we can equivalently say: Let $\mathcal{C}/$ be the <a href="http://en.wikipedia.org/wiki/quotient_category" rel="nofollow">quotient category</a> of $\mathcal{C}$ which identifies all morphisms (if present) from $A$ to $B$ as one. Then:</p> <p>$$\text{Set}(X) :\equiv X\ \text{is an initial object in } \mathsf{Graph}/$$</p> <h2>Question(s)</h2> <p>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}$ <em>is</em> a concrete category).</p> <p>What I'd like to learn is - among other things - how the above definition of being a <em>set</em> relates to the usual notions:</p> <ul> <li><p>Which concrete categories don't have sets?</p></li> <li><p>Which non-concretizable categories <em>do</em> have sets?</p></li> </ul> http://mathoverflow.net/questions/114117/sets-structured-sets-without-structure/114119#114119 Answer by Qfwfq for Sets = structured sets without structure Qfwfq 2012-11-22T01:09:45Z 2012-11-22T01:51:25Z <p>I will call <em>source objects</em> 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.</p> <p>1) The category of fields is concretizable and doesn't have source objects.</p> <p>2) $HoTop_{*}$ (the homotopy category of pointed topological spaces) is not concretizable and every object is a source object.</p> http://mathoverflow.net/questions/114117/sets-structured-sets-without-structure/114121#114121 Answer by Andrej Bauer for Sets = structured sets without structure Andrej Bauer 2012-11-22T01:15:10Z 2012-11-22T01:15:10Z <p>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.</p> <p>In any case, the important thing about structures are <em>homomorphisms</em> between them, not how they might happen to be built from sets.</p> <p>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 <em>relations</em> (morphisms) between them are.</p> <p>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?</p> <p>Unless I misunderstood you completely, I think the correct answer is "this is the wrong question".</p> http://mathoverflow.net/questions/114117/sets-structured-sets-without-structure/114122#114122 Answer by David Roberts for Sets = structured sets without structure David Roberts 2012-11-22T01:22:12Z 2012-11-22T01:22:12Z <p>(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.)</p> <p>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 <a href="http://conceptualmathematics.wordpress.com/2012/06/04/perugia-notes-prof-f-w-lawvere/" rel="nofollow">here</a>. 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)$.</p> <p>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 <a href="http://ncatlab.org/nlab/show/fully+formal+ETCS" rel="nofollow">ETCS</a>, or <a href="http://ncatlab.org/nlab/show/SEAR" rel="nofollow">SEAR</a> 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 <em>not</em> 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 <em>not</em> what you want to think of as maps between minimally structured objects!</p>