Lemat Dicksona

W matematyce lemat Dicksona $stwierdza, że ​​każdy zbiór krotek$ liczb naturalnych skończenie wiele elementów minimalnych . Ten prosty fakt z kombinatoryki został przypisany amerykańskiemu algebraiście LE Dicksonowi , który wykorzystał go do udowodnienia wyniku teorii liczb dotyczącej liczb doskonałych . Lemat ten był jednak z pewnością znany wcześniej, na przykład Paulowi Gordanowi w jego badaniach nad teorią niezmienniczości .

Przykład

Nieskończenie wiele par minimalnych liczb rzeczywistych x , y (czarna hiperbola), ale tylko pięć minimalnych par liczb całkowitych dodatnich (kolor czerwony) ma xy ≥ 9.

Niech ${\ Displaystyle K}$ będzie stałą liczbą i niech ${(x, y) \ mid xy \ geq K \}}$ \ zbiór par liczb, których iloczyn wynosi co najmniej ${\ displaystyle K}$ . $x}$ zdefiniowaniu na dodatnich liczbach rzeczywistych , ma nieskończenie wiele minimalnych elementów postaci , $}$ jednym dla każdej liczby dodatniej $, K / x)$$Displaystyle ($ ; ten zbiór punktów tworzy jedną z gałęzi hiperboli . Pary na tej hiperboli są minimalne, ponieważ nie jest możliwe, $}$ inna para należąca do była mniejsza lub równa $x$${\ Displaystyle (x, K / x$ w obu jego współrzędnych. Jednak lemat Dicksona dotyczy tylko krotek liczb naturalnych, a nad liczbami naturalnymi jest tylko skończenie wiele par minimalnych. Każda minimalna para liczb naturalnych ma i $y \ równoważnik K}$$≤$ i $\$ y równoważnik K niż K , to ( x − 1, y ) również należełoby do S , zaprzeczając minimalności ( x , y ), i symetrycznie, gdyby y było większe niż K , to ( x , y − 1) również należało do S . $ma$ ponad liczbami naturalnymi najwyżej minimalną $liczbę elementów,$ liczbę skończoną.

Oświadczenie formalne

Niech ${\ displaystyle \ mathbb {N}}$ będzie zbiorem nieujemnych liczb całkowitych ( liczb naturalnych ), niech n będzie dowolną stałą stałą i niech $\ displaystyle \ mathbb {N}}$ N zbiór $krotek$ liczb naturalnych. Tym krotkom można nadać punktowy porządek częściowy , porządek iloczynu , w którym ${\ Displaystyle (a_ {1}, a_ {2}, \ kropki, a_ {n}) \ równoważnik (b_ {1}, b_ {2}, \ kropki b_ {n})}$ wtedy i tylko wtedy, gdy ${\ Displaystyle a_ {i} \ leq b_ {i}}$ dla każdego ${\ displaystyle i}$ . Zbiór krotek, które są większe lub równe jakiejś określonej krotce $\ Displaystyle (a_ {1}, a_ {2}, \ kropki, a_ {n})$ } dodatni ortant z wierzchołkiem w danej krotce.

W tym zapisie lemat Dicksona można przedstawić w kilku równoważnych formach:

• W każdym niepustym podzbiorze istnieje co najmniej jeden, ale nie więcej niż $skończona$ liczba elementów, które są $S$$}$ S { $displaystyle S}$ dla punktowego porządku częściowego.
• Dla każdej nieskończonej sekwencji $krotek$$\ Displaystyle (x_ {i}) _ {i \ in \ mathbb {N}}} -$ liczb naturalnych istnieją dwa indeksy ${\ displaystyle i <j}$ takie, że zachodzi w odniesieniu do porządku punktowego ${\ displaystyle x_ {i} \ równoważnik x_ {j}}$
• Częściowo $($$nieskończonych$ nie zawiera antyłańcuchów ani ) malejących
• Zbiór $_$ dobrze _ _
• Każdy podzbiór $z$ być objęty skończonym zbiorem dodatnich ortantów, których wszystkie wierzchołki należą do $S$ { $}$ .

Uogólnienia i zastosowania

$może$ użył swojego lematu, aby udowodnić, że dla dowolnej danej liczby $istnieć$ tylko skończona liczba nieparzystych liczb doskonałych które mają co najwyżej czynniki pierwsze . Jednak pozostaje otwarte , czy w ogóle istnieją nieparzyste liczby doskonałe.

Relacja podzielności między P - gładkimi liczbami , liczbami naturalnymi, których wszystkie czynniki pierwsze należą do skończonego zbioru P , nadaje tym liczbom strukturę częściowo uporządkowanego zbioru izomorficznego do ${\ Displaystyle (\ mathbb {} N} ^{|P|},\równik )}$ . Zatem dla dowolnego zbioru S z P -gładkich liczb istnieje skończony podzbiór S taki, że każdy element S jest podzielny przez jedną z liczb w tym podzbiorze. Fakt ten wykorzystano na przykład do wykazania, że ​​istnieje algorytm klasyfikowania wygrywających i przegrywających ruchów z pozycji początkowej w grze Sylver coinage , chociaż sam algorytm pozostaje nieznany.

krotki ${\ Displaystyle (a_ {1}, a_ {2}, \ kropki, a_ {n})}$ w ${\ Displaystyle \ mathbb {N} ^ { n}}$ odpowiada jeden za jeden z jednomianami x $^ {a_ {n}}}$$\ Displaystyle x_ {1} ^ {a_ {1}} x_ {2} ^ {a_ {2}} \ kropki x_ {n$ } nad zbiorem $x_$${n.}}$${\ Displaystyle x_ {1}, x_ {2}, \ kropki$ . W ramach tej korespondencji lemat Dicksona może być postrzegany jako szczególny przypadek twierdzenia bazowego Hilberta stwierdzającego, że każdy ideał wielomianu ma skończoną podstawę dla ideałów generowanych przez jednomiany. Rzeczywiście, Paul Gordan użył tego przekształcenia lematu Dicksona w 1899 roku jako część dowodu twierdzenia Hilberta o podstawie.

Zobacz też

• Lemat Gordana