0
$\begingroup$

Could someone verify my attempt at the following problem?

Let $(A,\preceq)$ and $(B, \preceq ')$ be Partially ordered sets and suppose that $h:A \rightarrow B$ satisfies $x \preceq y \iff h(x) \preceq 'h(y)$ for all $x,y \in A$.Prove that h is one-to-one.

Attempt:

Let $(A,\preceq)$ and $(B, \preceq ')$ be POSETS and suppose that $h:A \rightarrow B$ satisfies $x \preceq y \iff h(x)\preceq 'h(y)$ for all $x,y \in A$.

Suppose for a contradiction that $h$ is not one-to-one,then there exists some $x,y \in A$ such that (i) $h(x)=h(y)$ and $x\neq y$.

By anti-symmetry,if $x \preceq y$ and $y \preceq x$ then $x=y$. The logically equivalent contraposition suggests that if $x \neq y$ then $ x \npreceq y$ or $y \npreceq x$.

Since $x \neq y$ by (i) then the following divison by cases are possible.

[case : $x \npreceq y$ and $y \preceq x$]

by $x \preceq y \iff h(x)\preceq 'h(y)$ the following holds :

  • $x \npreceq y$ implies $h(x)\npreceq 'h(y)$ and
  • $y \preceq x$ implies $h(y)\preceq 'h(x)$

therefore with $h(x)\npreceq 'h(y)$ and $h(y)\preceq 'h(x)$ then $h(x) \neq h(y)$ which contradicts (i) according to which $h(x)=h(y)$

[case : $x \preceq y$ and $y \npreceq x$]

..similar as the previous case

[case : $x \npreceq y$ and $y \npreceq x$]

by $x \preceq y \iff h(x)\preceq 'h(y)$ the following holds :

  • $x \npreceq y$ implies $h(x)\npreceq 'h(y)$ and
  • $y \npreceq x$ implies $h(y)\npreceq 'h(x)$

therefore with $h(x)\npreceq 'h(y)$ and $h(y)\npreceq 'h(x)$ then $h(x) \neq h(y)$ which contradicts (i) according to which $h(x)=h(y)$.

Therefore h is one-to-one.


it looks right but feels iffy to me because for each of the cases i conclude that $h(x) \neq h(y)$ on the bases that

if $h(x) \preceq 'h(y)$ and $h(y)\preceq 'h(x)$ then $h(x)=h(y)$.

where for example in the last case, $h(x)\npreceq 'h(y)$ and $h(y)\npreceq 'h(x)$ was implied to yield $h(x) \neq h(y)$ ...is that logically right ?

thank you for your time.

$\endgroup$
  • 1
    $\begingroup$ The antisymmetry is indeed all you need. $\endgroup$ – Matt Samuel Apr 16 '19 at 21:28
  • $\begingroup$ Thank you, the reason i used contradiction is due to confusion of the meaning of 'if' ,'only if' in definitions as opposed to in theorems,corollaries,lemmas....is my proof still correct though? $\endgroup$ – HalfAFoot Apr 17 '19 at 5:12
1
$\begingroup$

You don't really need proof by contradiction

$$h(x)=h(y)$$ $$\Longrightarrow h(x)\preceq^{\prime}h(y)\:\land\:h(y)\preceq^{\prime}h(x)$$ $$\Longrightarrow x\preceq y\:\land\:y\preceq x$$ $$\Longrightarrow x=y$$

$\endgroup$
  • 2
    $\begingroup$ No need to work with a contradiction: $h(x) = h(y)$ implies $x = y$ as you showed, so $h$ is one-to-one. $\endgroup$ – Mark Kamsma Apr 16 '19 at 21:29
  • 1
    $\begingroup$ @MarkKamsma Indeed, was in the middle of editing my answer. $\endgroup$ – eranreches Apr 16 '19 at 21:30
  • $\begingroup$ Yes! That was the confusion i had. In mathematical defintions, it seems that 'if' and 'only if' statements should be regarded as 'iff'..which is why i used proof by contradiction and why i highlighted my concerns about things being iffy...after browsing the internet it seems that technically, occurences of 'if' , 'only if' in mathematical definitions linking A and B, imply that A and B are synonymous hence practically one can treat such statements as A iff B...am i understanding this right? Also, is my proof by contradiction okay? Thanks $\endgroup$ – HalfAFoot Apr 17 '19 at 5:19

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.