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$".
Asked
Active
Viewed 1,422 times
0
-
What would the notation $R^n$ mean in the context of a relation? – Christopher King Aug 15 '13 at 15:53
-
3@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
2 Answers
6
$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!
PrincessEev
- 43,815
Kom
- 303
1
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.
Brian M. Scott
- 616,228