Una enumeración es una lista completa y ordenada de todos los elementos de una colección. El término se usa comúnmente en matemáticas e informática 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 la lista puede contener 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 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 usa 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 en 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, cada uno de los cuales consta de todas las permutaciones de algún conjunto finito. Hay 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 gráficos, el objetivo es contar particiones o gráficos 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 enumerado 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 ordenación 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 . Según 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 orden 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 contable si puede ser enumerado, es decir, si existe una enumeración del mismo. De lo 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, ya que puede enumerarse mediante el segmento inicial vacío de los números naturales.
El términoEl 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 cuales se puede calcular una función de enumeración con un algoritmo.
Para evitar distinguir entre un conjunto finito y un conjunto infinito contable, suele ser útil utilizar otra definición que sea equivalente: un conjunto S es contable si y sólo si existe una función inyectiva a partir 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 . Según 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 la enumeración mencionada anteriormente es el caso especial en el que α 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 de identidad 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 generalizado. Si también se asume el axioma de elección , entonces todos los conjuntos se pueden enumerar 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 por defecto entre este grupo de matemáticos de una enumeración de un conjunto tiende a ser cualquier secuencia α arbitraria que enumere 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 ambigüedades, se puede utilizar el término finitamente enumerable o numerable 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 de índices arbitrario I sobre S. En este contexto amplio, todo conjunto S puede enumerarse trivialmente mediante la función identidad de S sobre sí mismo. Si no se asume el axioma de elección o una de sus variantes, S no necesita tener ningún buen ordenamiento . Incluso si se asume 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" más que "en qué orden". En la práctica, este significado amplio de enumeración se utiliza a menudo para comparar los tamaños relativos o cardinalidades de diferentes conjuntos. Si uno trabaja en la teoría de conjuntos de Zermelo-Fraenkel sin el axioma de elección, es posible que desee 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 a S no tiene por qué ser necesariamente implican la existencia de una inyección de S en I.
En la teoría de la computabilidad, a menudo se consideran enumeraciones contables con el requisito adicional de que la asignació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), en referencia al uso de la teoría de la recursividad en las formalizaciones de lo que significa que el mapa sea computable.
En este sentido, un subconjunto de 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 incontables subconjuntos de números naturales que pueden enumerarse mediante una función arbitraria con dominio ω y solo un número 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 del listado es importante. Existe una enumeración computable del conjunto de detención, pero no una que enumere los elementos en orden creciente. Si hubiera uno, 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 los algoritmos de enumeración .
La definición del diccionario de enumeración en Wikcionario.
