Prove that a binary relation R over a set A is a strict order if and only if R is irreflexive and transitive

582 Views Asked by At

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.

1

There are 1 best solutions below

1
On

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.