作者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/cn.aspx?n=bbs/Math/M.1633418830.A.B39.html
要证明每个 vector space 都有基底的话，不能使用排除法，不然无法有限多步内完成。
谢谢大家！
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 111.242.238.220 (台湾)
※ 文章网址: https://webptt.com/cn.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