What is the number of elements of upper sets in a finite power set?

116 Views Asked by At

Take any finite set $X$ with cardinality $|X|=n$. Let $P(X)$ denote the power set of $X$ ordered by inclusion. Let $\uparrow\{x\}$ denote an upper set of $P(X)$, i.e. a subset $U$ such that if $\{x\}\subseteq p$ for $\{x\},p\in P(X)$, then $p\in U$.

What is the formula for calculating the number of elements of $U$, given the cardinality $n$ of $X$? Since for singleton $\{x\}$, $U$ is just an ultrafilter, its number of elements would be $2^{n-1}$. What if we take the upper set $\uparrow\{x,y\}$ for $x\neq y$, and similarly for more elements of $X$?

1

There are 1 best solutions below

0
On BEST ANSWER

If I understand you correctly, given $A\subseteq X$ you're looking for the set $$ {\uparrow}A = \{ B\in\mathcal P(X) \mid A\subseteq B \} $$ But this is the same set as $$ \{ C\cup A \mid C\in\mathcal P(X\setminus A) \} $$ which (since adding $A$ to each of these $C$s is obviously an injective operation) has the same cardinality as $\mathcal P(X\setminus A)$, namely $2^{|X|-|A|}$.