作者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/m.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