Consider two relations $R$ and $S$ on a set $A$ with $R$ being antisymmetric. Prove $R \cap S$ is antisymmetric.

89 Views Asked by At

Consider two relations $R$ and $S$ on a set $A$ with $R$ being antisymmetric. Prove $R \cap S$ is antisymmetric.

Theorem The subset of an antisymmetric relation is also antisymmetric.

The intersection $R \cap S$ of $R$ and $S$ is a subset of $R$:

$R \cap S \subseteq R$

Now, according to the theorem, since the subset of an antisymmetric relation is antisymmetric it follows that the intersection $R \cap S$ is also antisymmetric. This concludes the proof.

I now prove the theorem by contradiction. Let $T \subseteq R$ and $T$ is not antisymmetric. Then there exists elements of $T$ which violate antisymmetry, namely that there are elements $(x, y) \in T$ and $(y, x) \in T$ such that $x \neq y$. However, since $T$ is a subset of $R$ these elements would also be in $R$ which would mean that $R$ is not antisymmetric. But $R$ is antisymmetric, a contradiction. Therefore $T$ must be antisymmetric.

Is this proof correct? Or is there a better way to prove the claim?

1

There are 1 best solutions below

0
On BEST ANSWER

I am making my comment an answer as well.

Your proof is technically accurate, but not efficient in the sense that you unnecessarily phrase it as a contradiction. A more direct method is as follows.

Suppose $R$ is an anti-symmetric relation and $T$ is a subset of $R$. Then, if $(x,y)$ and $(y,x)$ are in $T$, we have $(x,y)$ and $(y,x)$ are in $R$. Since $R$ is anti-symmetric, $x=y$. Thus, $T$ is also anti-symmetric.