Prove that if $R$ is a preorder over a set A, then $S_R$ is a strict order.

Question

$aS_Rb$ if $aRb \cap bꞦa$

My working:

Theorem: If $R$ is a preorder over a set $A$, then $S_R$ is a strict order.

Example relation:

R = { {a,b}, {b,c}, {c,c}, {f,c}, {f,e}, {e,f}, {e,b}, {b,e}, {d,e}, {d,d}, {d,a}, {a,d} }

Therefore $S_R$ = { {a,d}, {a,b}, {d,e}, {a,e}, {b,e}, {b,c}, {e,f}, {c,f} }

Lemma 1: The binary relation $aS_Rb$ is irreflexive.

Proof: Consider an arbitrary $a \in S_R$. We need to prove $S_R$ is irreflexive. Consider an element $b=a$. If $aRb$ is false we can conclude that the relation is irreflexive.

Lemma 2: The binary relation $aS_Rb$ is transitive.

Proof: Consider an arbitrary $a, b, c, \in S_R$. We need to prove that $S_R$ is transitive. To do so, begin by checking if $aRb$ and $bRc$ is true. After that check the relation $aRc$. If $aRb \cap aRc \implies aRc$ then we can conclude that $R$ is transitive. $\blacksquare$

I was wondering if someone can check this proof, while i was writing it something didn't seem right about it i.e. it seemed incredibly small in length and i felt like i regurgitated the definitions of irreflexivity and transitivity.

Answer 1

Seems that you made some incorrect assumptions in your proof.

First of all, when you want to prove that a relation has or doesn't have some properties (reflexivity, transitivity, asymmetry etc.) it's often better to employ the definitions of those properties.

Second of all, you need to learn how to use these definitions correctly, this will prevent you from wrong assumptions which might make your proof incorrect.

So, let's go back to your proof.

Lemma 1: The binary relation $S_R$ is irreflexive.

As far as I'm concerned your statement doesn't prove anything. It only uses some vague assumptions:

If $aRb$ is false we can conclude that the relation is irreflexive.

And note you can't prove statements by saying "if something is true we can conclude". To really prove the statement you need to show that "something is really true".

Let's see what the definition of irreflexivity:

A binary relation $R$ on set $A$ is called irreflexive if for each $a \in A$ $a \not R a$.

So as it turned out we have to show that for an arbitrary $a \in A$, we have that $a \not S_R a$. There's also an interesting point here that we have to prove a negation, so we need to either negate a definition of $S_R$ to proceed with the prove or employ proof by contradiction.

Proof: So consider an arbitrary $a \in A$, we will show that $a \not S_R a$ (see how I use the definition of irreflexivity here). For the sake of contradiction, let's assume that $a S_R a$ which means that $aRa \land a\not Ra $ (see how I use the definition of $S_R$). But these two statements are impossible, because they contradict each other, so we have reached the contradiction and our assumption that $a S_R a$ is wrong, therefore $a \not S_R a$. $\blacksquare$

Lemma 2: The binary relation $aS_Rb$ is transitive.

In this proof there is the same mistake, it doesn't prove anything, it only assumes that if something were true, then what I'm trying to prove would be also true. But it's important to understand that proofs don't work that way, you shouldn't assume, you should prove, your reader shouldn't even have any doubts about what you're saying in your proofs.

It's a very good point that you're using the definition of transitivity in this proof. But be careful, when using definitions like the transitivity which is below:

A binary relation $R$ on set $A$ is called transitive if for each $a, b, c \in A$ if $a R b \land b R c$ then $a R c$.

Here you don't need to prove that $a R b$ and $b R c$, you can assume this for free, because you already selected them from the set, you intentionally select such $a, b, c$, where $a R b \land b R c$. You ignore elements which doesn't meet this condition (this how implication works). And after you select such elements you need to prove that $a R c$. This is what you need to prove.

Proof: Consider arbitrary $a, b, c \in A$ such that $a S_R b \land b S_R c$. We will prove that $a S_R c$, by showing that $a R c \land c \not R a$. Since $a S_R b$ we know that $a R b \land b \not R a$. Since $b S_R c$ we know that $b R c \land c \not R b$. Since $R$ is a preorder, it's transitive and since $a R b \land b R c$, consequently we have that $a R c$.

Now we need to show that $c \not R a$. For the sake of contradiction, let's assume that $c R a$. Then since $R$ is a preorder, it's transitive and since $c R a \land a R b$, we have that $c R b$. But this contradicts the fact that $b R c \land c \not R b$, therefore our assumption is wrong and $c \not R a$. Since $a R c \land c \not R a$, we know that $a S_R c$ as required. $\blacksquare$