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

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

-
What would the notation $R^n$ mean in the context of a relation? –  PyRulez Aug 15 '13 at 15:53
@PyRulez It most likely means the $n$-fold composite relation: i.e. $R^2$ is the relation where $a R^2 c$ if and only if there exists $b$ such that $a R b$ and $b R c$. –  Nick Peterson Aug 15 '13 at 15:54
@NicholasR.Peterson Correct. –  Kom Aug 15 '13 at 15:54
If you're "not even sure where to start", then start by writing down the definition of "antisymmetric relation" and "$R^n$". –  MJD Aug 15 '13 at 15:59
Thanks everyone, think I have proven it below –  Kom Aug 15 '13 at 16:10

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

-

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.

-