# Concrete models of abstract structures

Most mathematicians seem to be contented with the fact, that abstract structures cannot be directly modelled as such in a set theory without ur-elements. What seems to me the standard stance: Set theory works pretty well without ur-elements, and it's simpler without them.

Given an abstract (uninterpreted) theory there are always infinitely many set-theoretic models (= concrete structures) which can be grouped in isomorphism classes. The only candidates for the corresponding abstract structures seem to be those isomorphism classes (as one once tried to model natural numbers as isomorphism classes of equipollent sets). But these are not sets (but proper classes, thus hard to handle), especially not "sets with structure" (but collections of). Only an arbitrary representative of such an isomorphism class would be a set with the desired structure, but it would be a too-concrete model, necessarily equipped with a lot of undesired structure - unless its base set consists of ur-elements!

For example, there is nothing like the standard (set-theoretic) model of the natural numbers as one definite abstract (set with) structure, but only concrete constructions (like von Neumann ordinals).

But wouldn't it be good to be able to single out the standard model as an infinite graph of "dots and arrows" by allowing ur-elements in the set-theoretic universe? (dots = ur-elements, arrows = ordered pairs)

$$\bullet \rightarrow \bullet \rightarrow \bullet \rightarrow\ ...$$

Of course there would be infinitely many such models (permutations of the dots!), but they would be undistinguishable in a stronger sense than just being isomorphic, because the ur-elements are undistinguishable (apart from being different).

Questions:

1. Is it just not worth the effort to deal with ur-elements for this purpose, because one can live comfortably without such set-theoretic abstract models?

2. Or is there a severe conceptual error or misunderstanding in this undertaking: it's not only not worth the effort, but it will lead into trouble?

3. Could this nevertheless shed a light on the interconnection between set theory and category theory (which pretends to know only dots and arrows)?

Side note: With ur-elements one can model each single natural number as a "bag of dots" (not as a "bag of structured objects" like the von Neumann ordinals), thus giving set-theoretic sense to Hilbert's strokes, which never really made it into set theory, did they?

