Kőnig lemması - Kőnig's lemma

Kőnig'in lemması veya Kőnig'in sonsuz lemması , onu 1927'de yayınlayan Macar matematikçi Dénes Kőnig'e bağlı olarak grafik teorisinde bir teoremdir . Sonsuz bir grafiğin sonsuz uzun bir yola sahip olması için yeterli bir koşul sağlar. Bu teoremin hesaplanabilirlik yönleri, matematiksel mantık , özellikle hesaplanabilirlik teorisinde araştırmacılar tarafından kapsamlı bir şekilde araştırılmıştır . Bu teoremin ayrıca yapıcı matematik ve ispat teorisinde önemli rolleri vardır .

Lemmanın ifadesi

Let G olmak bir bağlı , lokal sonlu , sonsuz grafiktir (bu araçlar: herhangi iki köşe bir yol ile bağlı olabilir, grafik sonsuz sayıda köşe bulunmaktadır, ve her bir köşe sonlu sayıda diğer köşe bitişik). Daha sonra G bir ışın içerir : bir tepe noktasında başlayan ve ondan sonsuz sayıda tepe noktası boyunca devam eden basit bir yol (tekrarlanan köşeleri olmayan bir yol).

Bunun yaygın bir özel durumu, her sonsuz ağacın ya sonsuz dereceli bir tepe noktası ya da sonsuz basit bir yol içermesidir .

Kanıt

Herhangi bir köşe v ₁ ile başlayın . G'nin sonsuz sayıda köşesinin her birine v _1'den basit bir yolla ulaşılabilir ve bu tür yolların her biri, v _1'e bitişik sonlu sayıda köşeden biriyle başlamalıdır . V _1'den geçmeden sonsuz sayıda köşeye ulaşılabilen bitişik köşelerden biri olmalıdır . Olmasaydı, grafiğin sonsuz olduğu varsayımıyla çelişecek şekilde tüm grafik, sonlu sayıda sonlu kümenin birleşimi olurdu ve dolayısıyla sonlu olurdu. Böylece bu köşelerden birini seçip ona v ₂ diyebiliriz .

Şimdi sonsuz birçok köşe G ulaşılabilir v ₂ köşe içermez basit yolu ile v ₁ . Bu tür her bir yol, v _2'ye bitişik sonlu sayıda köşeden biriyle başlamalıdır . Dolayısıyla, yukarıdakine benzer bir argüman, sonsuz sayıda noktaya ulaşılabilen bitişik köşelerden birinin olması gerektiğini gösterir; birini seçin ve v _{3 olarak adlandırın} .

Bu şekilde devam ederek, matematiksel tümevarım ve bağımlı seçim aksiyomunun zayıf bir versiyonu kullanılarak sonsuz basit bir yol inşa edilebilir . Her bir adımda, olduğu indüksiyon hipotezi durumları sonsuz sayıda belirli bir düğüm basit bir yol ile ulaşılabilir v _ı köşe sonlu takımından birine geçmez. Tümevarım argümanı, v _i'ye bitişik köşelerden birinin , sonlu kümeye v _i eklendiğinde bile, tümevarım hipotezini karşılamasıdır .

Bu tümevarım argümanının sonucu, tüm n için, yapının tanımladığı gibi bir v _n köşesini seçmenin mümkün olmasıdır . Yapıda seçilen köşe kümesi, grafikte bir zincirdir, çünkü her biri bir öncekine bitişik olarak seçilmiştir ve yapı, aynı tepe noktasının asla iki kez seçilmemesini garanti eder.

Hesaplanabilirlik yönleri

Kőnig'in lemmasının hesaplanabilirlik yönleri kapsamlı bir şekilde araştırılmıştır. Kőnig'in lemmasının bu amaç için en uygun biçimi, herhangi bir sonsuz sonlu dallandırılmış alt-ağacının sonsuz bir yola sahip olduğunu belirten biçimdir . Burada , doğal sayılar kümesini ( sıra sayısı olarak düşünülür ) ve düğümlerinin tümü sonlu doğal sayı dizileri olan ağacı gösterir; burada bir düğümün ebeveyni, diziden son elemanın çıkarılmasıyla elde edilir. Her sonlu dizi, kendisine ait kısmi bir fonksiyonla tanımlanabilir ve her sonsuz yol, bir toplam fonksiyonla tanımlanabilir. Bu, hesaplanabilirlik teorisi tekniklerini kullanan bir analize izin verir. ${\ displaystyle \ omega ^ {<\ omega}}$${\ displaystyle \ omega}$${\ displaystyle \ omega ^ {<\ omega}}$${\ displaystyle \ omega}$

