A rigid type of structure that can be put on every set?

Question

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?

Answer 1

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 $\operatorname{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]\to 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]\to C[T,X]$, and the composite $C[T,X]\to C[T,W]\to 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]\to E$ sending $X$ to $Y$, which in turn has a nonidentity automorphism. But because $C[T,X]\to C[T,W]\to C[T,X]$ is the identity, this functor $C[T,X]\to 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 $\mathsf{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 $\in$ (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.

Answer 2

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.

Answer 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 transitive 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.