如何实现无限集类?

I'm designing a class library for discrete mathematics, and I can't think of a way to implement an infinite set.

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

What I have so far is: I have an abstract base class, Set, which implements the interface ISet. For finite sets, I derive a class FiniteSet, which implements each set method. I can then use it like this:

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

Now I want to represent an infinite set. I had the idea of deriving another abstract class from set, InfiniteSet, and then developers using the library would have to derive from InfiniteSet to implement their own classes. I'd supply commonly used sets, such as N, Z, Q, and R.

现在我想表示一个无限集，我有一个想法，从集合，InfiniteSet推导另一个抽象类，然后使用这个库的开发人员必须从InfiniteSet推导来实现他们自己的类。我将提供常用的集合，如N、Z、Q和R。

But I have no idea how I'd implement methods like Subset and GetEnumerator - I'm even starting to think it's impossible. How do you enumerate an infinite set in a practical way, so that you can intersect/union it with another infinite set? How can you check, in code, that N is a subset of R? And as for the issue of cardinality.. Well, that's probably a separate question.

但我不知道如何实现子集和GetEnumerator之类的方法——我甚至开始认为这是不可能的。如何以实际的方式枚举一个无限集，以便与另一个无限集相交?如何在代码中证明N是R的子集?至于基数问题。这可能是另一个问题。

All this leads me to the conclusion that my idea for implementing an infinite set is probably the wrong way to go. I'd very much appreciate your input :).

所有这些使我得出结论，我实现无限集的想法可能是错误的。非常感谢您的建议。

Edit: Just to be clear, I'd also like to represent uncountably infinite sets.

编辑:澄清一下，我还想表示无穷无尽的集合。

Edit2: I think it's important to remember that the ultimate goal is to implement ISet, meaning that any solution has to provide (as it should) ways to implement all of ISet's methods, the most problematic of which are the enumeration methods and the IsSubsetOf method.

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

5 个解决方案

#1

It is not possible to fully implement ISet<T> for uncountably infinite sets.

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

Here's a proof (courtesy of Bertrand Russell):

这里有一个证据(由伯特兰·罗素提供):

Suppose you have created a class MySet<T> that can represent an uncountably infinite set. Now let's consider some MySet<object> objects.

假设您创建了一个MySet 类，它可以表示一个不可计数的无限集。

We label a particular MySet<object>, call it instance, "abnormal" if:

我们将一个特定的MySet

instance.Contains(instance) returns true.

instance.Contains(实例)返回true。

Similarly, we would label instance as "normal" if:

同样，如果:

instance.Contains(instance) returns false.

instance.Contains(实例)返回false。

Note that this distinction is well-defined for all instance.

注意，这个区别对于所有实例都是定义良好的。

Now consider an instance of MySet<MySet<object>> called paradox.

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

We define paradox as the MySet<MySet<object>> which contains all possible normal instances of MySet<object>.

我们将悖论定义为MySet< set

What should paradox.Contains(paradox) return?

应该paradox.Contains(悖论)返回?

If it returns true, then paradox is abnormal and should have returned false when called on itself.

如果返回true，则悖论是不正常的，在调用本身时应该返回false。

If it returns false then paradox is normal, and should have returned true when called on itself.

如果它返回false，那么悖论是正常的，当调用它自己时，它应该返回true。

There is no way to implement Contains to resolve this paradox, so there is no way to fully implement ISet<T> for all possible uncountable sets.

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

Now, if you restrict the cardinality of MySet<T> to be equal to or less than the cardinality of the continuum (|R|), then you will be able to get around this paradox.

现在，如果你限制MySet 的基数等于或小于连续体的基数(|R|)，你就能绕过这个悖论。

Even then, you will not be able to implement Contains or similar methods because doing so would be equivalent to solving the halting problem. (Remember that the set of all C# programs has cardinality equal to |Z| < |R|.)

即使这样，您也不能实现包含或类似的方法，因为这样做将等同于解决停机问题。(记住，所有c#程序的集合具有基数等于|Z| < | r|)。

EDIT

编辑

To be more thorough, here's is an explanation of my assertion that "doing so would be equivalent to solving the halting problem."

更彻底地说，这里有一个对我的断言的解释:“这样做将等同于解决停止问题。”

Consider the MySet<string> that consists of all C# programs (as strings) which halt in a finite amount of time (suppose they halt for any input, to be precise). Call it paradox2. The set is *recursively enumerable", meaning that you could implement GetEnumerator on it (not easily, but it is possible). That also means that it is well defined. However, this set is not "decidable" because its complement is not recursively enumerable.

考虑MySet ，它由所有c#程序(作为字符串)组成，在有限的时间内停止(准确地说，假设它们为任何输入停止)。称之为paradox2。集合是*递归可枚举的，这意味着您可以在它上面实现GetEnumerator(不容易实现，但这是可能的)。这也意味着它定义得很好。但是，这个集合是不可“确定的”，因为它的补语不是递归可枚举的。

Define a C# program as follows:

定义一个c#程序如下:

using ... //Everything;

public static class Decider {

    private MySet<string> _haltingSet = CreateHaltingSet();

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

Compile the above program, and pass it as input to itself. What happens?

编译上述程序，并将其作为输入传递给自己。会发生什么呢?

If your Contains method is properly implemented, then you've solved the halting problem. However, we know that that's not possible, so we can only conclude that it is not possible to properly implement Contains, even for countably infinite sets.

如果Contains方法得到了正确的实现，那么就解决了停止问题。但是，我们知道这是不可能的，所以我们只能得出结论，即使对于可数无穷集，也不可能正确地实现Contains。

You might be able to restrict your MySet<T> class to work for all decidable sets. However, then you will still run into all sorts of problems with your function never halting in a finite amount of time.

您可能可以将MySet 类限制为所有可决定集的工作。然而，你仍然会遇到各种各样的问题你的函数永远不会在有限的时间内停止。

As an example, let's pretend we have an arbitrary precision real type called Real, and let's let nonHalting be an instance of MySet<Real> that includes all the non-trivial zeros of the Riemann Zeta function (this is a decidable set). If you can properly implement IsProperSubsetOf on nonHalting to return in a finite amount of time when passed the set of all complex numbers with real part 1/2 (also a decidable set), then you'll win a Millennium Prize.

举个例子，假设我们有一个任意精度的实类型，叫做实数，让我们让非停止成为MySet< real >的一个实例，它包含了Riemann Zeta函数的所有非平凡的零(这是一个可判定的集合)。如果您能够正确地实现IsProperSubsetOf on non - halt，并在有限的时间内返回所有实部1/2(也是一个可决定的集合)的复数集，那么您将获得千年奖。

#2

You're going to have to generalize what you mean by Set.

你必须推广你所说的集合。

If you are going to have an infinite set, you won't be able to get a meaningful Enumeration over it, so you won't define set operations with operations on enumerations.

如果你将有一个无限集，你将不能得到一个有意义的枚举，所以你不会定义集合操作和对枚举的操作。

If you define a Set<f> in terms of a bool IsMember(f obj) method, it can be used for infinite sets.

如果您用bool IsMember(f obj)方法定义一个集合，它可以用于无限集。

You define a union or intersection of two sets as the logical and or or of the IsMember method of the two sets.

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

#3

represent uncountably infinite sets

代表不可数无限集

Lets examine this statement in the context of how it is done in practice. For example, when asking weather a set A is a subset of set Z (positive integers) the subject is not Z. Every number in Z is not analyzed. What is analyzed is the set in question, A. Because there is no way to compare Ak (A sub k where k is a number between 1 and |A|) to every value of Z (infinite), every value of A must be compared to the properties which constitute Z. If every value in A satisfies the properties of Z then A is a subset of Z.

让我们在实践中如何实现这个语句的上下文中进行检查。例如，当问是否集合a是集合Z(正整数)的子集时，主语不是Z。分析是设置问题,因为没有办法比较Ak(下标k,k是一个数字1 - | |)每个Z(无限)的价值,每一个价值必须与属性构成Z如果每个值满足Z的属性是Z的一个子集。

how can you represent in code R union N

如何在代码R联盟N中表示

Same process as above. The properties of R are "any real number" - in code this could be "any double that doesn't throw an exception" (Obviously Math.Pow(-1,.5) will give issues and is not in R as a result). The properties of N are "any integer" - in code this could be any number where Math.Floor != Math.Ceiling. The union of these two is the union of their properties. Any number which adheres to the properties of R or N - in code this would be any number which does not throw an exception to create or which Math.Floor != Math.Ceiling.

同样的过程。R的属性是“任意实数”——在代码中，这可以是“任何不会抛出异常的双精度浮点数”(显然，Math.Pow(-1，.5)会产生问题，因此不会出现在R中)。N的性质是“任意整数”——在代码中，这可以是数学中的任意数。地板! = Math.Ceiling。这两者的结合就是他们的财产的结合。任何符合R或N属性的数——在代码中，这将是任何不抛出异常的数，或者是哪个数学。地板! = Math.Ceiling。

Summary

总结

To represent uncountable infinite sets, use their properties not their values.

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

edits

编辑

N ⊆ R ?

N⊆R ?

Lets go back to the properties idea since that is the theme I would pursue. Is N a subset of R? For N to be a subset of R then the properties of N must satisfy all of the properties of R. The list of properties will need to be accurate. To represent the numeric value of infinity, I would suggest using a class which contains a nullable int number and a normal int sign.

让我们回到属性的概念，因为这是我要追求的主题。N是R的子集吗?对于N是R的一个子集那么N的性质必须满足R的所有性质，属性列表必须准确。要表示无穷大的数值，我建议使用包含可空int数和普通int符号的类。

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

Something along those lines. Number.Value == null implies infinite. The Sign can be used to show negative (-1), +- (0), or positive (1).

的事情等。号码。Value == null表示无限。这个符号可以用来表示负数(-1)、正数(0)或正数(1)。

Back to the N subset of R situation. Aside from the properties listed earlier, N would also have Infinite.Number == null and Infinite.Sign == 0 as a bounds for its properties. As would R. So, N would be able to satisfy the boundary property. Next would be the properties defined above. I actually got stuck here. I am not sure how to prove in code that every number which .Floor == .Ceiling will not cause an exception. However, since there are only 9 of these types of super sets (Rational, Irrational, Integer, Real, Complex, Imaginary, Transcendental, Algebraic, Natural) you could specially define their interactions on the infinite scale and then use a simpler implementation for finite comparisons.

回到R的N个子集。除了前面列出的属性之外，N也有无穷大。Number = null和Infinite。符号== 0是它的性质的边界。就像r, N可以满足边界性质。接下来是上面定义的属性。我被困在这里了。我不知道如何在代码中证明. floor = . ceiling = . ceiling的每一个数字都不会引发异常。然而，由于只有9种类型的超集(理性的、不合理的、整数的、真实的、复杂的、虚构的、超越的、代数的、自然的)，您可以在无限的范围内定义它们的交互，然后用一个更简单的实现来进行有限的比较。

#4

What exactly are you going to do with it. You can't enumerate it.

你到底要用它做什么?你不能列举。

I thinking I be treating it as a descendant of the universal set.

我认为我把它当作宇宙集合的后代。

I think I'd start from the other end

我想我应该从另一端开始

Define a Universal set where Ismember is always true Then a descendant where IsMember is true if it's a representation of a natural number {1,2,3,4} is a further restriction of N

定义一个通用集合，其中Ismember总是为真，那么如果Ismember是一个自然数{1,2,3,4}的表示，则Ismember是真，那么Ismember就是真，这是N的进一步限制

A thought anyway

一个思想无论如何

#5

It's possible with lots of limitations, just like symbolic expression handling.

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

Here is a little example:

这里有一个小例子:

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

#1