# 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 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?.)

-
That's the first time I heard of a structure having only nontrivial automorhphisms. –  Harald Hanche-Olsen Nov 20 '09 at 14:45
That was a typo! Of course I mean no nontrivial automorphisms. (or only the trivial automorphism). –  Joel David Hamkins Nov 20 '09 at 16:33

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.

-
This is great! Thanks very much. But now I am confused. I had always thought that there was a rough equivalence between the ZFA symmetric models via the Jech-Shore embedding theorem and the symmetric models obtained by the forcing technique (by looking at the class of symmetric names). For example, Cohen used the latter method to build a model of ZF with a non-wellorderable set of reals. But you are saying that the ZFA symmetric models only map their atoms in at a higher level? So do the ZFA proofs via Jech-Shore provide a model of ZF with no well-ordering of the reals? –  Joel David Hamkins Jan 2 '10 at 21:17
I am accepting this answer, since it shows that some amount of choice is required. But it seems to remain open whether the question of every set having a rigid binary relation is actually equivalent to AC. It could be weaker than AC. –  Joel David Hamkins Jan 2 '10 at 21:19
About the ZFA proofs: Given a ZFA model with a permutation group G and associated normal filter F, the embedding theorem gives a symmetric forcing model where the permutations on A are now translated to very similar permutations on certain names for sets of ordinals. I am not sure when the reals in these models will have no well-ordering (probably in almost all nontrivial cases). In certain cases it definitely will, for example if the set of reals could be well-ordered, then its powerset could be linearly ordered and these embedding theorems can be used to give models where that fails. –  Justin Palumbo Jan 5 '10 at 20:32
Thanks for the explanation, but your description makes it sound like the forcing construction. I'll have a look at Jech's description of the embedding theorem. Meanwhile, Justin, there seem to be two of you, one at mathoverflow.net/users/2426, and another at mathoverflow.net/users/2436. Which is really you? Perhaps the administrators can merge these identities. –  Joel David Hamkins Jan 6 '10 at 4:18
Both are me; I was originally confused about how to make an account and lost access to the first one. It probably is a good idea for me to contact the admins and ask them to put them together, or maybe delete the old one. –  Justin Palumbo Jan 6 '10 at 5:04

As Joel pointed out in the comments, although an answer to this question was accepted there remained the issue of whether the statement in question was equivalent to the axiom of choice. By modifying the proof of Joel's theorem about sets of reals admitting rigid binary relations, I believe I can show that in the standard Cohen model $M$ for the failure of AC the statement "every set admits a rigid binary relation" holds. In particular, this statement is strictly weaker than AC and fails to imply any of the choice principles that fail in that model. A further question that might be interesting is whether every set in this model admits a rigid linear order.

Theorem. In $M$ every set admits a rigid binary relation.

