1
$\begingroup$

This is my relation: $R= \{(0,1), (1,2)\}$

I know it is not transitive, because: $$ 0R1 \wedge 1R2 \Rightarrow 0R2,$$ but this is false

Now I want to check, if it is antisymmetric. How can I write down, that it is an antisymmetric relation.

I know the definition: $$ aRb \wedge bRa \Rightarrow a=b $$

$\endgroup$
1
  • 1
    $\begingroup$ By the way, you can use \text{blah blah blah} to insert blah blah blah into your mathematics formulas. For example $\text{I know the definition: }\pi=3$ renders as $\text{I know the definition: }\pi=3$. $\endgroup$ – MJD Nov 6 '14 at 20:55
3
$\begingroup$

As you said, the relation is antisymmetric if $$\text{for all $a,b$,}\qquad aRb\land bRa \implies a=b.$$

Or equivalently, it is antisymmetric unless there are some $a$ and $b$ for which $aRb$ and $bRa$ but nevertheless $a\ne b$.

Does your relation have $a$ and $b$ for which $aRb$ and $bRa$ and also $a\ne b$?

$\endgroup$
1
$\begingroup$

Brute force works; it's not hard to enumerate all possible values of $(a,b)$ where $aRb$ is true or where $bRa$ is true, and those are the only values of $(a,b)$ where the implication could possibly be false.

(and because the implication is symmetric under swapping $a$ and $b$, it's enough just to consider the $(a,b)$ pairs where $aRb$ is true)


In more detail, if it turns out to be true, this would be a proof by cases: the two cases are "$aRb \wedge bRa$ is true" and "$aRb \wedge bRa$ is false". If you can show the implication is true in both cases, then the implication is true.

In the first case, you're essentially solving for all possible values of $(a,b)$ that make it true, and then checking the value of the implication.

Another way to arrange the same argument is to try and solve the equation "the implication is false". The first step of solving is that it is equivalent to the simultaneous system of two equations "$aRb \wedge bRa$ is true" and "a \neq b". If you continue solving and ultimately prove that there are no $(a,b)$ that satisfy this system, you've proven the implication is never false: i.e. that it's always true.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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