作者chun10396974 (娜嗲希抠老公)
看板Math
标题Re: [代数] 证明集合对应关系
时间Wed Apr 9 10:42:27 2025
※ 引述《arrenwu (最是清楚哇她咩)》之铭言：
: 我下面会分别证明两个命题
: (下面 B 跟 L 我都用大写)
: I = {L, L+1, L+2, ... BL-1}
: 命题1： 如若x > BL-1 , 则存在唯一正整数k 使得 floor(x/B^k) 属於 I
: 命题1的证明相对直观
: 我们可以把比 BL-1 大的正整数们，
: 分成 [LB, LB^2-1], [LB^2, LB^3-1], ...... [LB^k, LB^(k+1)-1] . ....
: 这几个区间，相互之间都没有重叠，
: 所以 x 一定在某个区间 [LB^k, LB^(k+1)-1] 里面
: 而在这个区间里面，因为 LB^k <= x <= LB^(k+1)-1，
: 所以 L <= x/B^k <= LB - 1/B^k，
: floor(x/B^k) 必然在 I 里头
: 命题2： 如果 x < L，
: 并任意给定一个数列 {d[i]}，此数列的任何一项都在 [0, B-1] 中。
: 定义一个新的数列 A[n] ：
: A[0] = x
: A[n+1] = BA[n] +d[n] ,for all n >= 1
: 则存在唯一正整数 k 使得 A[k] 在 I 里头
: (你可能觉得这命题好像被我写得面目全非，
: 但原本写的那个 xB^k + d[1]B^(k-1) + .... + d[k] 其实就是 A[k])
: 首先呢，我们可以看出 A[n+1] - A[n] = (B-1)A[n] + d[n] > 0，
: 数列 A[n] 是个严格递增的数列，
: 所以只要 n 够大，A[n]会超过所有 I 里面的数。
: 但这个数列又有一个性质，就是
: 如果 A[n] < L, 则 A[n+1] <= BL-1
: 也就是说，如果 A[n] 比 I 里面所有的数都小，
: 那 A[n+1] 不可能比 I 里面所有的数都大
: 证明这个也不难， A[n+1] = B*A[n] + d[n]
: <= B*(L-1) + d[n] (A[n] <= L-1)
: <= B*(L-1) + B-1 (d[n] <= B-1)
: <= LB - 1
: 整理下来就是：(1) A[0] = x 比 I 里面的数都小。
: (2) A[n] 比 I里面的数都小的时候，
: A[n+1] 不可能比 I 里面的数都大
: (3) 因为 A[n] 严格地增，
: 所以会有某个 n 使得 A[n] 比 I 里面所有的数都大
: (1),(2),(3) => 存在某个正整数 k 使得 A[k] 落在 I 里面
: 下一步就是证明：
: 如果 L <= A[k] <= LB-1，则 A[k-1] < L 且 A[k+1] > LB-1
想再请教一个问题，为何对於某区间
I={L, L+1, ..., BL-1}
给定一任意x<L，只要选择Is的长度是(B-1)x，亦即Is={x, x+1, ..., Bx-1}
就能确保利用您所证明的正整数k之对应关系，能够覆盖整个I
-----
Sent from JPTT on my Samsung SM-G9980.
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 111.83.75.241 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Math/M.1744166550.A.365.html
1F：推 arrenwu : 什麽东西能够覆盖整个 I？ 04/09 11:53
2F：→ chun10396974: Is能够覆盖I 04/09 13:31
3F：→ chun10396974: 例如第一篇文中的I=[8, 15] 04/09 13:35
4F：→ chun10396974: 而若x=3，则Is=[3, 3×2-1]可以完全覆盖 04/09 13:35
5F：→ chun10396974: 若x=2，则Is=[2, 2×2-1]可以完全覆盖 04/09 13:35
6F：→ chun10396974: 假如x=3，但是Is只取[3, 4]就会导致I中的10和11找不 04/09 13:41
7F：→ chun10396974: 到其在Is中的对应者 04/09 13:41
8F：推 arrenwu : 你说的是原图里面的 (12)？04/10 08:53
9F：→ arrenwu : 能否把你想要证明的结果写成一个定理的形式？04/10 08:53
10F：→ arrenwu : 你所有的描述都还在自然语言的范畴，非常模糊04/10 08:53
11F：→ arrenwu : 所谓的Is覆盖 I 是怎麽个覆盖法？04/10 09:37
12F：→ chun10396974: 我描述的不是很清楚，04/10 11:07
13F：→ chun10396974: 我想问的是为何只要Interval Is满足[x, x+1, ..., B04/10 11:07
14F：→ chun10396974: x-1]，那就能保证Is符合原图中的(12)04/10 11:07
15F：推 arrenwu : 那张图里面的 C(s,x) 和 C(s,Is) 是啥意思？04/10 11:36
C(s, x)指的就是先前您证明的正整数k之对应关系，当前state为x，在收到输入symbol为s?
※ 编辑: chun10396974 (111.83.75.241 台湾), 04/11/2025 08:23:38
16F：推 arrenwu : 你有你原本那张图的来源吗？04/11 10:03
https://arxiv.org/pdf/1311.2540
※ 编辑: chun10396974 (111.83.75.241 台湾), 04/11/2025 10:11:24
※ 编辑: chun10396974 (111.83.75.241 台湾), 04/11/2025 10:14:07
17F：→ chun10396974: C的定义在第八页的下方 04/11 10:14
18F：推 arrenwu : 他这个2014 Jan 6 的版本看起来跟你最原本贴的好像 04/13 11:12
19F：→ arrenwu : 有落差了。你方便指出你现在想证明的结论是在Jan 6 04/13 11:12
20F：→ arrenwu : 版本的哪部分吗？ 04/13 11:12
21F：→ chun10396974: 欲证给定第九页的方程式(9)，只要选取Is=[x, Bx-1] 04/14 17:06
22F：→ chun10396974: ，必能满足方程式(10)的关系 04/14 17:06