En matemáticas , una secuencia de números enteros es una secuencia (es decir, una lista ordenada) de números enteros .
Una secuencia de números enteros puede especificarse explícitamente dando una fórmula para su término n -ésimo, 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 (secuencia A000045 en la OEIS ). La secuencia 0, 3, 8, 15, ... se forma según la fórmula n 2 − 1 para el término n -ésimo: una definición explícita.
Alternativamente, una secuencia de números enteros puede definirse por una propiedad que poseen los miembros de la secuencia y que no poseen otros números enteros. Por ejemplo, podemos determinar si un número entero dado es un número perfecto (secuencia A000396 en la OEIS ), aunque no tengamos una fórmula para el n -ésimo número perfecto.
Una secuencia de números enteros es computable si existe un algoritmo que, dado n , calcula un n , para todo n > 0. El conjunto de secuencias de números enteros computables es contable . El conjunto de todas las secuencias de números enteros es incontable (con cardinalidad igual a la del continuo ), y por lo tanto no todas las secuencias de números enteros son computables.
Aunque algunas secuencias de números enteros tienen definiciones, no existe una forma sistemática de definir qué significa que una secuencia de números 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 de números enteros es una secuencia definible relativa a M si existe alguna fórmula P ( x ) en el lenguaje de la teoría de conjuntos, con una variable libre y sin parámetros, lo cual es verdadero en M para esa secuencia de números enteros y falso en M para todas las demás secuencias de números enteros. En cada uno de esos M , hay secuencias de números enteros definibles que no son computables, como las secuencias que codifican los saltos de Turing de conjuntos computables.
Para algunos modelos transitivos M de ZFC, cada secuencia de números enteros en M es definible en relación con M ; para otros, solo algunas secuencias de números enteros lo son (Hamkins et al. 2013). No hay una manera sistemática de definir en M en sí mismo el conjunto de secuencias definibles en relación con M y ese conjunto puede incluso no existir en algunos de esos M . De manera similar, el mapa del conjunto de fórmulas que definen secuencias de números enteros en M a las secuencias de números enteros que definen no es definible en M y puede no existir en M . Sin embargo, en cualquier modelo que posea dicho mapa de definibilidad, algunas secuencias de números enteros en el modelo no serán definibles en relación con el modelo (Hamkins et al. 2013).
Si M contiene todas las secuencias de números enteros, entonces el conjunto de secuencias de números enteros definibles en M existirá en M y será contable y numerable en M.
Una secuencia de números enteros positivos se denomina secuencia completa si cada número entero positivo puede expresarse como una suma de valores en la secuencia, utilizando cada valor como máximo una vez.
Las secuencias de enteros que tienen su propio nombre incluyen: