Věta Lambek – Moser - Lambek–Moser theorem
v kombinatorická teorie čísel, Věta Lambek – Moser je zobecněním Beattyho věta který definuje a rozdělit pozitivního celá čísla do dvou podmnožin z jakékoli monotónní celočíselné funkce. Naopak každé rozdělení kladných celých čísel do dvou podmnožin lze definovat z monotónní funkce tímto způsobem.
Věta byla objevena Leo Moser a Joachim Lambek. Dijkstra (1980) poskytuje a vizuální důkaz výsledku.[1]
Výrok věty
Věta platí pro všechny neklesající a unomezená funkce F která mapuje kladná celá čísla na nezáporná celá čísla. Z jakékoli takové funkce F, definovat F * být funkcí s celočíselnou hodnotou, která je co nejblíže k inverzní funkce z F, v tom smyslu, že pro všechny n,
- F (F *(n)) < n ≤ F (F *(n) + 1).
Z této definice vyplývá, že F ** = FDále nechte
- F(n) = F (n) + n a G(n) = F *(n) + n.
Výsledek to pak uvádí F a G se přísně zvyšují a že rozsahy F a G tvoří oddíl kladných celých čísel.
Příklad
Nechat F (n) = n2;[2] pak .Tím pádem F(n) = n2 + n a Pro n = 1, 2, 3, ... hodnoty F jsou pronická čísla
- 2, 6, 12, 20, 30, 42, 56, 72, 90, 110, ...
zatímco hodnoty G jsou
- 1, 3, 4, 5, 7, 8, 9, 10, 11, 13, 14, ....
Tyto dvě sekvence se doplňují: každé kladné celé číslo patří přesně jedné z nich. Věta Lambek – Moser uvádí, že tento jev není specifický pro pronická čísla, ale spíše vzniká při jakékoli volbě F s příslušnými vlastnostmi.
Beattyho věta
Beattyho věta, definující oddíl celých čísel ze zaokrouhlování jejich násobků o iracionální číslo r > 1, lze považovat za příklad věty Lambek – Moser. V Beattyho větě a kde . Podmínka, že r (a proto s) být větší než jedna znamená, že tyto dvě funkce neklesají; odvozené funkce jsou a Posloupnosti hodnot F a G tvořící odvozený oddíl jsou známé jako Beattyho sekvence.
Univerzálnost
Věta Lambek – Moser je univerzální v tom smyslu, že může vysvětlit jakékoli rozdělení celých čísel na dvě nekonečné části. Li S = s1,s2,... a T = t1,t2,... jsou libovolné dvě nekonečné podmnožiny tvořící oddíl celých čísel, lze zkonstruovat dvojici funkcí F a F * ze kterého lze tento oddíl odvodit pomocí věty Lambek – Moser: definovat F (n) = sn − n a F *(n) = tn − n.
Zvažte například rozdělení celých čísel na sudá a lichá čísla: nechte S být sudá čísla a T být lichá čísla. Pak sn = 2n, tak F (n) = n a podobně F *(n) = n − 1. Tyto dvě funkce F a F * tvoří inverzní pár a rozdělení generované pomocí věty Lambek – Moser z této dvojice je pouze rozdělení kladných celých čísel na sudá a lichá čísla.
Lambek a Moser diskutují o vzorcích zahrnujících funkce počítání prvočísel pro funkce F a F * vznikající tímto způsobem z rozdělení kladných celých čísel na prvočísla a složená čísla.
Viz také
- Sekvence obrazců a obrazů Hofstadter, další dvojice komplementárních sekvencí, na které lze aplikovat větu Lambek – Moser
Poznámky
- ^ Další důkaz viz „Důkaz pro Lambekovu a Moserovu větu“ (PDF), Matematický Excalibur, 4 (1): 2, 1998
- ^ Příklad z Garry, Y. K. K. (1997), „Inverzní sekvence a komplementární sekvence“ (PDF), Matematický Excalibur, 3 (4): 2
Reference
- Beatty, Samuel (1926), „Problém 3173“, Americký matematický měsíčník, 33 (3): 159, doi:10.2307/2300153 Řešení Beatty, A. Ostrowski, J. Hyslop a A. C. Aitken, sv. 34 (1927), str. 159–160.
- Dijkstra, Edsger W. (1980), Na větě Lambka a Mosera (PDF)Zpráva EWD753, University of Texas.
- Lambek, Joachim; Moser, Leo (Srpen – září 1954), „Inverzní a doplňkové sekvence přirozených čísel“, Americký matematický měsíčník, 61 (7): 454–458, doi:10.2307/2308078