Proving the intersection of two partially ordered sets is a partially ordered set – transitivity

discrete mathematics

I need to prove that if $R,S$ are both partially ordered sets (POsets)
then $R \cap S$ is a POsets as well.

I got stuck while proving it is transitive:

let $<a,b>,<b,c> \in R\cap S$ then, WLOG, $<a,b>,<b,c> \in R$
and thus $<a,c> \in R$ because R is a POSet.
Similarly $<a,c> \in S$ and thus $<a,c> \in R \cap S$

Is it considered a proof of transitivity? Are there any mistakes along the way?

Best Answer

I think you mean that $R$ and $S$ are both partial orders on some set $X$, so that $X$ is the partially ordered set, not $R$ and $S$ themselves.

It’s fine, apart from one slight misuse of language. You don’t actually mean ‘without loss of generality’, since you’re not picking just one of the alternatives and saying that it doesn’t matter which one is picked: you’re picking both and observing that $\langle a,b\rangle$ and $\langle b,c\rangle$ are both in both $R$ and $S$. Thus, you can apply transitivity of both $R$ and $S$ to conclude, as you did, that $\langle a,c\rangle$ is in both $R$ and $S$ and hence in their intersection. Drop the WLOG, and you’re fine.

Related Question