0
$\begingroup$

The problem I am working on is, "What is the covering relation of the partial ordering $\{(A,B)|A⊆B\}$ on the power set of $S$, where $S=\{a, b, c\}$?"

I am reading the answer key, and I can follow it for the most part. What I don't understand is this, "In this problem $A \preceq B$ when $A \subseteq B$. For $(A,B)$ to be in the covering relation, we need $A$ to be a proper subset of $B$ but we must also have no subset strictly between $A$ and $B$."

I understand the part about having no subset between $A$ and $B$, that would contradict the very definition of of a covering relation. For example, I know that $(\{a\},\{a,b,c\})$ is not in the covering relation, because of the the ordered-pair $(\{a,b\},\{a,b,c\})$, meaning that $\{a,b\}$ is an intermediate value. The part that I don't understand is why $A$ has to be a proper subset of $B$. Why is that?

Edit: Let $(S,\preceq)$ be a poset. We say that an element$y∈S$ covers an element $x∈S$ if $x≺y$ and there is no element $z∈S$ such that $x≺z≺y$. The set of pairs $(x, y)$ such that $y$ covers$x$ is called the covering relation of $(S,\preceq)$. From the description of the Hasse diagram of a poset, we see that the edges in the Hasse diagram of $(S,\preceq)$ are upwardly pointing edges corresponding to the pairs in the covering relation of(S,). Furthermore, we can recover a poset from its covering relation, because it is the reflexive transitive closure of its covering relation. (Exercise 31 asks for a proof of this fact.) This tells us that we can construct a partial ordering from its Hasse diagram.

  • 0
    Wait, you wrote "I understand the part about having no subset between$A$and B" in your question, so isn't it clear why $(\{a\},\{a,b,c\})$ isn't in the covering relationship?2012-11-16

1 Answers 1

2

So, the key for understand why it is a proper subset is the symbol $\prec$ compared to the symbol $\preceq$. If $(P,\preceq)$ is a poset, then $x\prec y$ means "$x\preceq y$ and $x\neq y$."

Now, in the specific poset, $(P,\preceq) = (S,\subseteq)$, where $S$ is the set of all subsets of $\{a,b,c\}$. $S$ is a set with $8$ elements. We can list $S$ explicitly: $S=\{\emptyset,\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\},\{a,b,c\}\}$.

It might be easier if you don't use $A,B,C$ for elements of $S$, since it might confuse the question between the lower case letters, $a,b,c$. Instead, let's use $X$, $Y$, and $Z$ for elements of $S$.

So $Y$ covers $X$ if (1) $X\prec Y$, and (2) there is no $Z\in S$ such that $X\prec Z\prec Y$.

(1) means $X\preceq Y$ and $X\neq Y$, But $\preceq$ in this poset is just $\subseteq$. So $X\preceq Y$ means $X\subseteq Y$. So necessarily, if $Y$ covers $X$, then $X$ is a subset of $Y$ and $X\neq Y$. But that is just the the definition of "$X$ is a proper subset of $Y$."

$Y=\{a,b,c\}$ is not a cover for $X=\{a\}$ because $Z=\{a,b\}$ has the property $X\prec Z\prec Y$, which violates the definition of "$Y$ is a cover for $X$."