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 se puede especificar explícitamente dando una fórmula para su enésimo término, 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 cualesquiera para obtener el siguiente: una descripción implícita (secuencia A000045 en el OEIS ). La secuencia 0, 3, 8, 15, ... se forma según la fórmula n 2 − 1 para el n.ésimo término: una definición explícita.
Alternativamente, una secuencia de números enteros puede definirse mediante una propiedad que poseen los miembros de la secuencia y otros números enteros no. Por ejemplo, podemos determinar si un número entero dado es un número perfecto (secuencia A000396 en el OEIS ), aunque no tengamos una fórmula para el enésimo número perfecto.
Una secuencia de enteros es una secuencia computable si existe un algoritmo que, dado n, calcula an , para todo n > 0. El conjunto de secuencias de enteros computables es contable . El conjunto de todas las secuencias de números enteros es incontable (con cardinalidad igual a la del continuo ), por lo que no todas las secuencias de números enteros son computables.
Aunque algunas secuencias de enteros tienen definiciones, no existe una forma sistemática de definir lo que 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 secuencias de números enteros dentro de M son en realidad números enteros y secuencias de números enteros. Una secuencia de 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, que es verdadera en M para esa secuencia de enteros y falsa en M para todas las demás. secuencias enteras. En cada uno de estos 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 números 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 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 puede no existir 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 de enteros, entonces el conjunto de secuencias de enteros definibles en M existirá en M y será contable y contable en M.
Una secuencia de números enteros positivos se llama secuencia completa si cada número entero positivo se puede expresar como una suma de valores en la secuencia, usando cada valor como máximo una vez.
Las secuencias de números enteros que tienen su propio nombre incluyen: