假设我们俩各自独立地随机选取一个有无穷多个顶点的图（两点之间1/2的概率有边1/2的概率没有边）。那么，我们俩选到相同的图的概率是多少？
令人难以置信、但想通了之后又异常显然的是，两个图相同的概率为1。并且，我可以精确地告诉你，这个相同的图是什么样子的。考虑这样一个无穷大的图，我们用自然数1, 2, 3, …给所有顶点标号，然后如果y的二进制表达中的右起第x位为1，就在顶点x和顶点y之间连一条线。比如，顶点5就和顶点1、顶点3相连。我可以证明，我们俩都100%地会选取到上述这个图。
我们先来定义一个东西。我们说一个图是“任意连通”的，如果对于任意两个不相交的有限点集U和V，总能找到一个顶点x，使得x和U里面的所有顶点都相连，但和V里面的任一顶点都不相连。下面我们先证明，随机选取一个无穷大的图，该图满足任意连通性的概率为1；其次我们说明，所有满足任意连通性的图都是同构的。
为什么一个随机选取的无穷大图具有任意连通性的概率为1呢？我可以反过来说明，一个随机图不满足该性质的概率为0。考虑两个任意的有限点集U和V，假设这两个点集一共有n个点。那么，随便选取一个点x，它和U里所有点都相连，但和V里所有点都不相连的概率显然为1/2^n（因为两点之间是否相连是独立确定的，且概率为1/2）。不管n有多大，1/2^n总是一个不为0的数，但供我选的点有无穷多个。在我第k次选点后还找不到满足条件的点的概率为(1-1/2^n)^k，它是一个最终趋于0的值。
然后我们来证明，只要两个图都满足这个性质，我一定能为它们的顶点适当编号，使得图A的点x点y之间有边当且仅当图B的点x点y之间有边。这个证明是构造性的。假设我们已经找到了一个图A和图B的同构子图，这个子图有6个顶点，分别标号为1, 2, 3, 4, 5, 6。在图A当中选取下一个未编号的顶点，把它标号为顶点7。假设顶点7和前面6个顶点中的2, 4相连，和1, 3, 5, 6都不相连。由于图B满足任意连通性，因此图B当中必然也存在一个点，它和自己图里的那个2, 4相连，和1, 3, 5, 6都不相连。于是，把图B中的这个新的点编号为顶点7。不断执行该操作，就可以给图里的每个顶点确定一个适当的编号。
有一个问题是，不断这样操作后，虽然图A里的所有顶点都能找到图B中的对应顶点，但图B中可能还剩有顶点一直未被编号。问题的解决办法也很简单：利用任意连通性找到图B中与图A中的顶点7相对应的点后，立马换成让B选取下一个未编号的顶点并命其为顶点8，让图A利用任意连通性来找它的对应点。如此交替变更图A和图B的角色，就能保证两个图中的每个点都能编上号了。
那么，为什么我刚才说，我们选出的图都和第二段中描述的那个图相同呢？因为，那个图显然满足任意连通性。
来源：http://blogs.warwick.ac.uk/dangoodman/entry/something_completely_ridiculous/
相同改成同构比较合适。。
其实仔细想一想确实是“异常显然”。。。
对于两个n个顶点构成的随机图，两者同构的概率“约等于”1-(1-(1/2)^(n*(n-1)/2))^(n!)。n取无穷大时极限为1
嗯~拜托帮忙把links里的地址改一下，http://www.asyanyang.com/
楼上 >_<
仔细研究了一下，这个证明似乎是有问题的，简单的讲就是有限个1乘起来还是1但无限个1乘起来就未必是1了。
从另一个角度考虑，对于两个n个顶点构成的随机图，定义两者同构的概率p(n)。p(n)小于两者边数相同的几率，显然地，后者在n->∞时为0。之前对于p(n)的估计比较粗糙。
这个证明的最后一步好像有问题
你最后一步只证明了包含有限点的“任意连通”图是同构的
其中使用的是数学归纳法
但是, 注意数学归纳法只能证明有限集合的命题
对于无限集 数学归纳法是不适用的
最后一步的证明两个“任意连通”图同构是有问题的
证明过程使用了数学归纳法
但是数学归纳法只适用于证明有限集的命题
对于无限集数学归纳法是不适用的
唉
恩… asyanyang.com 即将成为OI人访问最多的非OI blog了.
数学归纳法基于反证法和最小数原理，可以应用于无限集，假设原命题不成立，必然存在最小的n使得p(n)不成立，然后可以将其证伪
不錯～
地基的数学归纳法定义不知从何而来？
http://zh.wikipedia.org/w/index.php?title=%E6%95%B0%E5%AD%A6%E5%BD%92%E7%BA%B3%E6%B3%95&variant=zh-cn
这个是一般被认同的数学归纳法的定义。
那么，随机选取两个无穷大的方阵，它们相似的概率是不是也是1呢？赫赫，如果是，它们的特征值排序后构成一个什么样的无穷序列呢？（注：可以从简单的情况开始，设方阵中的每个数都是满足正态分布的实数。并且方阵是对称的，好让它的特征值可以排序。赫赫。）
3L……M67MS以前说过什么话……
看来高估了这里的水平.我再来解释下,普通的数学归纳法是不适用无限集的
只有超限归纳法适用于无限集, 超限归纳法是数学归纳法在序数上的扩展
现在来尝试用超限归纳法证明
1. 假设任意连通图A拥有α个点时候 图A与构造图同构
2. 则任意连通图B拥有β=α+1个点的时候 图B与构造图同构
(α, β为序数)
两步都有问题.
步骤1问题: 构造图只构造了顶点数小于ω的图, 所以当α > ω时图A不可能与构造图同构
步骤2问题: 若要在图A中加入第β个定点, 那么要把α个点分为U,V两个集合, 如果α >= ω, 那么U,V中必然有一个集合拥有无穷个点, 但是原证明中只证明了有限个点连通性(原文:考虑两个任意的有限点集U和V).
对于α = ω的情况, 无法用数学归纳法证明 也无法用超限归纳法证明
所以在ZFC集合论中, 楼主的命题对所有图都不成立
(ZFC集合论包含选择公理, 选择公理等价于良序公理, 所以集合顶点数必然是个良序的, 所以必然是一个序数)
关于 超限归纳法 序数 ω 的定义 ZFC集合论 选择公理 良序公理 请自行wikipedia
回10楼: 我不知道你强调”数学归纳法”本身的证明有什么意义
回12楼: 要懂得尊重别人 多考虑考虑再回复 人家知道啥是数学归纳法
祝贺Blog四周年~~
数学归纳法显然不适用于无穷的情况，记得大一上数理逻辑的时候老师举的例子，考虑集合{1,2,…,n},n有限的情况下，该集合均有最大的数，n为无穷的时候（虽然不能这么说，但相信大家明白我的意思），就没有了。这个例子或许不太好，不过15楼解释的比较清楚了～
@15楼
首先我当时似乎没有什么态度问题，陈述事实而已。
你的表述自然是会引起误解的。“不适用于无限集”的说法显然违背数学归纳法的一般理解，而我当然无从猜想你究竟是什么意思。
另外，我认为这里是可以转化为数学归纳法的叙述形式的，只是表面上不符合而已。
15楼可以啊！学中文的不能小觑。你问问数学的学生，是不是每个人都知道超限归纳。
不好意思 我浏览器显示出了问题，把15楼和16楼弄混了。
我还是没弄懂哪里使用了数学归纳法
@15
我不明白为什么不能用普通的数学归纳法（原命题基于自然数的啊），请解释下，谢谢。
对于你步骤二中的问题，原文只是举了有限集为例子说明概率的求法，再求极限后求出无限图任意联通的的概率。
我水平比较低，才升高中，请多指教
我来个简化到极点的例子：
证明(0, 1)中一个随机实数以概率1与0.1111111111111111111111………….同构。
首先可证明：随机实数小数点后只有有限个1的概率为0（对应于“任意连通”：）。
选一个“n点同构子图”0.1…1，得到“n+1点同构子图”0.1…11的概率为1，按数学归纳法原理，证毕。
前面的极简例子上下文是：通过改变数字顺序达成一致叫做同构。这是在别的地方讨论时的上下文。
顿悟~楼主的证明方法只能证明存在无穷大同构子图，不能证明所有的点都包括进来了，就象我证明随机实数与0.11111……同构的实质一样。
还是不准确，更准确表述为：
楼主的证明方法只能证明以概率1存在无穷大同构子图，不能证明以概率1将所有的点都包括进来了，就象我证明随机实数与0.11111……以概率1同构的实质一样。
我是文盲，我不知道啥叫超限归纳，但是我觉得如果一个图边集是空的，另一个有边它们怎么能同构呢……
两个随机选取的n点有穷图同构的概率应当是随n的增长而减小直至趋于0的，如果到实无穷图时反而突变为以概率1同构，本身就否定了归纳法在这种情况下的适用性。
@24
选一个“n点同构子图”0.1…1，得到“n+1点同构子图”0.1…11的概率为1,这步如何归纳
首先我承认这个证明我没看懂。下面的文字只是就命题而言
我认为出现争议的核心原因在于将“相等”应用到无限的时候所导致的矛盾。
最简单的例子：设把硬币抛阿列夫零次为一次试验，则两次试验中正反面个数分别相同的概率为p。
1.定义p（n）为把硬币抛n次，正反面个数一样的概率。
我们可以定义p=p（n）|n->∞。p=0
2.正面的个数是阿列夫零的概率为1，反面亦然。阿列夫零与阿列夫零相等。从而两个试验的结果相同的概率为1。
这两种解释在似乎都没错。只是因为命题表达不严密（如何严密化？？）所造成互相矛盾的结果。这篇文章应该是采取了后种解释吧。
不过不知道大家对我前面提出过的“有限个1乘起来还是1；但无限个1乘起来就未必是1了”这一论点有何想法？
pp评论的有道理。严格地说，就是这样：
样本空间为所有的随机图：{A:V(A)=N,E(A)=…}
定义事件S为{A:∀U,V⊂V(A)，∃x，x与U相连而与V分离}，而将A的子集对编号为U_i,V_i后令事件S_i为{A:∃x，x与U_i相连而与V_i分离}，则显然S=⋂S_i。
我们的证明只给出了对每一个i，P(S_i)=1
于是就有两个问题：
各S_i未必互相独立
aleph0个1相乘未必为1（概率论中的1都是极限意义上的）
[ZT]我现在想到一个证明，但仍有一个尾巴，等着老大的测度论。
引理：两个可数个顶点的无穷图A、B都可以用自然数将全部顶点无遗漏地标上号。（不证自明吧）
1、A{0}和B{0}是同构的，tsy所说的找不到归纳起点问题不存在，不过博主一开始就用了6个顶点的起点，是有点迷惑人的。
2、然后，找到与A{0，1}同构的—假定为—B{0，5}
3、接下来，从A、B中找出未取出的最小编号点，这里是B{2}
4、接下来，找出与B{0，2，5}同构的—也是假定为—A{0，1，8}
5、接下来重复第2步，这次找到的是A{2}
6、重复第4步，找出与A{0，1，2，8}同构的—假定为—B{0，2，5，9}
……
这样，如果每一步是必然事件而非以概率1找到下一个同构顶点，则A、B的任意顶点N都将在不迟于第2N步被取出，A、B同构被证明。
可是，如果某一步就是找不到下一个同构顶点，而除此之外的无穷次寻找都能找到，似乎这个测度为零的事件不会破坏以概率1找到下一个顶点的说法。
如果无穷次寻找中以非0概率发生1次找不到下个顶点的情况，就破坏了A、B同构概率为1的结论，但并不破坏每一步找到下一个同构顶点的概率为1的性质。
第3步找到的应是B{1}，痴呆了~
pp 无限个1相乘 最简单的例子就是e=lim(1+1/n)^n (n->∞)
sss 引理：两个可数个顶点的无穷图A、B都可以用自然数将全部顶点无遗漏地标上号。（不证自明吧） 这个是错的 存在不可数图的
@35
引理是对的啊，他只针对顶点可数
@31、32
很有道理，原来是证明任意连通性成立时，每次选点不是必然事件，而是概率为1，无限个1相乘未必是1.
@35
你那个例子有问题，这里的无限个1相乘未必是1，每个1的极限都要是1，而不是这串1的极限是1
用熵的思想去想,无穷的话肯定是均匀的.两个均匀的东西肯定是同构的.所以如果物理定律是一样的话,无数多个宇宙也肯定是同构的,如果他们无限大.
数学归纳法只适用于证明有限集的命题
对于无限集数学归纳法是不适用的
这个证明是错的，顶点个数未必可数
还有，无穷多个概率为零的命题至少有一个成立的概率未必为零
比如：对于正整数n
n=1? n=2? … n=k? …
实际上，n顶点图的连边方法有2^n(n-1),这个数远远大于n!
另外，15L真相