集合论基础

• 自反性： In(x, A) <-> In(x,A)，这是重言式，始终为真
• 对称性：即如果集合 A=B 则 B=A， A=B 的描述是： In(x,A)<->I(x,B) 根据逻辑等价关系的性质，交换顺序也是真命题： In(x,B)<->I(x,A), 因此 B=A

• 传递性，即如果集合 A=B，B=C 则 A=C，同样，将其逻辑描述写出来后，逻辑等价是传递性决定了集合等价的传递性。

  这些证明看上去是乏味的，原因在于目前只是把集合的等于关系 "翻译" 到逻辑语言中的，"属于"关系的等价性上。

• E 和 {E} 不同：因为 In(E,{E}) 为真, 但由于空集不包括任何元素，因此 In(E,E) 是恒为假的，于是二者相等的逻辑表征命题为假：

  In(E,E)<->In(E,{E}) # False
  

• 同理可以说明 E 和 {{E}} 不同，E 和 {E,{E}} 不同

• {E} 和 {{E}} 不同，因为：

  In(y,{E})<->y=E
  In(y,{{E}})<->y={E}
  

  由于刚证明 E 和 {E} 不同，所以 In(y,{E}) 无法等价到 In(y,{{E}})

• {{E}} 和 {E,{E}} 不同，因为：

  In(y,{{E}})<->y={E}
  In(y,{E,{E}})<->y={E}|y=E
  

  由于前面证明 {E} 不等于 E, 所以 y={E}|y=E 和 y={E} 不等价，因此属于关系 In(y,{{E}}) 不能等价到 In(y,{E,{E}})

记空集为 E, 用 | 表示集合的并， 那么 A | A = A | E = E | A = A。

.

• 证明 A|A=A ： 对象 x 属于 A|A 等价于 In(x,A)|In(x,A), 而 p|p 等价于 p, 因此这等价于 In(x,A), 根据集合相等定义，可知 A|A=A
• 证明 A|E = A: 对象 x 属于 A|E 等价于 In(x,A)|In(x,E) 为真，但 x 属于空集一定是假，p|False 要为真 , p 必须为真，因此 In(x,A) 为真，因此 A|E = A
• 根据 | 的交换律，可以证明 E|A=A|E, 因此 E|A=A

用 Subeq(A,B) 表示集合 A 是 B 的子集， Sub(A, B) 则表示 A 是 B 的真子集。

• Subeq 的传递性：

  Subeq(A,B) 表明 In(x,A)->In(x,B), Sebeq(B,C) 表明 In(x,B)->In(x,C) 根据蕴含逻辑规则的属性， A->B, B->C 那么 A->C, 所以 In(x,A)->In(x,C), 因此 Subeq(A,C)

• Subeq 的反对称性：

  Subeq(A,B) 表明 In(x,A)->In(x,B), Sebeq(B,A) 表明 In(x,B)->In(x,A) 而这就是 A=B 的定义。

• Sub 的传递性：

  Sub(A,B) 表明 In(x,A)->In(x,B) 且 A!=B, Seb(B,C) 表明 In(x,B)->In(x,C) 且 B!=C, 因此这里有 Subeq(A,C), 我们要证明 A!=C, 由于不相等是没有传递性的，因此不能直接得到。可以用反证法，如果 A=C, 那么根据替换公理 Sub(C,A) 就成立了，而这意味着 C!=A, 导致矛盾，因此 A!=C.

设 A 和 B 是集合，证明命题 Subeq(A, B)、A|B = B 和 A&B = A 三者在逻辑上是等价的

要说明逻辑等价，那么先翻译成逻辑语言：

A(x)[In(x, A)->In(x, B)] # Subeq(A, B)
A(x)[In(x, A|B)<->In(x, B)] # (A|B)=B
A(x)[In(x, A&B)<->In(x, A)] # (A&B)=A

可以把 A(x) 量词拿掉，相当于常说的：给定任意 x, 证明以下三者等价

In(x, A)->In(x, B) # Subeq(A, B)
In(x, A|B)<->In(x, B) # (A|B)=B
In(x, A&B)<->In(x, A) # (A&B)=A

• A|B=B 继续拆成：

  In(x, A|B)->In(x, B) & In(x, A|B)<-In(x, B)
  => (In(x, A)|In(x, B))->In(x, B) & (In(x, A)|In(x, B))<-In(x, B)
  

  后者逻辑上恒为真，因此它等价于 (In(x, A)|In(x, B))->In(x, B)

• 同理， A&B=A 拆成：

  In(x, A&B)->In(x, A) 以及 In(x, A&B)<-In(x, A)
  => (In(x, A)&In(x, B))->In(x, B) & (In(x, A)&In(x, B))<-In(x, B)
  

  前者其逻辑上恒为真，因此它等价于 (In(x, A)&In(x, B))<-In(x, B)

• 定义 p 为 In(x,A), q 为 In(x,B), 那么我们说明的是 p->q, p->(p&q) 以及 (p|q)->q 是等价的。一种做法是列出真值表，另一种是把 p->q 写成等价的 ~p|q. 那么：
  • p->(p&q) 等价于 ~p|(p&q), 根据分配律等价于 (~p|p)&(~p|q) 等价于 ~p|q
  • (p|q)->q 等价于 ~(p|q)|q, 根据德摩根以及分配律这等价于 (~p|q)&(~q|q) 等价于 ~p|q
• 因此三个关系在逻辑展开层面都是等价的。

设 A、B、C 都是集合，令 X 表示包含 A、B、C 作为其子集的集合。那么有：

• (a) A|E=A 以及 A&E=E
  • In(x, A|E) 表示 In(x, A)|In(x,E), 而 In(x,E) 恒为 False, 因此 In(x, A)|In(x,E) 逻辑上等价于 In(x,A), 后者就是表示 x 在集合 A 中，反过来类似。因此 A|E=A
  • In(x, A&E) 表示 In(x, A)&In(x,E), 而 In(x,E) 恒为 False, 因此 In(x, A)&In(x,E) 逻辑上等价于 In(x,E), 后者对应了空集，反过来 In(x,E)->In(x,A&E) 是空推断。因此 A&E=E.
• (b) A|X=X, A&X=A

  • A|X 定义为其元素 x 满足 In(x, A|X) 为真, 它等价于 In(x, A)|In(x, X), 而由于 A 是 X 的子集，因此 In(x,A)->In(x,X), 因此不论 x 属于 A 还是属于 X 都能推出它属于 X 的。

    反过来如果 In(x,X) 为真 那么根据逻辑 or 运算性质，In(x, A)|In(x, X) 为真。 因此 A|X=X 。

  • A&X 定义为其元素 x 满足 In(x, A&X) 为真, 它等价于 In(x, A)&In(x, X), 其逻辑上能推导出 In(x,A) 为真。

    反过来，如果 In(x,A) 为真，由于 A 是 X 的子集表明 In(x,A)->In(x,X) 为真, In(x,A)&In(x,X) 为真，根据交集的定义 In(x,A&X) 也为真。因此 A&X=A 。

• (c) A|A=A, A&A=A
  • A|A 定义为其元素 x 满足 In(x, A|A) 为真, 继而等价于 In(x, A)|In(x, A), 由于逻辑中 ((p|p)<->p), 因此这等价于 In(x,A), 因此 A|A=A
  • A&A 定义为其元素 x 满足 In(x, A&A) 为真, 继而等价于 In(x, A)&In(x, A), 由于逻辑中 ((p&p)<->p), 因此这等价于 In(x,A), . 因此 A&A=A

• (d) 交换律： A|B=B|A, A&B=B&A
  • A|B 定义为其元素 x 满足 In(x, A|B) 为真, 继而等价于 In(x, A)|In(x, B), 由于逻辑中 ((p|q)<->(q|p)), 因此这等价于 In(x,B)|In(x,A). 因此 A|B=B|A
  • A&B 定义为其元素 x 满足 In(x, A&B) 为真, 继而等价于 In(x, A)&In(x, B), 由于逻辑中 ((p&q)<->(q&p)), 因此这等价于 In(x,B)&In(x,A). 因此 A&B=B&A
• (e) 结合律： (A|B)|C=A|(B|C), (A&B)&C=A&(B&C)
  • (A|B)|C 定义为其元素 x 满足 (In(x, A)|In(x, B))|In(x,C), 逻辑上等价于 In(x, A)|(In(x, B)|In(x,C)). 因此 (A|B)|C=A|(B|C)
  • (A&B)&C 定义为其元素 x 满足 (In(x, A)&In(x, B))&In(x,C), 逻辑上等价于 In(x, A)&(In(x, B)&In(x,C)). 因此 (A&B)&C=A&(B|C)
