我无法证明一个用于稳定婚姻问题的Gayle Shapley算法正确性证明的引理
引理在算法过程中，每个男孩A只会被不适合A的女孩拒绝
书中的证明是用归纳法。
我们用归纳法证明了引理。考虑波士顿池算法的任意一轮，在医生α拒绝一家医院A而选择另一家医院B，这种拒绝意味着α更喜欢B而不是A。每个在B的偏好列表中高于α的医生都已经拒绝了B，因此，通过归纳假设对B是不可行的。现在考虑将α分配给A的任意匹配，我们已经确定α更喜欢B而不是A。如果B比它的伙伴更喜欢α，匹配是不稳定的。另一方面，如果B更喜欢它的伴侣而不是α，那么(根据我们之前的论证)它的伙伴是不可行的，匹配也是不稳定的。我们得出这样的结论不存在将α赋值给a的稳定匹配
这里医院对应男孩(他们建议按优先级递减)，医生对应女孩。
有人能解释引理和证明吗?我认为混乱在于缺乏对不可行的定义。婚姻算法做了以下假设:
- 一个男孩愿意和任何女孩结婚(但按照他的偏好顺序向她们求婚)。 一个自由的女孩会接受任何求婚，但会抛弃她现在的未婚夫。如果她更喜欢的男孩向她求婚。
男孩和阿尔法的婚姻;和Girl β是否不可用如果:
- 有一个不同的Boy α′β;优于α和α;';也更喜欢β
- 有一个不同的Girl β′α;优于β和β;';也更喜欢α
引理说明这是不可能发生的。
- 对于情形1,if α′如果存在，他会更早向她求婚，因为她已经和别人订婚了，她一定拒绝了他。所以要么&;真的更喜欢她现在的伴侣(拒绝了& α;′)，或者& α;更喜欢他的伴侣(没有抽出时间向β求婚)。
- 对于情形2,if β′如果存在，他会更早向她求婚，既然他已经和别人订婚了，她一定是甩了他或者拒绝了他。任一表示& β;&撇;现在和她更喜欢的人在一起。
将上述逻辑应用于归纳步骤，得出结论:& α;和β;和他们命中注定的伴侣在一起。
假设你(B)和你最好的朋友(A)向同一个女孩(alpha)求婚。比起他，她更喜欢你。如果你向她求婚，那就意味着没有比阿尔法更适合你的女孩了(如果有更好的，你就会去找她)。你梦中比阿尔法更好的女孩已经对你说了不，所以她们是不可用的。
。假设上帝让阿尔法和你最好的朋友在一起，而不是你。如果你更喜欢alpha而不是你现在的女孩，你们的关系是不稳定的，因为你想要一个更好的女孩，你会去找她(alpha)，因为她还没有拒绝你。另一方面，如果你更喜欢别人alpha，那么你就被困住了，因为在第一段我们说过没有更好的了。这意味着，如果alpha对你最好的朋友说不，那么她就不适合他。