Löwenheim–Skolem teoremi - Löwenheim–Skolem theorem

Gelen matematiksel mantık , Löwenheim-Skolem teoremi varlığı ve bir teoremi olan kardinalitesi ait modelleri adını, Leopold Löwenheim ve Thoralf Skolem .

Kesin formülasyon aşağıda verilmiştir. Bu, sayılabilir bir birinci mertebeden teorinin sonsuz bir modeli varsa , o zaman her sonsuz temel sayı κ için κ büyüklüğünde bir modele sahip olduğunu ve sonsuz bir modele sahip hiçbir birinci mertebeden teorinin izomorfizme kadar benzersiz bir modele sahip olamayacağını ima eder . Sonuç olarak, birinci dereceden teoriler, sonsuz modellerinin kardinalitesini kontrol edemezler.

(Aşağı doğru) Löwenheim-Skolem teoremi, Lindström teoreminde birinci dereceden mantığı karakterize etmek için kullanılan kompaktlık teoremi ile birlikte iki temel özellikten biridir . Genel olarak, Löwenheim-Skolem teoremi, ikinci dereceden mantık gibi daha güçlü mantıklarda geçerli değildir .

teorem

Löwenheim–Skolem teoreminin çizimi

Genel biçiminde, Löwenheim–Skolem Teoremi , her σ imzası için , her sonsuz σ - M yapısının ve her sonsuz kardinal sayının κ ≥ | σ | , öyle bir σ - yapısı N vardır | N | = κ ve öyle ki

  • eğer k < | M | o zaman N , M'nin temel bir alt yapısıdır ;
  • eğer κ > | M | o zaman N , M'nin temel bir uzantısıdır .

Teorem genellikle yukarıdaki iki duruma karşılık gelen iki kısma ayrılır. Teoremin bir yapının tüm küçük sonsuz kardinalitelerin temel alt yapılarına sahip olduğunu iddia eden kısmı aşağı doğru Löwenheim-Skolem Teoremi olarak bilinir . Teoremin, bir yapının tüm büyük kardinalitelerin temel uzantılarına sahip olduğunu iddia eden kısmı, yukarı doğru Löwenheim-Skolem Teoremi olarak bilinir .

Tartışma

Aşağıda, genel imza ve yapı kavramını ayrıntılı olarak ele alıyoruz.

kavramlar

imzalar

Bir imza fonksiyonu semboller bir dizi oluşur S fonksiyon , ilişki semboller bir dizi S rel ve bir fonksiyonu temsil Arity fonksiyonu ve ilişki sembolleri. (Boş bir işlev sembolüne sabit sembol denir.) Birinci derece mantık bağlamında, bir imza bazen dil olarak adlandırılır. İçindeki fonksiyon ve ilişki sembolleri kümesi sayılabilir ise sayılabilir denir ve genel olarak bir imzanın kardinalitesi içerdiği tüm sembollerin kümesinin kardinalliğidir.

Birinci dereceden bir teori , sabit bir imzadan ve bu imzada sabit bir dizi cümleden (serbest değişkenleri olmayan formüller) oluşur. Teoriler genellikle teoriyi oluşturan aksiyomların bir listesi verilerek veya bir yapı verilerek ve teorinin yapı tarafından tatmin edilen cümlelerden oluştuğunu alarak belirtilir.

Yapılar / Modeller

Bir imza Verilen σ , bir σ - yapı M sembollerin somut yorumudur σ . Temel bir kümeden (genellikle " M " ile gösterilir ) ve σ'nın fonksiyon ve ilişki sembollerinin yorumlanmasından oluşur . Sabit bir sembolün bir yorumlama σ içinde M basitçe bir elementtir M . Daha genel olarak, bir bir yorumu N -ary işlev simgesi f bir fonksiyonudur M n için M . Benzer şekilde, bir ilişki sembolü bir yorumlama R bir bir N ile -ary ilişki M , yani bir alt kümesi  M n .

