Prove that all subsets of $\mathbb{N}$ can be labeled as either "large" or "small", where
$A \subset \mathbb{N} \text{ is large} \iff \overline{A} \text{ is small}$.
If $A$ is large, then any superset of $A$ is large, and if $A$ is small, any subset of $A$ is small.
Union of two small subsets is small, intersection of two large subsets is large.
All finite subsets are small, all subsets with finite complements are large.
Now forget about the fourth condition for a moment.
Let "partial labeling" be such a labeling where some of the subsets are unlabeled. Consider the set $\mathcal{L}$ of all partial labelings $L$ of subsets of $\mathbb{N}$ and partially order it by inclusion: $L_1 \leq L_2$ if $L_2$ has the same labels as $L_1$ for those sets that are labeled in $L_1$.
Now, for any totally ordered subset $S$ of $\mathcal{L}$ consider the union $U = \cup_{L \in S} L$ of all the labelings of that subset. It can be easily seen that $U$ is a proper labeling (for every set that has a label in $U$ there exists a labeling $L$ in $S$ such that (1) and (2) hold, and for every pair of sets there exists $L$ in $S$ containing both of them, so (3) holds).
In other words, we have proven the precondition of Zorn's lemma that every chain has an upper bound, so for every partial labeling $L$ there exists a maximal labeling agreeing with $L$. Clearly, being maximal, this labeling would be defined on every subset of $\mathbb{N}$.
Now let's recall about (4) and take $L$ to be such that (4) holds: label all finite subsets as small and their complements as large, and take the maximal element $M_L \geq L$. That would be the nonprincipal ultrafilter on $\mathbb{N}$.
Is this reasoning correct?
It was noted in the comments that one need to show that there indeed are no unlabeled subsets in $M_L$ as it's not that clear. I tried to prove the original claim inductively first by considering $L$ satisfying (4) and then showing that we could inductively take any yet unlabeled $A \subset \mathbb{N}$ and label it so that (1-3) hold.
The way I was doing that is by considering any other already labeled $B \subset \mathbb{N}$ and trying to show that there is no contradiction if either $B \subset A$, $A \subset B$ or $A \neq B, A \cap B \neq \emptyset$. But this is clumsy and perhaps unnecessary in this case. What would be an elegant way to show that $M_L$ does not contain any unlabeled subsets?