• (f) 分配律： A&(B|C) = (A&B)|(A&C), A|(B&C)=(A|B)&(A|C)
  • A&(B|C) 定义为其元素 x 满足 In(x, A)&(In(x, B)|In(x,C)), 逻辑上， p&(q|r) 真值等价于 (p&q)|(p|r), 因此这等价于 (In(x, A)&(In(x, B))|(In(x, A)&In(x,C)), 也就是 (A&B)|(A&C) 的定义。
  • A|(B&C) 定义为其元素 x 满足 In(x, A)|(In(x, B)&In(x,C)), 逻辑上， p|(q&r) 真值等价于 (p|q)&(p&r), 因此这等价于 (In(x, A)|(In(x, B))&(In(x, A)|In(x,C)), 也就是 (A|B)&(A|C) 的定义。
• (g) A|(X-A)=X, A&(X-A)=E
  • A|(X-A) 定义为其元素 x 满足 In(x, A)|(In(x, X)&~In(x,A)), 也就是 p|(q&~p) 的形式，根据逻辑上的分配关系，这等价于 (p|q)&(p|~p), 而后者恒为真，因此等价于 p|q, 所以相当于元素 x 满足 In(x, A)|In(x, X), 这是 A|X 的定义，根据 (b) 可知它等于 X
  • A&(X-A) 定义为其元素 x 满足 In(x, A)&(In(x, X)&~In(x,A)), 也就是 p&(q&~p) 的形式，这是一个恒为假的命题，只有（唯一的）空集的定义是 In(x,E) 恒为假
• (h) De Morgan 定律： X-(A|B)=(X-A)&(X-B), X-(A&B)=(X-A)|(X-B)
  • X-(A|B) 定义为其元素 x 满足 In(x, X)&~(In(x, A)|In(x,B)), 也就是 p&~(q|r) 的形式，根据逻辑上的德摩根定律，~(q|r) 等价于 ~q&~r, p&~(q&r) 等价于 p&~q&~r. 等价于 (p&~q)&(p&~r), 它对应的是 (X-A)&(X-B) 的定义
  • X-(A&B) 定义为其元素 x 满足 In(x, X)&~(In(x, A)&In(x,B)), 也就是 p&~(q&r) 的形式，根据逻辑上的德摩根定律，~(q&r) 等价于 ~q|~r, p&~(q&r) 等价于 p&(~q|~r). 根据逻辑上 or 和 and 的分配率，它等价于 (p&~q)|(p&~r), 它对应的是 (X-A)|(X-B) 的定义

这里充分反应出集合论和基本的命题逻辑运算的同构性，所以集合的这些关系基本就是把集合以及集合所在元素套到 In(x,A) 关系里，然后用命题逻辑里的 | & -> 重新复述一遍。

这是 3.1.5 的延续，继续证明交并集合的包含关系，实际有六条，也都是对偶性质的， 证明时把集合语言翻译成底层的命题语言

• Subeq(A&B, A）：根据定义 A&B 意味着 In(x,A)&In(x,B) 为真，逻辑上能够蕴含 In(x,A), 也就是 In(x,A)&In(x,B)->In(x,A) 为真，这就是 Subeq(A&B, A）的定义。
• Subeq(A&B, B）：根据定义 A&B 意味着 In(x,A)&In(x,B) 为真，逻辑上能够蕴含 In(x,B), 也就是 In(x,A)&In(x,B)->In(x,B) 为真，这就是 Subeq(A&B, B）的定义。

• Subeq(C, A&B) ：Subeq(C, A)&Subeq(C, B) 定义为元素 x 满足 (In(x,C)->In(x,A))&(In(x,C)->In(x,B)), 也就是 (p->q)&(p->r) 形式，由于 p->q 等价于 ~p|q, 因此 (p->q)&(p->r) 可以写成 (~p|q)&(~p|r), 这其实是对 ~p|(q&r) 的分配展开结果，而 ~p|(q&r) 又等价于 p->(q&r), 也就是 In(x,C)->In(x,A)&In(x,B), 根据交集的定义，In(x,A)&In(x,B) 等价于 In(x,A&B), 因此最终 x 满足 In(x,C)->In(x,A&B), 而这是 Subeq(C, A&B) 的定义。

  因此 Subeq(C, A)&Subeq(C, B) 当且仅当 Subeq(C, A&B)

• Subeq(A, A|B）：根据定义 A|B 意味着 In(x,A)|In(x,B) 为真，In(x,A) 逻辑上能够蕴含该命题, 也就是 In(x,A)->In(x,A)|In(x,B) 为真，这就是 Subeq(A, A|B）的定义。
• Subeq(B, A|B）：根据定义 A|B 意味着 In(x,A)|In(x,B) 为真，In(x,B) 逻辑上能够蕴含该命题, 也就是 In(x,B)->In(x,A)|In(x,B) 为真，这就是 Subeq(B, A|B）的定义。

• Subeq(A, C)&Subeq(B, C) 定义为元素 x 满足 (In(x,A)->In(x,C))&(In(x,B)->In(x,C)), 也就是 (p->r)&(q->r) 形式，由于 p->q 等价于 ~p|q, 因此 (p->r)&(q->r) 可以写成 (~p|r)&(~q|r), 这其实是对 (~p&~q)|r 的分配展开结果，而它又等价于 ~(p|q)|r, 继而等基于 (p|q)->r, 也就是 (In(x,A)|I(x,B))->In(x,C), 根据并集的定义，In(x,A)|In(x,B) 等价于 In(x,A|B), 因此最终 x 满足 In(x,A|B)->In(x,C), 而这是 Subeq(A|B, C) 的定义。

  因此 Subeq(A, C)&Subeq(B, C) 当且仅当 Subeq(A|B, C)

assert A & (A | B) == A
assert A | (A & B) == (A & B) | A == A

• 由于 3.1.7 中证明 A 是 A|B 的子集，根据命题 3.1.28 (b) 中 A&X=A 可知 A&(A|B)=A
• 由于 3.1.7 中证明 A&B 是 A 的子集，根据命题 3.1.28(e)的交换律以及 (f) 中 A|X=X 可知： A|(A&B)=(A&B)|A=A

假如 A|B=X, A&B=E, 那么 A=X-B, B=X-A, 这里体现了两个互补集合的关系。

注意在命题 3.1.28 (g) 中有 A|(X-A)=X, A&(X-A)=E, 如果把 X-A 替换成 B 就很接近。 但这只能说明给定 B=X-A 能够得到 A|B=X, A&B=E, 而本题是证明其反方向。

根据命题 3.1.28 (h) 中，我们有：

X-(A|B)=(X-A)&(X-B), X-(A&B)=(X-A)|(X-B)

但把本题的前提代入，只能得到 (X-A)&(X-B)=E, (X-A)|(X-B)=X, 这看上去和前提是对偶的， 但同样无法直接说明 A=X-B.

因此还是要编译到逻辑语言层面来论述：

• 定义 p,q,r 分别为 In(x,A), In(x,B), In(x,X)
• A&B=E 意味着 In(x,A)&In(x,B) 恒为假，后者写成 p&q ，那么 ~(p&q) 为真，也就是 ~p|~q 为真，等价于 p->~q, 即 In(x,A)->~In(x,B).
• 另一方面，根据练习 3.1.7, A 是 A|B 的子集，而 A|B=X, 这说明 A 是 X 的子集， 所以有 In(x,A)->In(x,X), 结合 In(x,A)->~In(x,B), 就得到如果 x 在集合 A 中， 那么 x 在 X 且 x 不在 B 中，后者是 X-B 的定义，因此 In(x,A)->In(x,X-B)

• 前文提到，根据命题 3.1.28 可以有 (X-A)&(X-B)=E, (X-A)|(X-B)=X, 那么套用以上两个步骤相同的思路，可以得到 In(x,X-B)->In(x,X-(X-A))

  而 X-(X-A) 根据定义可以写成 r&~(r&~p) 的形式，等价于 r&(~r|p) 等价于 r&p, 由于 A 是 X 的子集，那么 p->r, 等价于 ~p|r, 结合 r&p，真值表上等价于 p, 因此 X-(X-A)=A

  所以有 In(x,X-B)->In(x,A), 于是我们有等价关系 In(x,A)<->In(x,X-B) 这是 A=X-B 的定义。

• 同理，把 A B 互换可以证明 B=X-A

A-B, A&B, B-A 是互不相交，且它们的并集是 A|B

这里仍然是规约到命题逻辑：

• 定义 p,q 为 In(x,A) 和 In(x, B)
• 那么 A-B ，A&B, B-A 对应的命题是 p&(~q), p&q, q&(~p)
• 它们两辆之间的并联关系： p&(~q)&p&q, p&(~q)&q&(~p) 和 p&q&q&(~p) 都是 False. 因此它们的并集都是空集，所以它们互不相交
• 三个命题进行或运算，(p&(~q))|(p&q)|(q&(~p))
  • 一种做法是求真值表，可以看到它和 p|q 等价
  • 另一种是形式上化简，稍微复杂，但也能得到 p|q

将替代公理：

In(z, {y: P(x,y) & In(x, A)})<->E(x)[In(x, A)&P(x,z)]

的 P(x,y) 改成 (y=x)&P(x)，P(x) 为分离公理中的过滤性命题，因此分离公理的逻辑描述就是：

E(x)[In(x, A)&(z=x)&P(x)]

该命题要成立的话，要满足 P(x) 并且 z 就是 x, 这就是分离公理的语义。

• 公理 3.8 蕴含公理 3.2, 只要设置 P(x) 恒为假，因此没有任何对象能在集合中，即构建了空集

• 公理 3.8 蕴含公理 3.3，只要设置 P(x) 表示的是 x=a，可以构建一个只有对象 a 的集合 {a}

  对于双元素集合，设置 P(x) 为 x=a 或 x=b, 可以构建 {a,b}

• 公理 3.8 蕴含公理 3.4，对于两个集合 A,B，P(x) 表示 In(x,A)|In(x,B) ，因此可以将两个集合并起来。
• 公理 3.8 蕴含公理 3.5，此时对于集合 A, P(x)表示 In(x,A)&Q(x)，这里 Q(x) 表示公理 3.5 中的性质 P(x)。
• 公理 3.8 蕴含公理 3.6，此时对于集合 A, P(x) 表示 In(x,A)&Q(x,y) ,这里 Q(x,y) 对应公理 3.6 中的 P(x,y)
• 公理 3.8 蕴含公理 3.7，这里 P(x) 表示 x 是满足 Peano 公理的对象。

正则公理说明集合不能包含自身（去除自引用）且两个集合不能互相引用

• 正则公理说明集合不能包含自身（去除自引用）
  • 对于空集， ~In(E,E) 是恒为真的，因此空集不能包含自身
  • 对于非空集合，如果存在自引用，即 In(A,A), 那么根据公理 3.3, 存在一个集合 {A}, 但是 该集合不满足正则公理，因为其唯一元素 A 是集合且与其自身相交，因为它们都包括集合 A. 导致了矛盾
  • 所以 A 包含 A 是不可能的
• 正则公理说明两个集合不能互相引用（去除互递归）
  • 如果 A B 都是集合，并且 A 和 B 互相引用
  • 那么根据公理 3.3 可以构造一个包含两个元素的集合 {A,B}, 对于其内部对象 A 它包含了 B, 因此 A 和 {A,B} 是相交的，同理 B 和 {A,B} 也相交，A,B 又都是集合，因此违法了正则公理，导致矛盾
  • 所以 A 包含 B, 同时 B 包含 A 是不可能的

概括公理等价于存在一个包含一切的集合

• 如果概括公理成立，则只需要令 P(x)=True 就构造出一个包含一切对象的集合。
• 如果存在包含所有对象的集合，那么根据分离公理就可以得到概括公理。

所以概括公理和"存在包含一切对象集合" 这个命题（或公理）是等价的

函数相等复合自反性、对称性、传递性和替换性质

• 函数相等符合自反性： f=f
  • 根据函数定义，f 的 domain 和 range 与自身都相等，这来自于集合相等的自反性
  • 给定任意 x: f(x)=f(x), 这来自于对象相等的自反性
• 函数相等符合对称性： f=g 则 g=f
  • 根据函数定义，g 和 f 的 domain 和 range 都相等，这来自于集合相等的对称性
  • 给定任意 x: f(x)=g(x) 等价于 g(x)=f(x), 这来自于对象相等的对称性
• 函数相等符合传递性： f=g, g=h 则 f=h
  • 根据函数定义，f 和 g 的 domain 和 range 都相等，g 和 h 的 domain 和 range 都相等，根据集合相等关系的传递性， f 和 h 的 domain 和 range 都相等。
  • 给定任意 x: f(x)=g(x)=h(x), 因此 f(x)=h(x), 这来自于对象相等的传递性。

如果 f, f':X -> Y and g, g': Y -> Z 函数满足 f = f' and g = g', 那么 g|f = g'|f':

• 根据前提 g|f 和 g'|f' 都是 X->Z 上的函数，因此 domain 和 range 都相等

• 给定任意 x, 由于 f=f', 根据函数相等定义，f'(x)=f(x), 而根据函数的定义中映射的唯一性有：

  • g(f'(x)) = g(f(x))
  • g'(f'(x)) = g'(f(x))

  由于 g=g', 根据函数相等定义 g(f(x))=g'(f(x)), 从而以上两个式子中等式左右的对象都相等，因此有：

  • g|f = g'|f' = g|f' = g'f
• 所以 g|f = g'|f'

函数 f : X -> Y 和 g : Y -> Z ，它们的复合是 g|f: X->Z

• 如果 f 和 g 都是单射，那么 g|f 是单射：

  假设 x 和 x' 是 X 集合里的元素，根据 f 的单射定义： 如果 x!=x', 那么 f(x)!=f(x'), 且它们都属于集合 Y, 再根据 g 的单射定义有 g(f(x))!=g(f(x')), 因此 g|f 是单射

• 如果 f 和 g 都是满射，那么 g|f 是满射：

  对于任意 Z 集合中的元素 z ，根据 g 的满射定义：Y 集合存在一个元素 y，满足 g(y)=z, 根据 f 的满射定义，X 集合中存在一个元素 x, 满足 f(x)=y， 合起来就是 z=g(f(x))=(g|f)(x), 因此 g|f 是满射。

以上两个性质蕴含了如果 f 和 g 都是双射，那么 g|f 是双射

空函数始终是单射的，如果空函数的值域也是空集，那么它是满射，同时是双射

对于空函数 f: E->Y,

• 单射对应的是逻辑命题 x!=x'->f(x)!=f(x') 为真，由于空函数定义域为空，找不到 x 和 x' 元素，因此这是一个恒为真的空推断。所以空函数为单射

• 满射的定义是 In(y,Y)->E(x)P(x,y)

  由于空集里的存在性命题恒为假，因此 E(x)P(x,y) 恒为假，要保证 p->False 为真， p 就必须为假，而 In(y,Y) 恒为假意味着 Y 是空集，因此只有值域是空集的空函数是满射。

• 当 Y 是空集的时候，空函数也是双射了。

f:X->Y, f':X ->Y, g:Y ->Z, and g':Y -> Z 都是函数

• 如果 g|f=g|f' 并且 g 是单射，那么 f=f'

  用反证法：如果 f!=f', 那么存在一个 x 使得 f(x)!=f'(x), 这两个都是 Y 中的元素， 由于 g 是单射，那么 g(f(x))!=g(f'(x)), 所以 (g|f)!=(g|f') 与前提矛盾了。所以 f=f' 。

  直觉解释是，如果第二阶段的映射不是单射，比如输入 y1,y2 都输出 z, 那么对同一个 x, f 可以映射到 y1, f' 映射到 y2 从而保证 g|f 和 g|f' 还是相等。更极端的例子是 g 是一个常数函数： g(y)=1, 那么 f 和 f' 可以是任意不相同的函数。

• 如果 g|f=g'|f 并且 f 是满射，那么 g=g'

  用反证法： 如果 g!=g'，那么说明存在一个 Y 集合里的元素 y, g(y)!=g'(y),f 是 满射意味着，元素 y 有一个 X 集中的对应元素 x 满足 y = f(x). 这说明存在一个元素 x, 使得 g(f(x))!=g'(f(x)), 与前提矛盾。因此 g=g'

  如果 f 不是满射呢？这意味着复合映射中间阶段的 Y 集合有些元素可以没有对应的 x, 那么 g 和 g' 可以只是部分相同的函数，比如 g(y)=y 和 g'(y)=|y|, 对于 g(y), 输入小于 0 的部分没有对应的 x

• 如果 g|f 是单射，那么 f 也是单射
• 如果 g|f 是满射，那么 g 也是满射

.

f : X -> Y and g : Y -> Z 都是函数.

• 如果 g|f 是单射，那么 f 也是单射吗？

  是的，用反证法，如果 f 不是单射，意味着存在两个不同的元素 x!=x' 经过 f 映射后结果相同 f(x)=f(x'), 那么再经过 g 映射， g(f(x))=g(f(x')), 这与 g|f 是单射矛盾。

• 如果 g|f 是单射，是否 g 也要是单射？

  g 不需要是单射，因为经过 f 的映射，输入 g 的元素可以不用完全覆盖集合 Y.

  比如假设 g(1)=1 且 g(2)=1, 那么 g 就不是单射，但 f(x)=1 且 X={1}, 这样 y=2 永远不会取到，因此 g|f 变成了从 {1} 到 {1} 的单射。

• 如果 g|f 是满射，那么 g 也是满射吗？

  是的，用反证法，如果 g 不是满射，那么存在一个集合 Z 里的元素 z 它没有对应的 y 使得 g(y)=z, 从而也不会有对应的 X 中的元素 x 使得 z=g(f(x)), 这与 g|f 是满射矛盾。

• 如果 g|f 是满射，那么 f 也是满射吗？

  f 不需要是满射，比如 f(x)=1, 集合 Y={1,2} 而 g(y)=1, 集合 Z={1}.

f : X -> Y 是双射函数, 其逆记为 ~f: Y -> X

• 证明消去律 1：对于任意 X 中的元素 x, ~f(f(x))=x

  首先逆 ~f 的定义是，对于所有 Y 集合中元素 y 存在唯一的 X 中元素 x 使得 f(x)=y, 这个 x 记为 ~f(y)

  • "对于所有 y 存在" 来自于 f 的满射性质
  • "存在唯一的 x" 来自于 f 的单射性质

  f 双射的定义是，对于所有 X 集合中元素 x 存在唯一的 Y 中元素 y 使得 y=f(x).

  因此给定 x, y=f(x), 因为 ~f 是良好的函数，根据替换公理有 ~f(f(x))=~f(y), 根据 ~f 定义这里 ~f(y) 就是 x, 所以 ~f(f(x))=x

• 证明消去律 2：对于任意 Y 中的元素 Y, f(~f(y))=y

  给定任意 Y 中元素 y, 存在唯一的 x 满足 f(x)=y, 这个 x 记为 ~f(y), 也就是 x=~f(y)，根据替代公理有 f(x)=f(~f(y))=y

• 证明 ~f 也是可逆的，并且它的逆 ~~f=f

  根据定义，~f 是一个有效的 Y->X 上的函数。

  因此它的逆的描述就是： 对于所有 X 中的元素 x, 存在唯一的 Y 中元素 y 满足 ~f(y)=x. 此时 y 的值被记为 ~~f(x), 将 ~~f 是 X 到 Y 的函数，记作 ~f 的逆。

  但这个描述和 f 的定义完全一样，对于所有 x ，f(x) 都和 ~~f(x) 一样，所以 ~~f=f

f: X-> Y 和 g: Y-> Z 都是双射， g|f 也是双射， g|f 的逆是 ~f|~g

• g|f 也是双射： 证明见练习 3.3.2

• g|f 的逆是 ~f|~g

  首先， g|f 的逆记为 ~(g|f), 它满足对于任意 Z 中元素 z, 都有 ~(g|f)(z)=x

  同时满足，(g|f)(x)=g(f(x))=z, 我们记 f(x) 为 y. 那么由于 f 的双射性质， x=~f(y), 由于 g 的双射性质， y=~g(z)

  因此 (~f|~g)(z)=~f(~g(z))=~f(y)=x

  也就是说对于任意 z, (~f|~g)(z)=x=~(g|f)(z)

  这意味着 ~f|~g 和 g|f 是相等的。

X 是 Y 的子集，Y 又是 Z 的子集，定义 I1（原文里用 \( \iota_{X\to Y} \) 表示) 是从 X 集合到 Y 集合的恒等映射或包含映射，其定义为 I(x)=x, I2 表示 Y 到 Z 的恒等映射。

1. 证明 I2|I1 是从 X 到 Z 的恒等映射 给定任意 X 中元素 x, (I2|I1)(x) = I2(I1(x)) = I2(x) = x

   而 I2|I1 的 domain 和 range 分别是 X 和 Z, 且由于子集关系， I1(x) 在 Y 中，I2(x) 在 Z 中，因此 I2|I1 是定义良好的函数，并且符合恒等映射定义

2. f 是 A->B 上的任意函数，证明 f=f|I, f=I|f

   • 先证明 f=f|I, 这里 I 是从 A 到 A 的恒等映射

     对任意 A 中元素 a, (f|I)(a)=f(I(a))=f(a), 因此 f|I=f

     其中 I(a) 是集合 A 中元素，在 f 的 domian 中，因此以上过程是有效的。

   • 再证明 f=I|f, 这里 I 是从 B 到 B 的恒等映射

     对任意 A 中元素 a, (I|f)(a)=I(f(a))=f(a), 因此 I|f=f

     其中 f(a) 是集合 B 中元素，在 I 的 domian 中，因此以上过程是有效的。

3. f 是 A-> B 上双射函数，那么：

   • f|~f = I, I 是 B 到 B 上的映射

     根据练习 3.3.6，给定任意 B 中元素 b， f(~f(b))=b, 也就是 (f|~f)(b)=b ,这满足恒等映射定义，所以 f|~f=I

   • ~f|f = I, I 是 A 到 A 上的映射

     根据练习 3.3.6，给定任意 A 中元素 A， ~f(f(a))=a, 也就是 (~f|f)(a)=a ,这满足恒等映射定义，所以 ~f|f=I

4. 如果 X 和 Y 不相交，且 f :X->Z 和 g:Y -> Z 都是函数，证明存在一个唯一的函数 h:(X|Y)->Z, 使得 h 同时满足以下两个性质：

   • h|I=f, I 是从 X 到 X|Y 的恒等映射

     构造 h 为：对于在 X|Y 集合中的任意元素 w, 如果 In(w,X) 那么其结果 h(w)=f(w), 如果 In(w,Y), 那么其结果 h(w)=g(w), 由于 X 和 Y 不相交，因此 In(w,X) 和 In(w,Y) 不会同时成立，因此以上定义是良好的。

     此时对于任意 X 中元素 x, (h|I)(x)=h(I(x))=f(x), 因此 h|I=f, 根据练习 3.1.7 可知，X 是 X|Y 的子集，因此 I 的定义是良好的

   • h|I=g, I 是从 Y 到 X|Y 的恒等映射

     对于任意 Y 中元素 y, (h|I)(y)=h(I(y))=g(y), 因此 h|I=g, 根据练习 3.1.7 可知，Y 是 X|Y 的子集，因此 I 的定义是良好的

   • 唯一性说明：

     如果如果存在另一个 h'(x)同样满足以上性质，那么根据 h'|I=f 和 h'|I=g 的性质可以知道，当输入是 X 中元素时，h'(x)=f(x)=h(x), 当输入是 Y 中元素时，h'(y)=g(y)=h(y), 所以 h'=h.

f:X->Y 是双射函数，并且 ~f 是它的逆， V 是 Y 的一个子集

证明 V 在 ~f 下的象等于 V 在 f 下的逆象，可以统一用 ~f(V) 表示

• 这里要证明的是两个集合相等，先写出这两个集合的定义：

  根据定义 V 在 ~f 下的象 A={~f(y):In(y, V)}, V 在 f 下的逆象 B={In(x,X):In(f(x), V)}

• 那么对任意在 A 集合中的元素 a, 它都有一个在 V 中的元素 y 使得 a=~f(y), 那么根据逆的定义我们知道 a 是在 X 集合中。 根据替代公理有： f(a)=f(~f(y)), 根据练习 3.3.6, 可知等式右侧就是 y, 因此 f(a)=y 也就是说 f(a) 是在集合 V 中，因此命题 In(a,X)&I(f(a),V) 为真，而这就是集合 B 中元素的定义，这证明了在 A 中的元素也在 B 中。
• 那么对任意在 B 集合中的元素 b, 它满足 In(f(b),V), 而由于 f 是双射，因此 V 中只有唯一的元素 y 符合 y=f(b), 根据替代公理有： ~f(y)=~f(f(b)), 根据练习 3.3.6 可知等式右侧是 b, 因此 ~f(y)=b, 这符合集合 A 元素的定义，因此任意在 B 中的元素都在 A 中。
• 所以 A=B, 可以用 ~f(V) 统一表示

f:X->Y 是函数， S 是 X 的子集，U 是 Y 的子集，那么，一般情况下， 即 f 不是单射也不是满射时：

• S 是 ~f(f(S)) 的子集
• f(~f(U)) 是 U 的子集

在练习 3.3.7 中讨论了函数和逆函数复合后的关系，即 ~f(f(x))=x, f(~f(y))=y 。 类似的，本练习则是象与逆象的复合关系。

证明之前，我们先将目标集合"编译"成逻辑语言，以便之后在逻辑上进行论证：

1. f(S) 的编译：

   对任意 f(S) 中的元素 y, 满足 E(x)[f(x)=y&In(x,S)]

2. ~f(U) 的编译：

   对任意 ~f(U) 中的元素 x, 满足 In(x,X)&In(f(x), U)

3. ~f(f(S)) 的编译：

   对任意 ~f(f(S)) 中的元素 x, 满足 In(x,X)&In(f(x), f(S))

   而根据编译 1, 命题 In(f(x), f(S)) 可以重写为 E(z)[f(z)=f(x)&In(z,S)], 这里我们用 z 替代了存在量词里变量 x, 以避免冲突。

   因此，对任意 ~f(f(S)) 中的元素 x, 满足：

   In(x,X)&E(z)[f(z)=f(x)&In(z,S)]

4. f(~f(U)) 的编译：

   对任意 f(~f(U)) 中的元素 y, 满足 E(x)[f(x)=y&In(x,~f(U))], 注意这里量词变量 又用 x 替换了，因为不会有冲突。

   而根据编译 2, In(x,~f(U)) 等价于 In(x,X)&In(f(x), U)

   因此对任意 f(~f(U)) 中的元素 y, 满足：

   E(x)[f(x)=y&In(x,X)&In(f(x), U)],

   根据等号替换规则，这继续等价于

   E(x)[f(x)=y&In(x,X)&In(y, U)]

   注意最后一个表达式没有量词限制的变量 x, 所以它可以直接取出来，因此等价于

   E(x)[f(x)=y&In(x,X)]&In(y, U)

现在可以讨论关系了：

• ~f(f(S)) 和 S 的一般关系：

  x 满足 In(x,X)&E(z)[f(z)=f(x)&In(z,S)] 是否能蕴含 In(x, S), 看上去不行， 因为如果 x 在 X-S 中，但 S 中存在一个 z 使得 f(z)=f(x) 是完全可能的，因为 函数允许多对一。

  反过来，如果 In(x, S) ，由于 S 是 X 子集，那么 In(x, X) 成立，同时只要 z 就选择 x 本身，就能满足 f(z)=f(x).

  因此 S 是 ~f(f(S)) 的子集。

• f(~f(U)) 和 U 的一般关系

  如果 y 满足 E(x)[f(x)=y&In(x,X)]&In(y, U), 那么自然的满足 In(y,U), 因为 p&q 蕴含 q, 但反过来 q 无法推出 p&q

  所以 f(~f(U)) 是 U 的子集

A, B 是 X 的子集，f:X->Y 是一个函数

1. 证明 Subeq(f(A&B), f(A)&f(B))

   在 f(A&B) 中的元素 y 满足 E(x)[f(x)=y&In(x,A)&In(x,B)]

   在 f(A)&f(B) 的元素 y' 满足 E(x)[f(x)=y'&In(x,A)]&E(x)[f(x)=y'&In(x,B)]

   前一个命题是蕴含后一个命题的，因为逻辑上：

   E(x)[P(x)&Q(x)&R(x)] 蕴含 E(x)[P(x)&Q(x)]&E(x)[P(x)&R(x)]

   注意其反过来是不一定成立的，所以 f(A&B) 是 f(A)&f(B) 的子集，但不等于 f(A)&f(B)

2. 证明 Subeq(f(A)-f(B), f(A-B))

   在 f(A)-f(B) 中的元素 y 满足 E(x)[f(x)=y&In(x,A)&In(x,B)]

   在 f(A-B) 的元素 y' 满足 E(x)[f(x)=y'&In(x,A)]&E(x)[f(x)=y'&In(x,B)]

   f(A)\f(B)的定义是\({x \in {f(a): a\in A }: x\not \in {f(b): b\in B }}\),对于其中的任意元素 z，都存在一个元素 y，满足 f(y) = z,且\(y\in A\),且此时 y 不在 B 中，因为如果 y 在 B 中，那么 f(y)就会在集合{f(b): b$∈$B}中,而 z 也会在这个集合中，与前提矛盾。因此换个写法，\(z\in \{f(y) = z : y \in A , y\not \in B\}\).而这个集合就是 f(A\B) 反过来不一定成立，例如 A = (-1,0},B = {0,-1},\(f(x) = x^2\),此时 f(A)\f(B)=\(\emptyset\)，但是 f(A\B) = {1}

3. 证明\(f(A \cup B) = f(A) \cup f(B)\)。先证明\(f(A \cup B) \subseteq f(A) \cup f(B)\)，对于任意 z\(\in\){\(f(x): x\in A\) or \(x \in B\)},存在一个元素 x，f(x) = z,且 x 至少在 A 和 B 之中，分两种情况，如果 x 在 A 中，那么\(z\in \{f(x): x\in A\}\),根据集合公理 3.4(\(x\in A\cup B \Leftrightarrow X \in A\) or \(x \in B\))可以得到\(z\in f(A) \cup f(B)\),同理，如果 x 在 B 中也得到同样结论，因此\(f(A \cup B) \subseteq f(A) \cup f(B)\).再证明\(f(A) \cup f(B) \subseteq f(A \cup B)\),分两种情况，如果 z\(\in f(A)\),那么 z$∈ ${\(f(x): x\in A\)},这可以得到 z$∈ ${\(f(x): x\in A\) or \(x\in B\)},因此可以得到 z 在集合 f(A$∪$B)中。同理另一种情况也得到一样的结论，所以\(f(A) \cup f(B) \subseteq f(A \cup B)\)

f:X->Y 是函数, U,V 是 Y 的子集。

• ~f(U|V)=~f(U)|~(V)

  在 ~f(U|V) 中的元素 x 满足命题 In(x, X)&(In(f(x),U)|In(f(x),V))

  根据分配律，有 (In(x, X)&In(f(x),U)|(In(x, X)&In(f(x),V))

  这就是 ~f(U)|~(V) 的定义，因此二者逻辑上等价。

• ~f(U&V)=~f(U)&~(V)

  在 ~f(U&V) 中的元素 x 满足命题 In(x, X)&(In(f(x),U)&In(f(x),V))

  它等价于 (In(x, X)&In(f(x),U)&(In(x, X)&In(f(x),V))

  这就是 ~f(U)&~(V) 的定义，因此二者逻辑上等价。

• ~f(U-V)=~f(U)-~(V)

  在 ~f(U-V) 中的元素 x 满足命题 In(x, X)&(In(f(x),U)&~In(f(x),V))

  它等价于 (In(x, X)&In(f(x),U)&(In(x, X)&~In(f(x),V))

  这就是 ~f(U)-~(V) 的定义，因此二者逻辑上等价。

f:X->Y 是函数，S 是 X 的子集， U 是 Y 的子集

• 练习 3.4.2 已经证明，一般情况下， S 是 ~f(f(S)) 的子集

  而对任意在 ~f(f(S)) 集合的元素 x ，要满足命题 In(x,X)&E(z)[f(z)=f(x)&In(z,S)]

  该命题在一般情况下无法蕴含 In(x, S), 因为如果 x 在 X-S 中，但 S 中存在令一个 z 使得 f(z)=f(x), 那么该命题仍然为真，而此时 x 并不在 S 中。

  然而，如果对于任意 x ， E(z)[f(z)=f(x)&In(z,S)] 都能蕴含 In(x, S), 那么这意味着不可能存在一个不同于 x 的 z 使得 f(z)=f(x), 因为一旦出现这种情况， 就能够用 S 把 x 和 z 划分开， z 在 S 中而 x 在 S 之外，导致 In(x, S) 不成立。

  所以 f 必须是 X->Y 的单射函数。（因为我们在讨论任意 S 都满足 ~f(f(S))=S）

  反过来如果 f 是单射，根据定义如果 f(z)=f(x), 则 z=x, 所以 E(z)[f(z)=f(x)&In(z,S)] 为真的话 In(x, S) 就为真，因此 ~f(f(S)) 是 S 的子集。

  所以 ~f(f(S))=S 的充要条件是 f 为单射

• 练习 3.4.2 已经证明，一般情况下， f(~f(U)) 是 U 的子集

  对任意在 f(~f(U)) 中的元素 y, 要满足 E(x)[f(x)=y&In(x,X)]&In(y, U)

  它可以推导出 In(y, U), 但它要能被 In(y,U) 推导， E(x)[f(x)=y&In(x,X)] 必然恒为 True, 而这要求 f 在 X->U 上是满射，由于我们讨论的是任意集合 U, 因此它可能覆盖 Y 的所有元素，所以 f 在 X->Y 上也是满射。

  而如果 f 是满射，那么对任意 y 都有 E(x)[f(x)=y&In(x,X)], 因此 E(x)[f(x)=y&In(x,X)]&In(y, U) 等价于 In(y, U).

  所以 f(~f(U))=U 的充要条件是 f 为满射。

• 根据幂集公理，对于任意集合 X 都可以构建一个集合 F = {0,1}^X, 它包含了从集合 X 到 {0,1} 上的所有函数。
• 根据替换公理，对 F 中所有元素，都可以进行一个操作，即取 {1} 在该函数上的逆象，记为 S = {~f({1}): In(f,F)}, 这是一个高阶函数的操作。
• 证明 S 是 P 的子集：对于任意在 S 中的元素 s, 它是 {1} 的一个逆象，根据逆象定义，它是 X 上的子集，因此它是 P 中的元素。
• 证明 P 是 S 的子集, 对于任意在 P 中的元素 p, 它是 X 的一个子集，那么我们可以构造一个函数 g, 对于任意在 p 中的元素 x 满足 g(x)=1 不在 p 中的元素 x 满足 g(x)=0, 根据练习 3.3.8 对恒等映射的说明，我们知道这个函数 g 是定义良好且唯一的，而该函数是从 X->{0,1} 的函数，即 g 属于 F，因此 S 中存在集合 {1} 在 g 上的逆象。因此 p 属于 S, 即 P 是 S 的子集。
• 由于 S 和 P 互为子集，所有 S=P, 因此 P 是一个幂集。

这是通过二进制构造幂集的方法。

如果 X' 和 Y' 分别是 X 和 Y 的子集，那么函数 f:X'->Y' 是 X->Y 上的偏函数，而所有这些偏函数能够构成一个集合。

证明某个对象是集合，是要说明它可以通过集合公理构造出来。但是证明某个对象不是集合，可以用反证法来说明，例如规范公理证明不存在万有集合。

首先理清幂集公理声称可以构建出一个包含 X->Y 上的所有函数的集合， "所有函数" 意味着什么？

• 首先函数要求所有在 X 上的元素都有对应的 Y 中的元素，但 Y 中的元素可以没有对应的 x 。
• 因此计算它们之间有多少个函数的算法之一是：
  • 找出 Y 的所有非空子集 Y'
  • 将该子集作为值域，构造出 X->Y' 上所有满射的函数
  • 合并所有 X->Y' 上的满射函数集合

对于偏函数，核心区别就在于并不是所有 X 中的元素 x 都有对应的 f(x), 因此我们需要在 X 的 子集里构建函数集合，另外 X'->Y 上的所有函数看上去好像包括 X'->Y' 上的所有函数的，但数学上 它们是不相等的，因为其值域不同，比如从 {1}->{1,2} 上有一个函数，它只满足 f(1)=1, 在 {1}->{1} 上也有一个满足 f(1)=1 的函数，但二者并不相等。

因此要构造出所有偏函数集合：

• 只需要先用引理 3.4.9 分别构造出 X,Y 的所有子集组成的集合，记为 Sx 和 Sy

• 用集合替换公理以及幂集公理对 Sx 中每个集合 X' 构造从 X'->Y' 的幂集

  {Pow(X',Y'): In(X', Sx)&In(Y', Sy)}
  

• 根据并集公理，将以上集合里所有集合求并, 这就是 X 到 Y 上所有的偏函数组成的集合 PF。

公理 3.1 ，公理 3.3 和公理 3.11 可以推导出 公理 3.4

给定任意两个集合 X, Y, 根据公理 3.1 ，由于它们是对象，于是根据公理 3.3 可以构造出集合 {X,Y}, 然后根据公理 3.11 构造出两个集合的并集 X|Y

如果 b 和 b' 是集合 I 中的两个元素，并且 I 中每个元素 i 都指向一个特定的集合 A[i]

那么以下两集合相同：

• {In(x,A[b]): A(i)[In(i,I)->In(x, A[i])] }
• {In(x,A[b']): A(i)[In(i,I)->In(x, A[i])] }

这里 A(i) 是量词和变量 i, A[i] 是从 A 中选出标签为 i 的集合

本题仍然是证明两个集合相等。因此用集合相等的定义证明即可.

注意，为什么要先选一个 I 中的元素 b 或 b', 然后再用该元素指示的集合与其他集合的关系来构造多个集合的交集？

为什么不能把并集公理里的论述改一下，比如定义 r(A) 是对 A 中所有集合的交集，那么 r(A) 中任何元素 x 都满足：

In(x, r(A)) <-> A(S)[In(S, A)->In(x,S)]

同样，如果加上替换公理可以用一个索引集合 I 来构造多个集合的交集：

In(x, r(A[I])) <-> A(i)[In(i,I)->In(x,A[i])]

我的理解是，以上需要引入一个新的公理，因为没有现成的公理能够表达出这种操作，而以上描述的是一个和并集公理平行的"交集公理", 并集公理核心提供的实际是对选择迭代操作提供了合法性（无穷集合也适用），给定一个包含集合的的集合，该公理使得我们可以从中选择出所有集合然后对它们取并，没有该公理的情况下，我们只能对给定的某个两个集合取并。

然而先从 I 中选一个确定的集合 b, 然后用分离公理就可以直接描述出所有集合的交集了。（但并集公理无法用这种方式构建，因为分离公理实际描述的是两个 and 命题，而并集构造需要用 or 命题）

由于 b 和 b' 都是 I 中的一部分，即有命题 In(b, I) 的情况下 A(i)[In(i,I)->In(x, A[i])] 是可以推导出 In(x,A[b]) 的，所以对于以下两个命题

In(x,A[b])&A(i)[In(i,I)->In(x, A[i])]
In(x,A[b'])&A(i)[In(i,I)->In(x, A[i])]

都等价于 A(i)[In(i,I)->In(x, A[i])], 因此两个集合也是等价的。

I,J 都是指示集合，对任意属于 I|J 中元素 i, 都有一个对应的集合 A[i], 那么：

• u(A[I])|u(A[J]) 等于 u(A[I|J])
• r(A[I])&r(A[J]) 等于 r(A[I&J])

这里 r(A) 是 练习 3.4.9 中定义的 A 中所有集合的交集 #+end_example

还是在证明集合相等，因此转换为逻辑语言的等价：

• 根据定义，所有在 u(A[I|J]) 中的元素 x, 都满足命题：

  E(i)[In(i,I|J)&In(x,A[i])]
  

  In(i,I|J) 根据定义是可以展开成 I(i, I)|I(i,J) 的：

  E(i)[(In(i,I)|In(i,J))&In(x,A[i])]
  <-> ;; 将 & 分配到 | 中
  E(i)[(In(i,I)&In(x,A[i]))|(In(i,J))&In(x,A[i])]
  

  而存在量词对 | 是有分配率的，因此以上等价于

  E(i)[(In(i,I)&In(x,A[i]))]|E(i)[(In(i,J))&In(x,A[i])]
  

  而这就是 u(A[I])|u(A[J]) 的定义

• 同理，根据定义，所有在 r(A[I&J]) 中的元素 x, 都满足命题：

  A(i)[In(i,I&J)->In(x,A[i])]
  <-> ;; 根据 I&J 定义
  A(i)[In(i,I)&In(i,J)->In(x,A[i])]
  <-> ;; 全称量词对 & 的分配变换规则
  A(i)[In(i,I)&In(x,A[i])]&A(i)[In(i,J)&In(x,A[i])]
  

  而最后一个命题就是元素在 r(A[I])|r(A[J]) 中的定义。

X 是集合，I 是非空集合，I 中任意元素 i 都索引一个集合 A[i], 它是 X 的子集。 因此对于每个 A[i] 都有对应补集 X-A[i], 这些补集组成的集合称为 B, 可以通过 i 去 B 中索引得到 B[i]=X-A[i].

那么：

• X-u(A[I]) = r(B[I])
• X-r(A[I]) = u(B[I])

证明方式仍然是展开定义：

• 在 u(A[I]) 中元素 x 满足：

  E(i)[In(i,I)&In(x,A[i])]
  

• 在 X-u(A[I]) 中元素 x 满足：

  In(x,X)&~E(i)[In(i,I)&In(x,A[i])]
  <-> ;; 存在量词上做德摩根: ~E(x)(p&q) 等价于 A(x)(p->~q)
  In(x,X)&A(i)[In(i,I)->~In(x,A[i])]
  

• 在 r(B[I]) 中元素 x 满足

  A(i)[In(i,I)->In(x,B[i])]
  <-> ;; B 的定义
  A(i)[In(i,I)->(In(x,X)&~In(x,A[i]))]
  <-> ;; p->q&r 等价于 (p->q)&(p->r)
  A(i)[(In(i,I)->In(x,X))&(In(i,I)->~In(x,A[i]))]
  <-> ;; 全称量词分配
  A(i)[(In(i,I)->In(x,X))&A(i)[(In(i,I)->~In(x,A[i]))]
  

  我们想要证明 A(i)[(In(i,I)->In(x,X)) 等价于 I(x,X)

• 在 u(B[I]) 中元素 x 满足：

  E(i)[In(i,I)&In(x,B[i])]
  <-> ;; 差集定义
  E(i)[In(i,I)&In(x,X)&~In(x,A[i])]
  <-> ;; In(x,X) 不包含变量 i
  In(x,X)&E(i)[In(i,I)&~In(x,A[i])]
  

• 在 X-r(A[I]) 中元素 x 满足：

  In(x,X)&~A(i)[In(i,I)->In(x,A[i])]
  <->;; 德摩根
  In(x,X)&E(i)[In(i,I)&~In(x,A[i])]
  

  因此 X-r(A[I])=u(B[I])

TODO 为什么没用到 A[i] 是 X 子集？

用公理 3.3 可以定义 (x, y) 为 {{x}, {x, y}} 或者 (x, y) := {x, {x, y}} ，两种定义都符合：

(x, y) = (x', y') <-> (x=x')&(y=y')

.

两个定义的性质证明都涉及到不断向下一层去要结果的过程，但证明上我们需要反过来：

• 先证明 {x} {x'}, 以及 {x,y} {x',y'} 的关系

  如果 x=x'且 y=y', 根据公理 3.3, 任意在 {x} 中的元素 y 都满足 y=x, 由于 x='x, 因此 y=x' 这意味着 y 在 {x'} 中，同理可证明 {x'} 中元素都在 {x} 中，因此 {x}={x'}.

  反过来，如果 {x}={x'}, 在 {x} 中的元素只有 x, 它在 {x'} 中，而后者只有 x', 因此 x=x' 。

  这就证明 x=x' 等价于 {x}={x'}

  同样的，根据双元素集合公理，任意在 {x,y} 中元素 z, 要么 z=x, 要么 z=y, 分情况讨论可以发现 z 都在 {x', y'} 中。反过来也类似，因此 {x,y}={x',y'}

  反过来，如果 {x,y}={x',y'}, 有两种情况：

  • x=x',y=y'
  • x=y', y=x'
• 再证明 (x,y) 定义为 {{x}, {x, y}} 时的等价性质

  • 先证明从右到左：

    {{x}, {x, y}} = {{x'}, {x', y'}} <- (x=x')&(y=y')
    

    由于右边的关系以及前文的说明，我们知道 {x}={x'}, {x,y}={x',y'}, 因此根据双元素集合公理，类似证明 {x,y}={x',y'}, 可以证明 (x,y)=(x',y')

  • 证明从左到右：

    {{x}, {x, y}} = {{x'}, {x', y'}} -> (x=x')&(y=y')
    

    类似前文的证明， {{x}, {x, y}}={{x'}, {x', y'}} 意味着两种情况：

    • {x} = {x',y'}, {x,y}={x'}

      这意味着 x=x'=y'=y, 因此 x=x', y=y' 成立

    • {x} = {x'}, {x,y}={x', y'}

      前文已经知道，{x,y}={x', y'} 意味着以下两种情况

      • x=x', y=y': 这直接是我们想要的结果

      • x=y', y=x': 但 {x}={x'} 意味着 x=x', 因此必须有 x=x'=y'=y

        这也说明了 x=x' 以及 y=y'

  • 如果 A=B, 根据集合等于的定义，任意在 A 中元素要满足

    In(z,A)->In(z,B)
    

• 接着证明 (x,y) 定义为 {x, {x, y}} 时的等价性质

  • 先证明从右到左：

    {x, {x, y}} = {x', {x', y'}} <- (x=x')&(y=y')
    

    由于右边的关系以及前文的说明，我们知道 x=x', {x,y}={x',y'}, 因此根据双元素集合公理，类似证明 {x,y}={x',y'}, 可以证明 (x,y)=(x',y')

  • 证明从左到右：

    {x, {x, y}} = {x', {x', y'}} -> (x=x')&(y=y')
    

    {x, {x, y}}={x', {x', y'}} 意味着两种情况：

    • x={x',y'}, {x,y}=x'

      但这意味着， {x,y} 集合中包含了 {x',y'} 集合，后者又包含了 {x,y}, 导致了互 包含，根据正则公理以及练习 3.2.2, 这种情况是无法出现的。

    • x = x', {x,y}={x', y'} 前文已经知道，{x,y}={x', y'} 意味着以下两种情况
      • x=x', y=y': 这直接是我们想要的结果

      • x=y', y=x': 但我们还有约束 x=x', 因此必须有 x=x'=y'=y

        这也说明了 x=x' 以及 y=y'

采用这些定义可以表明笛卡尔积 X*Y 也是一个良好定义的集合。

如果 prod(X[:n]) 为空，那么至少有一个集合 X[i] 为空

引理 3.5.12 的逆否命题就是以上的结论。

I,J 是两个指示集合，其各个元素都指示了 A 集合中的集合， 定义集合 B={A[i]&A[j]: In((i,j),I*J)}, 那么

u(A[I])&u(A[J])=u(B)

仍然展开以上两个集合的逻辑表达：

• 在 u(A[I])&u(A[J]) 中的元素 x 满足

E(i)[In(i,I)&In(x, A[i])]&E(j)[In(j,J)&In(x, A[j])]

语义上看，这意味着，存在 i,j 两个分别在 I,J 中的独立索引，使得 x 同时在 A[i] 和 B[i] 中

• 在 u(B) 中元素 x 满足：

E((i,j))[In(x,A[i])&In(x,A[j])&In((i,j), IxJ)]
<-> ;;IxJ 定义
E(i)(j)[In(x,A[i])&In(x,A[j])&In(i,I)&In(j, J)]

语义上看，意味着存在 i,j, 两个分别在 I,J 中的独立索引，使得 x 同时在 A[i] 和 B[i] 中。 因此二者完全等价。

形式规则上看，以下式子是恒为真的：

E(x)E(y)[P(x)&Q(y)]<->E(x)[P(x)]&E(y)[Q(Y)]

f: X->Y 是一个函数，定义 f 的图 G(f) 为 X*Y 的一个子集 {(x, f(x)) : In(x,X)}。 那么两个函数相等等基于它们的图相等。

• 正向：给任意 x, (x,f(x)) 在 G(f) 中，同样 (x,g(x)) 在 G(g) 中。

  而如果两个函数 f, g 相等，那么在 G(f) 中元素 (x,f(x)) 也会在 G(g) 中， 即对应 (x,g(x))=(x,f(x)), 反过来同样成立。

• 反向：如果两个函数的图相等，那么给任意 G(f) 中元素 (x, f(x)) 都能在 G(g) 中找到相同元素， (x,g(x)), 根据有序对等于性质，意味着 g(x)=f(x). 因此 f=g.

反过来，如果 X*Y 的某个一个子集 G 具有下述性质：对每一个 X 中元素 x,集合 {In(y,Y): In((x, y), G)} 中恰好有一个元素（或者换言之，G 满足垂线测试），那么恰好存在一个函数 f:X->Y ，它的图与 G 相等。

这和前一个问题的差别在于，给定一个纯粹的 X*Y 集合的子集 G，该集合的样子与函数的图的样子很像，那么证明存在一个函数，它的图就是 G.

因此可以直接构造出一个函数 f:X->Y, 对每一个 x 中的元素 f(x) 就等于那个唯一的在集合 {In(y,Y): In((x, y), G)} 中的 y. 首先由于 y 是唯一的，因此该函数是定义良好的。

接着，根据这种的定义方式，对任意在 f 的图中的元素 (x,f(x)) 都会在图 G 中。 反过来，在 G 中的任意元素 (x,y), 由于 y 都对应了一个 f(x) 所以它在 f 的图中。

(这里核心是， X*Y 的子图 G 中覆盖了所有 X 集合里的情况)

可以通过引理 3.4.9 推导出公理 3.10

前文中，引理 3.4.9 （子集引理）说的是可以通过幂集公理构造出某个集合的所有子集构成的集合，本题则反过来，说明可以通过子集引理推导出幂集公理。

具体说来，假设对于任意 X, 可以获得它们所有子集构成的集合 Pow(X), 或者记为 2**X, 那么如何获得给定集合 X 到 Y 上的所有函数组成的集合？

额外地，练习 3.5.2 中可以用满射函数定义 n 元组，而练习 3.5.10 中可以建立笛卡尔积与函数的同构，因此考虑用笛卡尔积。

获得 Y 的所有子集 2**Y, 然后对其中每个子集 y ，构建 X 到 y 的笛卡尔积 X*y，产生的每个集合都与一个 X 到 Y 的子集上的满射函数同构，将所有 X*y 合并就得到了所有的图

递归定义的严格定义： 设 f:N*N -> N 是一个函数，c 是一个自然数。则存在一个函数 a:N->N 使得 a(0) = c 且对任意的 n ∈ N 均有 a(n ++)= f(n,a (n)), 而且这个函数是唯一的。

命题 2.1.16 里定义了递归定义，但那个时候没有严格定义函数。首先我们证明的是 a 的存在，而 f 是给定的，因此先非正式地看 a 为什么存在并且是唯一的，用加法例子代入，

f(m,n)=m+n

对于任意自然数 n ，存在一个函数

• n=0 时：空笛卡尔积的定义知道，0 重选择的结果并不是空集，而是 {()}
• n=1 时：根据引理 3.1.6 知道，非空集合中一定能选择出一个对象，因此 prod(X[:1]) 选出的是 X[1] 集合，而 X[1] 非空是前提
• 通过归纳法，可以从第 n+1 集合里选择出一个元素与已经假设存在的 n 元组拼接，因此存在 n+1 元组。
• 无限多个集合时，无法自然推广，需要引入选择公理

所有自然数集合都是同构的，同构意味着存在从一个集合到另一个集合之间的双射函数

假设有另一个集合叫作另类自然数 N'，其中有一个对象 a, 以及一个增长函数 s(a), 它们都符合 peano 公理。那么证明自然数集合 N 到 N' 之间存在一个双射，满足 f(0)=a ，且对任意自然数 n, 以及任意另类自然数 m, 有 f(n)=m, 当且仅当 f(n++)=f(s(m)).

• 自反： 存在双射函数 f:X->X ，f(x)=x, 可以说明这是双射，因为 x!=y 时 f(x)=x!=y=f(y), 同时所有 x 都有逆。
• 对称： 根据双射函数定义（双射本身称为可逆函数），其逆函数 ~f 也是 Y->X 的双射函数
• 传递： f:X->Y, g:Y->Z 是双射，根据 练习 3.3.7 f|g 是 X->Z 的双射函数

一个集合 X 的基数为 0，当且仅当 X 是空集。

如果 X 基数为 0, 那么它与集合 {In(x, N): 1<=i<=0} 存在双射。 但不存在从非空集合到空集的函数，因此 X 为空集。

反过来，如果 X 是空集根据练习 3.3.3, 空集到任意集合 Y 的函数只有 Y 是空集的时候才是双射，因此 X 只能和空集有双射，故 X 基数为 0.

反证法，假设自然数集是有限的，它的基数是某个自然数 n, 那么根据定义存在 N 到有限集合 X={In(i,N): 1<=i<=n} 的一个双射。把 X 到 N 方向的映射记为 f, 接着证明所有 f(i) 都是有界的，也就是 f(i) 小于等于某个自然数 M:

• n=1 时，f 是一个从 {1} 到自然数集 N 的函数，假设其唯一的映射是 f(1)=a, 那么令 M=a 就找到了使得所有 f(i)<=M 的值。
• 假设 f:{1…n}->N 下存在自然数 M 使得对所有 i, f(i)<=M
• 那么 f:{1…n,n++}->N 时，如果 f(n++)<=M, 根据假设，所有 f(i) 仍然小于等于 M, 如果 f(n++)>=M ，则重新将 M 选为 f(n++), 此时仍然存在某个自然数使得所有 f(i)<=M

但这意味着 M++ 不在集合 N 中，与自然数集性质矛盾。

a) X 是有限集，设 x 是一个对象并且 x 不是 X 中的元素。那么 X|{x} 是有限的，且 #(X|{x})=#(X)+1。

假设 X 基数是 n, 那么 f:X->{1…n} 是双射函数，对于 X|{x} 可以构造出一个到 {1…n++} 的双射函数 g，对于所有在 X|{x} 集合中元素 y, 如果 y!=x, 则 g(y)=f(y), 否则 g(y)=n++ 那么由于 f 是双射，且 n++ 不等于其他自然数，那么这就是一个双射函数，且该集合的基为 n+1.

b) X,Y 都是有限集，那么 X|Y 是有限的，且 #(X|Y)<=#(X)+#(Y)。 另外，如果 X 和 Y 是不相交的（即 X&Y=E），那么 #(X|Y)=#(X)+#(Y)。

假设 Y 的基数是 n ，用归纳法：

• n=0 时， Y 是空集，根据前文知道 X|E=X 是有限的, 而 #(X|Y)<=#(X)+#(Y) 也成立。
• 假设基数为 n 时， #(X|Y)<=#(X)+#(Y), 且在 X Y 不相交时取等号。
• 可以把基数为 n++ 的集合看作是 Y'=Y|{y}, 这里 y 不是 Y 中的元素，其中 Y 是基数为 n 的某个集合。根据 1) 有 #(Y')=#(Y)+1=n+1
• X|(Y')=(X|Y)|{y}, 现在分两种情况：

  • 如果 y 在 X 中，那么 X|Y'=X|Y

    因此： #(X|Y')=#(X|Y)<=#(X)+#(Y)<=#(X)+#(Y)+1=#(X)+#(Y').

  • 如果 y 不在 X 中，那么根据 1) 有

    #(X|Y')=#(X|Y)+1<=#(X)+#(Y)+1=#(X)+#(Y)

    在 X 和 Y 不相交的假设下

    #(X|Y')=#(X|Y)+1=#(X)+#(Y)+1=#(X)+#(Y')

c) X 是有限集，Y 是 X 的一个子集。那么 Y 是有限的，且 #(Y)<=#(X)。另外，如果 Y 是 X 的一个真子集，那么我们有 #(Y)<#(X)。

当 Y 是 X 的子集时，根据集合定义可以证明 X=(X-Y)|Y, 且 (X-Y)&Y=E, 根据 2) 的结论就有 #(X)=#(X-Y)+#(Y)

由于基数都是自然数，因此 #(Y)<=#(X), 并且如果 Y 是 X 的真子集，那么 Y!=X, 有 #(Y)!=#(X), 最终 #(Y)<#(X)

d) 如果 X 是有限集，f:X->Y 是一个函数，那么 f(X) 是一个有限集并且满足 #(f(X))<= #(X)。另外，如果 f 是单射，那么 #(f(X)) = #(X)。

设 X 的基数为 n, 对其归纳：

• n=0 时，这是一个空函数，空集的象 f(S) 也是空，因此 #(f(X))=0<=0=#(X)，根据练习 3.3.3, 空函数是单射，所以单射下的等于关系也成立。
• 基数为 n 时满足归纳假设，那么基数为 n++ 时，X' 可以写成 X|{x}, x 不在 X 中。
  • 对于任意函数 f', 可以定义为当 z 属于 X 的时候 f'(z)=f(z), 这里 f 是 X->Y 上的任意一个函数, 当 z=x 的时候， f'(z)=y:
    • 当 y 在 f(X) 中时， f'(X')=f(X), #(f'(X))=#(f(X))<=#(X)<=#(X')
    • 当 y 不在 f(X) 中时， f'(X')=f(X)|{y}, 根据 1) 可知 #(f'(X))=#(f(X))+1<=#(X)+1=#(X')
  • 如果 f' 是单射，那么 f 必须是单射，否则可以找出两个在 X 里的不同元素导致它们的映射结果相同，从而违反单射定义。 并且 f'(x) 不会在 f(X) 中，因此 #(f'(X'))=#(f(X))+1=#(X)+1=#(X')

e) 设 X 和 Y 都是有限集，那么笛卡儿积 X*Y 是有限的并且 #(X*Y)=#(X)*#(Y)。

设 Y 基数为 m ， X 的基数是 n, 对 n 进行归纳：

• n=0 时，得到的是空集，因此符合要求。
• n=1 时，X={x} ， 那么 {x}*Y 只能从 {x} 中选择一个元素，得到的是 {(x,y1),(x,y2)..} 这样的结果，它可以和 Y 构建一一对应关系 f(y1)=(x,y1), 因此命题仍然成立。

• 假设基数为 n 情况下成立，并将 X' 看作 X|{x}, x 不在 X 中 根据练习 3.5.4, (X|{x})*Y =(X*Y|{x}*Y), 由于 x 不在 X 中，因此在 {x}*Y 中的任意元素 (x,y) 都不在 X*Y 中，因此 X*Y 和 {x}*Y 是不相交的，根据 2) 可以知道

  #(X'*Y)=#(X*Y)+#({x}*Y)=n*m+m=(n+1)*m=#(X')*#(Y)
  

  因此归纳步骤也成立。

f) 设 X 和 Y 都是有限集，那么集合 Y**X（在公理 3.10 中被定义）是有限的，并且 #(Y**X)=#(Y)**#(X)。

假设 Y 基数是 m, X 的基数是 n, 对 n 进行归纳：

• n=0 时，根据定义 3.3.7, 在任意 Y 下空函数只有一个，因此 #(Y**X)=1, 而根据定义 2.3.11, m**0=1, 因此命题成立。
• n=1 时，X={x} ， 那么从 {x} 到 Y 的函数，只能是给定相同 x ，得到对应不同的 Y 上的元素，比如 f1(x)=y1, f2(x)=y2…, 因此 Y**{x} 的基数等于 Y 的基数。 命题同样成立。

• 假设基数为 n 情况下 #(Y**X)=m**n，并将 X' 看作 X|{x}, x 不在 X 中，我们想证明以下结论：

  #(Y**X')=#(Y**X)*#(Y**{x})=m*m**n=m**(n+1)
  

  这里指数关系规约到乘法关系，而 5) 提供了一种乘法关系，因此我们要说明从 X|{x} 到 Y 的所有函数可以一一映射到 X**Y 和 {x}**Y 的笛卡尔积上。

  这是合理的，因为对任意 X|{x} 到 Y 的函数 f，对于在 X 集合中元素的映射关系，都可以在 X**Y 中找到，而对于 {x} 的映射关系，都可以在 {x}**Y 中找到，反过来也是如此。

  因此归纳步骤也成立。

设 A 和 B 是集合，可构造出一个明确的双射表明： A*B 和 B*A 有相等的基数。然后利用命题 3.6.14， 给出引理 2.3.2 的另一种证明方法。

假设 a 是 A 中元素，b 是 B 中元素，那么 A*B 到 B*A 的双射为： f((a,b))=(b,a)

• 单射说明：对于所有在 A*B 中的 (a,b) 都有对应的 (b,a), 且如果它们不相等，根据有序对相等属性，其映射结果也会不相等
• 满射说明：对于每一个在 B*A 中的 (b,a) 都有对应的 (a,a)

对乘法假换律的证明：

• 根据 3.6.14 里基数算术的性质，A*B 的基数是 #(A)#(B), B*A 的基数是 #(B)#(A)
• 而 A*B 到 B*A 有双射关系，因此基数相等 #(A)#(B)=#(B)#(A)

设 A、B、C 是集合，可以构造一个明确的双射来表明：集合 (A**B)**C 和 A**(B*C) 有相等的基数 。因此推导出 (a**b)**c = a**(b*c) 对任意的自然数 a、b、c 均成立。利用类似的论证方法可推导出 (a**b)(a**c)=a**(b+c)

设 A 和 B 是集合，如果存在一个从 A 到 B 的单射 f : A -> B，那么我们称 A 的基数小于或等于 B 的基数。结论：如果 A 和 B 都是有限集，那么 A 的基数小于或等于 B 的基数，当且仅当 #(A)<=#(B)。

定义 3.6.10 里是定义了有限集合的基数，那么根据这个定义我们就能得到以上的结论。 但本题相当于重新定义了基数的小于等于关系，并且适用于无穷。然后在这个定义下去证明结论。

• 正向：如果 A 的基数小于等于 B, 那么根据前提可知存在一个 A->B 的单射函数 f,根据命题 3.6.14 第 4 条 #(f(A))=#(A), 而根据象的定义， f(A) 它一定是 B 的子集，根据命题 3.6.14 第 3) 条，#(f(A))<=f(B), 因此 #(A)<=#(B)

• 反向：如果 #(A)<=#(B), 假设分别为 m, n, 那么有 m<=n ，根据定义，存在一个双射函数 h:A->{1..m} ，同样存在一个双射函数 g:{1..n}->B 。

  现在构造一个函数 f:A->B, 对所有 A 中元素 f(a)=g(h(a)):

  • 该函数是定义良好的，因为 h(a) 的值都在 1 到 n 之间，因此 g(h(a)) 均存在。
  • 该函数是单射的，因为对于任意两个 A 中的不同元素 a1,a2, h(a1)!=h(a2), 因此 g(h(a1))!=g(h(a2))

  因此 A 到 B 存在一个单射函数 f

设 A 和 B 是集合，并且存在一个从 A 到 B 的单射 f: A → B（即 A 的基数小于或等 于 B 的基数）。证明：存在一个从 B 到 A 的满射 g : B → A

这里的核心在于 A B 可以都是无穷集合，因此不能把将其规约到 #(A)<=#(B) 的场景。

如果 A 是空集，那么空函数是单射，

f 是单射的话，每个元素 a 都有对应的 B 中元素 f(a), 且 f(a) 只有唯一的逆 a, 因此构造一个函数 g, 对每个在 B 中元素 b，如果 In(b, f(A)), 那么 g(b)=a, 否则 g(b)=

设 A 和 B 是有限集，证明： A|B 和 A&B 也是有限集，并且 #(A)+#(B)=#(A|B)+#(A&B)。

根据命题 3.6.14, A|B 是有限集，同时 A&B 是 A|B 的子集，因此也是有限集。

• A|B 可以拆分成三个不相交的子集： A-B, A&B, B-A
• A 可以拆分成两个不相交的子集： A-B, A&B
• B 可以拆分成两个不相交的子集： B-A, A&B

根据命题 3.6.14:

#(A)+#(B)=#(A-B)+#(B-A)+#(A&B)+#(A&B)=#(A|B)+#(A&B)

I={1…n}, A[1]…A[n] 都是有限集，满足 #(u(A[I]))>n, 则 I 中存在 i 使得 #(A[i])>=2

反证法，如果所有 A[i] 基数都小于或等于 1, 那么根据命题 3.6.14 第二条，应用 n 次之后 #(u(A[I]))<=1+…+1<=n, 与前提矛盾。