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

164 Views Asked by At

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.

1

There are 1 best solutions below

0
On BEST ANSWER

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