Covering of a partial order by upwards convex sets

Question

First off: I'm not an expert in order theory, so some of my terms might be off; correct them if you wish.

Let me call a subset $A$ of a lattice $(S,\le)$ upwards convex (not sure if that's actually good terminology) if it holds that for all $a,b\in A$ and all $x\in S$ with $a\le x\le a\vee b$ (where $\vee$ is join), also $x\in A$.

Now let $M$ be a finite set with $n$ elements and $P\subseteq 2^M$ any subset of its power set. $P$ is (of course) not necessarily upwards convex, but it can be covered by upwards convex sets: there exist subsets $P_1,\dots,P_k\subseteq P$ such that all $P_i$ are upwards convex and $P=P_1\cup\dots\cup P_k$. (One such covering is given by $P_1,\dots,P_k$ being the single-element subsets of $P$, proving the above existence claim.)

Say that $P$ is $k$-coverable if there exists a covering $P_1,\dots,P_k$ by upwards convex sets. Two questions:

1. What is the minimum $k$, as a function of $n$, such that any $P\subseteq 2^M$ is $k$-coverable?

2. What is the computational complexity of determining, given $P\subseteq 2^M$ and $k$, whether $P$ is $k$-coverable?

As a partial answer to (1), I can show that $k\ge n(n+1)/2 + 1$ using a recursive argument.

Answer 1

The answer to (1) is $2^{n-1}$. If $P$ is the collection of all subsets of even cardinality, then each convex subset of $P$ is a singleton. Hence $k\geq 2^{n-1}$.

On the other hand, one can fix $a\in M$ divide all the subsets into pairs differing only in $a$. Then $P$ is the union of its intersections with the pairs, and each intersection is clearly convex.