Una enumeración es una lista completa y ordenada de todos los elementos de una colección. El término se utiliza comúnmente en matemáticas y ciencias de la computación para referirse a una lista de todos los elementos de un conjunto . Los requisitos precisos para una enumeración (por ejemplo, si el conjunto debe ser finito o si se permite que la lista contenga repeticiones) dependen de la disciplina de estudio y del contexto de un problema determinado.
Algunos conjuntos pueden enumerarse mediante un orden natural (como 1, 2, 3, 4, ... para el conjunto de los números enteros positivos ), pero en otros casos puede ser necesario imponer un orden (quizás arbitrario). En algunos contextos, como en la combinatoria enumerativa , el término enumeración se utiliza más en el sentido de contar , con énfasis en la determinación del número de elementos que contiene un conjunto, en lugar de la producción de una lista explícita de esos elementos.
En combinatoria, enumeración significa contar , es decir, determinar el número exacto de elementos de conjuntos finitos, generalmente agrupados en familias infinitas, como la familia de conjuntos que consiste cada uno de ellos en todas las permutaciones de algún conjunto finito. Existen subáreas florecientes en muchas ramas de las matemáticas que se ocupan de enumerar en este sentido objetos de tipos especiales. Por ejemplo, en la enumeración de particiones y la enumeración de grafos, el objetivo es contar particiones o grafos que cumplan ciertas condiciones.
En la teoría de conjuntos , la noción de enumeración tiene un sentido más amplio y no requiere que el conjunto que se enumera sea finito.
Cuando se utiliza una enumeración en un contexto de lista ordenada , imponemos algún tipo de requisito de estructura de ordenamiento en el conjunto de índices . Si bien podemos hacer que los requisitos de ordenamiento sean bastante laxos para permitir una gran generalidad, el requisito previo más natural y común es que el conjunto de índices esté bien ordenado . De acuerdo con esta caracterización, una enumeración ordenada se define como una sobreyección (una relación sobre) con un dominio bien ordenado. Esta definición es natural en el sentido de que un buen ordenamiento dado en el conjunto de índices proporciona una forma única de enumerar el siguiente elemento dada una enumeración parcial.
A menos que se especifique lo contrario, una enumeración se realiza mediante números naturales . Es decir, una enumeración de un conjunto S es una función biyectiva de los números naturales o un segmento inicial {1, ..., n } de los números naturales a S .
Un conjunto es numerable si es enumerable, es decir, si existe una enumeración del mismo. En caso contrario, es incontable . Por ejemplo, el conjunto de los números reales es incontable.
Un conjunto es finito si puede enumerarse mediante un segmento inicial propio {1, ..., n } de los números naturales, en cuyo caso, su cardinalidad es n . El conjunto vacío es finito, pues puede enumerarse mediante el segmento inicial vacío de los números naturales.
El términoEl término "conjunto enumerable " se utiliza a veces para conjuntos contables. Sin embargo, también se utiliza a menudo paraconjuntos enumerables computablemente, que son los conjuntos contables para los que se puede calcular una función de enumeración con un algoritmo.
Para evitar distinguir entre un conjunto finito y un conjunto infinito contable, a menudo es útil utilizar otra definición que es equivalente: un conjunto S es contable si y sólo si existe una función inyectiva de él en los números naturales.
En la teoría de conjuntos , existe una noción más general de enumeración que la caracterización que requiere que el dominio de la función de enumeración sea un segmento inicial de los números naturales donde el dominio de la función de enumeración puede asumir cualquier ordinal . Bajo esta definición, una enumeración de un conjunto S es cualquier sobreyección de un ordinal α sobre S . La versión más restrictiva de enumeración mencionada anteriormente es el caso especial donde α es un ordinal finito o el primer ordinal límite ω. Esta versión más generalizada extiende la definición antes mencionada para abarcar listados transfinitos .
Según esta definición, el primer ordinal incontable puede enumerarse mediante la función identidad en de modo que estas dos nociones no coincidan. De manera más general, es un teorema de ZF que cualquier conjunto bien ordenado puede enumerarse bajo esta caracterización de modo que coincida hasta el reetiquetado con la enumeración de listado generalizada. Si también se supone el Axioma de Elección , entonces todos los conjuntos pueden enumerarse de modo que coincida hasta el reetiquetado con la forma más general de enumeraciones.
Dado que los teóricos de conjuntos trabajan con conjuntos infinitos de cardinalidades arbitrariamente grandes , la definición predeterminada entre este grupo de matemáticos de una enumeración de un conjunto tiende a ser cualquier α-secuencia arbitraria que enumera exactamente todos sus elementos. De hecho, en el libro de Jech, que es una referencia común para los teóricos de conjuntos, una enumeración se define como exactamente esto. Por lo tanto, para evitar la ambigüedad, se puede usar el término finitamente enumerable o denumerable para denotar uno de los tipos correspondientes de enumeraciones contables distinguidas.
Formalmente, la definición más inclusiva de una enumeración de un conjunto S es cualquier sobreyección de un conjunto índice arbitrario I sobre S. En este contexto amplio, cada conjunto S puede enumerarse trivialmente mediante la función identidad de S sobre sí mismo. Si no se supone el axioma de elección o una de sus variantes, S no necesita tener ningún buen ordenamiento . Incluso si se supone el axioma de elección, S no necesita tener ningún buen ordenamiento natural.
Por lo tanto, esta definición general se presta a una noción de conteo en la que nos interesa "cuántos" en lugar de "en qué orden". En la práctica, este amplio significado de enumeración se utiliza a menudo para comparar los tamaños relativos o las cardinalidades de diferentes conjuntos. Si se trabaja en la teoría de conjuntos de Zermelo-Fraenkel sin el axioma de elección, se puede querer imponer la restricción adicional de que una enumeración también debe ser inyectiva (sin repetición) ya que en esta teoría, la existencia de una sobreyección de I sobre S no necesariamente implica la existencia de una inyección de S sobre I.
En la teoría de la computabilidad, a menudo se consideran enumeraciones contables con el requisito adicional de que la aplicación de (conjunto de todos los números naturales) al conjunto enumerado debe ser computable . El conjunto que se enumera se denomina recursivamente enumerable (o computablemente enumerable en un lenguaje más contemporáneo), haciendo referencia al uso de la teoría de la recursión en las formalizaciones de lo que significa que la aplicación sea computable.
En este sentido, un subconjunto de los números naturales es computablemente enumerable si es el rango de una función computable. En este contexto, enumerable puede usarse para significar computablemente enumerable. Sin embargo, estas definiciones caracterizan clases distintas ya que hay una cantidad incontable de subconjuntos de los números naturales que pueden enumerarse mediante una función arbitraria con dominio ω y solo una cantidad contable de funciones computables. Un ejemplo específico de un conjunto con una enumeración pero no una enumeración computable es el complemento del conjunto de detención .
Además, esta caracterización ilustra un lugar donde el orden de la lista es importante. Existe una enumeración computable del conjunto de detención, pero no una que enumere los elementos en un orden creciente. Si hubiera una, entonces el conjunto de detención sería decidible , lo cual es demostrablemente falso. En general, ser recursivamente enumerable es una condición más débil que ser un conjunto decidible .
La noción de enumeración también se ha estudiado desde el punto de vista de la teoría de la complejidad computacional para diversas tareas en el contexto de algoritmos de enumeración .
La definición del diccionario de enumeración en Wikcionario
