= Solution
Number the <natural numbers> from one. If the <power set> could be enumerated as $A_1,A_2,\ldots$, form $D=\{j:j\notin A_j\}$. For each $j$, membership of $j$ in $D$ is opposite to its membership in $A_j$, so $D\ne A_j$. This contradicts completeness of the enumeration. Thus the <Cantor diagonal argument> proves that the <power set> is an <uncountable set>.
For a finite <subset> $A$, define $b(A)=\sum_{j\in A}2^{j-1}$. This is a nonnegative <integer> and the map is injective: if two finite <subsets> differ, let $k$ be their largest differing element. Its contribution $2^{k-1}$ exceeds the sum $1+2+\cdots+2^{k-2}$ of all smaller possible contributions, so their codes differ. There are infinitely many singleton <subsets>. Hence the <countability of finite subsets of a countable set> here is countable infinitude.
To treat all <bijections>, associate to every <subset> $A\subseteq\mathbb N$ the <permutation> that swaps $2j-1$ and $2j$ when $j\in A$, and fixes both when $j\notin A$. These disjoint pair swaps define a <bijection> of $\mathbb N$. Different <subsets> give different <permutations>, so the map from the <power set> into $X$ is injective. Therefore $X$ is an <uncountable set>.
Every <finitely supported permutation> fixes all elements above some $k$. A <bijection> fixing that tail must permute $\{1,\ldots,k\}$: it cannot send a smaller element into the fixed tail without violating injectivity. There are exactly $k!$ such <permutations>. Thus
$$
Y=\bigcup_{k\geq1}\{\sigma:\sigma(j)=j\text{ for every }j>k\}
$$
is a <countable union> of finite <sets>. Enumerate first by $k$, then by one of the finitely many <permutations> at that $k$; duplicates can be omitted. Infinitely many distinct pair swaps belong to $Y$, so $Y$ is countably infinite. \b[The full family is uncountable, while the finitely supported family is countably infinite.]
Back to article page
