为什么能证明?

回复帖子

@御坂10026号 2020-09-16 23:23 回复

RT,这张表为什么能证明有理数可枚举?而且有理数不是无限的吗?

集合元素可枚举 和 集合元素无穷多 不是一个概念。

就像你数数,虽然可以一个一个数下去,但是你数不完。所以正整数无穷多但是可枚举。

@zrzring  2020-09-17 08:47 回复 举报

枚举正有理数可以转化为枚举正整数集合的二元组,但是枚举数对,横着枚举你只能枚举第一行,竖着同理,而斜着枚举完美解决这一问题,于是我们就有了一个枚举的方法,进而证明可枚举(负有理数同理)

@_Mobius_ 2020-09-17 09:32 回复 举报

设 $f(n)$ 为按照题目所给方式枚举 cantor 表,遇到的第 $n$ 个与以前所有数都不同的数。比如 $f(1)=1/1$, $f(2)=1/2$, $f(5)=1/3$(注意不是 $2/2$,因为以前出现过)

那么显然有 $n\ne m\iff f(n)\ne f(m)$,并且 $f(n)$ 会取遍所有的正有理数。所以正整数可以和正有理数一一对应,所以正有理数是可枚举的。

然后设 $g(n)=\begin{cases}0&n=1\\f(n/2)&n>1,n\bmod 2=0\\-f((n-1)/2)&n>1,n\bmod 2=1\end{cases}$

显然也可以类似的证明全体有理数是可枚举的。

@_bzy  2020-09-17 09:53 回复 举报

有理数可列可数大概可理解为有理数可以编号。

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。