c# - universo - tipos de conjuntos

¿Cómo puedo implementar una clase de conjunto infinito?

Question

Estoy diseñando una biblioteca de clases para matemáticas discretas, y no puedo pensar en una forma de implementar un conjunto infinito .

Lo que tengo hasta ahora es: tengo una clase base abstracta, Set, que implementa la interfaz ISet. Para conjuntos finitos, obtengo una clase FiniteSet, que implementa cada método de conjunto. Puedo usarlo así:

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}

Ahora quiero representar un conjunto infinito. Tuve la idea de derivar otra clase abstracta del conjunto, InfiniteSet, y los desarrolladores que usan la biblioteca tendrían que derivarse de InfiniteSet para implementar sus propias clases. Proporcionaría conjuntos utilizados comúnmente, como N, Z, Q y R.

Pero no tengo idea de cómo implementaría métodos como Subset y GetEnumerator, incluso estoy empezando a pensar que es imposible. ¿Cómo se enumera un conjunto infinito de una manera práctica, de modo que se puede cruzar / unir con otro conjunto infinito? ¿Cómo se puede verificar, en código, que N es un subconjunto de R? Y en cuanto a la cuestión de la cardinalidad ... Bueno, esa es probablemente una pregunta por separado.

Todo esto me lleva a la conclusión de que mi idea para implementar un conjunto infinito es probablemente el camino equivocado. Te agradecería mucho tu opinión :).

Editar: Para ser claros, también me gustaría representar conjuntos infinitos incontables.

Edit2: Creo que es importante recordar que el objetivo final es implementar ISet, lo que significa que cualquier solución debe proporcionar (como debería) formas de implementar todos los métodos de ISet , los más problemáticos son los métodos de enumeración y el método IsSubsetOf .

Answer 1

¿Qué vas a hacer exactamente con eso? No puedes enumerarlo

Creo que lo estoy tratando como un descendiente del conjunto universal.

Creo que comenzaría desde el otro lado

Definir un conjunto universal donde Ismember es siempre verdadero Entonces un descendiente donde IsMember es verdadero si es una representación de un número natural {1,2,3,4} es una restricción adicional de N

Un pensamiento de todos modos

Answer 2

Es posible con muchas limitaciones, al igual que el manejo de expresiones simbólicas.

Aquí hay un pequeño ejemplo:

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

Answer 3

No es posible implementar completamente ISet<T> para conjuntos incontables infinitos.

Aquí hay una prueba (cortesía de Bertrand Russell):

Supongamos que ha creado una clase MySet<T> que puede representar un conjunto incontable infinito. Ahora consideremos algunos MySet<object> .

Etiquetamos un MySet<object> , lo llamamos instance , " anormal " si:

instance.Contains(instance) devuelve true.

Del mismo modo, etiquetaríamos la instance como " normal " si:

instance.Contains(instance) devuelve falso.

Tenga en cuenta que esta distinción está bien definida para todas las instance .

Ahora considere una instancia de MySet<MySet<object>> llamada paradox .

Definimos la paradox como MySet<MySet<object>> que contiene todas las instancias normales posibles de MySet<object> .

¿Qué debería paradox.Contains(paradox) return?

Si devuelve true , entonces la paradox es anormal y debería haber resultado false cuando se invoca a sí misma.

Si devuelve false , la paradox es normal , y debería haber regresado true cuando se llamaba a sí misma.

No hay forma de implementar Contains para resolver esta paradoja, por lo que no hay forma de implementar completamente ISet<T> para todos los posibles conjuntos incontables.

Ahora, si restringe la cardinalidad de MySet<T> para que sea igual o menor que la cardinalidad del continuo (| R |), podrá evitar esta paradoja.

