免費論壇 繁體 | 簡體
Sclub交友聊天~加入聊天室當版主
分享
返回列表 发帖

幂集

本帖最后由 hbghlyj 于 2019-9-19 23:34 编辑

证明或证伪
若$A\cap2^B⊆2^C,2^A\cap B⊆2^C$,则$A\cap B⊆C$

基础知识:集合A的幂集是由A的所有子集构成的集合,即$2^A=\{x|x⊆A\}$
举例{a,b}的幂集为{∅,{a},{b},{a,b}}
{a,b,c}的幂集为{∅,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}
∅的幂集为单元素集{∅}

若$2^A⊆2^B$,则A⊆B
证明:$\because 2^A⊆2^B,A\in2^A,\therefore A\in 2^B$,即A⊆B
这个命题可以自我加强为:
若$2^{2^A}⊆2^{2^B}$,则A⊆B

本帖最后由 hbghlyj 于 2019-10-5 10:19 编辑

回复 1# hbghlyj
一个有限集的幂集,可以如下排列,使相邻两个集间恰相差一个元素
此命题等价于:k维立方体图有H路
设集合A有n个元素,把每个元素编号,设A={1,2,3,…,n}.我们用一个长度为n的由0与1构成的序列来表达每个子集,规则是若A的元素i在该子集中,则在序列的第i位上写1,否则写0.例如,空集$\emptyset$=0,0,0,…,0;{1}=1,0,0,…,0;{n}=0,0,…,1;{2,3}=0,1,1,0,…,0.于是A的全部子集共有$2^n$个.
以这2个子集对应的序列为顶点,仅当两序列只有一个同位数码相异时,在此二顶点间连一边,得图G.例如n=1时,G为图A-7(A)所示的单位线段;n=2时,G为图A-7(B)所示的正方形.图A-7(B)是由两个图A-7(A)如下作成的:在一个的0,1码前加上0,变成00,01,在另一个的0,1码前加上1,变成10,11,再把一个放在另一个上方,连上两个“竖边”作成一个正方形.复制两个图A-7(B),把一个放在另一个的上方,在上方的各顶点标志码前加一个0,在下方的各顶点标志码前加一个1,再用4条竖线联结上下相对的顶点,构成n=3时的图G(图A-7(C),它是一个立方体.如果n=k的图G已作好,则把n=k的图及其复件分别放在上方和下方,在上方图的各顶点标志码前加一个0,在下方图的各顶点标志码前加一个1,再在上、下两方对应的顶点间连竖直的边,则得n=k+1的图G.图A-7(C)是n=3的情形,图A-7(D)是n=4的情形.n=k的图G称为k维立方体图.用数学归纳法容易证明k维立方体图有哈密顿图(k≥2).对于n=1,显然成立,因为这时1维立方体图是$K_2$,是一条哈密顿链.对于n=2,它是四边形,显然是哈密顿圈.若对于n=k,它是哈密顿图,考虑n=k+1.把G中上方和下方的n=k时的哈密顿圈上各删去一条对应边,再把这两条对应边的对应端点间的两条边选来与上下方的哈密顿链并成一个n=k+1时的哈密顿圈,如图A-7(D)中的粗线所示把G中的顶点按哈密顿圈上的顺序放在一个圆周上,从任一顶点出发,沿逆时针(或顺时针)为序,则把全部子集排了序,使得相邻子集相差一个元素

TOP

返回列表 回复 发帖