# Establishing A Covering Relation

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.

-
Is your question why $A$ must be a subset, or why it must be a proper subset? – Thomas Andrews Nov 16 '12 at 14:44
What is the definition of the "cover" relationship in your book? – Thomas Andrews Nov 16 '12 at 14:45
@ThomasAndrews My question is, why does it have to be a proper subset? I edited my post to include the description my book gives on Covering relations. – Mack Nov 16 '12 at 15:17
Also, the answer key says that $(\{a\},\{a,b,c\}$ won't be in there, but $(\{a,b\},\{a,b,c\}$. Why couldn't it be the other way around? – Mack Nov 16 '12 at 15:35
What do you mean by "the other way around?" Do you mean why can't $\{a,b,c\}$ be considered a cover of $\{a\}$? – Thomas Andrews Nov 16 '12 at 15:51

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

-