Celá sekvence - Integer sequence

Image
Začátek sekvence Fibonacci na budově v Göteborgu

V matematiky , An celé číslo sekvence je sekvence (tj uspořádaného seznamu) z celých čísel .

Celočíselnou sekvenci lze specifikovat explicitně zadáním vzorce pro její n- tý termín, nebo implicitně uvedením vztahu mezi jeho členy. Například posloupnost 0, 1, 1, 2, 3, 5, 8, 13, ... ( Fibonacciho posloupnost ) je tvořena počínaje 0 a 1 a poté přidáním jakýchkoli dvou po sobě jdoucích výrazů k získání dalšího: implicitní popis. Posloupnost 0, 3, 8, 15, ... je vytvořena podle vzorce n 2  - 1 pro n- tý termín: explicitní definice.

Alternativně může být celočíselná sekvence definována vlastností, kterou členové sekvence mají a ostatní celá čísla nemají. Například můžeme určit, zda dané celé číslo je dokonalé číslo , i když pro n- té dokonalé číslo nemáme vzorec .

Příklady

Celé sekvence, které mají svůj vlastní název, zahrnují:

Vypočitatelné a definovatelné sekvence

Celočíselná sekvence je vypočítatelná sekvence, pokud existuje algoritmus, který vzhledem k n vypočítá a n pro všechna n > 0. Množinu vypočítatelných celočíselných sekvencí lze spočítat . Sada všech celočíselných posloupností je nespočetná (s mohutností rovnou té v kontinuu ), a tak ne všechny celočíselné sekvence jsou vypočítatelné.

Ačkoli některé celočíselné sekvence mají definice, neexistuje žádný systematický způsob, jak definovat, co to znamená, aby byla celočíselná sekvence definovatelná ve vesmíru nebo v jakémkoli absolutním (na modelu nezávislém) smyslu.

Předpokládejme, že soubor M je přechodný model, z teorie množin ZFC . Transitivita M znamená, že celá čísla a celočíselné sekvence uvnitř M jsou ve skutečnosti celá čísla a sekvence celých čísel. Celočíselná posloupnost je definovatelná posloupnost vzhledem k M, pokud existuje nějaký vzorec P ( x ) v jazyce teorie množin, s jednou volnou proměnnou a bez parametrů, což platí v M pro tuto celočíselnou sekvenci a v M pro všechny ostatní celočíselné sekvence. V každém takovém M jsou definovatelné celočíselné sekvence, které nelze vypočítat, například sekvence, které kódují Turingovy skoky vypočítatelných množin.

U některých tranzitivních modelů M ZFC je každá sekvence celých čísel v M definovatelná vzhledem k M ; pro ostatní jsou to pouze některé celočíselné sekvence (Hamkins et al. 2013). Neexistuje žádný systematický způsob, jak definovat v M samotném množinu sekvencí definovatelných vzhledem k M a tato množina nemusí v některých takových M dokonce existovat . Podobně, mapa z množiny formulí, které definují číslo sekvence v M na celé číslo sekvence, které definují není definovatelná v M a nemusí existovat v M . Avšak v každém modelu, který takovou mapu definovatelnosti má, nebudou některé celočíselné sekvence v modelu definovatelné vzhledem k modelu (Hamkins et al. 2013).

Pokud M obsahuje všechny celočíselné sekvence, pak sadu sekvencí celého čísla definovatelný v M bude existovat v M a je počitatelné a počitatelné v M .

Kompletní sekvence

Sekvence kladných celých čísel se nazývá úplná sekvence, pokud lze každé kladné celé číslo vyjádřit jako součet hodnot v sekvenci, přičemž se každá hodnota použije maximálně jednou.

Viz také

Reference

  • Hamkins, Joel David; Linetsky, David; Reitz, Jonas (2013), „Pointwise Definable Models of Set Theory“, Journal of Symbolic Logic , 78 (1): 139–156, arXiv : 1105,4597 , doi : 10,2178 / jsl.7801090 .

externí odkazy