Re: [代數] 證明集合對應關係

[chun10396974 (娜嗲希摳老公)]

※ 引述《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://www.ptt.cc/bbs/Math/M.1744166550.A.365.html
推 arrenwu     : 什麼東西能夠覆蓋整個 I？
→ chun10396974: Is能夠覆蓋I
→ chun10396974: 例如第一篇文中的I=[8, 15]
→ chun10396974: 而若x=3，則Is=[3, 3×2-1]可以完全覆蓋
→ chun10396974: 若x=2，則Is=[2, 2×2-1]可以完全覆蓋
→ chun10396974: 假如x=3，但是Is只取[3, 4]就會導致I中的10和11找不
→ chun10396974: 到其在Is中的對應者
推 arrenwu     : 你說的是原圖裡面的 (12)？
→ arrenwu     : 能否把你想要證明的結果寫成一個定理的形式？
→ arrenwu     : 你所有的描述都還在自然語言的範疇，非常模糊
→ arrenwu     : 所謂的Is覆蓋 I 是怎麼個覆蓋法？
→ chun10396974: 我描述的不是很清楚，
→ chun10396974: 我想問的是為何只要Interval Is滿足[x, x+1, ..., B
→ chun10396974: x-1]，那就能保證Is符合原圖中的(12)
推 arrenwu     : 那張圖裡面的 C(s,x) 和 C(s,Is) 是啥意思？
C(s, x)指的就是先前您證明的正整數k之對應關係，當前state為x，在收到輸入symbol為s?
※ 編輯: chun10396974 (111.83.75.241 臺灣), 04/11/2025 08:23:38
推 arrenwu     : 你有你原本那張圖的來源嗎？
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
→ chun10396974: C的定義在第八頁的下方
推 arrenwu     : 他這個2014 Jan 6 的版本看起來跟你最原本貼的好像
→ arrenwu     : 有落差了。你方便指出你現在想證明的結論是在Jan 6
→ arrenwu     : 版本的哪部分嗎？
→ chun10396974: 欲證給定第九頁的方程式(9)，只要選取Is=[x, Bx-1]
→ chun10396974: ，必能滿足方程式(10)的關係