(1)由于S是可数集,存在S到自然数N的单射.
自然的,存在S×S到N²的单射射g.
接下来我们证明N²是可数集,即存在N²到N的单射f.
可以利用算数基本定理来构造单射f：对于任意大于1的正整数,存在唯一的质因数分解形式.
令f(n,m) = (2^n)*(3^m),n,m ∈ N.
则对任意n,m,r,s ∈N,若f(n,m) = f(r,s),则有(2^n)*(3^m) = (2^r)*(3^s),根据算数基本定理有n = r,m = s.可见f是一个单射.
接下来构造复合映射f∘g:S×S→N,由于f和g都是单射,则f∘g亦为单射.
可见,存在S×S到N的单射,S×S为可数集.
(2)利用(1),用数学归纳法可证：
首先S1 = S为可数集.假设S{n-1}为可数集,注意到Sn = S{n-1}×S,根据(1),Sn也为可数集.