We study the deductive strength of the following statements:
𝖱𝖱: every set has a rigid binary relation,
𝖧𝖱𝖱: every set has a hereditarily rigid binary relation,
𝖲𝖱𝖱: every set has a strongly rigid binary relation,
in set theory without the Axiom of Choice. 𝖱𝖱 was recently formulated by J. D. Hamkins and J. Palumbo, and 𝖲𝖱𝖱 is a classical (non-trivial) 𝖹𝖥𝖢-result by P. Vopěnka, A. Pultr and Z. Hedrlín.