Putnam 2009 A4问题：有理数集合S是否必包含所有有理数？及个人解答正确性验证

问题描述 #

设S是有理数集的一个子集，满足以下条件：
(a) (0 \in S);
(b) 若(x \in S)，则(x+1 \in S)且(x-1 \in S);
(c) 若(x \in S)且(x \notin {0,1})，则(\frac{1}{x(x-1)} \in S)。

问：S是否一定包含所有有理数？

你的尝试解答 #

我现在明确知道根据性质(a)，S包含0。

再看性质(b)：如果S包含0，反复应用(b)的话，就能得到：
(0 \in S \Rightarrow -1 = 0-1 \in S \Rightarrow -2 = -1-1 \in S \Rightarrow \dots)，同样(1 = 0+1 \in S \Rightarrow 2 = 1+1 \in S \Rightarrow \dots)，所以所有整数都在S里。

再看性质(c)：如果S里有一个不是0或1的元素x，那么(\frac{1}{x(x-1)})也在S里，反复应用这个性质的话，S会包含一系列形如(\frac{1}{x(x-1)})的有理数。

所以我觉得S不一定包含所有有理数，它只是基于(a)(b)(c)这三个性质包含有理数集的一个特定子集。

解答正确性分析 #

很遗憾，你的结论是错的——实际上S必须包含所有有理数，咱们来一步步补全严谨的推导，看看为什么：

首先，你关于“所有整数都属于S”的推导完全正确，这是后续推理的基础。接下来我们要证明任意有理数(\frac{p}{q})（(p,q)为整数，(q>0)）都能被构造进S：

第一步：证明所有单位分数(\frac{1}{q})属于S #

我们用数学归纳法来证：

• 当(q=1)时，(1\in S)，显然成立；

• 假设对于所有小于(q)的正整数(k)，(\frac{1}{k}\in S)。现在看(q)本身：因为(q)是整数，所以(q\in S)，根据条件(c)，我们可以得到：
  [
  \frac{1}{q(q-1)} \in S
  ]
  而我们知道(\frac{1}{q(q-1)} = \frac{1}{q-1} - \frac{1}{q})（通分即可验证）。根据归纳假设，(\frac{1}{q-1}\in S)，又因为S在整数平移下封闭（条件(b)反复应用的结果），所以：
  [
  \frac{1}{q} = \frac{1}{q-1} - \frac{1}{q(q-1)}
  ]
  等式右边的两个元素都属于S，因此(\frac{1}{q})必然也在S里。

  这样归纳下去，所有形如(\frac{1}{q})的单位分数都属于S。

第二步：证明任意有理数(\frac{p}{q})属于S #

对于任意有理数(\frac{p}{q})，我们可以把它写成整数(k)加上一个介于0和1之间的分数(\frac{r}{q})（其中(0\leq r<q)）。

因为(\frac{1}{q}\in S)，结合S的平移封闭性（条件(b)）：比如要得到(\frac{r}{q})，我们可以用(1 - \frac{q-r}{q})，而(\frac{q-r}{q})是由(q-r)个(\frac{1}{q})通过整数平移组合而来；再通过给(\frac{r}{q})加上整数(k)，就能得到(\frac{p}{q})。

举个具体例子：要得到(\frac{2}{3})，我们已经有(\frac{1}{3}\in S)，而(1\in S)，所以(1 - \frac{1}{3} = \frac{2}{3}\in S)；要得到(\frac{5}{4})，我们有(\frac{1}{4}\in S)，那么(\frac{1}{4} + 1 = \frac{5}{4}\in S)，完全符合条件(b)。

所以本质上，通过条件(c)的生成能力，结合整数平移，S可以覆盖所有有理数，你的结论漏掉了这种生成的完备性，才误以为S只是一个特定子集。

备注：内容来源于stack exchange，提问作者Bojackkkkk