Dicksons lemma - Dicksons lemma - Wikipedia

İçinde matematik, Dickson lemması her setin çiftleri doğal sayılar sonlu sayıda minimal elemanlar. Bu basit gerçek kombinatorik Amerikalı cebirciye atfedildi L. E. Dickson, bunu bir sonucu kanıtlamak için kullanan sayı teorisi hakkında mükemmel sayılar.[1] Bununla birlikte, lemma kesinlikle daha önce biliniyordu, örneğin Paul Gordan araştırmasında değişmez teori.[2]

Misal

Sonsuz sayıda minimal gerçek sayı çifti x,y (siyah hiperbol), ancak yalnızca beş minimum çift pozitif tam sayı (kırmızı) xy ≥ 9.

İzin Vermek sabit bir sayı olsun ve çarpımı en az olan sayı çiftleri kümesi . Pozitif üzerinden tanımlandığında gerçek sayılar, formun sonsuz sayıda minimal öğesi vardır , her pozitif sayı için bir ; bu noktalar kümesi, bir nesnenin dallarından birini oluşturur hiperbol. Bu hiperbol üzerindeki çiftler minimumdur, çünkü ait olan farklı bir çift için mümkün değildir. küçük veya eşit olmak her iki koordinatında. Bununla birlikte, Dickson'ın lemması yalnızca doğal sayıların demetleriyle ilgilidir ve doğal sayılar üzerinde yalnızca sonlu sayıda minimal çift vardır. Her minimum çift doğal sayıların ve , için eğer x daha büyüktü K sonra (x −1,y) ayrıca ait olacaktır S, asgarîliğiyle çelişen (x,y) ve simetrik olarak eğer y daha büyüktü K sonra (x,y −1) ayrıca ait olacaktırS. Bu nedenle, doğal sayıların üzerinde, en fazla minimal elemanlar, sonlu bir sayı.[not 1]

Resmi açıklama

İzin Vermek negatif olmayan tam sayılar kümesi (doğal sayılar ), İzin Vermek n herhangi bir sabit sabit olabilir ve izin ver seti olmak -doğal sayıların çiftleri. Bu tuplelar bir verilebilir noktasal kısmi sipariş, ürün siparişi içinde ancak ve ancak , Belirli bir demetten daha büyük veya ona eşit olan tuple kümesi pozitif oluşturur orthant tepe noktası verilen tuple.

Bu gösterimle, Dickson'ın lemması birkaç eşdeğer biçimde ifade edilebilir:

  • Her alt kümede nın-nin , en az bir, ancak sonlu sayıdan fazla olmayan öğe vardır minimal elemanlar nın-nin noktasal kısmi düzen için.[3]
  • Her sonsuz dizi için nın-nin -doğal sayıların çiftleri, iki endeks var öyle ki noktasal sıraya göre tutar.[4]
  • Kısmen sıralı set sonsuz içermez Antikalar ne de sonsuz (kesinlikle) azalan diziler nın-nin -tuples.[4]
  • Kısmen sıralı set bir iyi kısmi düzen.[5]
  • Her alt küme nın-nin tepe noktalarının tümü ait olan sonlu bir pozitif orthantlar kümesi tarafından kapsanabilir .

Genellemeler ve uygulamalar

Dickson, herhangi bir sayı için bunu kanıtlamak için lemmasını kullandı. sadece sınırlı sayıda olabilir garip mükemmel sayılar en çok olan asal faktörler.[1] Bununla birlikte, herhangi bir tek mükemmel sayı olup olmadığı açıktır.

bölünebilme arasındaki ilişki P-düzgün numaralar, asal çarpanlarının tümü, Sınırlı set P, bu sayılara kısmen sıralı bir izomorfik kümenin yapısını verir . Böylece, herhangi bir set için S nın-nin P-düzgün sayılar, sonlu bir altkümesi var S öyle ki her unsuru S bu alt kümedeki sayılardan biriyle bölünebilir. Bu gerçek, örneğin, bir şeyin var olduğunu göstermek için kullanılmıştır. algoritma oyunun ilk konumundan itibaren kazanan ve kaybeden hamleleri sınıflandırmak için Sylver madeni para Algoritmanın kendisi bilinmese de.[6]

Tuples içinde bire bir karşılık gelen tek terimli bir dizi değişkenler . Bu yazışma altında, Dickson'ın lemması özel bir durum olarak görülebilir. Hilbert'in temel teoremi her olduğunu belirten polinom ideal tek terimlilerin ürettiği idealler için sınırlı bir temele sahiptir. Aslında, Paul Gordan Hilbert'in temel teoreminin bir kanıtı olarak 1899'da Dickson lemmasının bu yeniden ifadesini kullandı.[2]

Ayrıca bakınız

Notlar

  1. ^ Daha dikkatli bir şekilde, şunlardan birini göstermek mümkündür: ve en fazla ve koordinatlardan birinin her seçimi için en fazla bir minimum çift bulunduğunu, buradan en fazla minimal elemanlar.

Referanslar

  1. ^ a b Dickson, L. E. (1913), "Tek mükemmel ve ilkel bol sayıların sonluluğu n farklı asal faktörler ", Amerikan Matematik Dergisi, 35 (4): 413–422, doi:10.2307/2370405, JSTOR  2370405.
  2. ^ a b Buchberger, Bruno; Winkler, Franz (1998), Gröbner Tabanları ve Uygulamaları, London Mathematical Society Lecture Note Series, 251, Cambridge University Press, s. 83, ISBN  9780521632980.
  3. ^ Kruskal, Joseph B. (1972). "İyi yarı-sıralama teorisi: Sık keşfedilen bir kavram". Kombinatoryal Teori Dergisi. A Serisi 13 (3): 298. doi:10.1016/0097-3165(72)90063-5.
  4. ^ a b Figueira, Diego; Figueira, Santiago; Schmitz, Sylvain; Schnoebelen, Philippe (2011), "Ackermannian ve Dickson lemması ile ilkel-özyinelemeli sınırlar", 26th Annual IEEE Symposium on Logic in Computer Science (LICS 2011), IEEE Computer Soc., Los Alamitos, CA, s. 269, arXiv:1007.2989, doi:10.1109 / LICS.2011.39, BAY  2858898.
  5. ^ Onn, Shmuel (2008), "Konveks Ayrık Optimizasyon", in Floudas, Christodoulos A.; Pardalos, Panos M. (editörler), Optimizasyon Ansiklopedisi, Cilt. 1 (2. baskı), Springer, s. 513–550, arXiv:matematik / 0703575, Bibcode:2007math ...... 3575O, ISBN  9780387747583.
  6. ^ Berlekamp, ​​Elwyn R.; Conway, John H .; Guy, Richard K. (2003), "18 İmparator ve Parası", Matematik Oyunlarınız için Kazanma Yolları, Cilt. 3, Academic Press, s. 609–640. Özellikle bkz. "Sonuçlar hesaplanabilir mi", s. 630.