# $(\forall x \in A)(\forall y \in A)(x Ry \iff P_x ⊆ P_y)$ for a partial order $R$

This is Velleman's exercise 4.4.10:

Suppose $R$ is a partial order on $A$. For each $x ∈ A$, let $P_x = \{a ∈ A | aRx\}$. Prove that $∀x ∈ A∀y ∈ A(x Ry ↔ P_x ⊆ P_y)$.

Here's my proof of it:

Proof. Suppose $x$ and $y$ to be arbitrary elements of $A$.

($\rightarrow$) Suppose $xRy$. Suppose $aRx$. Since $R$ is transitive then from $aRx$ and $xRy$ we get $aRy$. Therefore if $aRx$ then $aRy$ and therefore if $xRy$ then $(aRx \rightarrow aRy).$

($\leftarrow$) Suppose $(aRx \rightarrow aRy)$. By the definition of partial order we have $xRy$ and therefore if $(aRx \rightarrow aRy)$ then $xRy$.

From ($\rightarrow$) and ($\leftarrow$) we'll have $(x Ry ↔ P_x ⊆ P_y)$ and since $x$ and $y$ were arbitrary then $∀x ∈ A∀y ∈ A(x Ry ↔ P_x ⊆ P_y)$.

Is my proof correct? Particualrly the backward direction in which I didn't use "$(aRx \rightarrow aRy)$" directly.

Thanks a lot.

The $\leftarrow$ does indeed need a bit of work.

Use that $R$ is reflexive to get that $xRx$, and hence $x \in P_x$. Since $P_x \subseteq P_y$ that means that $x \in P_y$, and hence $xRy$

• Dang you beat me by a few seconds :D – John Griffin Sep 23 '17 at 20:32
• Funny how that happens :) – Bram28 Sep 23 '17 at 20:34
• @JohnGriffin. So what? Is the stack a competitive game? – William Elliot Sep 23 '17 at 23:06

It seems correct, but you did skip a step in the backward direction with the words "by the definition of partial order". Here's a rewording:

Suppose $P_x\subseteq P_y$. Since $R$ is reflexive, we have $x\in P_x$. Thus the assumption gives $x\in P_y$, so that $xRy$.

This shows that you do infact use $(aRx\to aRy)$.

• Great minds ... – Bram28 Sep 23 '17 at 20:32