2
$\begingroup$

I call a system of precedences $U$ a set of nonempty subsets of some poset. I will denote $A<B \Leftrightarrow \forall a\in A, b\in B: a<b$ for sets $A,B\in U$.

Find sufficient and necessary restrictions on binary relations $<$ and $\subseteq$ such that there exists a system $U$ of precedences such that they are exactly (up to isomorphism) $<$ and $\subseteq$ on $U$.

(I wrote my conditions for these operations for a system of precedences in https://cs.stackexchange.com/q/85951/39512 but I'm not sure if these conditions are right.)

The proposed conditions in that answer can be written as the following:

  • $\subseteq$ is a non-strict partial order relation and $<$ is a strict partial order relation.

  • $\forall a,b,a_1,b_1\in U:(a<b \wedge a_1\subseteq a \wedge b_1\subseteq b \Rightarrow a_1<b_1)$.

(Not relevant to the question, just where the questions appeared from) Systems of precedences origin from subsets of $U$ being sets of operations, where operations with higher precedences should be applies before operations of lower precedences.)

You may assume that all sets in consideration are finite.

$\endgroup$
  • $\begingroup$ Is your partial ordering strict or non-strict? $\endgroup$ – Alex Vong Jan 6 '18 at 0:25
  • 2
    $\begingroup$ @AlexVong You see I use $<$ symbol denoting strict partial order $\endgroup$ – porton Jan 6 '18 at 8:02
  • 1
    $\begingroup$ I couldn't understand the phrase "such that they are exactly $<$ and $\subseteq$ on $U$" - maybe an example would help. What set are the binary relations $<$ and $\subseteq$ defined on? Where do you use the definition of $<$ for sets ($A<B\iff \cdots$)? $\endgroup$ – Dap Jan 8 '18 at 6:22
  • 1
    $\begingroup$ Counterexample to my answer proposed in the question (so we need to find another answer): Consider $U = \{\{0, 1\}, \{2, 3\}, \{ 0 \}, \{ 1 \}, \{ 2 \}, \{ 3 \} \}$ with the usual order of the digits and induced order of singletons, but with $\{0, 1\}$ incomparable with $\{2, 3\}$. It also cannot be a system of precedences via any isomorhism $\varphi$, because $\varphi \{0, 1\} < \varphi \{2, 3\}$ is implied by $\forall x \in \varphi \{ 0 \}, y \in \varphi \{ 2 \} : x < y$ (etc.) what is implied by $\varphi \{ 0 \} < \varphi \{ 2 \}$ what is implied by $\{ 0 \} < \{ 2 \}$. $\endgroup$ – porton Jan 10 '18 at 5:51
  • 1
    $\begingroup$ Is your supposed counterexample not isomorphic to $V=\{\{0,1,4\},\{2,3\},\{0\},\{1\},\{2\},\{3\}\}$? Am I missing something? $\endgroup$ – Taneli Huuskonen Jan 11 '18 at 10:58
2
+100
$\begingroup$

Let $(A,\subseteq^A,<^A)$ satisfy your proposed conditions. For $a\in A$, let $f(a)=\{b\in A\mid b\subseteq^A a\}$. Let $U$ be the range of $f$. Now, consider $a,b\in A$. Assume first $b\subseteq^A a$. Then for every $c\in f(b)$, it holds that $c\subseteq^A b\subseteq^A a$ and hence, by the transitivity of $\subseteq^A$, we have $c\subseteq^A a$ and therefore $c\in f(c)$. So, $f(b)\subseteq f(a)$. Assume then $b\not\subseteq^A a$. Then $b\in f(b)$ but $b\notin f(a)$, so $f(b)\not\subseteq f(a)$. We have shown that $b\subseteq^A a$ iff $f(b)\subseteq f(a)$. This also implies that $f$ is one-to-one.

Assume now that $b <^A a$. Let $a'\in f(a)$ and $b'\in f(b)$. Then $a' \subseteq^A a$ and $b' \subseteq^A b$, so it follows from your assumptions that $b' <^A a'$. Thus $f(b) < f(a)$. On the other hand, $a\in f(a)$ and $b\in f(b)$, and therefore $f(b) < f(a)$ implies, in particular, that $b <^A a$.

$\endgroup$

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.