Let $A=\{1,2,3,4,5\}$. Can we find a relation on A that is total but not transitive?

Question

Total is defined as ${\displaystyle \forall a,b\in A(aRb\lor bRa)}$. I'm just really confused.

I don't think it's possible to find such a relation, but I just want to be sure or be corrected if I am wrong. Thanks.

Answer 1

Mace4 returned the following:

% number = 1
% seconds = 0

% Interpretation of size 5

 < : 
       | 0 1 2 3 4
    ---+----------
     0 | 1 0 1 0 0
     1 | 1 1 0 0 0
     2 | 0 1 1 0 0
     3 | 1 1 1 1 0
     4 | 1 1 1 1 1

 c1 : 0

 c2 : 2

 c3 : 1

i.e. $0R0,0R2,1R0,1R1,2R1,2R2,3R0,3R1,3R2,3R3,4R0,4R1,4R2,4R3,4R4$

or, $xRy \iff (x \le y \land (x,y) \ne (2,0)) \lor ((x,y)=(0,2))$.

Then, $0R2$ and $2R1$, but $\neg 0R1$.

Answer 2

To not be transitive there have to be $3$ elements $a,b,c$ so that $aRb$ and $bRc$ but $a\not R c$. Wolog let's assume $1R2$ and $2R3$ and $1\not R3$.

Now the condition of the $R$ is that either $1R3$ or $3R1$. Since $1\not $ we must have $3R 1$.

so that is $4$ out of $25$ possible pairings and we do have it not transitive. We just have to make it complete.

We can go through the remaining $21$ pairs and make choices so that for each $(x,y)$ and $(y,x)$ one of them are in the relationship.

Or we can take a sledgehammer and just declare them all in the relationship.

...

Let $R$ be such that all $aRb$ except $1\not R 3$. That will be complete. And it will not be transitive.