Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 2 down vote accepted

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.