For each positive integer $n$, let $f(n)$ denote the smallest possible value of
$$
\left|A_{1} \cup A_{2} \cup \cdots \cup A_{n}\right|,
$$
where $A_{1}, A_{2}, \ldots, A_{n}$ are sets such that $A_{i} \nsubseteq A_{j}$ and $\left|A_{i}\right| \neq\left|A_{j}\right|$ whenever $i \neq j$.
Determine $f(n)$ for each positive integer $n$.
We will prove that
$$
f(1)=0, \quad f(2)=3, \quad \text { and } \quad f(n)=n+2 \text { for } n \geq 3 .
$$

It is clear that $f(1)=0$ by taking $A_{1}=\{\}$.
We obtain $f(2) \leq 3$ by taking $A_{1}=\{1\}$ and $A_{2}=\{2,3\}$. Since in order to satisfy the subset condition, neither set can be empty and a singleton set must contain a unique element, it is clear that $f(2) \geq 1+2=3$, so we conclude that $f(2)=3$.
Next, we prove that $f(n) \geq n+2$ for $n \geq 3$. Suppose that $A_{1}, A_{2}, \ldots, A_{n}$ satisfy the conditions of the problem and are listed in increasing order of cardinality. We first observe that for all $1 \leq k \leq n-1$ we must have $\left|A_{k+1}\right| \geq\left|A_{k}\right|+1$. We also observe in particular that $A_{1} \nsubseteq A_{n}, A_{2} \nsubseteq A_{n}$, and $A_{1} \nsubseteq A_{2}$.
We find that there is never a solution such that $\left|A_{n}\right|n$, then we observe that there must be at least one element in any arbitrarily chosen set $A_{k}$ for $1 \leq k<n$ which is not in $A_{n}$. We select $k=1$ without loss of generality, and find
$$
\left|A_{1} \cup A_{2} \cup \cdots \cup A_{n}\right| \geq\left|A_{1} \cup A_{n}\right| \geq\left|A_{n}\right|+2=n+2 .
$$

In either case, we find that $f(n) \geq n+2$.
It remains to show that $f(n) \leq n+2$ for $n \geq 3$, which we do using an inductive construction. The base cases are given by $n=3$ and $n=4$ below, and it is easy to check that they do indeed satisfy the conditions of the problem.
$$
\begin{array}{ll}
n=3: & A_{1}=\{1\}, A_{2}=\{2,3\}, A_{3}=\{3,4,5\} \\
n=4: & A_{1}=\{1\}, A_{2}=\{2,3\}, A_{3}=\{2,4,5\}, A_{4}=\{3,4,5,6\}
\end{array}
$$

Now suppose that for some $n \geq 3$, sets $A_{1}, A_{2}, \ldots, A_{n}$ satisfy the following conditions:
- $A_{i} \nsubseteq A_{j}$ for $i \neq j$;
- $\left|A_{i}\right| \neq\left|A_{j}\right|$ for $i \neq j$;
- $\left|A_{k}\right|=k$ for $1 \leq k \leq n$; and
- $\left|A_{1} \cup A_{2} \cup \cdots \cup A_{n}\right|=n+2$.

If these more restrictive conditions are satisfied, we necessarily have $f(n) \leq n+2$.
Write $A=A_{1} \cup A_{2} \cup \cdots \cup A_{n}$ and let $a$ and $b$ be two elements that do not belong to $A$. Consider the following $n+2$ sets:
$$
\begin{aligned}
B_{1} & =\{a\} \\
B_{k+1} & =A_{k} \cup\{b\}, \quad \text { for } \quad k=1,2, \ldots, n \\
B_{n+2} & =A
\end{aligned}
$$

We now show that the new sets $B_{1}, B_{2}, \cdots, B_{n+2}$ satisfy all four of the conditions we require in our base case. First, we prove the subset condition:
- By the inductive assumption, we know $B_{i}$ is not a subset of $B_{j}$ for $2 \leq i<j \leq n+1$.
- By construction, $B_{1}$ is not a subset of $B_{j}$ for $2 \leq j \leq n+2$.
- By construction, $B_{i}$ is not a subset of $B_{n+2}$ for $1 \leq i \leq n+1$.

It follows that $B_{i}$ is not a subset of $B_{j}$ for any $i \neq j$.
Next, we prove the conditions that $\left|B_{i}\right| \neq\left|B_{j}\right|$ for $i \neq j$ and, more generally, that $\left|B_{k}\right|=k$. We have this by construction for $k=1$ and by the inductive hypothesis for $2 \leq k \leq n+2$, so both are satisfied.
Lastly, we observe that $\left|B_{1} \cup B_{2} \cup \cdots \cup B_{n+2}\right|=n+4$, so the final property is satisfied as well.
Combined with the prior base cases for $f(3)$ and $f(4)$, this construction shows by induction that $f(n) \leq n+2$ for all $n \geq 3$. Since we already know from our previous work that $f(n) \geq n+2$, we conclude that $f(n)=n+2$ for $n \geq 3$.