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$

| cite | improve this answer | |
  • $\begingroup$ Dang you beat me by a few seconds :D $\endgroup$ – John Griffin Sep 23 '17 at 20:32
  • $\begingroup$ Funny how that happens :) $\endgroup$ – Bram28 Sep 23 '17 at 20:34
  • $\begingroup$ @JohnGriffin. So what? Is the stack a competitive game? $\endgroup$ – 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)$.

| cite | improve this answer | |
  • 1
    $\begingroup$ Great minds ... $\endgroup$ – Bram28 Sep 23 '17 at 20:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.