Secuencia entera

Inicio de la secuencia de Fibonacci en un edificio en Gotemburgo

En matemáticas, una secuencia de enteros es una secuencia (es decir, una lista ordenada) de enteros.

Una secuencia de enteros se puede especificar explícitamente dando una fórmula para su término n, o implícitamente dando una relación entre sus términos. Por ejemplo, la secuencia 0, 1, 1, 2, 3, 5, 8, 13,... (la secuencia de Fibonacci) se forma comenzando con 0 y 1 y luego sumando dos términos consecutivos para obtener el siguiente: una descripción implícita. La sucesión 0, 3, 8, 15,... se forma según la fórmula n² − 1 para el nésimo término: una definición explícita.

Alternativamente, una secuencia de enteros puede definirse mediante una propiedad que poseen los miembros de la secuencia y otros enteros no. Por ejemplo, podemos determinar si un entero dado es un número perfecto, aunque no tengamos una fórmula para el nésimo número perfecto.

Ejemplos

Las secuencias enteras que tienen su propio nombre incluyen:

Secuencias computables y definibles

Una secuencia entera es una secuencia computable si existe un algoritmo que, dado n, calcula a_n , para todos los n > 0. El conjunto de secuencias enteras computables es contable. El conjunto de todas las secuencias de enteros es incontable (con una cardinalidad igual a la del continuo), por lo que no todas las secuencias de enteros son computables.

Aunque algunas secuencias de enteros tienen definiciones, no existe una forma sistemática de definir qué significa que una secuencia de enteros sea definible en el universo o en cualquier sentido absoluto (independiente del modelo).

Supongamos que el conjunto M es un modelo transitivo de la teoría de conjuntos ZFC. La transitividad de M implica que los números enteros y las secuencias de números enteros dentro de M son en realidad números enteros y secuencias de números enteros. Una secuencia entera es una secuencia definible relativa a M si existe alguna fórmula P(x) en el idioma de la teoría de conjuntos, con una variable libre y sin parámetros, lo cual es verdadero en M para esa secuencia entera y falso en M para todas las demás secuencias enteras. En cada M, hay secuencias enteras definibles que no son computables, como secuencias que codifican los saltos de Turing de conjuntos computables.

Para algunos modelos transitivos M de ZFC, cada secuencia de enteros en M es definible en relación con M; para otros, solo lo son algunas secuencias enteras (Hamkins et al. 2013). No existe una forma sistemática de definir en M en sí mismo el conjunto de secuencias definibles en relación con M y es posible que ese conjunto ni siquiera exista en alguno de esos M. De manera similar, el mapa del conjunto de fórmulas que definen secuencias enteras en M a las secuencias enteras que definen no se puede definir en M y es posible que no exista en M. Sin embargo, en cualquier modelo que posea dicho mapa de definibilidad, algunas secuencias enteras en el modelo no serán definibles en relación con el modelo (Hamkins et al. 2013).

Si M contiene todas las secuencias enteras, entonces el conjunto de secuencias enteras definibles en M existirá en M y será contable y contable en M.

Secuencias completas

Una secuencia de enteros positivos se denomina secuencia completa si cada entero positivo se puede expresar como una suma de valores en la secuencia, usando cada valor como máximo una vez.