Let $R$ and $S$ be two distinct relations defined on a set $A$ such that $R$ is of order and $S$ is of equivalence. Indicate which of the following statements is impossible to occur:
- $R\subseteq S$.
- $|R|>|S|$.
- $R\cup S$ is of order.
- $R\cap S$ is not of order.
I have no idea how to find the impossible statement.
I tried finding some examples of relations $R$ and $S$ to prove the impossibility, but then I realized that I can take other examples where the statement is true.
Equality is both an order relation and an equivalence, so (1) can occur.
Equality is contained in any order relation, so (2) can occur too.
Since equality is of both types, taking $R$ and $S$ to be equality, their union is still equality, an order relation, so (3) can occur.
Now, if $R$ is an order relation and $S$ an equivalence, they are both reflexive and transitive, and so $R \cap S$ is reflexive and transitive too.
Can you prove that $R \cap S$ is still anti-symmetric? If so, then $R\cap S$ is an order relation, and so it can't happen that $R\cap S$ is not an order relation, that is (4) cannot occur.