•  11-12-2019
  •  | 
  •  

题

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

到目前为止，我所拥有的是:我有一个抽象基类Set，它实现了接口ISet。对于有限集，我派生了一个类FiniteSet，它实现了每个set方法。然后我可以这样使用它:

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方法。

有帮助吗？

解决方案

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

这是一个证明（由伯特兰*罗素提供）:

假设你已经创建了一个类 MySet<T> 这可以代表一个不可数的无限集合。现在让我们考虑一些 MySet<object> 物体。

我们给一个特定的标签 MySet<object>, ，叫它 instance, "异常"如果:

instance.Contains(instance) 返回true。

同样，我们会标记 instance 作为"正常"如果:

instance.Contains(instance) 返回false。

请注意，这种区别对所有人都有明确的定义 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.该集合是*递归可枚举"，意味着您可以实现 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函数的所有非平凡零（这是一个可判定集）。如果你能正确地实施 IsProperSubsetOf 上 nonHalting 要在有限的时间内返回，当通过所有复数的集合与实数部分1/2（也是一个可判定的集合），那么你将赢得一个 千年奖。

其他提示

你将不得不概括你的意思。

如果您要有一个无限的集合，您将无法获得有意义的枚举，因此您不会在枚举上定义带有操作的集合操作。

如果在Set<f>方法方面定义了一个生成的IcodeTagcode，它可以用于无限集。

您将两个组定义为两组的逻辑且odemember方法的一个工会或两个集合。

表示无数无限集

让我们在如何在实践中进行检查。例如，当询问天气时，SET A是SET Z（正整数）的子集，主题不是Z.未分析Z中的每个数字。分析的是所讨论的内容，A.因为没有办法比较AK（一个k的子k是k之间的一个数字，其中k在1和|）到z（无限）的每个值，每个值必须是与构成z的属性相比。如果a中的每个值满足z的属性，那么a是z的子集。

如何在Code r Union n 中表示

相同的过程如上所述。 R的属性是“任何实数” - 在代码中，这可能是“任何不抛出异常的双倍”（显然的Math.Pow(-1,.5)将发出问题并且不在R中的结果）。 n的属性是“任何整数” - 在代码中，这可能是Math.floor！= Math.Ceiling的任何数字。这两个人的联盟是其性质的结合。遵守R或N的属性的任何数字，这将是任何未抛出异常的数字，以创建或其中math.floor！= math.ceiling。

摘要

表示不可数无限集，使用它们的属性不是它们的值。

编辑

n⊆r？

让我们回到物业的想法，因为这是我会追求的主题。是r的一个子集？对于n为r的子集，则n的属性必须满足R的属性的 all 。属性列表需要准确。要代表无限远的数值，我会建议使用包含可用的int号和正常int标志的类。 

public class Infinite
{
 public int? Number { get; set; }
 public int Sign { get; set; }
}
. 沿那些线的东西。 node.value== null意味着无限。标志可用于显示负（-1），+ - （0）或正（1）。

回到R情况的N个子集。除了前面列出的属性之外，n还将具有Infinite.number== null和Infinite.sign== 0作为其属性的界限。正如那样，所以，n将能够满足边界属性。接下来将是上面定义的属性。我真的被困在这里。我不确定如何在代码中证明每个数字.floor== .ceiling不会导致例外。但是，由于这些类型的超集中只有9种（Rational，非理性，整数，真实，复杂，虚空，超越，代数，自然），您可以特别地定义其在无限尺度上的相互作用，然后使用更简单的实施比较。

你要做什么。 你不能枚举它。

我认为我是将其视为通用集的后代。

我想我从另一端开始

定义ISMember始终为真的通用集 然后如果它是自然数的表示，那么一个后裔 {1,2,3,4}是N 的进一步限制 无论如何

一个思想

有很多限制，就像符号表达处理一样。

这里是一个少女： 

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;
        }
    }
}
.

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top