Proving $R^n$ is antisymmetric when R is antisymmetric

1.4k Views Asked by At

Needing to solve this problem in a past paper. Not even sure where to start.

Let $R$ be a binary relation on some set S. Prove or disprove the following claim. "If $R$ is antisymmetric then $R^n$ is antisymmetric for every positive integer $n$".

2

There are 2 best solutions below

0
On BEST ANSWER

$S=\{1,2,3,4\}$

$R = \{(1,3), (3,2), (2,4), (4,1)\}$

$R^2 = \{(1,2), (3,4), (2,1), (4,3)\}$

$R$ is antisymmetric, however $R^2$ is not antisymmetric, therefore disproven by counterexample.

Thanks guys!

0
On

HINT: Construct a counterexample for $n=2$; you can take $S$ to be a $4$-element set and $R$ to contain exactly $4$ ordered pairs.