number of antichains and number of downsets

447 Views Asked by At

This question is taken from the book Introduction to Lattices and Order by Davey and Priestley. Question 14 of Chapter 1.

Definition : If $P$ is and ordered set and $Q\subseteq P$, then $Q$ is a down-set if whenever, $x\in Q$, $y\in P$ and $y\leq x$, we have $y\in Q$.

Question : Let $P$ be a finite ordered set. Let $\mathcal{O}(P)$ be the set of all down-sets of $P$. Show that for all $x\in P$, $|\mathcal{O}(P)|=|\mathcal{O}(P\backslash \{x\})|+|\mathcal{O}(P\backslash (\uparrow x \cup \downarrow x))|$.

I suppose the hint given by the question, which says that there exists a one-to-one correspondence between elements in $\mathcal{O}(P)$ and antichains of $P$, is essential here.

If I am to denote $\mathcal{A}(P)$ as the set of all anti-chains of $P$, all I've got is $|\mathcal{O}(P)|=|\mathcal{A}(P)|$. I tried to check if it's the case that $|\mathcal{A}(P)|=|\mathcal{A}(P\backslash \{x\})|+|\mathcal{A}(P\backslash (\uparrow x \cup \downarrow x))|$. However, I really could not see any link between them.

Thus, I would like to seek your input to help me see the links here. Thank you.

1

There are 1 best solutions below

2
On BEST ANSWER

HINT: Suppose that $A$ is an antichain in $P$. If $x\notin A$, then $A$ is an antichain in $P\setminus\{x\}$. If $x\in A$, then $A\setminus\{x\}$ is an antichain in $P\setminus(\uparrow\!\!x\cup\downarrow\!\!x)$.