Bir alt ağaç her dizi sonlu sayıda hemen uzantıları vardır ettiği formül (olduğunu, ağaç bir grafik olarak görülmektedir sonlu derecesine sahip) olarak adlandırılır sonlu dallanma . Her sonsuz alt ağacının sonsuz bir yolu yoktur, ancak Kőnig'in lemması, herhangi bir sonlu dallanan alt ağacın böyle bir yola sahip olması gerektiğini gösterir. ${\ displaystyle \ omega ^ {<\ omega}}$${\ displaystyle \ omega ^ {<\ omega}}$

Herhangi bir alt ağaç için T arasında gösterimde Dahili ( T ) arasında ayırma düğümlerinin kümesini ifade eder , T , bir sonsuz yol vardır yerleştirilmesi ile tanımlanır. T hesaplanabilir olduğunda bile Ext ( T ) seti hesaplanamayabilir. Bir yola sahip olan her T alt ağacı Ext ( T ) ' den hesaplanabilen bir yola sahiptir . ${\ displaystyle \ omega ^ {<\ omega}}$${\ displaystyle \ omega ^ {<\ omega}}$

Hiçbir aritmetik yolu ve gerçekten de hiperaritmetik yolu olmayan, sonlu olarak dallanmayan hesaplanabilir alt ağaçlarının olduğu bilinmektedir . Bununla birlikte, bir yolu olan her hesaplanabilir alt ağaç , kanonik tam set olan Kleene's O'dan hesaplanabilen bir yola sahip olmalıdır . Bunun nedeni, T hesaplanabilir olduğunda Ext ( T ) kümesinin her zaman olmasıdır ( analitik hiyerarşiye bakın ) . ${\ displaystyle \ omega ^ {<\ omega}}$${\ displaystyle \ omega ^ {<\ omega}}$${\ displaystyle \ Pi _ {1} ^ {1}}$${\ displaystyle \ Sigma _ {1} ^ {1}}$

Hesaplanabilir sınırlanmış ağaçlar için daha ince bir analiz yapılmıştır. Bir alt ağaç olarak adlandırılır computably sınırlı veya yinelemeli sınırlanan hesaplanabilir bir fonksiyon olması durumunda f den için ağaç ve her her sekansı için bu tür n , n dizisinin inci elemanının en ise f ( n ). Böylece f , ağacın ne kadar "geniş" olduğuna dair bir sınır verir. Aşağıdaki temel teoremler , sonsuz, hesaplanabilir sınırlı, hesaplanabilir alt ağaçları için geçerlidir . ${\ displaystyle \ omega ^ {<\ omega}}$${\ displaystyle \ omega}$${\ displaystyle \ omega}$${\ displaystyle \ omega ^ {<\ omega}}$