-
I do not understand your first sentence... –  Mariano Suárez-Alvarez Feb 13 '11 at 18:14
If anything, I prefer having a gigantic class of isomorphic things from which I can say I am studying an arbitrary representative, than one specific set-with-structure. Indeed, one of the main "philosophical" points I have seen in category theory so far is that one should not attempt to force choices like this. –  Zev Chonoles Feb 13 '11 at 20:03
Quick observation regarding your second sentence: We do in fact consider models of set theory with urelements or atoms (i.e., models of ZFA), and these have proven useful for studying weaker forms of the axiom of choice. See Jech for more details. –  Jason Feb 14 '11 at 0:08
If anyone cares: to the extent that I understand the leading sentence of this question, I do not agree with it. –  Pete L. Clark Feb 14 '11 at 1:47
The questions you raise have been addressed by philosophers under the name of "structuralism," cf. e.g. "What numbers could not be" by Paul Benacerraf. It can be addressed mathematically by using "structural set theory", in which (in most presentations) all elements of sets are "urelements". Structural set theory is most commonly presented using category theory (the original being Lawvere's ETCS), but it doesn't need to be. –  Mike Shulman Feb 14 '11 at 5:02

I take your question to be about what we might call the structuralist perspective, the view that we specify mathematical objects and structures by their defining structural features, ignoring any internal or otherwise irrelevant structure that an instantiation of the object might exhibit. You perceive a tension between this view and the pure theory of sets, in which every set carries its hereditary $\in$-structure. You propose that the concept of urelements---objects that are not sets but which can be elements of sets---provide exactly what is needed to implement the structuralist perspective, for because urelements have no internal set-theoretic structure, there would seem to be nothing to ignore. So the plan appears to be for us to present the natural numbers as given canonically by urelements and thereby hope to finesse any need to engage the structuralist perspective directly.

But this strategy doesn't actually succeed, does it, since someone might permute the urelements---swap two of them, say---and thereby build a perfectly good copy of the natural numbers, still made from urelements. If the urelements were supposed to provide for you a canonical concept of the natural numbers, then you would have a canonical number $5$, but which urelement will you say is the real number $5$? Similarly, as you mention, we might swap the "dots" in your question. So even when we build our structures from urelements, the structuralist issue still arises. But the point of having them, if I understand you correctly, was to avoid that issue.

Secondly, urelements are often described as distinct but indistiguishable, each having all the same properties as the others. But this is problematic, since an urelement $x$ is the only urelement that has the property of being $x$, as well as the only element of $\{x\}$ and so on. Perhaps that urelement is also my favorite urelement! Or perhaps it was created first among all the urelements, whatever that might mean, or perhaps it even does have a secret internal, irrelevent mathematical but not set-theoretic structure that is hidden from our knowledge and which remains inaccessible to us. You might reply that all these are features of urelements that you want to ignore---they are irrelevant---but this would simply be admitting that you haven't avoided the structuralist issue with urelements.

I take these issues to show that urelements don't actually help us avoid the need to engage with the structuralist perspective directly. We want to adopt the structuralist view, and to specify our mathematical objects by their defining structural features rather than by the essential nature of their constituent objects.

The urelement concept arises naturally from two views in naive set theory, first, the view that one must have some objects before it is sensible to speak of sets of objects, and second, the view that set theory is essentially a supplemental theory, built on top of other mathematical theories, providing assistance in theoretic argument. One first has the natural numbers, for example, whatever they are, and then one may consider sets of natural numbers and sets of these sets and so on, and the same for real numbers, and these sets assist with the original mathematical analysis.

Set theorists quickly realized, however, that the structuralist perspective allowed them to abandon any need for the urelements---all the favorite mathematical structures can be constructed out of pure sets. Set theory proceeds in a pure, elegant development without urelements, and set theorists adopt the structuralist perspective wholesale. (What is a set, really? I don't care---but I care about the structure of its $\in$-relations to the other sets.) Even the urelements themselves can be simulated by finding structural copies of them within the pure set theory, just as we construct the integers and the real field.

In this way, both of the naive views mentioned two paragraphs back are overturned: the cumulative hierarchy of sets arises from nothing, towering higher than we can imagine, while providing the desired instances of all of our favored mathematical structures. This is the sense in which set theory unifies mathematics, by providing a common forum in which we can view all other mathematical arguments as taking place.

Lastly, let me mention that the idea of permuting urelements gave rise to the earliest consistency proofs of $\neg AC$. One begins with a model of ZFA, and then fixes a group of permutations of the urelements, restricting to the universe of sets that hereditarily respect that group action. It can be arranged that the resulting symmetric model satisfies $ZFA+\neg AC$, and so we arrive at models without the axiom of choice. It was not known how to do this in a pure set theory until Cohen introduced the forcing technique. Nevertheless, the Jech-Sochor embedding theorem shows that every initial segment of a permutation model of ZFA has a copy as a permutation model of ZF, in the pure theory, in which the iterated power set structure of the atoms is respected up to that bound. This theorem therefore simultaneously redeems the early approach to $\neg AC$ using urelements, while also showing that the method was not necessary for that application.

-
I have to admit I did not even understand the question until I read this answer. –  Qiaochu Yuan Feb 14 '11 at 15:26
@Joel: Thanks very much for this lucid answer. But one side question remains open: Cannot be made more precise sense of the "feeling" that isomorphic structures over atoms are "more equal" than isomorphic structures over pure sets, inheriting the "distinct but undistinguishable"-property from their atoms? But asking this question again might mean, that I didn't understand your argument at all. –  Hans Stricker Feb 14 '11 at 15:57
Beautiful answer, Joel---above your average, and that already is quite a feat! –  Mariano Suárez-Alvarez Feb 14 '11 at 16:29
Hans, I also feel the pull of that view; somehow we view the urelements as being all on the same level. But keep in mind that we might also view all sets essentially as urelements, as dots all on the same level, with the $\in$ relation merely a relation between them imposed from above, which can be ignored or set aside when that relation is not the focus. This is the structuralist procedure. –  Joel David Hamkins Feb 14 '11 at 19:08
Hans, about your second comment, the point is that once you have the idea that there are some properties to be ignored, since they do not concern the structure in which you are interested, then you've adopted the structuralist view. In this case, I don't see that urelements provide any further advantage. –  Joel David Hamkins Feb 14 '11 at 19:09

(I held off on posting this as an "answer" because I didn't realize until reading Joel's post what exactly you were asking. But now, I think this is the answer.)

One can achieve a set theory in which "the" natural numbers is a set of dots with no additional structure (like von Neumann ordinals). I like to call it "structural set theory," because it is in line with the philosophical point of view called "structuralism" advocated by Benacerraf and others. The classic paper on the philosophy is Benacerraf's What numbers could not be, which is well worth a read.

The main caveat is, as you say, that there will be infinitely many models, not just one. And, as you say, they will exactly be isomorphic and "in a stronger sense," not just isomorphic, but there is no additional data which needs to be "forgotten" or "ignored" in order to realize the isomorphism. Each of them is nothing but an abstract model of the Peano axioms (for instance), and while they may not be identical, there is nothing one can say to distinguish one from the other. In fact, in some structural set theories, one is not even allowed to ask the question of whether two such structures are "identical" versus merely "canonically isomorphic."

Structural set theories are, indeed, most commonly presented using category theory. The original, and most commonly cited, example is Lawvere's Elementary Theory of the Category of Sets, described here. This takes the form of a collection of axioms describing "the category of sets." An "element" of a set X is defined to be a function from the terminal set into X. Colin McLarty in his paper Numbers can be just what they have to (also well worth a read) argued that ETCS resolves exactly the structural issue that Benacerraf complained about, in the way described above.

Structural set theories do not have to be presented using category theory, however, nor do they have to take "elements" as a "defined notion". In order to make this point, I described a structural set theory called SEAR.

Finally, structural set theories are equivalent in strength to classical "material" or "membership-based" set theories. The equivalence was originally proven by Cole, Mitchell, and Osius using ETCS-like structural set theories. In one direction the construction is easy: simply forget all the extraneous membership data in a material set theory to obtain a structural one. In the other direction the construction is tricky: one has to build up a collection of "well-founded trees" or something with which to model the global membership predicate that supplies the sets in a membership-based set theory with all their extraneous structure (which most practicing mathematicians then proceed to ignore).

So why isn't structural set theory more used? Well, material set theories have the weight of history behind them. And most mathematicians are perfectly happy to just ignore all the extraneous data, rather than insisting that it not be there (and there's no reason they should so insist, either; the role of foundations in most mathematics is largely to be ignored anyway). And when doing pure set theory of the sort practiced by modern set theorists (which, some people might argue, would better be called "well-foundedness theory"), there are definitely advantages of convenience to using material set theory, von Neumann ordinals, etc.

-
Thanks very lot! I definitely would like to accept it, but you know, that this is not possible. –  Hans Stricker Feb 15 '11 at 8:39
No worries -- I'm not in this for the "reputation game." (-: –  Mike Shulman Feb 16 '11 at 5:22

To complement Andreas's answer (and perhaps Joel's forthcoming answer) let me plug Aczel's Anti-Foundation Axiom. This axiom says that every suitable "dots and arrows" diagram (as described by Hans) determines a unique set. It is thus a convenient way to generate a unique suitable set of elements for just about any type of abstract structure than one wants to define. For more on this axiom, I recommend reading Aczel's Non-Well-Founded Sets (MR0940014) which can be found here.

