如何实现无限集类？

Question

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

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

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的子集？至于基数问题..嗯,这可能是一个单独的问题.

所有这些使我得出结论,我实现无限集的想法可能是错误的方法.我非常感谢你的意见:).

编辑:为了清楚起见,我也想代表无数的无限集.

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

Answer 1

不可能完全实现ISet<T>无数无限集.

这是一个证明(由Bertrand Russell提供):

假设您已经创建了一个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>包含Riemann Zeta函数的所有非平凡零点的实例(这是一个可判定的集合).如果你能正确地实现IsProperSubsetOf上nonHalting时通过与实部1/2(也可判定一组)设定的所有复杂的数字在有限的时间后返回,那么你会赢得一个千禧年大奖.