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