0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Henry Mar 12 '18 at 10:35
0
$\begingroup$

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\}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.