Incluso entonces, no podrá implementar Contains o métodos similares porque hacerlo sería equivalente a resolver el problema de detención. (Recuerde que el conjunto de todos los programas de C# tiene cardinalidad igual a | Z | <| R |.)

EDITAR

Para ser más completo, aquí hay una explicación de mi afirmación de que "hacerlo sería equivalente a resolver el problema de detención".

Considere el MySet<string> que consiste en todos los programas de C # (como cadenas) que se detienen en un período de tiempo finito (supongamos que se detienen para cualquier entrada, para ser precisos). Llámalo paradox2 . El conjunto es * recursivamente enumerable ", lo que significa que puede implementar GetEnumerator en él (no fácilmente, pero es posible). Eso también significa que está bien definido. Sin embargo, este conjunto no es" decidible "porque su complemento no es recursivo. enumerable.

Defina un programa C # de la siguiente manera:

using ... //Everything;

public static class Decider {

    private MySet<string> _haltingSet = CreateHaltingSet();

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

Compila el programa anterior y pásalo como entrada a sí mismo. ¿Lo que pasa?

Si su método Contains se implementa correctamente, entonces ha resuelto el problema de detención. Sin embargo, sabemos que eso no es posible, por lo que solo podemos concluir que no es posible implementar Contains adecuada, incluso para conjuntos infinitamente contables.

Es posible que pueda restringir su MySet<T> para que funcione en todos los conjuntos decidibles. Sin embargo, entonces todavía se encontrará con todo tipo de problemas con su función que nunca se detiene en un período finito de tiempo.

Como ejemplo, imaginemos que tenemos un tipo real de precisión arbitrario llamado Real , y dejemos que nonHalting sea ​​una instancia de MySet<Real> que incluya todos los ceros no triviales de la función Zeta de Riemann (este es un conjunto decidible). Si puede implementar correctamente IsProperSubsetOf en nonHalting para regresar en un tiempo finito cuando pase el conjunto de todos los números complejos con la parte 1/2 real (también un conjunto decidible), entonces ganará un Premio Milenio.

Answer 4

Tendrás que generalizar lo que quieres decir con Set.

Si va a tener un conjunto infinito, no podrá obtener una Enumeración significativa sobre él, por lo que no definirá las operaciones de conjunto con operaciones en enumeraciones.

Si define un Set<f> en términos de un bool IsMember(f obj) , se puede usar para conjuntos infinitos.

Define una unión o intersección de dos conjuntos como el método lógico y o del método IsMember de los dos conjuntos.

Answer 5

representar incontables conjuntos infinitos

Examinemos esta afirmación en el contexto de cómo se hace en la práctica. Por ejemplo, cuando se pregunta por el clima, un conjunto A es un subconjunto del conjunto Z (enteros positivos), el sujeto no es Z. No se analiza cada número en Z. Lo que se analiza es el conjunto en cuestión, A. Debido a que no hay forma de comparar Ak (A sub k donde k es un número entre 1 y | A |) con cada valor de Z (infinito), cada valor de A debe ser comparado con las propiedades que constituyen Z. Si cada valor en A satisface las propiedades de Z, A es un subconjunto de Z.

¿Cómo se puede representar en el código R union N

El mismo proceso que el anterior. Las propiedades de R son "cualquier número real" - en el código esto podría ser "cualquier doble que no arroje una excepción" (Obviamente Math.Pow(-1,.5) dará problemas y no está en R como resultado ) Las propiedades de N son "cualquier número entero"; en código, podría ser cualquier número donde Math.Floor! = Math.Ceiling. La unión de estos dos es la unión de sus propiedades. Cualquier número que se adhiera a las propiedades de R o N - en código esto sería cualquier número que no arroje una excepción para crear o Math.Floor! = Math.Ceiling.

Resumen

Para representar conjuntos infinitos incontables, use sus propiedades, no sus valores.

editar

N ⊆ R?

Volvamos a la idea de propiedades ya que ese es el tema que buscaría. ¿Es N un subconjunto de R? Para que N sea un subconjunto de R, las propiedades de N deben satisfacer todas las propiedades de R. La lista de propiedades deberá ser precisa. Para representar el valor numérico de infinito, sugeriría usar una clase que contenga un número int nullable y un signo int normal.

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

Algo en esa línea. Number.Value == null implica infinito. El signo se puede usar para mostrar negativo (-1), + - (0) o positivo (1).

Volver al subconjunto N de la situación R. Además de las propiedades enumeradas anteriormente, N también tendría Infinite.Number == null e Infinite.Sign == 0 como límites para sus propiedades. Como lo haría R. Entonces, N podría satisfacer la propiedad de límite. Siguiente serían las propiedades definidas arriba. De hecho, me quedé atrapado aquí. No estoy seguro de cómo probar en el código que cada número que .Floor == .Ceiling no cause una excepción. Sin embargo, dado que solo hay 9 de estos tipos de súper conjuntos (Racional, Irracional, Integer, Real, Complejo, Imaginario, Trascendental, Algebraico, Natural), usted podría definir especialmente sus interacciones en la escala infinita y luego usar una implementación más simple para lo finito. comparaciones