Concrete models of abstract structures - MathOverflow

Concrete models of abstract structures

2011-02-13T18:07:11Z

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:

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?

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?

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?}

Answer by Andreas Blass for Concrete models of abstract structures

2011-02-14T00:21:27Z

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.

Answer by François G. Dorais for Concrete models of abstract structures

2011-02-14T11:03:07Z

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.

Answer by Joel David Hamkins for Concrete models of abstract structures

2011-02-14T15:04:10Z

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.

Apologies for this long answer...

Answer by Mike Shulman for Concrete models of abstract structures

2011-02-15T06:55:52Z

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

Answer by Hans Stricker for Concrete models of abstract structures

2011-02-15T09:03:53Z

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.