希尔伯特旅馆，奇数房住男性、偶数房住女性，是否通过交换房间就能令旅客全是女性？

如果是有限次交换，不能令旅客全是女性。

如果是无限次交换，可以令旅客全是女性。

关于这个结论的原因，其他答主已经解释得很好了。

我在这里主要澄清一下关于“交换”的三个不同概念：自然数集的置换（permutation）、自然数集上的双射（bijection）、自然数集的序（order）。

在有限集上，置换就是双射，而且对于某个特定的序，存在唯一的双射与之对应。可以说，对于有限集，这三个概念是在说同一个事情。

但是对于无限集，这三个概念各不相同。

零、希尔伯特旅馆的数学意义

希尔伯特旅馆号称无限旅馆，但“无限”并非“万有”。至少，旅馆的房间是用自然数来编号的。

也就是说，旅馆的房间编号不能是除自然数之外的其他东西。

旅馆的入住情况相当于为每个自然数（作为房间编号）指定一位旅客或者指定为未入住。相当于“定义域为自然数集”的函数，这就是序列（sequence）。

初始状态下，旅馆是满的。奇数房住男性，偶数房住女性。我们为每个旅客编号，其号码与所住房间一致。这样就得到了自然数列 $1,2,3,…$

其中，奇数代表男性旅客，偶数代表女性旅客。

无限次交换“完成之后”，如果对于某个自然数（代表旅客编号），存在房间编号与之对应，则说明该旅客还在旅馆。否则，我们就说，该旅客已被踢出旅馆。

为了方便讨论，在本文中约定自然数从1开始。

一、置换

1.1 置换的定义

自然数集的置换，是指有限次交换所形成的映射。有时也表述为：自然数列 $1,2,…,n$ 中除有限项之外的其他所有项保持不动，这有限项任意重排列所形成的映射，即为自然数集的一种置换。

1.2 希尔伯特旅馆内的置换

将置换应用到希尔伯特旅馆，不能令旅客全是女性。
可以用数学归纳法证明。初始状态下，有男性旅客。假设第 $k$ 次交换时，旅馆有男性旅客。那么一次交换不能将其踢出。所以第 $k+1$ 次交换后，仍有男性旅客。证毕。

二、双射

2.1 双射的定义

自然数集上的双射，是指从自然数集到自然数集的映射，既是单射又是满射。

所谓单射，是指将全体自然数不重复地指定给各个自然数。
$a≠b⇒f(a)≠f(b)$

所谓满射，是指将全体自然数不遗漏地指定给各个自然数。
$∀n∈N,∃a∈N,f(a)=n$

2.2 双射与置换的关系

用数学归纳法可以证明，任一置换都是双射。

但是，存在某个双射，不是置换。

例如，对于所有自然数 $n$ ，交换第 $2n$ 项与第 $2n+1$ 项。

相当于将自然数列 $1,2,3,…$ 中的元素两个两个地结为一组，交换每组内的两个元素。

可以看到，生成的数列符合双射的定义。

但这种双射需要进行无限次（可数次）交换才能实现，所以不符合置换的定义。

2.3 希尔伯特旅馆内的双射

将双射应用到希尔伯特旅馆，不能令旅客全是女性。

这是因为，映射前的第 1 个房间是男性。

映射后，这位旅客搬到了 $f(1)$ 号房间。仍在希尔伯特旅馆。

三、无限次交换

3.1 无限次交换的定义

我们对无限次交换制定一些规则，使其成为一个良定义。

每次只交换一对元素；
只进行可数无限次交换，这些交换操作可以写成一个序列；
对于任意自然数 $n$ ，必定存在某个自然数 $k$ ，使得从第 $k$ 次之后的交换不会涉及到前 $n$ 个元素。

规则一、二是为了保证交换操作是一个序列。这样才能讨论对应潜无穷的收敛结果。
规则三是为了保证这些交换操作一定是收敛的。

3.2 无限次交换“完成之后”的结果

任意有限或可数无限次交换“完成之后”都能得到一个单射。

这是因为对于任意自然数 $n$ ，在有限次交换之后，它们的值就确定了。

任意单射都可以通过有限或可数无限次交换得到。

证明起来怪费劲的，直接写个“选择排序”吧。
把“选择排序”所执行的交换写成一个序列，将这些交换完成之后，即可得到想要的单射。

按照“选择排序”的思路，任意可数无限次交换，都可以简化为这样的操作：依次针对每个房间指定在它后面的另一个房间进行一次交换。

3.3 无限次交换与双射的关系。

我们所定义的有限或可数无限次交换与单射等价。

因此就有，任意双射都是单射，也就是说，任意双射都可以通过有限或可数无限次交换得到。

存在单射不是双射，也就是说，存在某种可数无限次交换，任意双射都不能与之对应。

3.4 希尔伯特旅馆内的单射

