数理逻辑，帮帮忙啊！求大神帮我证明

Question

1. 已经知道某集合S是可数集。证明下面两个命题：
(1) S×S = {(x, y)│x, yÎS}也是可数集
(2) 对于任意的自然数n，Sn = {(x1, x2…,xn)│xiÎS, i=1,2,…n}也是可数集

Answer 1

(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也为可数集。