MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I first quote a definition from Clone theory in Universal Algebra: A binary relation $\rho$ on a set U is strongly rigid if every universal algebra on U such that $\rho$ is a subuniverse of its square is trivial, i.e., the clone preserving ρ has only projections. It is known that there are only two strongly rigid relations on a 3-element domain. I found that

1) On a 4-element domain {0,1,2,3}, the following binary relation is possibly a strongly rigid relation: {(0,1), (0,2), (0,3), (1,0), (1,2), (2,0), (2,1), (2,3), (3,1), (3,2)}

2) On a 5-element domain {0,1,2,3,4}, the following relation is possibly a strongly rigid relation: {(0,2), (0,3), (0,4), (1,0), (1,3), (1,4), (2,0), (2,1), (2,4), (3,0), (3,1), (3,2), (3,4), (4,0), (4,1), (4,2), (4,3)}.

 Could you let me know if there is an easy way to prove the above statements?

This could be an algebraic proof, or by using a computer program.

share|cite|improve this question
It might help to clarify "trivial". The notion that makes the most sense to me is that the clone is trivial (only projection functions). It might also be that trivial means primal, but your examples don't suggest that. Can you relate primal to this notion of strongly rigid? – The Masked Avenger Aug 10 '13 at 3:57
I see I missed the title. However, it would be good to edit the question to include that trivial means the clone preserving $\rho$ has only projections. – The Masked Avenger Aug 10 '13 at 4:11

I do not see an easy way to prove it. The characterization you mention was published in the 1970's by Anne Fearnley, and the proof was a nicely organized but mildly tedious examination of cases based on the size of $\rho$. I do not think you will completely avoid such in showing your candidates are strongly rigid.

Something which might help is a characterization of pairs $\langle \rho' , f \rangle$ where any relation containing $\rho'$ is preserved by a nontrivial $f$. Fearnly uses a constant function and the corresponding ordered pair to show irreflexivity of strongly rigid relations. If you had a triangle and a partition of U into three parts, you could use a trivalent function to show some relations are not strongly rigid by mapping every pair to one of the six directed edges of the triangle. Alternatively, use Rosenberg's classification of minimal clones as a testbed for showing relations to be not strongly rigid. You might even have a theorem like rho is strongly rigid iff rho is not preserved by any of Rosenberg's functions, but you would have to prove the theorem first.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.