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

I have solved the problem affirmatively at least for sets of reals.

Theorem. Every set of reals admits a rigid binary relation (with no use of Axiom of Choice). Equivalently, every set of reals is the vertex set of a rigid directed graph.

Proof. Suppose that A is a set of reals. We may freely regard A as a subset of Cantor space 2^omega. Let us break into several cases.

Case 1. A is countable. This is the easy case, since we may simply impose a rigid structure on it by making it a linear order isomorphic to omega (or a finite linear order if A is finite).

Case 2. A is uncountable, but A has a countably infinite subset. Fix such a subset Z={z_0, z_1, ...} and fix a point z* in A-Z. For each finite binary sequence s, let U_s be the neighborhood in 2^omega of all sequences extending s, so that U_s(x) iff x extends s. Clearly, the structure (A,U_s)_s is rigid, since if you move any point x in A to another point, you will move it out of some neighborhood U_s that it was formerly in. We now reduce this structure to a binary relation. Let R be a relation on A that places all the z_n below z*, ordered like omega, and makes R(z*,z*) true. Next, enumerate the finite binary sequences as s_0, s_1, etc., (this does not require AC). We define R(x,y) iff x=z_n for some n, y is not z_m for any m, y is not z*, and U_{s_n}(y). That is, the first coordinate gives you some z_n, and hence some s_n, and then you use this to determine which neighborhood predicate to apply to y, but we only do this for y outside of Z union {z*}. I claim that the structure (A,R) is rigid. The reason is that z* and the reals z_n are definable in the structure (A,R), and so they are fixed by all automorphisms. (The real z* is the only one such that R(z*,z*), and the z_n are the only predecessors of z* wrt R.) Since every z_n is fixed, it follows that every automorphism must respect the neighborhood U_{s_n} intersect A, and hence fix all reals. So there are no nontrivial automorphisms.

Case 3. Weird A. The only remaining case occurs when A is uncountable, but has no countably infinite subset. (It follows that A will be Dedekind finite, but not finite.) In this case, every permutation of A will consist of disjoint orbits of finite length, since if there were an infinite orbit, then we could build a countably infinite subset of A by iterating it. But if every permutation of A is like that, then A has no permutations that respect the usual linear order < of the reals. Thus, (A,<) is rigid. QED

In particular, it is not true that the usual counterexample to AC in the symmetric forcing models is a counterexample to this rigidity question. Those sets are sets of reals, and this argument shows that they have rigid binary relations, without being well-orderable.

I'm not sure how far one can extend this idea. How about subsets of 2^kappa for any cardinal kappa? I think, however, that even this still won't give a full positive answer for all sets.