作业帮 > 英语 > 作业

可列不可列?Suppose that you’re walking on a road and every mile y

来源:学生作业帮 编辑:作业帮 分类:英语作业 时间:2024/05/22 13:34:14
可列不可列?
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)?
1.不可列
证明:设该集合为S.假设N与S存在一一对应函数f:N->S,
设f(i)=Ai1Ai2Ai3...
其中Aij=L或R
令B=B1B2B3.,其中BjAij,即当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.
.