0
$\begingroup$

Could you please help me understand how to deal with this question ?

Suppose $<A,\prec>$ is partially ordered set and $f(x)=${$a\in A|a\prec x$} is a function. Prove that $f$ is not injection function: there are $y \neq z \in A$ such as $f(y)=f(z)$.

While I can pretty easily prove this statement for a specific partially ordered set, I somehow cannot find a formal prove that will be valid for any partially ordered set.

Thank you.

$\endgroup$
  • $\begingroup$ That doesn't look true to me. $\endgroup$ – Lord Shark the Unknown Sep 30 '18 at 6:20
  • $\begingroup$ any well ordered set is partially ordered, yet such a mapping is injective. If I get this right the mapping is $A\to\mathcal P(A), x\mapsto \{a< x\}$ $\endgroup$ – Alvin Lepik Sep 30 '18 at 6:52
0
$\begingroup$

If your function collects elements strictly greater than the given element (so $f(a)$ doe not contain $a$) your function can not be injective over some set; for example, consider the set $A=\{1,2,3,6\}$ and the divisibility relation $\mid$. You can see that $f(2)=f(3)=\{6\}$.

However, it may be one-to-one over another set; the easiest example is the singleton with the trivial ordering. More complicated example is any linearly ordered set.

If $f(a)$ contains $a$, then $f$ is injective; if $f(a)=f(b)$ then $a\in f(b)$ and $b\in f(a)$, so $a\le b$ and $b\le a$.

$\endgroup$
  • $\begingroup$ Maybe this is an answer than my professor had wanted: if A is a partly ordered set than we cannot say that for any set A function f is ingective. $\endgroup$ – A. B. Sep 30 '18 at 7:17

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.