Number of sets that are downward-closed

720 Views Asked by At

Let $\mathbb{N}^{<\infty}$ be the set of all finite sequences of natural numbers (including the empty sequence) endowed with the extension ordering, so $s<t$ if $s$ is an initial segment of $t$. Call a subset $C\subset\mathbb{N}^{<\infty}$ downwards-closed if whenever $t\in C$ we also have $s\in C$ for all $s<t$.

How many downwards-closed subsets are there?

1

There are 1 best solutions below

0
On BEST ANSWER

Let $\Bbb N^\infty$ be the set of infinite sequences of natural numbers. Then there is an injection from $\Bbb N^\infty$ to the set of downward-closed sets of finite sequences defined the following way: $$ (n_1, n_2,n_3,\ldots) \mapsto \{(),(n_1), (n_1, n_2), (n_1, n_2, n_3), \ldots\} $$