如何实现一个无限集合类？

Question

我正在设计一个离散数学的类库，但是我想不出如何实现无限集合。

目前，我有一个抽象的基类Set，它实现了接口ISet。对于有限集合，我派生了一个类FiniteSet，它实现了每个集合方法。然后我可以像这样使用它：

FiniteSet<int> set1 = new FiniteSet<int>(1, 2, 3);
FiniteSet<int> set2 = new FiniteSet<int>(3, 4, 5);
Console.WriteLine(set1); //{1, 2, 3}
Console.WriteLine(set2); //{3, 4, 5}

set1.UnionWith(set2);
Console.WriteLine(set1); //{1, 2, 3, 4, 5}

现在我想要表示一个无限集合。我考虑从set派生另一个抽象类InfiniteSet，然后开发者使用库时必须从InfiniteSet派生自己的类。我会提供常用的集合，例如N、Z、Q和R。

但是我不知道如何实现Subset和GetEnumerator等方法——我甚至开始认为这是不可能的。你怎么以实际的方式枚举一个无限集合，以便与另一个无限集合相交/并集？你如何在代码中检查N是否是R的子集？至于基数的问题……好吧，那可能是一个单独的问题。

所有这些都让我得出结论，我实现无限集合的想法可能是错误的方法。非常感谢您的意见：）。

编辑：为了明确起见，我还想表示不可数无限集合。

编辑2：我认为重要的是要记住，最终目标是实现ISet，这意味着任何解决方案都必须提供（应该提供）实现所有ISet的方法的方法，其中最棘手的是枚举方法和IsSubsetOf方法。

- Daniel

---

@asawyer 我真的看不出来这与任何问题有关，除了实现枚举 - 但仍然存在实际实现的问题。 - Daniel

使用 yield return 创建一个可数无限集合非常容易。 - Michael Graczyk

根据定义，无法枚举一个不可数的集合。如果您愿意放弃枚举，则实现该集合应该很容易（只需使用检查成员资格的谓词即可）。交集使用两个谓词，并集使用两个谓词OR。 - Michael Graczyk

我并不想放弃枚举，因为那样我就得放弃ISet（对吧？）。即使我愿意，我仍然认为这个问题并不是微不足道的：我不知道如何解决编写检查N是否为R的子集的代码的问题。 - Daniel

如果你不担心你的代码在有限时间内执行，那么这一切都是微不足道的...... 你说得对，除了成员测试、并集和交集之外，我看不出你可以实现这个集合的任何方法。我会给出一个证明作为答案。 - Michael Graczyk

Answer 1

无法为不可数无限集完全实现ISet。

以下是一个证明（由Bertrand Russell提供）：

假设您已经创建了一个可以表示不可数无限集的类MySet。现在让我们考虑一些MySet对象。

我们将特定的MySet标记为“异常”，称之为instance，如果：

instance.Contains(instance)返回true。

同样，如果：

instance.Contains(instance)返回false，则将instance标记为“正常”。

请注意，这个区分对于所有instance都是定义良好的。

现在考虑一个名为paradox的MySet>实例。

我们将paradox定义为包含所有可能的MySet的正常实例的MySet>。

那么paradox.Contains(paradox)应该返回什么？

如果它返回true，则paradox是异常的，并且在自身调用时应该返回false。

如果它返回false，则paradox是正常的，并且在自身调用时应该返回true。

没有办法实现Contains来解决这个悖论，因此没有办法为所有可能的不可数集完全实现ISet。

现在，如果将MySet的基数限制为等于或小于连续体（|R|）的基数，则可以避免这种悖论。

即使如此，您也无法实现Contains或类似的方法，因为这样做相当于解决停机问题。（请记住，所有C#程序的集合的基数等于|Z| < |R|。）

编辑：

为了更全面地说明，以下是我断言“这样做相当于解决停机问题”的解释。

考虑由所有在有限时间内停机（精确地说，对于任何输入都会停机）的C#程序（作为字符串）组成的MySet，称其为paradox2。该集合是“递归可枚举”的，这意味着你可以在其中实现GetEnumerator（不容易，但是可能）。这也意味着它是明确定义的。然而，这个集合不是“可判定的”，因为它的补集不是递归可枚举的。

按照以下方式定义一个C#程序：

using ... //Everything;

public static class Decider {

    private MySet<string> _haltingSet = CreateHaltingSet();

    static void Main(string [] args) {
        Console.WriteLine(_haltingSet.Contains(args[0]));
    }
}

编译以上程序，并将其作为输入传递给自身。会发生什么？

如果您的“Contains”方法已正确实现，则解决了停机问题。但是，我们知道这是不可能的，因此我们只能得出结论：即使对于可数无限集，也不可能正确实现“Contains”。

您可能能够限制您的“MySet＜T＞”类，使其适用于所有可判定集。但是，然后您仍将遇到各种问题，例如函数永远不会在有限时间内停止。

例如，假设我们有一种称为“Real”的任意精度实数类型，让“nonHalting”成为“MySet＜Real＞”的一个实例，其中包括黎曼ζ函数的所有非平凡零点（这是一个可判定集）。 如果您可以正确实现“IsProperSubsetOf”在“nonHalting”上，并在传递所有实部为1/2的复数集合时在有限时间内返回，则可以赢得千禧年奖。

- Michael Graczyk

---

