[其他] 等價類形成分割，為何可以把重疊的類合併

看板Math作者 (God of Computer Science)時間3年前 (2022/01/15 20:06), 編輯推噓5(5推 0噓 49→)
留言54則, 5人參與, 3年前最新討論串1/1
如題，小弟在閱讀等價類可以形成分割的證明的時候，對某個地方有些疑問， 那個地方是這樣的：一般來說我們會 claim 集合 U = union of E[x] for all x in U， 然後說 E[x] 和 E[y] 要嘛互斥要嘛相等，然後 U = union of E[x] for all x in U'， where U' is some subset of U such that E[x] and E[y] are disjoint if x != y， 這裡小弟的疑問是，當我們要去說明那些相同的等價類可以視為同一個類的時候，為何 不需要無限多步，就可以說他們一樣？如果要 claim 一個集合內任意元素相等的話，那 x(1) = x(2), x(2) = x(3), ..., x(n) = x(n+1), ...理應要無限多步的證明才會成立。 會有這個疑問是因為有時候常常用到無限多步而無法成立證明的例子，例如這篇： https://www.ptt.cc/bbs/Math/M.1633418830.A.B39.html 要證明每個 vector space 都有基底的話，不能使用排除法，不然無法有限多步內完成。 謝謝大家！ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.242.238.220 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Math/M.1642248371.A.BC7.html
→
01/16 01:27, 3年前 , 1F
0.0看不懂你在說什麼。假設你的relation 叫E，
01/16 01:27, 1F
→
01/16 01:28, 3年前 , 2F
E[x]:={y\in U | (x,y)\in E}
01/16 01:28, 2F
→
01/16 01:29, 3年前 , 3F
那你的partition就是{P\subset U | P=E[x] for some
01/16 01:29, 3F
→
01/16 01:29, 3年前 , 4F
x \in U}。
01/16 01:29, 4F
→
01/16 01:29, 3年前 , 5F
你可能會去考慮一個quotient set，就是上面那個集合
01/16 01:29, 5F
→
01/16 01:30, 3年前 , 6F
他的元素是U中的一些子集。
01/16 01:30, 6F
→
01/16 01:32, 3年前 , 7F
簡單來說，我想問為什麼文中的 U' 會存在，僅此而已
01/16 01:32, 7F
→
01/16 01:43, 3年前 , 8F
雖然不知道為什麼你會寫成這個樣子，不過應該是有一
01/16 01:43, 8F
→
01/16 01:43, 3年前 , 9F
點關係。如果你承認選擇公理那就找個選擇函數就可以
01/16 01:43, 9F
→
01/16 01:44, 3年前 , 10F
了。vector spaces都有basis的證明也是要選擇公理。
01/16 01:44, 10F
→
01/16 01:44, 3年前 , 11F
不過這邊你也可以考慮U --> partition的surjection
01/16 01:44, 11F
→
01/16 01:45, 3年前 , 12F
要有U'就是要有一個section。不過我不確定是不是不
01/16 01:45, 12F
→
01/16 01:46, 3年前 , 13F
需要條件就可以說明存在一個section。基本上我不認
01/16 01:46, 13F
→
01/16 01:48, 3年前 , 14F
為一般來說是要用U'來表達這件事。不過我想代數領域
01/16 01:48, 14F
→
01/16 01:49, 3年前 , 15F
基本上都會承認選擇公理，有些時候就會需要U'的存在
01/16 01:49, 15F
→
01/16 01:49, 3年前 , 16F
性來寫下某些物件。
01/16 01:49, 16F
→
01/16 01:58, 3年前 , 17F
選擇公理是說無窮多個非空集合之中我可以每個集合都
01/16 01:58, 17F
→
01/16 01:59, 3年前 , 18F
挑出一個元素出來，但我甚至不知道要怎麼把選擇公理
01/16 01:59, 18F
→
01/16 01:59, 3年前 , 19F
套到這邊來。
01/16 01:59, 19F
推
01/16 23:30, 3年前 , 20F
等等, 這裡好像有點雞同鴨講
01/16 23:30, 20F
→
01/16 23:30, 3年前 , 21F
你是想知道怎麼判定由兩個元素各別生成的等價類
01/16 23:30, 21F
→
01/16 23:31, 3年前 , 22F
是互斥或全等「而已」, 還是想知道因此我們可以
01/16 23:31, 22F
→
01/16 23:31, 3年前 , 23F
用一個元素代表一個等價類, 並由此得到 U' 集合?
01/16 23:31, 23F
→
01/16 23:32, 3年前 , 24F
你文中的問題看起來像問前者
01/16 23:32, 24F
→
01/16 23:32, 3年前 , 25F
但你後來又說想知道 U' 怎麼生出來的
01/16 23:32, 25F
推
01/17 00:00, 3年前 , 26F
看起來你是覺得從「for all」開始就有問題了。
01/17 00:00, 26F
→
01/17 10:51, 3年前 , 27F
我想知道 U' 怎麼生出來的，也就是確切造成 disjoi
01/17 10:51, 27F
→
01/17 10:51, 3年前 , 28F
nt union 的集合，這個給定具體例子的時候我做得到
01/17 10:51, 28F
→
01/17 10:51, 3年前 , 29F
，因為就是把 partition 做出來再驗證，可是如果是
01/17 10:51, 29F
→
01/17 10:51, 3年前 , 30F
general case 的話就很難確定
01/17 10:51, 30F
→
01/17 11:26, 3年前 , 31F
如果是用 reduce 的說法，因為無法在有限步內達成，
01/17 11:26, 31F
→
01/17 11:26, 3年前 , 32F
我就不放心。
01/17 11:26, 32F
推
01/17 13:37, 3年前 , 33F
如果是這裡的話那就是 AoC: 給定許多等價類
01/17 13:37, 33F
→
01/17 13:37, 3年前 , 34F
(你應該知道每個等價類各都是一個集合)
01/17 13:37, 34F
→
01/17 13:37, 3年前 , 35F
AoC 表示我們可以在這 (可能無限多個) 等價類中
01/17 13:37, 35F
→
01/17 13:38, 3年前 , 36F
每個集合各挑一個元素出來形成一個集合
01/17 13:38, 36F
→
01/17 13:40, 3年前 , 37F
如果等價類只有有限多個那就是你說的有限多步搞定
01/17 13:40, 37F
→
01/17 13:40, 3年前 , 38F
所以 AoC 只有在無限多個集合時才會用
01/17 13:40, 38F
→
01/17 13:44, 3年前 , 39F
會不踏實的原因可能是因為選擇公理斷言存在的這個U'
01/17 13:44, 39F
→
01/17 13:44, 3年前 , 40F
你寫不出來; 或者反過來說, 你寫不出來的這個 U'
01/17 13:44, 40F
→
01/17 13:44, 3年前 , 41F
被選擇公理斷言存在
01/17 13:44, 41F
推
01/18 17:41, 3年前 , 42F
因為你定義的集合裡包含所有使你給的命題為真的元素
01/18 17:41, 42F
→
01/19 00:58, 3年前 , 43F
LPH66 真是切中要害 我現在就是這樣子的狀態
01/19 00:58, 43F
推
01/20 00:25, 3年前 , 44F
那沒辦法, 選擇公理就是個這樣的東西
01/20 00:25, 44F
→
01/20 00:26, 3年前 , 45F
它斷言一個選擇集合存在, 但在會用到它的狀況時
01/20 00:26, 45F
→
01/20 00:27, 3年前 , 46F
我們基本上寫不出那個集合
01/20 00:27, 46F
→
01/20 02:12, 3年前 , 47F
我後來主要是用集合建構
01/20 02:12, 47F
→
01/20 02:14, 3年前 , 48F
本來就不需要在有限多步之內完成，以無窮聯集與交集
01/20 02:14, 48F
→
01/20 02:14, 3年前 , 49F
為例，說明要從 collection 構建 union 本來就自動
01/20 02:14, 49F
→
01/20 02:15, 3年前 , 50F
只考慮相異的集合。另外加上題目的要求本來就只可能
01/20 02:15, 50F
→
01/20 02:16, 3年前 , 51F
考慮相異的集合 (相同就不可能 disjoint 了吧！)
01/20 02:16, 51F
→
01/20 02:17, 3年前 , 52F
兩大觀點切入，讓我完成了證明的撰寫
01/20 02:17, 52F
→
01/20 02:29, 3年前 , 53F
應該說，聯集就是 OR，交集就是 AND，那就沒有操作
01/20 02:29, 53F
→
01/20 02:29, 3年前 , 54F
步驟的限制了
01/20 02:29, 54F
‣ 更多 alan23273850 的文章
文章代碼(AID): #1XuhYpl7 (Math)