【CS】可数集合问题

youarestupidUID: 2123815

70. Let N be the set of all natural numbers. Which of the following sets are countable?
I. The set of all functions from N to {0,1}
II. The set of all functions from {0,1} to N
III. The largest subset of N
(A) None (B) I and II only (C) I and III only (D) II and III only (E) I, II, and III

答案：D
III.N的最大子集就是N，它是可数集合
为什么II是可数集合，而I就不是可数集合呢？请问I和II是怎么判断出来的？我怎么觉得都是可数集合。另外all functions只的是什么sin(0)=0 和 0^2＝0算一个function还是多个？
谢谢！

wjk302UID: 183696

我觉得可以这样来理解：
I    可以理解成N的所有子集构成的集合，是不可数集合
II   其实就是{（X,Y）|X,Y都是natural number}.当然是可数集了

marffinUID: 171144

function from N to {0, 1}怎么理解呢
比如f(x) = x mod 2应该也算吧？那各种各样的函数多了，比如f(x) = 1(x > 10) / 0(x <=  10)，10 可以随便改，所以I应该是错的

但II……达人解释

wjk302UID: 183696

II，从{0,1}到N的function完全由0和1在N中的像决定的啊，即由（f(0),f(1)）完全确定的啊，就是我上面说的那样啊

I，从N到{0,1}的function完全由0和1的原像确定的，而且一旦0的原像确定了，1的原像也就确定了，是0的原像的补集，所以完全由0的原像确定。而0的原像就是N的子集，就是我上面说的那样了。

youarestupidUID: 2123815

I和II不是互为反函数吗？如果II中从{0,1}到N的每个function有一条又向线段表示，那么I中从N到{0,1}的function不就是把II中这些线段反向吗？为什么从从{0,1}到N的function要看N，而从N到{0,1}的function就要看{0,1}呢？

youarestupidUID: 2123815

懂了，感谢wjk302

marffinUID: 171144

不是啊

如果存在f:{0, 1} -> N，那么这肯定是一个函数啦，哪里有把一个函数f的两个变量取值f(0)和f(1)叫成两个函数的呢？
II就是问这样的f有多少个啊