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.

Was it helpful?

Solution

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.

OTHER TIPS

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.

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.

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

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;
        }
    }
}
Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top