Как я могу реализовать класс бесконечного множества?

Невозможно полностью реализовать ISet<T> для несчетно бесконечных множеств.

Вот доказательство (любезно предоставлено Бертраном Расселом):

Предположим, вы создали класс MySet<T>, который может представлять несчетно бесконечное множество. Теперь давайте рассмотрим некоторые MySet<object> объекты.

Мы помечаем конкретный MySet<object>, называем его instance "ненормальным", если:

instance.Contains(instance) возвращает истину.

Точно так же мы пометим instance как "обычный", если:

instance.Contains(instance) возвращает ложь.

Обратите внимание, что это различие четко определено для всех 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>, включающим все нетривиальные нули дзета-функции Римана (это разрешимое множество). Если вы сможете правильно реализовать IsProperSubsetOf на nonHalting, чтобы вернуть за конечное время набор всех комплексных чисел с действительной частью 1/2 (также разрешимый набор), то вы выиграете Премия тысячелетия.

Вам придется обобщить то, что вы подразумеваете под Set.

Если у вас будет бесконечное множество, вы не сможете получить осмысленное перечисление над ним, поэтому вы не будете определять операции над множествами с операциями над перечислениями.

Если вы определяете Set<f> в терминах метода bool IsMember(f obj), его можно использовать для бесконечных наборов.

Вы определяете объединение или пересечение двух наборов как логическое и или или метода IsMember двух наборов.

представлять несчетно бесконечные множества

Давайте рассмотрим это утверждение в контексте того, как это делается на практике. Например, при запросе погоды набор A является подмножеством набора Z (целые положительные числа), субъект не является Z. Каждое число в Z не анализируется. Анализируется рассматриваемый набор A. Поскольку невозможно сравнить Ak (A sub k, где k — число от 1 до |A|) с каждым значением Z (бесконечным), каждое значение A должно быть по сравнению со свойствами, составляющими Z. Если каждое значение в A удовлетворяет свойствам Z, то A является подмножеством Z.

как вы можете представить в коде R объединение N

Тот же процесс, что и выше. Свойства R - это "любое действительное число" - в коде это может быть "любое двойное число, которое не вызывает исключение" (очевидно, что Math.Pow(-1,.5) вызовет проблемы и в результате не находится в R). Свойства N — «любое целое число» — в коде это может быть любое число, где Math.Floor != Math.Ceiling. Союз этих двух есть союз их свойств. Любое число, которое соответствует свойствам R или N — в коде это будет любое число, которое не вызывает исключение для создания или, которое Math.Floor != Math.Ceiling.

Сводка

Для представления несчетных бесконечных множеств используйте их свойства, а не их значения.

изменения

N ⊆ R?

Давайте вернемся к идее свойств, так как это тема, которую я хотел бы развивать. Является ли N подмножеством R? Чтобы N было подмножеством R, свойства N должны удовлетворять всем свойствам R. Список свойств должен быть точным. Чтобы представить числовое значение бесконечности, я бы предложил использовать класс, который содержит целочисленное число, допускающее значение NULL, и обычный знак int.

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

Что-то в этом духе. Number.Value == null подразумевает бесконечность. Знак можно использовать для отображения отрицательного (-1), +- (0) или положительного (1) значения.

Вернемся к подмножеству N ситуации R. Помимо перечисленных ранее свойств, N также будет иметь Infinite.Number == null и Infinite.Sign == 0 в качестве границ своих свойств. Как и R. Итак, N сможет удовлетворить граничному свойству. Далее будут свойства, определенные выше. Я действительно застрял здесь. Я не уверен, как доказать в коде, что каждое число, которое .Floor == .Ceiling, не вызовет исключения. Однако, поскольку существует только 9 таких типов надмножеств (рациональное, иррациональное, целочисленное, вещественное, сложное, мнимое, трансцендентное, алгебраическое, естественное), вы можете специально определить их взаимодействия в бесконечном масштабе, а затем использовать более простую реализацию для конечных. сравнения.

Что именно вы собираетесь с этим делать. Вы не можете перечислить это.

Я думаю, что буду относиться к нему как к потомку универсального набора.

Я думаю, я бы начал с другого конца

Определите универсальный набор, в котором Ismember всегда истинен. Тогда потомок, в котором IsMember истинен, если он представляет натуральное число {1,2,3,4}, является дополнительным ограничением N

В любом случае мысль

Это возможно с множеством ограничений, как и обработка символьных выражений.

Вот небольшой пример:

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