Enumeración

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

Listado ordenado de artículos en colección

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 se permite que la lista contenga repeticiones) dependen de la disciplina de estudio y el contexto de un problema dado.

Algunos conjuntos se pueden enumerar mediante un ordenamiento natural (como 1, 2, 3, 4,... para el conjunto de los enteros positivos), pero en otros casos puede ser necesario imponer un ordenamiento (quizás arbitrario). En algunos contextos, como 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 que la producción de una lista explícita de esos elementos.

Combinatoria

En combinatoria, la 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 una de las 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 enumeración de particiones y enumeración de gráficos el objetivo es contar particiones o gráficos que cumplan ciertas condiciones.

Teoría de conjuntos

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.

Listado

Cuando se utiliza una enumeración en un contexto de lista ordenada, imponemos algún tipo de requisito de estructura de ordenación en el conjunto de índices. Si bien podemos hacer que los requisitos sobre el 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. Según esta caracterización, una enumeración ordenada se define como una sobreyección (una relación ontológica) 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 listar el siguiente elemento dado una enumeración parcial.

Contables frente a incontables

A menos que se especifique lo contrario, se hace una enumeración por medio de números naturales. Eso es, un enumeración de un conjunto $S$ es una función bijeactiva de los números naturales $mathbb {N}$ o un segmento inicial ${1,... n}$ de los números naturales a $S$ .

Un conjunto es contable si se puede enumerar, 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}$ del natural números, en cuyo caso, su cardinalidad es $n$ . El conjunto vacío es finito, ya que se puede enumerar mediante el segmento inicial vacío de los números naturales.

El término enumerable conjunto se usa a veces para conjuntos contables. Sin embargo, también se usa a menudo para conjuntos computablemente enumerables, 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 e infinito contable, a menudo es útil usar otra definición que sea equivalente: un conjunto $S$ es contable si y solo si existe una función inyectiva de él a los números naturales.

Ejemplos

Los números naturales son enumerables por la función f()x) x. En este caso ${displaystyle fcolon mathbb {N} to mathbb {N} }$ es simplemente la función de identidad.
$mathbb {Z}$ , el conjunto de enteros es enumerable por ${displaystyle f(x):={frac {1-(-1)^{x},(2,x+1)}{4}}}$ ${displaystyle fcolon mathbb {N} _{0}to mathbb {Z} }$ es una bijeción ya que cada número natural corresponde a exactamente un entero. En el cuadro siguiente figuran los primeros pocos valores de esta enumeración:
x 0 1 2 3 4 5 6 7 8
f()x) 0 1 -1 2 -2 3 -3 4 -4
Todos los conjuntos finitos (no vacíos) son enumerables. Vamos S ser un conjunto finito con n 0 elementos y dejar K = {1,2,...n}. Seleccione cualquier elemento s dentro S y asignación f()n) s. Ahora. S ' = S−s} (donde - denota la diferencia). Seleccione cualquier elemento s ' ▪S ' y asignación f()n−1) = s ' . Continuar este proceso hasta que todos los elementos del conjunto hayan sido asignados un número natural. Entonces... ${displaystyle f:Kto S}$ es una enumeración de S.
Los números reales no tienen una enumeración contable como probada por el argumento diagonal de Cantor y la primera prueba incontable de Cantor.

x	0	1	2	3	4	5	6	7	8
f()x)	0	1	-1	2	-2	3	-3	4	-4

Propiedades

Existe una enumeración para un conjunto (en este sentido) si y sólo si el conjunto es contable.
Si un conjunto es enumerable tendrá una infinidad incontable de diferentes enumeraciones, excepto en los casos degenerados del conjunto vacío o (dependiendo de la definición precisa) se establece con un elemento. Sin embargo, si se requiere que las enumeraciones sean inyectables y permite sólo una forma limitada de parcialidad tal que si f()n) se define entonces f()m) debe definirse para todos m.n, entonces un conjunto finito N elementos tiene exactamente N! enumeraciones.
Una enumeración e de un conjunto S con dominio $mathbb {N}$ induce un bien-orden ≤ en ese conjunto definido por s ≤ t si ${displaystyle min e^{-1}(s)leq min e^{-1}(t)}$ . Aunque el orden puede tener poco que ver con el conjunto subyacente, es útil cuando es necesario algún orden del conjunto.

Ordinales

En la teoría de conjuntos, existe una noción más general de una 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 límite ordinal ω. Esta versión más generalizada amplía la definición antes mencionada para abarcar listados transfinitos.

De acuerdo con esta definición, primer ordinal incontable $omega _{1}$ puede enumerarse por la función de identidad en $omega _{1}$ para que estas dos nociones no coincide. Más generalmente, es un teorema de ZF que cualquier conjunto bien ordenado puede ser enumerado bajo esta caracterización de modo que coincida con relabeling con la enumeración generalizada. Si uno también asume el Axioma de la Elección, entonces todos los conjuntos pueden ser enumerados de modo que coincida con relabeling 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 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 exactamente así. Por lo tanto, para evitar la ambigüedad, se puede usar el término finitamente enumerable o numerable para denotar uno de los tipos correspondientes de enumeraciones contables distinguidas.

Comparación de cardinalidades

Formalmente, la definición más inclusiva de una enumeración de un conjunto S es cualquier sobreyección de un conjunto de índice arbitrario I a S. En este amplio contexto, cada conjunto S puede ser enumerado trivialmente por la función identidad de S sobre sí mismo. Si uno no asume el axioma de elección o una de sus variantes, S no necesita tener ninguna buena ordenación. Incluso si se asume el axioma de elección, S no necesita tener ningún buen ordenamiento natural.

Esta definición general, por lo tanto, se presta a una noción de conteo donde estamos interesados en "cuántos" en lugar de "en qué orden". En la práctica, este significado amplio de enumeración se usa a menudo para comparar los tamaños relativos o 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 en S no implica necesariamente la existencia de una inyección de S en I.

Computabilidad y teoría de la complejidad

En la teoría de la computabilidad uno suele considerar enumeraciones contables con el requisito añadido de que el mapeo de $mathbb {N}$ (conjunto de todos los números naturales) al conjunto enumerado debe ser computable. El conjunto que se enumera se llama entonces recursivamente enumerable (o computadamente enumerable en lenguaje más contemporáneo), refiriéndose al uso de la teoría de recursión en formalizaciones de lo que significa que el mapa 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 referirse a computable enumerable. Sin embargo, estas definiciones caracterizan clases distintas, ya que hay muchos subconjuntos incontables de los números naturales que pueden enumerarse mediante una función arbitraria con dominio ω y solo muchas funciones computables contables. Un ejemplo específico de un conjunto con una enumeración pero no una enumeración computable es el complemento del conjunto detenido.

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 uno, entonces el conjunto de detención sería decidible, lo cual es probablemente 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.

Más resultados...