# Sufficient and necessary conditions for order relations describing a certain system of sets

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.

• Is your partial ordering strict or non-strict? – Alex Vong Jan 6 '18 at 0:25
• @AlexVong You see I use $<$ symbol denoting strict partial order – porton Jan 6 '18 at 8:02
• 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$)? – Dap Jan 8 '18 at 6:22
• 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 \}$. – porton Jan 10 '18 at 5:51
• Is your supposed counterexample not isomorphic to $V=\{\{0,1,4\},\{2,3\},\{0\},\{1\},\{2\},\{3\}\}$? Am I missing something? – Taneli Huuskonen Jan 11 '18 at 10:58

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$.