Bir bir alt σ -Elektroseramiklerde yapı M bir alt alan ile elde edilir , N ve M tüm işlev sembollerin yorumların altında kapatılır σ (dolayısıyla tüm sabit sembollerin uyarlamalarını içermektedir σ yorumunu), ve daha sonra kısıtlayıcı N ile ilişki sembolleri . Bir ilköğretim altyapı bu çok özel bir durumdur; özellikle temel bir altyapı, orijinal yapıyla (temel uzantısı) tam olarak aynı birinci dereceden cümleleri karşılar.

Sonuçlar

Girişte verilen ifade, M'yi teorinin sonsuz bir modeli olarak alarak hemen takip eder. Teoremin yukarı kısmının ispatı, keyfi olarak büyük sonlu modellere sahip bir teorinin sonsuz bir modeli olması gerektiğini de gösterir; bazen bu teoremin bir parçası olarak kabul edilir.

Bir teori, izomorfizme kadar yalnızca bir modeli varsa kategorik olarak adlandırılır . Bu terim Veblen (1904) tarafından tanıtıldı ve bir süre sonra matematikçiler küme teorisinin bazı versiyonlarının kategorik bir birinci dereceden teorisini tanımlayarak matematiği sağlam bir temele oturtabileceklerini umdular. Löwenheim-Skolem teoremi, sonsuz bir modeli olan birinci dereceden bir teorinin kategorik olamayacağını ima ettiği için bu umuda ilk darbeyi vurdu. Daha sonra, 1931'de umut, Gödel'in eksiklik teoremi tarafından tamamen paramparça oldu .

Löwenheim-Skolem teoreminin birçok sonucu, birinci dereceden ve birinci dereceden olmayan özellikler arasındaki ayrım henüz anlaşılmadığından, 20. yüzyılın başlarında mantıkçılar için mantıksız görünüyordu. Böyle bir sonuç, her birinci dereceden tümevarım aksiyomunu karşılayan, ancak tümevarımsal olmayan alt kümelere sahip olan sayılamayan gerçek aritmetik modellerinin varlığıdır .

Let , N , doğal sayılar ve ifade R realse. Teoremden, ( N , +, ×, 0, 1) teorisinin (gerçek birinci mertebeden aritmetik teorisi) sayılamayan modelleri olduğu ve ( R , +, ×, 0, 1) teorisinin ( gerçek kapalı alanlar teorisi ) sayılabilir bir modele sahiptir. Elbette ( N , +, ×, 0, 1) ve ( R , +, ×, 0, 1) ile izomorfizme kadar karakterize eden aksiyomatizasyonlar vardır . Löwenheim-Skolem teoremi, bu aksiyomatizasyonların birinci dereceden olamayacağını gösterir. Örneğin, gerçek sayılar teorisinde, R'yi tam sıralı bir alan olarak karakterize etmek için kullanılan doğrusal bir düzenin eksiksizliği, birinci dereceden olmayan bir özelliktir.

Özellikle rahatsız edici olduğu düşünülen bir diğer sonuç, yine de gerçek sayıların sayılamayan olduğu cümlesini karşılaması gereken sayılabilir bir küme teorisi modelinin varlığıdır. Cantor teoremi , bazı kümelerin sayılamayan olduğunu belirtir. Bu mantık dışı durum Skolem'in paradoksu olarak bilinir hale geldi ; sayılabilirlik kavramının mutlak olmadığını gösterir .

Kanıt kroki

Aşağı doğru kısım

Her birinci dereceden formül için seçim aksiyomu bir fonksiyonun varlığını ima eder.

öyle ki, herkes için , ya

veya

Seçim aksiyomunu tekrar uygulayarak, birinci dereceden formüllerden bu tür işlevlere bir işlev elde ederiz.

Fonksiyon ailesi , güç setinde bir ön kapama operatörüne yol açar .

için

Yineleme bir de sayılabilir birçok kez sonuç kapanış operatörü rasgele bir alt kümesini almak şekilde ve tanımlanmış olan bir de bu görebilir sonra bir temel alt olan göre Tarski-Vaught testi .

Bu ispatta kullanılan hile, esasen, Skolem fonksiyonları için fonksiyon sembollerini dile getiren Skolem'den kaynaklanmaktadır . Bir de tanımlayabilir olarak kısmi fonksiyonlar şekilde , ancak ve ancak tanımlanır ancak önemli olan husus, böyle bir preclosure operatörü parametreleri ile her bir formül için bir çözüm içerir içinde bir çözelti olan ve