-

When dealing with mathematical structures represented as sets, one usually wants to forget some extraneous set-theoretic structure. For example, when dealing with real numbers, we don't (usually) want to think about whether they're Dedekind cuts or equivalence classes of Cauchy sequences or something else; we just want a complete ordered field. The use of urelements lets us build this "forgetting" into the mathematics itself --- we can use a complete ordered field with no additional structure.

The beginning of Barwise's book "Admissible Sets and Structures" has a good discussion of why one might want to use a set theory with urelements (even apart from their technical value in the admissible set theory developed in the book).

I might also mention Lawvere's description of abstract sets as having no external structure except cardinality and no internal structure except equality. (I can't find the source for the quotation just now; I hope I got it right.)

I look forward to Joel's promised answer.

-
As a mathematician who is not a set theorist, I confess I don't see the practical difference between set theories with urelements versus pure set theories: why do I need/want urelements to understand that a Dedekind complete ordered field exists and is unique up to unique isomorphism and that I don't care what sort of objects the elements of this field really are? It seems to me that the more categorical take on what the elements of a set "really are" (essentially: Don't Ask, Don't Tell) is more graceful and convenient than discussing set-theoretic ontologies like urelements. –  Pete L. Clark Feb 14 '11 at 1:45
@Pete: You don't need urelements to understand, and you don't need to care, and you can forget about all that tacitely. My question was for making explicit the "forgetting" and "not caring", just like Andreas says. –  Hans Stricker Feb 14 '11 at 7:42

I tried to digest Joel's and Mike's answers and came up with the following picture:

Starting with a model of pure and well-founded set theory we can see it as a class of dots with $\in$-arrows between them. In this picture, all sets have structural properties only, no intrinsical. Furthermore, all sets are distinguishable by their structural properties (Corollary 1.1 and Proposition 1.2 in Aczel's Non-Well-Founded Sets, p.5, if I understood this right). Especially there is exactly one empty set, exactly one singleton set containing the empty set, and so on.

Introducing atoms, we have the situtation, that the atoms cannot be distinguished by their structural properties: they all have no elements, they all are contained in exactly one singleton set, and so on.

But suddenly, also non-empty sets become undistinguishable: take any pure set and replace all its "recursive occurrences" of the empty set by one and the same atom, and you won't be able to distinguish the two structurally.

So atoms are no more structurally undistinguishable than normal sets (in the presence of atoms) - just like Joel says in one of his comments on his answer.

Together, these findings suggest that atoms may have no practical use in a structural set theory. Summarizing:

• Atoms don't have intrinisical properties, but they have structural properties, just as any other set. They are not as propertyless as one might have wanted.

• Furthermore, even normal sets may be seen as dots, having no intrinsical, but only structural properties.

• In the presence of atoms, atoms are no more undistinguishable than normal sets.

-
Well, you're using "structural" in the exact opposite of the way that I was. I would call the $\in$-relations between sets in a membership-based set theory "intrinsic", whereas "structural" properties are those which derive from "structure" placed on the set by the choice of the mathematician using them, such as an order relation, a binary operation, etc. But modulo that, I think I agree -- except that I wouldn't conclude from that that atoms have "no practical use." –  Mike Shulman Feb 16 '11 at 5:22
Oops, that's a big "modulo", interesting enough that you can agree, yet. (I really have to delve deeper into SEAR to get a feeling what your "structural" means.) –  Hans Stricker Feb 16 '11 at 7:17