Are these proofs about relations both equivalence and partial order correct

equivalence-relationslogicrelations

Task: Let $A$ be a set. Describe all the relations on $A$ that are at the same time:

i) symmetric and antisymmetric ii) equivalence and partial order

i) Theorem. Let $R$ be a relation on $A$, $R$ is symmetric and anti-symmetric if and only $R\subseteq i_{A}$. Where $i_{A}=\left\{ \left(a,b\right)\in A\times A\mid a=b\right\}$.

$\left(\rightarrow\right)$

Let $a,b$ be arbitrary elements of $A$. Suppose $aRb$. Since $aRb$ and $R$ is symmetric, then $bRa$. Since $aRb$, $bRa$ and $R$ is anti-symmetric, then $a=b$. Therefore since $a$ and $b$ are arbitrary we can conclude that $\forall a,b\in A\left(aRb\rightarrow ai_{A}b\right)$.

$\left(\leftarrow\right)$

Let $p,q,r,s$ be arbitrary elements of $A$. Suppose $pRq$. Suppose $rRs$ and $sRr$. Since $pRq$ and $R\subseteq i_{A}$, then $p=q$ and therefore $qRp$. Since $rRs$ and $R\subseteq i_{A}$, then $r=s$. Therefore since $p,q,r,s$ are arbitrary we can conclude that $\forall p,q\in A\left(pRq\rightarrow qRp\right)$ and $\forall r,s\in A\left(rRs\land sRr\rightarrow r=s\right)$.

ii) Theorem. Let $R$ a relation on $A$, $R$ is an equivalence and partial order relation if and only if $R=i_{A}$ and $R\neq\emptyset$.

$\left(\rightarrow\right)$

If $R$ is an equivalence relation, it must necessarily be symmetric, and if $R$ is an partial order relation, it must necessarily be anti-symmetric. So if $R$ is both, necessarily $R$ must be symmetric and anti-symmetric. But we shown that $R$ is symmetric and anti-symmetric if and only if $R\subseteq i_{A}$. Then if $R$ is an equivalence and partial order relation, it must necessarily be true that $R\subseteq i_{A}$. But if $i_{A}\nsubseteq R$ or $R=\emptyset$ are true that means $\exists x\in A\lnot\left(xRx\right)$, that is, $R$ would not be reflexive. Therefore the only solution is that $R=i_{A}$ and $R\neq\emptyset$ are both true .

$\left(\leftarrow\right)$

Our assumption is $R\subseteq i_{A}$, but we know from the theorem i) that $R$ is symmetric and anti-symmetric. We only need to verify that $R$ is transitive and reflexive. Let $x,y,z,a$ be arbitrary elements of A. Suppose $xRy$ and $yRz$. Since $R\subseteq i_{A}$, then $x=y=z$ therefore $xRz$. Since $a=a$ and $i_{A}\subseteq R$, then $aRa$. Therefore since $x,y,z,a$ are arbitrary we can conclude that $\forall x,y,z\in A\left(xRy\land yRz\rightarrow xRz\right)$ and $\forall a\in A\left(aRa\right)$.

Best Answer

The proofs are essentially correct with the sole remarks that:

  1. they could be formulated in a far more concise and syntactically correct way.
  2. the characterisation you have given in the second theorem is not entirely correct, the correct characterisation being $R \in \mathscr{Eq}(A) \wedge R \in \mathscr{Ord}(A) \Leftrightarrow R=\Delta_A$, where the notations (I dare hope) are self-explanatory: $\mathscr{Eq}(A)$ denotes the collection of all equivalences on $A$, $\mathscr{Ord}(A)$ likewise denotes the collection of all order relations on $A$ and finally $\Delta_A$ denotes the diagonal of $A$. In brief, the additional condition that $R \neq \varnothing$ that you add in your characterization is superfluous, for if $A \neq \varnothing$ then it also is the case that $\Delta_A \neq \varnothing$ hence from $R=\Delta_A$ it automatically follows that $R \neq \varnothing$ and if $A=\varnothing$ then the only binary relation on $A$ (which is simultaneously an equivalence and a total order) is $\varnothing$, the empty relation.

I for one would go about proving the claims you mention as follows:

  1. Assume that $R \in \mathscr{Rel}(A)=\mathscr{P}(A\times A)$ (this denotes the collection of all binary relations on $A$) is simultaneously symmetric and antisymmetric, which means on the one hand that $R=R^{-1}$ and on the other that $R \cap R^{-1} \subseteq \Delta_A$. I am here referring to the symmetry operator: \begin{align} (\bullet)^{-1} \colon A \times A &\to A \times A \\ (\bullet)^{-1}(x, y) &= (y, x) \end{align} and for arbitrary subset $X \subseteq A \times A$ (for an arbitrary binary relation $X$ on $A$, in other words) I am using the tacit notation that $X^{-1}=(\bullet)^{-1}[X]$ is the direct image of $X$ through the symmetry operator. From a more general point of view, $X^{-1}$ is naturally defined as the symmetric (or inverse or reciprocal) of the graphic $X$ - a graphic being a set whose elements are all ordered pairs - however let us not divagate too much. From the given conditions it is clear that $R \cap R^{-1}= R \cap R=R \subseteq \Delta_A$. Conversely, if we assume that $R \subseteq \Delta_A$ it is easy to see that $R=R^{-1}$ - since any diagonal pair is fixed by the symmetry operator $(\bullet)^{-1}$ - and hence that $R \cap R^{-1}=R \subseteq \Delta_A$, entailing thus the fact that $R$ is both symmetric and antisymmetric.
  2. Given that $R \in \mathscr{Eq}(A) \cap \mathscr{Ord}(A)$ - since equivalences are by definition symmetric and orders antisymmetric - we infer from 1) that $R \subseteq \Delta_A$. However equivalences as order relations alike are also by definition reflexive, which means that $\Delta_A \subseteq R$ and thus by double inclusion we can conclude that $R=\Delta_A$. The converse inclusion - that $\left\{\Delta_A\right\} \subseteq \mathscr{Eq}(A) \cap \mathscr{Ord}(A)$ - is elementary, since $\Delta_A$ is easily seen to trivially satisfy all the requirements of reflexivity, symmetry, antisymmetry and transitivity (which follows essentially from the transitivity of equality).
Related Question