现在，如果你限制MySet<T>的基数等于或小于连续集合(|R|)的基数，那么你就能够解决这个悖论。我愿意做这个（我有点必须，不是吗：P？）。但是，IsSubsetOf如何等同于解决停机问题呢？ - Daniel

我会尝试找出一个例子。 - Michael Graczyk

@Daniel，集合是由指示函数定义的。（如上所述instance.Contains(object)。）计算“a是b的子集”等价于计算“a.Contains返回的真值比b.Contains少”。我认为从这里可以明显地看出，检查此类函数的可能返回值是停机问题。 - CoffeeTableEspresso

Answer 2

表示不可数无限集

让我们在实践中考虑这个声明。例如，当询问集合A是否是集合Z（正整数）的子集时，主题不是Z。不会分析Z中的每个数字。所分析的是问题中的集合A。因为无法将Ak（其中k是1到|A|之间的数字）与Z的每个值（无限）进行比较，所以必须将A中的每个值与构成Z的属性进行比较。如果A中的每个值都满足Z的属性，则A是Z的子集。

如何在代码中表示R和N的并集

与上面的过程相同。R的属性是“任何实数”-在代码中，这可以是“任何不会抛出异常的double”（显然， Math.Pow（-1，.5）会出问题，因此不属于R）。 N的属性是“任何整数”-在代码中，这可以是Math.Floor！= Math.Ceiling的任何数字。它们的并集是它们属性的并集。符合R或N的属性的任何数字-在代码中，这将是任何不会抛出异常以创建或者 Math.Floor！= Math.Ceiling的数字。

总结

要表示不可数的无限集，请使用其属性而不是其值。

---

编辑

N ⊆ R ?

让我们回到属性的想法，因为这是我要追求的主题。N是否是R的子集？对于N是R的子集，则N的属性必须满足R的所有属性。属性列表需要准确。为了表示无穷大的数值，建议使用一个包含可空int数字和普通int符号的类。

public class Infinite
{
 public int? Number { get; set; }
 public int Sign { get; set; }
}

大致如此。Number.Value == null表示无穷大。Sign可用于显示负数（-1）、+-（0）或正数（1）。

回到R的N子集情况。除了之前列出的属性外，N还将有Infinite.Number == null和Infinite.Sign == 0作为其属性的边界。R也是如此。因此，N将能够满足边界属性。接下来是上面定义的属性。我真的被卡住了。我不确定如何证明每个.Floor == .Ceiling的数字都不会引起异常。但是，由于只有9种这些超集（有理数、无理数、整数、实数、复数、虚数、超越数、代数数、自然数），您可以特别定义它们在无限尺度上的相互作用，然后使用更简单的实现进行有限比较。

- Travis J

---

这解决了联合问题，我认为这是最琐碎的问题之一，但仍不是N是否是R的子集问题或枚举问题。尽管如此，我很感激这个（写得很好的）答案 :)。 - Daniel

Answer 3

你需要概括一下“Set”的含义。

如果你要有一个无限集合，你将无法对它进行有意义的枚举，因此你不能通过枚举操作来定义集合操作。

如果你使用一个bool IsMember(f obj)方法来定义一个Set<f>，那么它可以用于无限集合。

你可以将两个集合的并集或交集定义为这两个集合的IsMember方法的逻辑和或逻辑或。

- antlersoft

---

我不确定我理解了 - 鉴于R的IsMember和N的IsMember，你如何确定N是R的子集。并且你如何求它们的交集或并集？ - Daniel

取决于R是否为自然数。如果R是自然数，则N并R为N，N交R为R。 - Tony Hopkinson

@TonyHopkinson 我在谈论如何在代码中实现它 :P.. 我知道如何在纸上做。此外，R并不仅包含自然数 - 它还有无限多的非自然数。 - Daniel

@Daniel -- 交集和并集很简单：(A并B).IsMember(f) = (A.IsMember(f) || B.IsMember(f)); (A交B).IsMember(f) = (A.IsMember(f) && B.IsMember(f)). 对于无限集合来说，判断A是否是B的子集并不容易（事实上，在最一般的情况下是不可能的，正如另一个答案中所示）。你将不得不以符号方式表示IsMember谓词，并证明A的谓词蕴含B。 - antlersoft

@Daniel。我也是这样认为的，这将像数学一样必须用符号和规则来表示。没有人通过枚举N的每个成员并查看它是否是R的成员来证明N是R的子集。 - Tony Hopkinson

Answer 4

这是可能的，但有很多限制，就像符号表达式处理一样。

这里有一个小例子：

class IntSet
{
    int m_first;
    int m_delta;

    public IntSet(int first, int delta)
    {
        m_first = first;
        m_delta = delta;
    }

    public override string ToString()
    {
        StringBuilder sb = new StringBuilder();

        sb.Append('[');
        sb.Append(m_first);
        sb.Append(',');
        sb.Append(m_first + m_delta);
        sb.Append(',');
        sb.Append("...");
        sb.Append(']');

        return sb.ToString();
    }

    public IEnumerable<int> GetNumbers()
    {
        yield return m_first;

        int next = m_first;

        while (true)
        {
            next += m_delta;

            yield return next;
        }
    }
}

- Feng Yuan

Answer 5

你打算用它来做什么呢？你不能枚举它。

我认为我会将其视为万能集合的后代。

我想我会从另一端开始

定义一个始终为真的IsMember的全集，然后定义一个后代，其中如果它是自然数的表示，则IsMember为真。{1,2,3,4}是N的进一步限制。

无论如何都是一个想法。

- Tony Hopkinson