Take the 2-minute tour ×

Call a type of structure rigid if any automorphism of such a structure is an identity. (This is a bit different from some other uses of the word, but hopefully I'll be forgiven.) For example, well-orderings are rigid. It follows that assuming the axiom of choice, there is a rigid type of structure (namely, a well-ordering) such that any set can be equipped with that type of structure (in a non-unique way, of course).

Now the axiom of choice isn't necessary for that conclusion. Extensional well-founded relations are also rigid, and the axiom of foundation implies that any set injects into an extensional well-founded relation (its transitive closure). Aczel's axiom of anti-foundation also suffices, since strongly extensional relations are also rigid, and anti-foundation implies that any set injects into such a relation. But with neither foundation nor anti-foundation, the membership relation $\in$ needn't be rigid. For instance, the set {a,b}, where a={a} and b={b} are unequal ill-founded sets with the same membership tree, has a nonidentity $\in$-automorphism which swaps a and b.

Now my question: If we don't assume choice or any sort of foundation, does there still exist a rigid type of structure with the property that any set can be equipped with that type of structure?

Edit: Of course, as Steven points out in the comments, I haven't said exactly what I mean by "type of structure." I'm using the word "structure" in the Bourbaki-sense, not in the sense of stuff, structure, property. Here's one way to make this question precise: does there exist a theory in higher-order logic which is rigid, in the sense that any automorphism of one of its models is the identity, and which admits a definable functor to Set which is essentially surjective?

share|improve this question
I am confused: what possible structure could prevent the function swapping a and b from being an isomorphism of {a,b}? –  Ori Gurel-Gurevich Nov 18 '09 at 6:35
Ori, a total ordering would do that. For then either a < b or b < a, so the function swapping a and b is not an automorphism of the ordered set {a, b}. –  Tom Leinster Nov 18 '09 at 7:49
What definition of structure are you using? Here is my attempt at a definition of structure on sets: A faithful functor from some category to Sets. To my mind what you are saying is that there is a category WellOrd of well ordered sets (NOT the skeleton of this category), in this category every object is rigid. The "forgetful functor" from WellOrd to Sets is faithful and surjective on objects (which says that every set can be well ordered). But of course there is such a functor from the discrete category with |Set| many objects to Sets, and every object in the discrete category is rigid... –  Steven Gubkin Nov 18 '09 at 14:35
I tried to clarify the sort of structure that I mean. –  Mike Shulman Nov 18 '09 at 16:37
Tom: right. I was confused with a "uniquely definable" structure ,like that produced by foundation, and forgot about the AC part. –  Ori Gurel-Gurevich Nov 18 '09 at 18:03

3 Answers 3

I understand the question in terms of the rigidity of first order structures, namely, does every set admit of a first order structure that is rigid?

You won't like the proof, but Yes, every set has a rigid structure, if you allow arbitrary first order languages. For suppose that B is a set. For each element b of B, let us introduce a first order unary predicate U_b, which holds exactly at b and at no other point. We may endow B as a first order structure by including all these predicates in the language, so that the structure is (B,{U_b}_{b in B}). Every element of B is clearly definable in this language, since b is the unique object x such that U_b(x). Thus, this structure is rigid. And the argument uses neither the Axiom of Choice nor Foundation.

The obvious objection here is that this is not a finite language; it is nothing like an order, which is what you had in mind. In this case, I suggest that the question should really be: Does every set have a binary relation, such that this relation makes the set into a rigid first order structure? Under the Axiom of Choice, the answer will be yes, since the set will be well-orderable. Without AC, I'm not sure. I suspect that this is some kind of choice principle.

I don't see how Foundation really figures into the question. Although it is true under Foundation that every transitvive set is rigid, what if the original set is not transitive? We can't really regard the transitive closure of the original set as imposing a first order structure on that set, since it is adding points rather than relations.

share|improve this answer
The title of the question was misleading, but I think if you read the whole thing, you'll see that what I want is one type of structure which is rigid for all sets, i.e. ∃-∀ not ∀-∃. I'm perfectly happy with infinitary languages and even higher-order structure, and I don't care whether it's a binary relation or anything like that. I tried to make this clearer in my edit. –  Mike Shulman Nov 19 '09 at 22:20
In the foundation example, we could take the type of structure to be "a well-founded extensional relation equipped with a chosen subset" and let the forgetful functor to Set pick out the subset. –  Mike Shulman Nov 19 '09 at 22:21
Since you don't seem particularly interested in the binary relation case, which seems central to me, I posted Question <mathoverflow.net/questions/6262>;. (I'm a newbie here, so please tell me if that isn't the right way to do things.) As you are entertaining infinitary languages, I'm not sure why my answer doesn't provide one "type" of structure in your sense. Call it, "Sets, equipped with many unary relations". In any case, I predicted you wouldn't like my answer! :-) –  Joel David Hamkins Nov 20 '09 at 13:38
It's because of the ∃-∀ versus ∀-∃. Your answer provides, for any given set B, a type of structure such that B admits a rigid structure of that type. What I want is one type of structure, such that for every set B, B admits a rigid structure of that type. –  Mike Shulman Nov 20 '09 at 16:12
I think a variant of your answer does work if you allow "structure" with proper-class-sized languages. Then you could define a language containing a predicate U_x for EVERY set x, and equip a set B with this structure where U_x holds of x precisely when x is in B. But while I'm happy with infinitary languages, I'd like them to be set-sized! –  Mike Shulman Nov 20 '09 at 16:15

