Friday, 16 August 2013

Are these proofs on partial orders correct?

Are these proofs on partial orders correct?

I'm trying to prove whether the following are true or false for partial
orders $P_1$ and $P_2$ over the same set $S$.
1) $P_1$ ¡È $P_2$ is reflexive?
True, since $P_1$ and $P_2$ contains all the pairs { ($x,x$) : $x$ in
$S$}, we know the union also does. Thus $P_1$ ¡È $P_2$ is reflexive. That
set of ($x,x$) elements is called ¦¤, or the diagonal of $S$.
2) $P_1$ ¡È $P_2$ is transitive?
False, since $x¡Üy$ and $y¡Üz$ in $P_1$ ¡È $P_2$. How do we know $x¡Üy$ is
from $P_1 and $y¡Üz$ isn't from $P_2? There's nothing guaranteeing that we
have $x¡Üz$.
3) $P_1$ ¡È $P_2$ is antisymmetric?
False, for all we know, $x¡Üy$ in $P_1$ and $y¡Üx$ in $P_2$. That would be
the complete opposite of asymetry - symmetry (for those two elements, at
least).

No comments:

Post a Comment