将单射（也就是可数无限次交换）应用到希尔伯特旅馆，可以令旅客全是女性。

最好的例子是@罗兰在他的回答中提出的。

我们可以用“选择排序”的思路，将这些交换写成一个序列：
$(1,2)(2,4)(3,6)(4,8)(5,10)(6,12)……$
也就是说，从1号房间开始，依次交换旅客。每次交换当前房间的旅客与两倍房号房间内的旅客。
需要注意的是，交换是针对房间的，而不是针对旅客。第一次交换后，1号旅客被换到2号房间。然后在第2次交换时再被换到4号房间。

用1天时间进行第1次交换， $\frac{1}{2}$ 天时间进行第2、3次交换，……， $\frac{1}{2^n}$ 天时间进行第 2n2^n 到 $2^{n+1}-1$ 次交换……2天后，旅馆就都是女性了。

四、序

4.1 序的定义

序是指满足三分性和传递性的一种映射 $f:\mathbb N\times\mathbb N\rightarrow\{<,=,>\}$ 。

（三分性）假设 $a\in\mathbb N$ 且 $b\in\mathbb N$ ，这三个命题有且仅有一个成立： $a<b, a=b, a>b$ 。
（传递性）如果 $a<b$ 且 $b<c$ ，则 $a<c$ 。

通俗地理解就是：给定任意两个自然数，可以为它们比大小。

自然数集的标准序是这样的： $1<2<3<\cdots$

4.2 序与双射的关系

任一双射都对应一个序。

双射所定义的序是这样的：如果 $f(a)<f(b)$ ，则 $a<_fb$ 。
由于 $f$ 是单射，可推出上述关系是等价关系。即 $f(a)<f(b)$ ，当且仅当 $a<_f b$ ； $f(a)=f(b)$ ，当且仅当 $a=_f b$ ； $f(a)>f(b)$ ，当且仅当 $a>_f b$ 。而 $f(a)<f(b),f(a)=f(b),f(a)>f(b)$ 有且仅有一个成立，所以 $a<_f b,a=_f b,a>_f b$ 有且仅有一个成立。
同样根据等价关系， $a<_f b, b<_fc$ 可以得到 $f(a)<f(b), f(b)<f(c)$ 。所以就有 $f(a)<f(c)$ ，从而 $a<_fc$ 。证毕。

只用到单射的条件就已经能对应一个序了……

但是，存在某个序，任一双射都不能与之对应。

可以定义一个这样的序： $2<3<4<\cdots<1$ 。
不难验证，这个序满足三分性和传递性，符合序的定义。
但是不存在能够与之对应的双射。
假设存在这样的双射 ff ，则对于任意 $n\in\mathbb N$ ，有 $f(1)>f(n)$ 。
由于 $f$ 是自然数集上的映射， $f(1)$ 是某个自然数。设 $f(1)=k$ 。
又由于 $f$ 是双射，所以必定存在自然数 $n\neq 0$ ，使得 $f(n)=k+1>f(1)$ ，与序的要求矛盾。因此不存在这样的双射。

4.3 序与无限次交换的关系

存在某种可数无限次交换，任意序都不能与之对应。

还是举上面这个例子。在上面的例子中，1和3不能比较大小。

存在某种序，不能通过有限或可数无限次交换得到。

证明起来也怪费劲的，直接写个“插入排序”吧。
任意序都能通过“插入排序”得到。但是某些“插入排序”不满足可数无限次交换中的规则三。
例如倒序 $\cdots<3<2<1$ 。

倒序不满足规则三，类似发散数列。这样也就不能讨论无限次交换之后希尔伯特旅馆的入住情况。
为了讨论无限次交换之后的情况，我们仅考虑满足规则三的那些序。

4.4 希尔伯特旅馆内的序

将可数次交换应用到希尔伯特旅馆，可以令旅客全是女性。

考虑这样的序： $2<4<6<\cdots<1<3<5<\cdots$ 。
可以通过“插入排序”得到，这次的“插入排序”满足规则三。

第一轮操作，通过交换旅客，将2号旅客排到1号旅客前面。耗时1天。
第二轮操作，通过交换旅客，将4、6号旅客排到1号旅客前面。耗时1/2天。
第三轮操作，通过交换旅客，将8、10、12、14号旅客排到1号旅客前面。耗时1/4天。
依次类推，2天后，旅馆就都是女性了。

五、总结

我们讨论了四种不同的“交换”：置换、双射、单射、序。

置换是有限次交换。
双射是不重复不遗漏的重新指定。
单射是不重复的重新指定，它等价于有限次交换或能够收敛的可数无限次交换。
序是一种具有三分性和传递性的关系，它等价于有限次交换或能够写成“插入排序”的可数无限次交换。

置换的集合是双射的集合的真子集。
双射的集合是单射的集合的真子集。
双射的集合是序的集合的真子集。