Over at Does every set admit a rigid binary relation?, I showed that at least for sets of reals, there is an affirmative answer. Namely, every set of reals admits a rigid binary relation, by an argument that uses neither the Axiom of Choice nor Foundation (and does not make use of any hereditary well-founded structure of the reals, so it would apply even if you conceived of numbers as urelements).

But it is not clear to me how to generalize this to higher sets.

share|improve this answer

This doesn't completely answer the question, but I think it's relevant.

Theorem: Let T and W be theories in higher-order logic (by which I mean the internal type theory associated to elementary topoi), where W has a specified underlying object X (i.e. we regard a model of W as an object X equipped with some additional stuff). Then it is not the case that both (1) T proves that W is rigid (as structure on X) and (2) in any topos satisfying T, every object can be equipped with W-structure.

Proof: Suppose that both the given conditions hold. Let C[T,X] be the free topos on the theory T and an additional object X, and let C[T,W] be the free topos on T and W. (Recall that for any theory S and any topos E, the category Log(C[S],E) of logical functors and natural isomorphisms from C[S] to E is equivalent to the category of models of S and their isomorphisms in E.) Now the generic model of W in C[T,W] has an underlying object, giving a logical functor C[T,X]→C[T,W]. And C[T,X] satisfies T, so by assumption, its generic object X can be equipped with W-structure; thus we also have a logical functor C[T,W]→C[T,X], and the composite C[T,X]→C[T,W]→C[T,X] is isomorphic to the identity. In other words, C[T,X] is a pseudo-retract of C[T,W]. Now let E be any other topos satisfying T and Y any object of E admitting a nonidentity automorphism (such as Y=1+1); then we have a logical functor C[T,X]→E sending X to Y, which in turn has a nonidentity automorphism. But because C[T,X]→C[T,W]→C[T,X] is the identity, this functor C[T,X]→E must factor through C[T,W], and since T proves that W is rigid, any automorphism of this functor must be the identity, a contradiction. ∎

This means that if you want a rigid type of structure that can be put on every set, you need to use more about sets than the fact that they form an elementary topos, or even a Boolean topos with a NNO, or any additional property of Set that can be expressed as a theory T in HOL. Note that AC, although it can be phrased as a "categorical" property not referring directly to ∈ (every surjection splits), cannot be expressed as a theory in HOL since it involves a quantification over all sets. Likewise for the "topos-theoretic axiom of foundation" that every set injects into some well-founded extensional relation. So the question is, what can we do with the remaining non-HOL axioms of ZF, i.e. basically replacement and (its consequence) unbounded separation.

share|improve this answer

Your Answer


