What is a cut pair in partially ordered class?

162 Views Asked by At

I haven't understood the definition of a cut in POSET. Let $A=\{1, 2, 3, 4, 5, 6, 7\}$.
Which of the following is a cut ?
a) $\{\{1, 2, 3\}, \{4, 5, 6, 7\}\}$ - Separates such that no element in Upper set(Second one) is less than Lower set(first one)
or
b) $\{\{1, 2, 4\}, \{3, 5, 6, 7\}\}$ - Just partition into two POSETS, without any restrictions.
or both?

Definition of a cut:
If $A$ is a partially ordered class, then a cut of $A$ is pair $(L, U)$ of nonempty subclasses of $A$ with the following properties:
i) $L ∩ U = Ø$ and $L ∪ U = A$.
ii) If $x ∈ L$ and $y \le x$, then $y ∈ L$.
iii) If $x ∈ U$ and $y \ge x$, then $y ∈ U$.

In this image a and f are not ordered. How can they be part of a cut ?

1

There are 1 best solutions below

2
On

For your first question about $A = \{1,2,3,4,5,6,7\}$, I assume that the partial order is the usual $\leq$. Then it is easy to see that $\{\{1,2,3\},\{4,5,6,7\}\}$ is a cut, because it satisfies i), and all elements that are less than an element in $L = \{1,2,3\}$ is also in $L$, and all elements that are greater than an element in $U = \{4,5,6,7\}$ is also in $U$, so ii) and iii) are also satisfied.

However, $\{\{1,2,4\},\{3,5,6,7\}\}$ with $L = \{1,2,4\}$ and $U = \{3,5,6,7\}$ is not a cut because $4 \in L$ and $3 \leq 4$, but $4 \notin L$, so condition ii) is not satisfied. In fact, condition iii) is also not satisfied because $3 \in U$ and $4 \geq 3$, but $4 \notin U$.

For the question in your image, we can simply check the definition:

i) is clearly satisfied.

ii) $a \in L$ and the elements below $a$ are $b$ and $c$, and these are also in $L$. $b \in L$ and the only element below $b$ is $c$, which is also in $L$. $c \in L$, but there are no elements below $c$.

iii) $f \in U$ and the elements above $f$ are $d$ and $e$ which are also in $U$. $e \in U$ and the only element above $e$ is $d$, which is also in $U$. Finally, $d \in U$, but there are no elements above $d$.

Hence $L = \{a,b,c\}$ and $U = \{d,e,f\}$ determines a cut.