yukarı kısım

İlk olarak, M öğesinin her öğesi için yeni bir sabit sembol ekleyerek imza genişletilir . Tam teorisi M genişletilmiş imza için σ' olarak adlandırılır prensip ait M . Bir sonraki adımda , imzaya κ birçok yeni sabit sembol eklenir ve herhangi iki farklı yeni sabit sembol c ve c' için M'nin temel diyagramına cc' cümleleri eklenir . Kompaktlık teoremini kullanarak, ortaya çıkan teorinin tutarlı olduğu kolayca görülür. Modellerinin en az κ kardinalitesine sahip olması gerektiğinden , bu teoremin aşağı doğru kısmı , kardinalitesi tam olarak κ olan bir N modelinin varlığını garanti eder . Temel bir altyapı olarak M'nin izomorfik bir kopyasını içerir .

diğer mantıklarda

(Klasik) Löwenheim-Skolem teoremi birinci mertebeden mantığa çok yakından bağlı olmasına rağmen, değişkenler diğer mantıklar için geçerlidir. Örneğin, ikinci dereceden mantıktaki her tutarlı teori , birinci süper kompakt kardinalden daha küçük bir modele sahiptir (var olduğu varsayılarak). Bir mantıkta (aşağıya doğru) bir Löwenheim-Skolem-tipi teoreminin uygulandığı minimum boyut, Löwenheim sayısı olarak bilinir ve bu mantığın gücünü karakterize etmek için kullanılabilir. Ayrıca, birinci dereceden mantığın ötesine geçersek, üç şeyden birinden vazgeçmemiz gerekir: sayılabilir kompaktlık, aşağı doğru Löwenheim-Skolem Teoremi veya soyut bir mantığın özellikleri .

Tarihsel notlar

Bu hesap esas olarak Dawson'a (1993) dayanmaktadır . Model teorisinin erken tarihini anlamak için, sözdizimsel tutarlılık (birinci dereceden mantık için tümdengelim kuralları kullanılarak hiçbir çelişki elde edilemez) ile tatmin edilebilirlik (bir model vardır) arasında ayrım yapılmalıdır . Biraz şaşırtıcı bir şekilde, tamlık teoremi bu ayrımı gereksiz hale getirmeden önce bile , tutarlı terimi bazen bir anlamda, bazen de diğer anlamda kullanılmıştır.

Daha sonra ne oldu ilk önemli sonuç modeli teorisi oldu Löwenheim teoremi içinde Leopold Löwenheim 'ın yayın 'Über Möglichkeiten im Relativkalkül'(1915):

Her sayılabilir imza için σ , karşılanabilir olan her σ -cümlesi sayılabilir bir modelde karşılanabilir.

Löwenheim'ın makalesi aslında daha genel Peirce –Schröder akrabalar hesabı ( niceleyicilerle ilişki cebiri) ile ilgiliydi . Ayrıca Ernst Schröder'in artık eskimiş notasyonlarını da kullandı . Makalenin İngilizce özeti ve modern gösterimler için bkz. Brady (2000 , bölüm 8).

Alınan tarihsel görüşe göre, Löwenheim'ın ispatı hatalıydı, çünkü lemma o sırada henüz yayınlanmış bir sonuç olmasa da, Kőnig'in lemmasını ispatlamadan dolaylı olarak kullandı . Badesa (2004) , revizyonist bir anlatımda , Löwenheim'ın ispatının tamamlanmış olduğunu düşünmektedir.

Skolem (1920) , daha sonra Skolem normal form olarak adlandırılacak olan formülleri kullanarak ve seçim aksiyomuna dayanarak (doğru) bir kanıt verdi :

M modelinde karşılanabilen her sayılabilir teori , M'nin sayılabilir bir alt yapısında karşılanabilir .

Skolem (1922) ayrıca, seçim aksiyomu olmaksızın aşağıdaki daha zayıf versiyonu kanıtladı:

Bir modelde karşılanabilen her sayılabilir teori, sayılabilir bir modelde de karşılanabilir.

