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.

Christianly

Creating an infinite set is very easy with yield return msdn.microsoft.com/en-us/library/9k7k7cf0.aspx – Nidifugous

@Nidifugous I don't really see how that's relevant to any of the issues here, other than implementing enumeration - which still leaves the issue of implementing it 'practically.' – Christianly

Creating a countably infinite set is easy with yield return. – Udometer

@Christianly What Michael said. Sorry if I misunderstood the question. – Nidifugous

No, it's all right, it's probably my fault for not specifying that I would also like to represent uncountably infinite sets - I'll edit my question to reflect this. – Christianly

By definition, you cannot enumerate over an uncountable set. If you are willing to give up enumeration, then implementing the set should be trivial (just have a predicate that checks for membership. Intersections AND two predicates, and unions OR them). – Udometer

I'm not exactly willing to give up enumeration, because then I'd have to give up ISet (right?). And even if I were, I still don't think that the problem becomes trivial: I don't see how the issue of writing code that checks if N is a subset of R is fixed. – Christianly

Well, if you're not worried about your code executing in finite time, then it is all trivial.... You are right though, other than membership tests, unions, and intersections, I don't see any way you can implement the set. I'll give a proof as an answer. – Udometer

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.

Udometer

"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." I'm willing to do this (I kind of have to, don't I :P?). But how does IsSubsetOf equate to solving the halting problem? – Christianly

I will try to figure out an example. – Udometer

@Daniel, the sets are defined by an indicator function. (instance.Contains(object) above.) Calculating "a is a subset of b" is equivalent to calculating "a.Contains returns true for less things than b.Contains". I think from here it should be obvious that checking the possible return values of functions like this is the halting problem. – Brooking

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.

Grodno

I'm not sure I understand - given the IsMember of R and the IsMember of N, how can you determine that N is a subset of R.. And how can you intersect them, or union them? – Christianly

Depends on whether R is typed. If R is natural numbers then N union R is N, and N intersect R is R. – Gravy

@TonyHopkinson I'm talking about how you can do it in code :P.. I know how to do it on paper. And also, R does not contain only natural numbers - it has uncountably infinite more non-natural numbers. – Christianly

@Christianly -- Intersection and union are easy: (A union B).IsMember(f) = (A.IsMember(f) || B.IsMember(f)); (A intersection B).IsMember(f) = (A.IsMember(f) && B.IsMember(f)). Testing that A is a subset of B is not easy (in fact, impossible in the most general case as shown in another answer) for infinite sets; you will have to represent the IsMember predicate symbolically and prove that A's predicate implies B. – Grodno

@Daniel. So was I, this is going to have to be symbols and rules just like the math is. No one has ever proved that N is a subset of R, by enumerating each memmber of N and seeing if it's a member of R, have they.... – Gravy

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

how can you represent in code R union 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.

Summary

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

---

edits

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.

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

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.

Baku

This fixes the unionizing problem, which in my opinion is the most trivial one, but still not the is N a subset of R? problem, or the enumeration problem. I appreciate the (well-written) answer though :). – Christianly

Answer 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

A thought anyway

Gravy

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

Muoimuon