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

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

2009-11-20T13:25:01Z

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

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

2009-11-20T18:56:42Z

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 by saf for Does every set admit a rigid binary relation? (and how is this related to the Axiom of Choice?)

2009-11-20T21:31:08Z

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

Answer by Joel David Hamkins for Does every set admit a rigid binary relation? (and how is this related to the Axiom of Choice?)

2009-11-24T19:40:42Z

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.

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

2009-12-28T16:53:37Z

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 by Justin Palumbo for Does every set admit a rigid binary relation? (and how is this related to the Axiom of Choice?)

2010-01-31T05:07:29Z

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 by ikp for Does every set admit a rigid binary relation? (and how is this related to the Axiom of Choice?)

2011-07-19T00:50:21Z

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

2011-07-19T12:44:03Z

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.