Proof: a relation is a partially ordering

Question

I tried to solve this problem, but I really don't know how to break the problem down into different parts so that it becomes easier.

The problem is:

Suppose $A$ is a set and $p$ a transitive and reflexive relation on A. From $p$, we can define an equivalence relation $s$ on A: $$a\, s\, b \iff a\,p\,b\, \land \, b\,p\,a$$

Using $p$ and $s$ we can define a relation $t$ on the set of equivalence classes $A/s$: $$[a]\,t\,[b] \iff \forall x \in [a]\, \forall y \in [b] \; x\,p\,y$$

Prove that $t$ partially orders $A/s$.

Answer 1

I’m assuming that your $A\setminus s$ is the quotient, which is normally written $A/s$.

You need to show that $t$ is reflexive, antisymmetric, and transitive. I’ll do reflexivity as an illustration.

Let $[a]\in A/s$; we must show that $[a]\mathrel{t}[a]$, i.e., that for each $x,y\in[a]$, $x\mathrel{p}y$. Since $x\in[a]$, we know that $x\mathrel{s}a$, and therefore $x\mathrel{p}a$ and $a\mathrel{p}x$. Similarly, $y\in[a]$, so $y\mathrel{p}a$ and $a\mathrel{p}y$. In particular, $x\mathrel{p}a$ and $a\mathrel{p}y$, and we know that $p$ is transitive, so $x\mathrel{p}y$, which is what we needed to prove.

To show that $t$ is antisymmetric, start with arbitrary $[a],[b]\in A/s$ such that $[a]\mathrel{t}[b]$ and $[b]\mathrel{t}[a]$, and show that $[a]=[b]$. Begin by translating the hypothesis that $[a]\mathrel{t}[b]$ and $[b]\mathrel{t}[a]$ into a statement about the elements of $[a]$ and $[b]$, and do the same for the desired conclusion that $[a]=[b]$. That will give you a hypothesis in terms of the known relations $p$ and $s$ that you can manipulate to get the desired conclusion.

Similarly, to show that $t$ is transitive, start with arbitrary $[a],[b],[c]\in A/s$ such that $[a]\mathrel{t}[b]$ and $[b]\mathrel{t}[c]$, and show that $[a]\mathrel{t}[c]$. As for the other two properties, begin by translating everything into statements about the members of $[a],[b]$, and $[c]$, so that you can use the known properties of $p$ and $s$.