UC知道可列不可列？
来源：百度知道 编辑：UC知道 时间：2024/06/17 09:44:25
Suppose that you’re walking on a road and every mile you go you come to
another fork in the road. Suppose the roads go on forever. Consider the
set of all paths (that is, all choices of L or R at every fork; so one path is
LLLLLLL...). Is this set in bijection with (in other words countable) orN
is it in bijection with the interval [0,1] (and therefore uncountable)?
another fork in the road. Suppose the roads go on forever. Consider the
set of all paths (that is, all choices of L or R at every fork; so one path is
LLLLLLL...). Is this set in bijection with (in other words countable) orN
is it in bijection with the interval [0,1] (and therefore uncountable)?
1。不可列
证明：设该集合为S。假设N与S存在一一对应函数f：N->S，
设f(i)=Ai1Ai2Ai3...
其中Aij=L或R
令B=B1B2B3....,其中Bj<>Aij，即当Aij=L，Bj=R；当Aij=R，Bj=L。
则B不同于任何一个f(i),但B又是S中一员，与f是一一对应函数矛盾。
2。与[0，1]能一一对应.
证明：
（1）
[0,1]可与S的一个子集一一对应，对应方法为：
将[0，1]从中间二分为
L=[0，1/2]和
R=（1/2，1]两个子区间，
每个子区间再从中间分为L和R，这么无限循环下去，
任何一个[0，1]中的实数可以“住”进一个子区间，如：
0住LLLLLLL......
......
0.25住LRLLL......
......
0.5住RLLLLLL......
......
1住RRRRRRR......
（2）S可与[0，1]的一个子集一一对应，对应方法为：
LLLLLL......对应0.111111111......
LRRLRRR.....对应0.1221222.......
RRRRRRR......对应0.2222222......
......
（3）然后根据Schröder-Bernstein theorem（http://planetmath.org/encyclopedia/SchroederBernsteinTheorem.html），S可与[0，1]一一对应。
这是希望杯的竞赛题啊？都是英文真难解题！
5555