• Böyle herhangi bir ağaç, durdurma sorununa karar verebilen kanonik Turing tam kümesinden hesaplanabilen bir yola sahiptir . ${\ displaystyle 0 '}$
• Böyle herhangi bir ağacın alçak bir yolu vardır . Bu, düşük temel teoremi olarak bilinir .
• Böyle herhangi bir ağacın hiperimmün olmayan bir yolu vardır . Bu, yoldan hesaplanabilen herhangi bir işleve hesaplanabilir bir işlevin hakim olduğu anlamına gelir.
• Ağacın hesaplanamayan herhangi bir alt kümesi için X , X'i hesaplamayan bir yola sahiptir  . ${\ displaystyle \ omega}$

Her sonsuz ikili ağacın sonsuz bir dalı olduğunu belirten zayıf bir Kőnig lemması , ikinci dereceden aritmetiğin WKL ₀ alt sistemini tanımlamak için kullanılır . Bu alt sistemin ters matematikte önemli bir rolü vardır . İşte ikili ağaç WKL içinde kanıtlanabilir ağaç computably sabit fonksiyonu 2. König lemmasının tam form aracılığıyla sınırlanan demek ki ağaçtaki her dizinin her dönem 0 olduğu bir ya da 1, değil mi ₀ , fakat daha güçlü ACA ₀ alt sistemine eşdeğerdir .

Yapıcı matematik ve kompaktlık ile ilişki

Yukarıda verilen ispat genellikle yapıcı olarak kabul edilmez , çünkü her adımda, sonsuz sayıda başka köşeye ulaşılabilen bitişik bir tepe noktası olduğunu tespit etmek için çelişkili bir ispat kullanır ve zayıf bir biçime güvenmesi nedeniyle seçim aksiyomu . Lemmanın hesaplama yönleriyle ilgili gerçekler, yapıcı matematiğin ana okulları tarafından yapıcı olarak kabul edilebilecek hiçbir kanıtın verilemeyeceğini göstermektedir .

LEJ Brouwer'ın  ( 1927 ) fan teoremi, klasik bir bakış açısından, Kőnig lemasının bir formunun tam tersidir. Bir alt-kümesi S arasında bir adlandırılır çubuğu herhangi bir fonksiyonu halinde ayarlamak için bazı ilk bölümüne sahip S . Her sekans çubukta ise veya çubukta değilse , bir çubuk çıkarılabilir (bu varsayım gereklidir çünkü teorem normalde dışarıda bırakılan orta kanunun kabul edilmediği durumlarda dikkate alınır ). Bir çubuk homojen bir değer olup olmadığını , N , böylece herhangi bir fonksiyon olduğu için fazla uzunlukta barda bir başlangıç bölümüne sahip . Brouwer'in fan teoremi, herhangi bir ayrılabilir çubuğun tek tip olduğunu söyler. ${\ displaystyle \ {0,1 \} ^ {<\ omega}}$${\ displaystyle \ omega}$${\ displaystyle \ {0,1 \}}$${\ displaystyle \ omega}$${\ displaystyle \ {0,1 \}}$${\ displaystyle N}$

Bu, çubuğu kompakt topolojik uzayın açık bir kaplaması olarak düşünerek klasik bir ortamda kanıtlanabilir . Çubuktaki her sıra, bu alanın temel bir açık kümesini temsil eder ve bu temel açık kümeler, varsayım yoluyla alanı kaplar. Kompaktlık nedeniyle, bu kapak sonlu bir alt kaplamaya sahiptir. N Fan teoreminin temel açık grubu sonlu alt örtüye olan uzun dizi uzunluğu olarak alınabilir. Bu topolojik kanıt, K mathnig lemmasının aşağıdaki biçiminin geçerli olduğunu göstermek için klasik matematikte kullanılabilir: herhangi bir doğal sayı k için , ağacın herhangi bir sonsuz alt ağacının sonsuz bir yolu vardır. ${\ displaystyle \ {0,1 \} ^ {\ omega}}$${\ displaystyle \ {0, \ ldots, k \} ^ {<\ omega}}$

Seçim aksiyomu ile ilişki

Kőnig'in lemması bir seçim ilkesi olarak düşünülebilir; Yukarıdaki ilk kanıt, lemma ile bağımlı seçim aksiyomu arasındaki ilişkiyi gösterir . Tümevarımın her adımında, belirli bir özelliğe sahip bir köşe seçilmelidir. En az bir uygun köşe olduğu kanıtlanmış olsa da, birden fazla uygun köşe varsa kanonik seçim olmayabilir. Aslında, bağımlı seçim aksiyomunun tüm gücüne ihtiyaç yoktur; aşağıda açıklandığı gibi, sayılabilir seçim aksiyomu yeterlidir.

Grafik sayılabilirse, köşeler iyi sıralanmıştır ve biri kanonik olarak en küçük uygun köşeyi seçebilir. Bu durumda, Kőnig'in lemması, ikinci dereceden aritmetikte aritmetik anlayışla ve a fortiori, ZF küme teorisinde (seçim olmaksızın) kanıtlanabilir .

Kőnig lemması, esasen bağımlı seçim aksiyomunun, her bir x için xRz gibi yalnızca sonlu sayıda z olacak şekilde tüm R ilişkileri ile sınırlandırılmasıdır . Seçim aksiyomu genel olarak bağımlı seçim ilkesinden daha güçlü olsa da, bağımlı seçimin bu kısıtlaması, seçim aksiyomunun kısıtlanmasına eşdeğerdir. Özellikle, her düğümdeki dallanma, sayılabilir olmadığı varsayılmayan keyfi bir kümenin sonlu bir alt kümesinde yapıldığında, Kőnig lemasının "Her sonsuz sonlu dallanan ağacın sonsuz bir yolu vardır" ilkesine eşdeğerdir. sayılabilir sonlu kümeler kümesi bir seçim işlevine, yani sonlu kümeler için sayılabilir seçim aksiyomuna sahiptir. Seçim aksiyomunun (ve dolayısıyla Kőnig lemasının) bu biçimi ZF küme teorisinde kanıtlanamaz.

Genelleme

Gelen setlerinin kategorisinde , ters sınırı Boş olmayan sonlu kümelerinin herhangi ters sisteminin olmayan boş. Bu, Kőnig lemmasının bir genellemesi olarak görülebilir ve sonlu kümeleri kompakt ayrık uzaylar olarak görerek ve ardından kompaktlığın sonlu kesişim özelliği karakterizasyonunu kullanarak Tychonoff teoremi ile kanıtlanabilir .

Ayrıca bakınız

• Aronszajn ağacı , lemmayı daha yüksek kardinalitelere genellerken karşı örneklerin olası varlığı için.
• PA derecesi

Notlar

Referanslar

• Brouwer, LEJ (1927), Fonksiyonların Tanımının Etki Alanları Üzerine . yayınlanan Van Heijenoort, Jean, ed. (1967), Frege'den Gödel'e
• Franchella, Miriam (1997), "Dénes König'in sonsuz lemmasının kökenleri hakkında", Tam Bilimler Tarihi Arşivi (51 (1) 3: 2-3): 3–27, doi : 10.1007 / BF00376449
• Howard, Paul; Rubin, Jean (1998), Seçim Aksiyomunun Sonuçları , Matematiksel Araştırmalar ve Monograflar, 59 , Providence, RI: American Mathematical Society CS1 Maint: önerilmeyen parametre ( bağlantı )
• Kőnig, D. (1927), "Über eine Schlussweise aus dem Endlichen ins Unendliche" , Açta Sci. Matematik. (Szeged) (Almanca) (3 (2-3)): 121-130, arşivlenmiş orijinal 2014-12-23 tarihinde , alınan 2014-12-23 CS1 Maint: önerilmeyen parametre ( bağlantı )
• Lévy, Azriel (1979), Temel Küme Teorisi , Springer, ISBN   3-540-08417-7 , MR   0533962 ; yeniden basım, Dover, 2002, ISBN   0-486-42079-5 .
• Rogers, Hartley, Jr. (1967), Özyinelemeli Fonksiyonlar ve Etkili Hesaplanabilirlik Teorisi , McGraw-Hill, MR   0224462
• Truss, J. (1976), "König lemmasının bazı vakaları", Marek, V. Wiktor; Srebrny, Marian; Zarach, Andrzej (ed.), Küme teorisi ve hiyerarşi teorisi: Andrzej Mostowski'ye bir anma övgü , Matematikte Ders Notları, 537 , Springer, s. 273–284, doi : 10.1007 / BFb0096907 , MR   0429557

daha fazla okuma

• Cenzer, Douglas (1999), " hesaplanabilirlik teorisindeki sınıflar", Hesaplanabilirlik Teorisi El Kitabı , Elsevier, s.  37–85 , doi : 10.1016 / S0049-237X (99) 80018-4 , ISBN${\ displaystyle \ Pi _ {1} ^ {0}}$  0-444-89882-4 , MR   1720779
• Kőnig, D. (1926), "Sur les yazışmaları multivoques des topluluklar" (PDF) , Fundamenta Mathematicae (Fransızca) (8): 114-134 CS1 Maint: önerilmeyen parametre ( bağlantı )
• Kınig, D. (1936), Theorie der Endlichen und Unendlichen Graphen: Kombinatorische Topologie der Streckenkomplexe (Almanca), Leipzig: Akad. Verlag
• Simpson, Stephen G. (1999), İkinci Derece Aritmetiğin Alt Sistemleri, Matematiksel Mantık Perspektifleri, Springer, ISBN   3-540-64882-8 , MR   1723993
• Soare, Robert I. (1987), Özyineli Olarak Numaralandırılabilir Kümeler ve Dereceler: Hesaplanabilir fonksiyonlar ve hesaplanabilir şekilde oluşturulmuş kümeler üzerine bir çalışma, Matematiksel Mantık Perspektifleri, Springer, ISBN   3-540-15299-7 , MR   0882921 CS1 Maint: önerilmeyen parametre ( bağlantı )

Dış bağlantılar

• Stanford Felsefe Ansiklopedisi: Yapıcı Matematik
• Mizar projesi tamamen resmiyet ve otomatik dosya içinde König lemmasının bir versiyonunun kanıtı kontrol etmiştir TREES_2 .