题目

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

提问时间：2021-02-25

答案

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