Skolem (1929) basitleştirilmiş Skolem (1920) . Son olarak, Anatoly Ivanovich Maltsev (Анато́лий Ива́нович Ма́льцев, 1936) Löwenheim-Skolem teoremini tam genelliğiyle kanıtladı ( Maltsev 1936 ). Skolem'in bir notundan alıntı yaptı, buna göre teorem Alfred Tarski tarafından 1928'de bir seminerde kanıtlandı . Bu nedenle, genel teorem bazen Löwenheim-Skolem-Tarski teoremi olarak bilinir . Ancak Tarski kanıtını hatırlamıyordu ve bunu kompaktlık teoremi olmadan nasıl yapabileceği bir sır olarak kaldı .

Skolem'in adının teoremin yukarı yönü ve aşağı yönü ile bağlantılı olması biraz ironiktir:

"Corollary 6.1.4'ü yukarı doğru Löwenheim-Skolem teoremi olarak adlandırma geleneğini takip ediyorum. Ama aslında Skolem buna inanmadı bile çünkü sayılamayan kümelerin varlığına inanmıyordu." Hodges (1993) .
"Skolem [...] sonucu anlamsız olarak reddetti; Tarski [...] oldukça makul bir şekilde Skolem'in biçimci bakış açısının aşağı doğru Löwenheim-Skolem teoremini tıpkı yukarı doğru gibi anlamsız sayması gerektiğini söyledi." Hodges (1993) .
"Efsaneye göre Thoralf Skolem, hayatının sonuna kadar, adının saçmalık olarak gördüğü bu türün bir sonucuyla ilişkilendirilmesiyle skandallandı, onun için sayılamayan setler, onun için gerçek varlığı olmayan kurgular." Poizat (2000) .

Referanslar

Kaynaklar

Löwenheim-Skolem teoremi, model teorisi veya matematiksel mantıkla ilgili tüm giriş metinlerinde işlenir .

Tarihsel yayınlar

  • Löwenheim, Leopold (1915), "Über Möglichkeiten im Relativkalkül" (PDF) , Mathematische Annalen , 76 (4): 447–470, doi : 10.1007/BF01458217 , ISSN  0025-5831 , S2CID  116581304
  • Maltsev, Anatoly Ivanovich (1936), "Untersuchungen aus dem Gebiete der mathematischen Logik" , Matematicheskii Sbornik , Novaya Seriya, 1(43) (3): 323–336
  • Skolem, Thoralf (1920), "Logisch-kombinatorische Untersuchungen über die Erfüllbarkeit oder Beweisbarkeit matematischer Sätze nebst einem Teorem über dichte Mengen", Videnskapsselskapet Skrifter, I. Matematisk-naturviden , 4 : 1
    • Skolem, Thoralf (1977), "Matematiksel önermelerin karşılanabilirliği veya kanıtlanabilirliği konusunda mantıksal-kombinatorik araştırmalar: L. Löwenheim tarafından bir teoremin basitleştirilmiş kanıtı ve teoremin genellemeleri", Frege'den Gödel'e: Matematiksel Mantıkta Bir Kaynak Kitap, 1879-1931 (3. baskı), Cambridge, Massachusetts: Harvard University Press, s. 252–263, ISBN 0-674-32449-8( çevrimiçi kopya , s. 252, Google Kitaplar'da )
  • Skolem, Thoralf (1922), "Einige Bemerkungen zu axiomatischen Begründung der Mengenlehre", Mathematikerkongressen I Helsingfors den 4–7 Temmuz 1922, den Femte Skandinaviska Matematikerkongressen, Redogörelse : 217–232
  • Skolem, Thoralf (1929), "Über einige Grundlagenfragen der Mathematik", Skrifter Utgitt av Det Norske Videnskaps-Akademi I Oslo, I. Matematisk-naturvidenskabelig Klasse , 7 : 1–49
  • Veblen, Oswald (1904), "Geometri için Bir Aksiyom Sistemi", Amerikan Matematik Derneği İşlemleri , 5 (3): 343-384, doi : 10.2307/1986462 , ISSN  0002-9947 , JSTOR  1986462

İkincil kaynaklar

Dış bağlantılar