2
$\begingroup$

Could someone look through my attempt at proving the following problem please?

Let $(A, \preceq)$ be a POSET.For each $x,y \in A$,let $P_x=\{a \in A: a \preceq x\}$. Let $F$ be the family of sets defined by $F=\{P_x:x\in A\}$.Therefore $(F,\subseteq)$ is a POSET.

Prove $x \preceq y \iff P_x \subseteq P_y$ for all $x,y \in A$.

Attempt :

Let $(A, \preceq)$ be a POSET. Let $x,y \in A$, $P_x=\{a \in A: a \preceq x\}$ and $F$ be the family of sets defined by $F=\{P_x:x \in A\}$ with $(F,\subseteq)$ being a POSET.

$(\Rightarrow)$ part of the proof

Assume that $x \preceq y$ and suppose for contradiction that $P_x \nsubseteq P_y$. By definition, there must exist some $x \in A$ such that $x \in P_x$ and $x \notin P_y$.

Since $\preceq$ is a partial order, then it is reflexive and hence $x \preceq x$ and consequently $x \in P_x$.

With $x \preceq y$ by assumption then $x \in P_y$

Therefore we have the following contradiction: $(x \in P_x \text{ and } x \in P_y)$ on the one hand and $(x \in P_x \text{ and } x \notin P_y)$ on the other.

$(\Leftarrow)$ part of the proof

Assume $P_x \subseteq P_y$.Since $\preceq$ is a partial order, therefore it is reflexive and $x \preceq x$ and also $x \in P_x$.

Since $x \preceq x$ and $P_x \subseteq P_y$ then $x \in P_y$. With $P_y=\{a \in A: a \preceq y\}$ and $x \in P_y$ then $x \preceq y$ as required.

Thank you

$\endgroup$
3
$\begingroup$

The outline of the proof is not far from correct, but you've made a mistake. Namely, in the $(\Rightarrow)$ direction, you pick $x \in A$ to verify $x \in P_x \setminus P_y$. There is no hypothesis that guarantees this can be done: if $P_x \not \subset P_y$ then when have some $a \in A$ with $a \in P_x \setminus P_y$ but it may very well be $a \neq x$.

Even when fixing this, there is no need to contradict the premise because your argument is in essence a direct one. By this, I mean the following: to prove $p \Rightarrow q$ you are assuming "$p$ and not $q$". Then, you prove $p \Rightarrow q$, which gives a contradiction as we have $p$ but were assuming "not $q$". Hence "$p$ and not $q$" is false and thus $p \Rightarrow q$ is true, as we wanted to prove. Note that the proof itself proves $p \Rightarrow q$ as an intermediate step, so we can avoid the contradiction altoghether (this will probably be clearer later on).

Finally, just a style remark (this is obviously personal, but since you are asking for a proof review, I figure that it can be useful). You are repeating information too many times. It may be useful to just state clearly which properties you use at the beginning. For example, in a more complex proof, you could add auxiliary lemmas.

Here's a possible proof,

Proposition. Let $(A, \preceq)$ be a poset. For each $x \in A$, we define $P_x := \{a \in A : a \preceq x\}$. If we consider the family $F = \{P_x\}_{x \in A}$ ordered by inclusion, then $(F, \subset)$ is a poset and moreover we have that $x \preceq y$ if and only if $P_x \subset P_y$.

Proof. First, let's observe that since $\preceq$ is reflexive, we have $x \in P_x$ for each $x \in A$. We prove both implications,

$(\Rightarrow)$ Let $x \preceq y$ be elements of $A$. If $z \in P_x$, then by definition we have $z \preceq x \preceq y$. Hence $z \in P_y$. This proves that, in effect, $P_x \subset P_y$.

$(\Leftarrow)$ Suppose that $P_x \subset P_y$. In particular, $x \in P_y$ and so by definition of $P_y$ we obtain $x \preceq y$. $\square$

$\endgroup$
  • $\begingroup$ Thank you Guido. Am I right in assuming that my mistake was assuming x $\in$ A rather than some element other than x,y in the ($\Rightarrow$) part? I purposefully made the proof more verbose than necessary because i fear if i leave repetitions out it may be annoying for forum members to scroll up and down for defintions/etc :) $\endgroup$ – HalfAFoot Apr 17 '19 at 7:08
  • 1
    $\begingroup$ No problem! Again, the latter was a personal remark. I myself tend to be rather verbose when writing proofs, so I try to keep an eye on phrasing efficiency. $\endgroup$ – qualcuno Apr 17 '19 at 7:10
  • $\begingroup$ oops i was editing the comment right when you posted a response...just to be sure ..am I right in thinking that my mistake was assuming x ∈ A rather than some element other than x,y in the (⇒) part? $\endgroup$ – HalfAFoot Apr 17 '19 at 7:11
  • 1
    $\begingroup$ Yes, that was the only mistake I found, and luckily it was an easily fixable one. Having $P_x \not \subset P_y$ implies there exists some $a \in A$ in $P_x \setminus P_y$, but we have no control over who $a$ can be. The other direction was fine :) $\endgroup$ – qualcuno Apr 17 '19 at 7:15
  • 1
    $\begingroup$ precision is as unforgiving as the devil! $\endgroup$ – HalfAFoot Apr 17 '19 at 7:17
2
$\begingroup$

Looks fine. It could have been a simplified a bit.

Suppose $x\preceq y$. To prove $P_x\subseteq P_y$, let $a\in P_x$. Then $a\preceq x$ by definition of $P_x$ and so by transitivity, $a\preceq y$. Therefore $a\in P_y$.

Suppose $P_x\subseteq P_y$. Then $a\in P_x\Rightarrow a\in P_y$. Since $x\preceq x$ by reflexivity, so $x\in P_x$. Therefore $x\in P_y$ and so by definition of $P_y$, we must have $x\preceq y$.

$\endgroup$
  • 1
    $\begingroup$ Thanks PJK, I do not know why i automatically use proof by contradiction! But i see the mistake nontheless. $\endgroup$ – HalfAFoot Apr 17 '19 at 7:16

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.