1
$\begingroup$

I was wondering if someone can check this proof for me. And if you have any other methods of proving this please feel free to write them below.

$\\$

Lemma 1: If $R$ over a set $A$ is a strict order then $R$ is irreflexive and transitive

Proof : Lets assume $R$ is a arbitary binary relation over the set $A$, is strict order. We need to prove $R$ is irreflexive and transitive.

Consequently we already know $R$ is a strict order relation. Therefore $R$ is irreflexive and transitive.

$\\$

Lemma 2: If $R$ over a set $A$ is irreflexive and transitive then $R$ is strict order.

Proof: Lets assume $R$ is an arbitrary relation that is reflexive and transitive. We will prove that $R$ is strict order.

Consequently, we know $R$ is irreflexive and transitive. Therefore we will need to prove $R$ is asymmetric.

Let $a$ and $b$ be arbitrary elements where $aRb$ holds. We will prove that $bRa$ doesn't hold. Consider $c$ to be an element such that $c=a$. The relation $R$ is transitive we know that $aRb \cap bRc$ should result in a false to prove the asymmetry of $R$. We know that $R$ is irreflexive therefore $aRc$ is false.

Notice that $aRb \cap bRc \implies aRc$ is true therefore we can conclude that aRb is asymmetric.

$\endgroup$
1
  • 1
    $\begingroup$ Looks good to me, except that you don't need to introduce $c$ in your second lemma. $\endgroup$ – Don Thousand Jan 22 '20 at 21:35
1
$\begingroup$

This is fine, though there are a couple of places where you say "reflexive" when you mean "irreflexive," and I would use "antisymmetric" instead of "asymmetric." Antisymmetric is what I've always seen used, and if I had to interpret it "asymmetric" would not imply "never symmetric," only that it's not symmetric in at least one case.

$\endgroup$
1
  • 1
    $\begingroup$ Antisymmetry and asymmetry have different meanings. Antisymmetry is $x\prec y$ and $y\prec x\to x=y$ and asymmetry is $x\prec y\to$ not $y\prec x$. Technically, they are the same in irreflexive relations, but one normally associates antisymmetry with lax orders and asymmetry with strict orders. $\endgroup$ – Matthew Daly Jan 22 '20 at 23:17

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.