Relation on a set of relations with these limitsprove equivalence / partial order

94 Views Asked by At

Let $S$ be a finite set. Define $\mathscr R(S)$ to be the set of relations on $S$. Define a relation $\mathscr R$ on $\mathscr R(S)$ as follows: $$\mathscr R=\{(\mathscr P,\mathscr Q)\mid \mathscr P,\mathscr Q∈\mathscr R(S),∀\,a,b∈S, \text{ if } a\mathscr P\,b,\text{ then } a\mathscr Q \,b\}.$$

Knowing that $\mathscr P$ is always a subset of $\mathscr Q$, then this relation is

Reflexive: Because a subset can be a subset of itself, thus $\mathscr P$ and $\mathscr Q$ can be equivalent for every $\mathscr P$.

Symmetric: Using same logic as above, the only relations that can exist where $(\mathscr P,\mathscr Q)$ exists, $(\mathscr Q,\mathscr P)$ exists when they are equal. Otherwise, when $\mathscr Q$ is a greater subset, it would not be in this relation.

Antisymmetric: Stated part of above

Transitive: If a set $\mathscr P$ is subset of $\mathscr Q$ and $\mathscr Q$ is a subset of $\mathscr V$, by standard set logic, $\mathscr P$ is a subset of $\mathscr V$, thus it is transitive.

With all four proven true, then this relation is a partial order (reflexive, transitive, antisymmetric) and a equivalence relation(reflexive, symmetric, transitive).

EDIT: I was just asking if the logic here is sound and true for all those statements?