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

Question

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

Answer 1

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.

Answer 2

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$.

Answer 3

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, \ldots\}$ 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\cup\{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.

Answer 4

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

Answer 5

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.

Answer 6

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

Answer 7

Related question:

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$.

Obviously AC implies this, and this is also implied by every set admitting a rigid binary relation.

Given such a structure, one can interpret it as a graph, but then you have to add more vertices so it's not completely clear to me.