“对每个变量只有选或不选两种选择的问题,用分治把 $n$ 个变量分成大小 $\lfloor n/2\rfloor$ 与 $\lceil n/2\rceil$ 的两组,分别枚举部分状态,再做兼容…”
形式陈述
对集合
若再有
包含关系满足自反性、反对称性与传递性:
直觉
成员关系与包含关系的量词层级不同。
这条等价式包含了一个真实的类型转换,不能据此把
例子与边界
权限系统给出一个结构化例子。若
要验证这条包含,应检查每一种只读权限在编辑角色中仍被允许;要否定反向包含,只需指出“修改”属于
嵌套集合尤其容易暴露类型错误。令
此时
空集是每个集合的子集,因为命题
推论与应用
双包含是证明集合相等的标准骨架:先从
这样的单个见证。对长集合表达式,先决定证明目标是全称包含还是存在反例,往往比直接展开所有符号更清楚。
包含与集合运算相互刻画:
若
幂集
参考资料
- Paul R. Halmos, Naive Set Theory, Dover, 2017, §§2–5。
- Richard Hammack, Book of Proof, 3rd ed., 2018, §§1.3–1.8。
- Daniel J. Velleman, How to Prove It, 3rd ed., Cambridge University Press, 2019, Chapter 3。