MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).
show/hide this revision's text 2 typo "only" should be "no"

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 only 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 http://mathoverflow.net/questions/5920.)
show/hide this revision's text 1

Does every set admit a rigid binary relation? (and how is this related to the Axiom of Choice?)

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 only 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 http://mathoverflow.net/questions/5920.)