Proof. Throughout we work in $M$. There is a set of reals $A$ such that any set $x$ can be injected into $A^{<\omega}\times\gamma$ for some ordinal $\gamma$ (see for example Lemma 5.25 in Jech's The Axiom of Choice). So any set can be injected into $\mathbb{R}^{<\omega}\times\gamma$ and indeed into $\mathbb{R}\times\gamma$ for some $\gamma$. Thus to prove the theorem it is in fact enough to strengthen Joel's theorem and prove that every subset $X$ of $\mathbb{R}\times\gamma$ admits a rigid binary relation. The proof is really just a slight tweaking, but I'll write it out. Let $<$ denote the lexicographical ordering on $\mathbb{R}\times\gamma$ inherited from the two usual linear orderings on the component sets. (I identify $\mathbb{R}$ with Cantor space $2^\omega$).

Case 1: $X$ has no countably infinite subset. Then $<$ restricted to $X$ is rigid, as any nontrivial permutation allows us to iterate the map countably many times on some moved element and get a countable subset.

Case 2: $X$ has a countably infinite subset $z_0,\ldots z_n,\ldots$ (and grab some other point $z^*$). Let $Z=\{z^* ,z_0,\ldots z_n,\ldots\}$. We define a rigid binary relation $R$ as follows. We set $R(z^* ,z^* )$ and put $z_0,\ldots z_n,\ldots$ below $z^*$ in ordertype $\omega$. Let $s_0,\ldots s_n\ldots$ enumerate the finite binary sequences. Then for $\langle x,\alpha\rangle\not\in Z$ we put $R(z_n,\langle x,\alpha\rangle)$ iff $s_n\subseteq x$. For $\langle x,\alpha\rangle$ and $\langle y,\beta\rangle$ both not in $Z$ we let $R(\langle x,\alpha\rangle,\langle y,\beta\rangle)$ hold iff $\langle x,\alpha\rangle<\langle y,\beta\rangle$.

We claim that $R$ is rigid. Let $\pi:X\rightarrow X$ be an $R$-automorphism. As in Joel's proof it is easy to see that every member of $Z$ gets fixed, and that as a result whenever $\pi(x,\alpha)=(y,\beta)$ we must have $x=y$. It easily follows from this that $\pi$ fixes the second coordinate of every member of $X\setminus Z$ as well, as now $\pi$ restricted to the second coordinate is an automorphism of a subset of $\gamma$, with respect to the usual well-ordered relation on $\gamma$.

-
Excellent! Thanks very much, Justin. This was a great idea, and I'm very appreciative. (You have a typo in your theorem--you want "every set admits..." not just "every set of reals admits...".) Both of your answers deserve far more up-votes than they have currently. –  Joel David Hamkins Jan 31 '10 at 21:33

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.

-
Very interesting! Does 2^kappa have a linear order? It does seem unlikely that this sort of trick could work for all sets. –  Mike Shulman Nov 28 '09 at 1:13
Well, 2^kappa has the same kind of linear order as 2^omega, namely, the lexical order (smaller = first difference bit is smaller). I agree that the method of this answer doesn't seem to generalize much. To make a direct generalization work for 2^kappa, you would seem to need a subset equinumerous with 2^{<kappa}, to get access to the neighborhoods. But what do you do in the other cases? Is the lexical order rigid if there is no subset equinumerous with 2^{<kappa}? And even if you can handle subsets of 2^kappa for every kappa, I don't see how this handles all sets. –  Joel David Hamkins Nov 29 '09 at 21:23

All sets have a rigid binary relation. I have a reference for this:

A rigid relation exists on every set P. Vopěnka, A. Pultr and Z. Hedrlin, Commentationes Mathematicae Universitatis Carolinae 6(1965), 149-155

-
Thanks! I admire Vopenka very much, so I'm pleased he answered this. I'll get back to you once I look this up... –  Joel David Hamkins Nov 20 '09 at 21:28
As saf said below, this paper does use AC. It is, of course, completely trivial that under AC, every set admits a relation (namely, a well-ordering) which is rigid in the sense of this question (and of my original one), namely, admitting no nontrivial AUTOmorphisms. What Vopenka-Pultr-Hedrlin prove is that in fact (assuming AC) there is a relation on any set which admits no nontrivial ENDOmorphisms. No infinite well-ordering has this property. –  Mike Shulman Nov 21 '09 at 1:38

A variant of Justin Palumbo's answer, blackboxing the forcing construction:

An infinite set X is called amorphous if all its subsets are finite or co-finite. X is called strongly amorphous (or superamorphous) if every relation on X (that is, every subset of $X^n$, for any $n$) is definable with finitely many parameters in the language of equality. (In other words, restricting to $n=2$ for simplicity: Every $R \subseteq X^2$ must be in the Boolean algebra generated by the sets $X_a:=\{(a,x): x\in X\}$, their converses and the diagonal. Unless I have forgotten a few more generators.)

(In particular, amorphous sets are Dedekind finite.)

Clearly, strongly amorphous sets have no rigid relation. Their consistency with ZF can be shown (as pointed out above) by first constructing a ZFA model with an amorphous set of atoms, then applying the Jech-Sochor theorem.

(Strongly) amorphous sets X (and related structures, such as the powerset of X) can often be used as counterexamples showing that some choice is needed.

-
A more established terminology: In "The structure of amorphous sets" (APAL 1995, MR1332569), Truss calls an amorphous set "STRICTLY AMORPHOUS" if every partition into finite classes must have almost all classes of size 1, and I think he proves (as one of the easy cases, actually) that this is the same as what I called "strongly amorphous" here. –  Goldstern Jul 19 '11 at 20:21

Theorem 2 of the Vopenka-Pultr-Hedrlin paper does assume the Axiom of Choice

-
Is it true that under ZF any set $X$ admits some rigid countable structure on it? where a structure is a subset of $\bigcup ({ P(X^n) : n< \omega })$ (i.e. it may contain binary relations, ternary relations, etc.), and countable means there is an injective function from the structure to $\omega$.