如何使用计算机代码检查一个无限集合是否在加法下封闭？

Question

给定k个正整数a1 < a2 < a3 < ... < ak，以及大于ak的所有整数，我们想要检查集合A = {ai : i ∈ [1,k]} ∪ {n : n > ak, n ∈ ℕ } = {a1, a2, a3, ... , ak, ak+1, ak+2, ...} 是否在加法下封闭。这意味着：

∑1 ≤ i ≤ k ai*bi ∈ A，对于任何非负整数bi。

例如，{2,4,6,7,8,....} 在加法下是封闭的。

有没有简单的方法来做到这一点？是否有我们可以在Mathematica或Matlab中使用的函数？

- Osiris Xu

---

如果集合是无限的，你如何知道它的所有成员是什么？ - Gabe

正如您在上面的集合A中所看到的，元素a_k之后，我们有a_k+1、a_k+2、a_k+3等等。每个数字都比它左边的数字增加了一。 - Osiris Xu

@OsirisXu：SO支持有序和无序列表，有序列表使用“1. ”作为前缀，无序列表使用“* ”、“- ”或“+ ”作为前缀。编辑您的问题并尝试一下。单击编辑器工具栏中的橙色问号以获取有关格式设置的更多信息和提示。 - outis

Answer 1

如果不连续的部分少于k个集合不是很大，我相信您可以直接这样处理：

a = {2, 4, 6};
Tr /@ Subsets[a, {2}];
TakeWhile[%, # < Last@a &];
Complement[%, a] === {}

- Mr.Wizard

---

如果集合不是很大呢？不确定有比“无限集合”更大的东西了（好吧，有稀疏无限集合和密集无限集合，但两者都是很大的）。而且，您取的任何有限子集肯定都不会是封闭的，因此这似乎没有什么帮助。 - Ben Voigt

@Ben，也许我误解了问题，或者推理失败了，但是我的意思是集合中小于a_k的有限部分。 - Mr.Wizard

我刚意识到这里应该有一个进一步的故事。为了检查集合是否完整，我们还应该检查将a_i多次加上自身是否也包含在集合中。 - Osiris Xu

@Ben 我明白你的意思。我会按照你的建议修改措辞。 - Mr.Wizard

@Mr.Wizard：是的，归纳法确保了非负整数权重的情况。等等，不对，还有一个未覆盖的特殊情况... - Ben Voigt

Answer 2

一个平凡的观察：任何一个操作数大于或等于a_k的总和都是A的成员，所以你只需要关注两个操作数都来自集合B={a_1 .. a_(k-1)}的总和。以下是朴素解法的伪代码：

for i from k-1 down to 1
  for j from i down to 1
    if (a_i + a_j < a_k) and (a_i + a_j is not in B) then
      return false
return true

- LaC

---

谢谢，LaC。但问题是如何快速检查a_i + a_j不在B中。还需要另一个循环吗？ - Osiris Xu

使用二分查找，假设B已排序。 - Alexander Kondratskiy

"a_k" 是 "一个正数"。问题并不保证它是整数。因此，我认为您需要将 "a_k" 包括在集合 "B" 中，并且当 "a_i + a_j > a_k" 时，您需要测试总和是否为整数。 - Ben Voigt

@BenVoigt：由于他将“大于a_k的所有整数”表示为a_k+1，a_k+2 ...，这也使得a_k成为整数，因此我假设他只是忘记指定a_1 ... a_k为整数了。 - LaC

Answer 3

你最近对问题的修改让它变得荒谬。我注意到：

• a_1 到 a_k 都是严格正整数
• 集合中其余成员都严格大于 a_k，因此也都是严格正整数

因此，集合中的所有成员都是严格正整数。

但是，∑a_i*n_i ∈ A 显然并不对所有非负整数 n_i 成立。

具体来说，当 n_i = 0 时，它不成立，因为总和为零，而零不是严格正整数，因此不是集合的成员。

现在，这是一个极为奇怪的“闭集”的定义，不是通常接受的用法。但按照你的定义，对于任何 k > 0，该集合都不是闭集。

- Ben Voigt

---

我同意，OP给出的“加法封闭”的新定义是错误的。现在他似乎想要“线性组合封闭”。 - LaC