12

我正在为离散数学设计一个类库，但我想不出一种方法来实现无限集。

到目前为止我所拥有的是：我有一个抽象基类 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}

现在我想代表一个无限集。我的想法是从集合 InfiniteSet 派生另一个抽象类，然后使用该库的开发人员必须从 InfiniteSet 派生来实现自己的类。我会提供常用的集合，例如 N、Z、Q 和 R。

但我不知道如何实现像 Subset 和 GetEnumerator 这样的方法——我什至开始认为这是不可能的。您如何以实用的方式枚举一个无限集，以便您可以将它与另一个无限集相交/联合？如何在代码中检查 N 是 R 的子集？至于基数问题。嗯，这可能是一个单独的问题。

所有这一切使我得出结论，我实现无限集的想法可能是错误的方法。我非常感谢您的意见:)。

编辑：为了清楚起见，我还想代表不可数的无限集。

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

4

5 回答 5

7

ISet<T>对于不可数的无限集，不可能完全实现。

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

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

MySet<object>如果出现以下情况，我们将其标记为instance“异常”：

instance.Contains(instance)返回真。

同样，如果出现以下情况，我们将标记instance为“正常”：

instance.Contains(instance)返回假。

请注意，这种区别对所有instance.

MySet<MySet<object>>现在考虑一个被调用的实例paradox。

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

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

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

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

没有办法Contains解决这个悖论，所以没有办法完全实现ISet<T>所有可能的不可数集。

现在，如果您将 的基数限制MySet<T>为等于或小于连续统的基数 (|R|)，那么您将能够绕过这个悖论。

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

编辑

更彻底地说，这里是对我的断言的解释，即“这样做就等于解决停机问题”。

考虑MySet<string>由在有限时间内停止的所有 C# 程序（作为字符串）组成的（假设它们为任何输入而停止，准确地说）。调用它paradox2。该集合是 *recursively enumerable”，这意味着您可以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>它包括黎曼 Zeta 函数的所有非平凡零点（这是一个可判定的集合）。如果您可以正确实现IsProperSubsetOfonnonHalting在有限时间内返回实部为 1/2 的所有复数的集合（也是可判定的集合），那么您将赢得千年奖。

于 2012-07-25T23:16:50.387 回答
2

表示不可数的无限集

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

你怎么能在代码 R union N 中表示

与上述相同的过程。R 的属性是“任何实数” - 在代码中这可能是“任何不引发异常的双精度数”（显然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 意味着无限。符号可用于显示负数 (-1)、+- (0) 或正数 (1)。

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

于 2012-07-25T23:19:40.650 回答
2

您将不得不概括您所说的 Set 的含义。

如果您将拥有一个无限集，您将无法获得有意义的枚举，因此您不会使用枚举操作来定义集合操作。

如果根据方法定义 a Set<f>，bool IsMember(f obj)它可以用于无限集。

您将两个集合的并集或交集定义为两个集合的 IsMember 方法的逻辑与或或。

于 2012-07-25T22:43:32.813 回答
0

你到底打算用它做什么。你无法枚举它。

我想我把它当作通用集的后代。

我想我会从另一端开始

定义一个 Ismember 始终为 true 的通用集 如果 IsMember 是自然数 {1,2,3,4} 的表示，则其后代为 true 是 N 的进一步限制

反正一个想法

于 2012-07-25T23:00:26.810 回答
0

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

这是一个小例子：

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;
        }
    }
}
于 2012-07-26T00:36:59.783 回答