Séquence d'entiers

En mathématiques , une suite d'entiers est une suite (c'est-à-dire une liste ordonnée) d' entiers .

Une suite d'entiers peut être définie explicitement en donnant une formule pour son n -ième terme, ou implicitement en établissant une relation entre ses termes. Par exemple, la suite 0, 1, 1, 2, 3, 5, 8, 13, ... (la suite de Fibonacci ) est formée en commençant par 0 et 1, puis en additionnant deux termes consécutifs quelconques pour obtenir le suivant : une description implicite dans l' OEIS ) . La suite 0, 3, 8, 15, ... est formée selon la formule ${\displaystyle n^{2}-1 <semantics><mrow><mstyle><msup><mi>n</mi><mrow><mn>2</mn></mrow></msup><mo>−</mo><mn>1</mn></mstyle></mrow><annotation>{\displaystyle n^{2}-1}</annotation></semantics></math><img src=$ n -ième terme : une définition explicite.

On peut aussi définir une suite d'entiers par une propriété que possèdent ses éléments et que les autres entiers ne possèdent pas. Par exemple, on peut déterminer si un entier donné est un nombre parfait ( dans l' OEIS ) , même si l'on ne dispose pas de formule pour calculer le n -ième nombre parfait.

séquences calculables et définissables

Une suite d'entiers est calculable s'il existe un algorithme qui, étant donné ${\displaystyle n <semantics><mrow><mstyle><mi>n</mi></mstyle></mrow><annotation>{\displaystyle n}</annotation></semantics></math><img src=$ ${\displaystyle a_{n <semantics><mrow><mstyle><msub><mi>un</mi><mrow><mi>n</mi></mrow></msub></mstyle></mrow><annotation>{\displaystyle a_{n}}</annotation></semantics></math><img src=$ $0 n > 0$ 0 L'ensemble des suites d'entiers calculables est dénombrable . L'ensemble de toutes les suites d'entiers est indénombrable (de cardinalité égale à celle du continu ), et par conséquent, toutes les suites d'entiers ne sont pas calculables.

Bien que certaines suites d'entiers aient des définitions, il n'existe aucun moyen systématique de définir ce que signifie la définition d'une suite d'entiers dans l'univers ou dans un sens absolu (indépendant du modèle).

Supposons que l'ensemble ${\displaystyle M <semantics><mrow><mstyle><mi>M</mi></mstyle></mrow><annotation>{\displaystyle M}</annotation></semantics></math><img src=$ ${\displaystyle M <semantics><mrow><mstyle><mi>M</mi></mstyle></mrow><annotation>{\displaystyle M}</annotation></semantics></math><img src=$ ${\displaystyle M <semantics><mrow><mstyle><mi>M</mi></mstyle></mrow><annotation>{\displaystyle M}</annotation></semantics></math><img src=$ suite définissable par rapport à ${\displaystyle M <semantics><mrow><mstyle><mi>M</mi></mstyle></mrow><annotation>{\displaystyle M}</annotation></semantics></math><img src=$ s'il existe une formule ${\displaystyle P(x) <semantics><mrow><mstyle><mi>P</mi><mo>(</mo><mi>x</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle P(x)}</annotation></semantics></math><img src=$ ${\displaystyle M <semantics><mrow><mstyle><mi>M</mi></mstyle></mrow><annotation>{\displaystyle M}</annotation></semantics></math><img src=$ ${\displaystyle M <semantics><mrow><mstyle><mi>M</mi></mstyle></mrow><annotation>{\displaystyle M}</annotation></semantics></math><img src=$ ${\displaystyle M <semantics><mrow><mstyle><mi>M</mi></mstyle></mrow><annotation>{\displaystyle M}</annotation></semantics></math><img src=$

Pour certains modèles transitifs ${\displaystyle M <semantics><mrow><mstyle><mi>M</mi></mstyle></mrow><annotation>{\displaystyle M}</annotation></semantics></math><img src=$ ${\displaystyle M <semantics><mrow><mstyle><mi>M</mi></mstyle></mrow><annotation>{\displaystyle M}</annotation></semantics></math><img src=$ ${\displaystyle M <semantics><mrow><mstyle><mi>M</mi></mstyle></mrow><annotation>{\displaystyle M}</annotation></semantics></math><img src=$ ${\displaystyle M <semantics><mrow><mstyle><mi>M</mi></mstyle></mrow><annotation>{\displaystyle M}</annotation></semantics></math><img src=$ ${\displaystyle M <semantics><mrow><mstyle><mi>M</mi></mstyle></mrow><annotation>{\displaystyle M}</annotation></semantics></math><img src=$ ${\displaystyle M <semantics><mrow><mstyle><mi>M</mi></mstyle></mrow><annotation>{\displaystyle M}</annotation></semantics></math><img src=$ ${\displaystyle M <semantics><mrow><mstyle><mi>M</mi></mstyle></mrow><annotation>{\displaystyle M}</annotation></semantics></math><img src=$ ${\displaystyle M <semantics><mrow><mstyle><mi>M</mi></mstyle></mrow><annotation>{\displaystyle M}</annotation></semantics></math><img src=$ ${\displaystyle M <semantics><mrow><mstyle><mi>M</mi></mstyle></mrow><annotation>{\displaystyle M}</annotation></semantics></math><img src=$

Si ${\displaystyle M <semantics><mrow><mstyle><mi>M</mi></mstyle></mrow><annotation>{\displaystyle M}</annotation></semantics></math><img src=$ ${\displaystyle M <semantics><mrow><mstyle><mi>M</mi></mstyle></mrow><annotation>{\displaystyle M}</annotation></semantics></math><img src=$ ${\displaystyle M <semantics><mrow><mstyle><mi>M</mi></mstyle></mrow><annotation>{\displaystyle M}</annotation></semantics></math><img src=$ ${\displaystyle M <semantics><mrow><mstyle><mi>M</mi></mstyle></mrow><annotation>{\displaystyle M}</annotation></semantics></math><img src=$

Séquences complètes

Une suite d'entiers positifs est dite complète si chaque entier positif peut être exprimé comme une somme de valeurs de la suite, chaque valeur étant utilisée au plus une fois.

Exemples

Les séquences d'entiers qui possèdent leur propre nom comprennent :

Hamkins, Joel David ; Linetsky, David ; Reitz, Jonas (2013), « Modèles définissables ponctuellement de la théorie des ensembles », Journal of Symbolic Logic , 78 (1) : 139–156 , arXiv : 1105.4597 , doi : 10.2178/jsl.7801090 , S2CID 43689192.