How can I implement an infinite set class?

Question

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:

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.

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.

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.

Answer 1

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

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.

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

instance.Contains(instance) returns true.

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

instance.Contains(instance) returns false.

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

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

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

What should paradox.Contains(paradox) return?

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

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

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.

---

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.

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|.)

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.

Define a C# program as follows:

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.

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.

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.

Answer 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.

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