Let us say that a set B admits a rigid binary relation, if there is a binary relation R such that the structure (B,R) has no nontrivial automorphisms. 


Under the Axiom of Choice, every set is well-orderable, and since well-orders are rigid, it follows under AC that every set does have a rigid binary relation. 


My questions are: does the converse hold? Does one need AC to produce such rigid structures? Is this a weak choice principle? Or can one simply prove it in ZF?


(This question spins off of Question [A rigid type of structure that can be put on every set?](https://mathoverflow.net/questions/5920).)



Does every set admit a rigid binary relation? (and how is this related to the Axiom of Choice?)
Update: Joel and I have written an article based on the concepts introduced in this question, which can be seen at <http://arxiv.org/abs/1106.4635>


It looks to me that it is consistent with ZF that there is a set without a rigid binary relation. Use
the standard technique for constructing such wierd sets. First construct a permutation model of ZFA where
the set of atoms A has the desired property and then use the Jech-Sochor theorem to transfer the result to a ZF model. Any sentence that
can be stated just using quantifiers over some fixed iteration of the powerset operation over A can be transferred.
In our case the sentence "A has no binary relation without a nontrivial automorphism" only needs to quantify
over say the fifth iteration of the powerset of A (probably less). The standard reference for these techniques
is Jech's text The Axiom of Choice from 1973. (There the Jech-Sochor theorem is called the First Embedding Theorem).


In our case what is called the basic Fraenkel model is the desired ZFA model. (This and other similar
models are constructed in Chapter 4). Suppose R is a binary relation on A. Then there is a finite set E (called
the support of R in Jech's terminology) such that any permutation of A fixing E pointwise maps R to itself. In
other words such bijections are automorphisms of R. Since E is finite we can without AC find nontrivial such bijections and
it follows that R is not rigid.


In fact examining the proof of the Jech-Sochor theorem shows that Joel's fact about sets of reals is optimal
in the following sense: models of ZFA are simulated by ZF models by transferring the set of atoms to a
set of sets of reals and thus one cannot in ZF go any further up the hierarchy of types than the
powerset of omega and hope to construct rigid binary relations.


