# Proof Wiki: Set of Finite Subsets of Countable Set is Countable/Proof 3

I was looking at this proof on proof wiki: https://proofwiki.org/wiki/Set_of_Finite_Subsets_of_Countable_Set_is_Countable/Proof_3, and line 3 of the proof confuses me:

and $\forall n \ge 0$ $$A^{(n+1)} = \left\{{a^{(n)} \cup a^{(1)}: a^{(n)} \in A^{(n)} \land a^{(1)} \in A^{(1)}}\right\}$$

However, $A^{(n+1)}$ is defined as "the set of subsets of $A$ with no more than $n+1$ elements" as previously stated in that proof. How is the above expression equivalent to this definition?

• In one direction, the union of a set with no more that $n$ elements and a set with no more than $1$ element has no more than $n+1$ elements; in the other direction, a set with no more than $n+1$ elements can be partitioned into two disjoint sets, one with no more that $n$ elements and the other with no more than $1$ element – Henry Mar 12 '18 at 10:35

If $a$ has less than $n+1$ elements then it is as an element of $A^{(n)}$ and we can write $a=a^{(n)}\cup a^{(1)}$ where $a^{(n)}:=a\in A^{(n)}$ and $a^{(1)}:=\varnothing\in A^{(1)}$.
If $a$ has exactly $n+1$ elements then it is not empty. Choosing some $x\in a$ we can write $a=a^{(n)}\cup a^{(1)}$ where $a^{(n)}:=a-\{x\}\in A^{(n)}$ and $a^{(1)}:=\{x\}\in A^{(1)}$.
This together proves that:$$A^{(n+1)}\subseteq\left\{{a^{(n)} \cup a^{(1)}: a^{(n)} \in A^{(n)} \land a^{(1)} \in A^{(1)}}\right\}$$
Conversely if $a=a^{(n)}\cup a^{(1)}$ where $a^{(n)}\in A^{(n)}$ and $a^{(1)}\in A^{(1)}$ then the number of elements of $a$ will not exceed $n+1$ so that $a\in A^{(n+1)}$.
This proves that:$$A^{(n+1)}\supseteq\left\{{a^{(n)} \cup a^{(1)}: a^{(n)} \in A^{(n)} \land a^{(1)} \in A^{(1)}}\right\}$$