Curry'nin paradoksu - Curry's paradox

Curry'nin paradoksu , keyfi bir F iddiasının , sadece birkaç görünüşte zararsız mantıksal tümdengelim kuralı gerektiren , kendisi için " C ise , o zaman F " diyen bir C cümlesinin yalnızca varlığından kanıtlandığı bir paradokstur . Yana F keyfi, bu kuralları olan herhangi mantık bir şeyi kanıtlamak için izin verir. Paradoks, doğal dilde ve belirli küme teorisi biçimleri , lambda hesabı ve birleştirici mantık dahil olmak üzere çeşitli mantıklarda ifade edilebilir .

Paradoks, mantıkçı Haskell Curry'nin adını almıştır . Löb teoremi ile olan ilişkisi nedeniyle Martin Hugo Löb'den sonra Löb paradoksu olarak da adlandırılmıştır .

doğal dilde

"A ise, o zaman B" şeklindeki istemlere koşullu istemler denir . Curry'nin paradoksu, bu örnekte gösterildiği gibi, belirli bir tür kendine gönderme yapan koşullu cümle kullanır:

Almanya Çin sınırında olmasa da , örnek cümle kesinlikle doğal dilde bir cümledir ve bu nedenle bu cümlenin doğruluğu analiz edilebilir. Paradoks bu analizden çıkar. Analiz iki adımdan oluşmaktadır.

1. İlk olarak, örnek cümlenin doğru olduğunu kanıtlamak için yaygın doğal dil kanıtlama teknikleri kullanılabilir.
2. İkincisi, örnek cümlenin gerçeği, Almanya'nın Çin ile sınır komşusu olduğunu kanıtlamak için kullanılabilir. Almanya'nın Çin'e sınırı olmadığı için bu, delillerden birinde bir hata olduğunu gösteriyor.

"Almanya'nın Çin ile sınırı" iddiası, başka herhangi bir iddia ile değiştirilebilir ve ceza yine de kanıtlanabilir olacaktır. Böylece her cümle kanıtlanabilir görünüyor. İspat yalnızca iyi kabul edilmiş tümdengelim yöntemlerini kullandığından ve bu yöntemlerin hiçbiri yanlış görünmediğinden, bu durum paradoksaldır.

resmi olmayan kanıt

Koşullu cümleleri kanıtlamak için standart yöntem ("eğer A, o zaman B" şeklindeki cümleler) " koşullu kanıt " olarak adlandırılır . Bu yöntemde "A ise, o zaman B"yi ispatlamak için önce A varsayılır ve daha sonra bu varsayımla B'nin doğru olduğu gösterilir.

Yukarıdaki iki adımda anlatıldığı gibi Curry paradoksunu üretmek için bu yöntemi "eğer bu cümle doğruysa, Almanya Çin ile sınır komşusudur" cümlesine uygulayın. Burada A, "bu cümle doğrudur", tüm cümleyi ifade ederken, B, "Almanya'nın Çin ile sınırıdır". Yani, A'yı varsaymak, "A ise, o zaman B" varsayımıyla aynıdır. Bu nedenle, A'yı varsayarken, hem A'yı hem de "A ise, o zaman B"yi varsaydık. Bu nedenle, modus ponens tarafından B doğrudur ve "Bu cümle doğruysa, o zaman 'Almanya Çin'in sınırındadır'' doğru olduğunu kanıtladık. her zamanki gibi, hipotezi varsayarak ve sonuca vararak.

Şimdi, "Eğer bu cümle doğruysa, o zaman 'Almanya Çin sınırındadır'' diye ispatladığımız için, o zaman yine modus ponens'i uygulayabiliriz, çünkü biliyoruz ki, "bu cümle doğrudur" iddiası doğrudur. Bu şekilde Almanya'nın Çin ile sınır komşusu olduğu sonucunu çıkarabiliriz.

resmi kanıt

cümle mantığı

Önceki bölümdeki örnek, biçimselleştirilmemiş, doğal dil akıl yürütmesini kullandı. Curry'nin paradoksu, bazı biçimsel mantık türlerinde de ortaya çıkar . Bu bağlamda, X'in kendisinin (X → Y) eşdeğer olduğu bir biçimsel cümle (X → Y) olduğunu varsayarsak, Y'yi biçimsel bir kanıtla kanıtlayabileceğimizi gösterir. Böyle bir resmi kanıtın bir örneği aşağıdaki gibidir. Bu bölümde kullanılan mantık gösteriminin açıklaması için, mantık sembolleri listesine bakın .

1. X := (X → Y)
   
   varsayım , başlangıç ​​noktası, "Bu cümle doğruysa, o zaman Y" ile eşdeğerdir.
2. X → X
   
   kimlik yasası
3. X → (X → Y)
   
   2'nin sağ tarafını değiştirin , çünkü X, X → Y'ye 1 ile eşdeğerdir
4. X → Y
   
   3'ten daralma ile
5. X
   
   4 yerine 1 koy
6. Y
   
   modus ponens tarafından 5 ve 4'ten

Alternatif bir kanıt Peirce yasası aracılığıyladır . X = X → Y ise (X → Y) → X. Bu, Peirce yasası ((X → Y) → X) → X ve modus ponens ile birlikte X'i ve ardından Y'yi (yukarıdaki kanıtta olduğu gibi) ifade eder.

Bu nedenle, eğer Y biçimsel bir sistemde ispatlanamaz bir ifade ise, o sistemde X'in ima (X → Y) ile eşdeğer olduğu bir X ifadesi yoktur. Buna karşılık, önceki bölüm, doğal (formalize edilmemiş) dilde, her doğal dil ifadesi Y için bir doğal dil ifadesi Z olduğunu, öyle ki Z'nin doğal dilde (Z → Y)'ye eşdeğer olduğunu gösterir. Yani Z, "Bu cümle doğruysa Y"dir.

Y'nin sınıflandırmasının zaten bilindiği belirli durumlarda, çelişkiyi ortaya çıkarmak için birkaç adım gereklidir. Örneğin, Y "Almanya, Çin ile sınır komşusudur" olduğunda, Y'nin yanlış olduğu bilinir.

1. X = (X → Y)
   
   Varsayım
2. X = (X → yanlış)
   
   Y'nin bilinen değerini değiştir
3. X = (¬X ∨ yanlış)
   
   Ima
4. X = ¬X
   
   Kimlik

Naif küme teorisi

Altta yatan matematiksel mantık herhangi bir kendine referans cümlesini kabul etmese bile, bazı saf küme teorisi biçimleri hala Curry'nin paradoksuna karşı savunmasızdır. Sınırsız kavramaya izin veren küme teorilerinde , yine de kümeyi inceleyerek herhangi bir mantıksal Y ifadesini ispatlayabiliriz.

Bunun hem ve üzerinde öncelikli olduğunu varsayarsak , ispat aşağıdaki gibi ilerler: ${\görüntüleme stili \içinde }$ ${\görüntüleme stili \ için }$${\görüntüleme stili \sol sağ ok }$

1. ${\displaystyle X=\sol\{x\orta x\in x\to Y\sağa\}}$
   
   X'un tanımı
2. ${\displaystyle x=X\to (x\in x\sol sağ ok X\inX)}$
   
   Üyelikte eşit kümelerin ikamesi
3. ${\displaystyle x=X\to ((x\in x\to Y)\sol sağ ok (X\in X\to Y))}$
   
   İki koşulun her iki tarafına bir sonucun eklenmesi (2'den)
4. ${\displaystyle X\in X\sol sağ ok (X\in X\to Y)}$
   
   Beton yasası (1 ve 3'ten)
5. ${\displaystyle X\in X\to (X\in X\to Y)}$
   
   İki koşullu eleme (4'ten)
6. ${\displaystyle X\in X\to Y}$
   
   Kasılma (5'ten itibaren)
7. ${\displaystyle (X\in X\to Y)\to X\in X}$
   
   İki koşullu eleme (4'ten)
8. ${\displaystyle X\in X}$
   
   Modus ponens (6 ve 7'den itibaren)
9. ${\görüntüleme stili Y}$
   
   Modus ponens (8 ve 6'dan itibaren)

Adım 4, tutarlı bir küme teorisinde geçersiz olan tek adımdır. In Zermelo-Fraenkel küme teorisine belirterek fazladan hipotez X (ile ZFC ZF veya onun uzantısında kanıtlanabilir değildir gerekli olacağını setidir Seçim aksiyomu ).

Bu nedenle, tutarlı bir küme teorisinde, yanlış Y için küme mevcut değildir . Bu, Russell paradoksunun bir varyantı olarak görülebilir , ancak aynı değildir. Küme teorisi için bazı öneriler, Russell'ın paradoksunu anlama kuralını kısıtlayarak değil, mantık kurallarını kısıtlayarak, kendi üyesi olmayan tüm kümelerin kümesinin çelişkili doğasını tolere edecek şekilde ele almaya çalışmıştır . Yukarıdaki gibi ispatların varlığı, böyle bir görevin o kadar basit olmadığını göstermektedir, çünkü yukarıdaki ispatta kullanılan tümdengelim kurallarından en az biri çıkarılmalı veya sınırlandırılmalıdır. ${\displaystyle \sol\{x\orta x\in x\to Y\sağa\}}$

Lambda hesabı

Curry'nin paradoksu, kısıtlı minimal mantıkla zenginleştirilmiş, türlenmemiş lambda hesabında ifade edilebilir . Lambda hesabının sözdizimsel kısıtlamalarıyla başa çıkmak için, iki parametre alarak ima fonksiyonunu belirtmelidir, yani lambda terimi olağan infix notasyonuna eşdeğer olacaktır . ${\görüntüleme stili m}$${\görüntüleme stili ((mA)B)}$ ${\ Displaystyle A\'dan B'ye}$

Keyfi bir formül , bir lambda işlevi tanımlanarak kanıtlanabilir ve burada Curry'nin sabit nokta birleştiricisini belirtir . Daha sonra tanımına ve bu nedenle yukarıda belirtilen cümlesel mantık geçirmez Diferensiyel çoğaltılmış olabilir: ${\görüntüleme stili Z}$${\displaystyle N:=\lambda p.((mp)Z)}$${\displaystyle X:=({\textsf {Y}}N)}$${\displaystyle {\textsf {Y}}}$${\görüntüleme stili X=(NX)=((mX)Z)}$${\displaystyle {\textsf {Y}}}$${\görüntüleme stili N}$

İçinde sadece yazılmış Lambda hesabı , sabit nokta combinators yazılan edilemez ve bu nedenle kabul edilmez.

birleştirici mantık

Curry'nin paradoksu, lambda hesabıyla eşdeğer ifade gücüne sahip olan birleştirici mantıkta da ifade edilebilir . Herhangi bir lambda ifadesi birleştirici mantığa çevrilebilir, bu nedenle Curry'nin paradoksunun lambda hesabındaki uygulamasının çevirisi yeterli olacaktır.

Yukarıdaki terim anlamına kombinatoriyel mantığı içinde ${\görüntüleme stili X}$${\görüntüleme stili (r\ r)}$

dolayısıyla

Tartışma

Curry'nin paradoksu, kendi kendini özyinelemeli bir işlevin bir ifade olarak oluşturulmasına izin veren temel mantık işlemlerini destekleyen herhangi bir dilde formüle edilebilir. Paradoksun inşasını destekleyen iki mekanizma, kendine referans (bir cümle içinden "bu cümleye" atıfta bulunma yeteneği) ve naif küme teorisinde sınırsız anlamadır . Doğal diller neredeyse her zaman, diğer birçok dilde olduğu gibi, paradoksu oluşturmak için kullanılabilecek birçok özellik içerir. Genellikle bir dile meta programlama yeteneklerinin eklenmesi, gereken özellikleri ekleyecektir. Matematiksel mantık genellikle kendi cümlelerine açık bir göndermeye izin vermez. Bununla birlikte, Gödel'in eksiklik teoremlerinin kalbi, farklı bir öz-gönderim biçiminin eklenebileceği gözlemidir; Gödel numarasına bakınız .

Sınırsız anlama aksiyomu, küme teorisinde özyinelemeli bir tanım oluşturma yeteneğini ekler. Bu aksiyom, modern küme teorisi tarafından desteklenmemektedir .

İspatın oluşturulmasında kullanılan mantık kuralları , koşullu ispat için varsayım kuralı, büzülme kuralı ve modus ponens'tir . Bunlar, birinci dereceden mantık gibi en yaygın mantıksal sistemlere dahildir.

Bazı biçimsel mantık için sonuçlar

1930'larda, Curry'nin paradoksu ve ilgili Kleene-Rosser paradoksu , özyinelemeli ifadelere dayanan biçimsel mantık sistemlerinin tutarsız olduğunu göstermede önemli bir rol oynadı . Bunlar, lambda hesabının ve birleştirici mantığın bazı versiyonlarını içerir .

Curry, Kleene-Rosser paradoksu ile başladı ve temel sorunun bu daha basit Curry paradoksunda ifade edilebileceği sonucuna vardı. Onun sonucu, yine de özyinelemeye izin verirken, birleştirici mantık ve lambda hesabının tümdengelimli diller olarak tutarlı hale getirilemeyeceğini söyleyerek ifade edilebilir.

Açıklayıcı (tümdengelimli) birleştirici mantık çalışmasında , 1941'de Curry, paradoksun ima ettiğini, kısıtlama olmaksızın, bir birleştirici mantığın aşağıdaki özelliklerinin uyumsuz olduğunu ima ettiğini kabul etti:

1. Kombinatoryal tamlık . Bu, bir soyutlama operatörünün sistemde tanımlanabilir (veya ilkel) olduğu anlamına gelir; bu, sistemin ifade gücüne ilişkin bir gerekliliktir.
2. Tümdengelimli tamlık . Bu türetilebilirlik için bir gerekliliktir, yani, maddi çıkarım ve modus ponens ile resmi bir sistemde, eğer Y, X hipotezinden kanıtlanabilirse, o zaman X → Y'nin de bir kanıtı vardır.

çözüm

Yalancı paradoksu veya Russell paradoksunun aksine, Curry paradoksunun , tamamen olumsuzlama içermediği için hangi olumsuzlama modelinin kullanıldığına bağlı olmadığını unutmayın . Bu nedenle, tutarsız mantıklar , yalancı paradoksa bağışık olsalar bile, bu paradoksa karşı hala savunmasız olabilirler.

Lambda hesabında çözünürlük yok

Kökeni Alonzo Church 'ın lambda calculus 'Eğer bir denklemi çözmek bir fonksiyonun bir tanımını sağlamak üzere nasıl?' Olmuş olabilir. Bu, bu denklikte ifade edilir,

Bu tanım, denklemi sağlayan tek bir fonksiyon varsa geçerlidir , aksi takdirde geçersizdir. Stephen Cole Kleene ve ardından Haskell Curry'nin birleştirici mantık ve Lambda hesabı ile keşfettiği problemin özü budur . ${\görüntüleme stili f}$${\görüntüleme stili f\ x=y}$

durum tanımlama ile karşılaştırılabilir

Bu tanım, karekök için yalnızca pozitif değerlere izin verildiği sürece iyidir. Matematikte varoluşsal olarak nicelleştirilmiş bir değişken birden fazla değeri temsil edebilir, ancak her seferinde yalnızca bir tane. Varoluşsal niceleme, bir denklemin birçok örneğinin ayrılmasıdır . Her denklemde değişken için bir değer bulunur.

Ancak matematikte, serbest değişkeni olmayan bir ifadenin bir ve yalnızca bir değeri olmalıdır. Yani sadece temsil edebilir . Ancak lambda soyutlamasını tek bir değerle sınırlamanın veya bir değer olduğundan emin olmanın uygun bir yolu yoktur. ${\ Displaystyle {\sqrt {4}}}$${\görüntüleme stili +2}$

Lambda hesabı, parametre olarak adlandırılan aynı işlevi ileterek özyinelemeye izin verir. Bu , için birden fazla veya hiç çözümü olmayan durumlara izin verir . ${\görüntüleme stili f\ x=y}$${\görüntüleme stili f}$

Lambda hesabı, yalnızca bir denklemin tek bir çözümünü temsil eden lambda soyutlamalarına izin verilirse matematiğin bir parçası olarak kabul edilebilir. Diğer lambda soyutlamaları matematikte yanlıştır.

Curry paradoksu ve diğer paradokslar, tümdengelimli bir sistem olarak kabul edilen Lambda hesabının tutarsızlığı nedeniyle Lambda hesabında ortaya çıkar . Ayrıca bkz . tümdengelimli lambda hesabı .

Lambda hesabı terimlerinin alanı

Lambda hesabı, kendi alanında tutarlı bir teoridir . Ancak lambda soyutlama tanımını genel matematiğe eklemek tutarlı değildir . Lambda terimleri, lambda hesabı alanındaki değerleri tanımlar. Her lambda teriminin o etki alanında bir değeri vardır.

İfadeleri matematikten lambda hesabına çevirirken, lambda hesabı terimlerinin alanı her zaman matematiksel ifadelerin alanına eşbiçimli değildir . Bu izomorfizm eksikliği, görünen çelişkilerin kaynağıdır.

Kısıtlanmamış dillerde çözünürlük

Hiç veya çok fazla çözümü olmayan bir denklemi örtük olarak çağıran birçok dil yapısı vardır. Bu sorunun sağlam çözümü, bu ifadeleri varoluşsal olarak nicelleştirilmiş bir değişkene sözdizimsel olarak bağlamaktır. Değişken, ortak insan muhakemesinde anlamlı olan, ancak matematikte de geçerli olan çoklu değerleri temsil eder.

Örneğin, Eval işlevine izin veren doğal bir dil matematiksel olarak tutarlı değildir. Ancak o doğal dilde Eval'e yapılan her çağrı tutarlı bir şekilde matematiğe çevrilebilir. Eval(ler) in matematiğe çevirisi

Öyleyse s = "Değer(ler) → y" olduğunda,

y yanlışsa, x = x → y yanlıştır, ancak bu bir yanlışlıktır, paradoks değil.

x değişkeninin varlığı doğal dilde örtüktü. Doğal dil matematiğe çevrildiğinde x değişkeni oluşturulur. Bu, matematiksel bütünlüğü korurken doğal dili doğal anlambilimle kullanmamıza izin verir.

Biçimsel mantıkta çözünürlük

Biçimsel mantıktaki argüman, (X → Y) X olarak adlandırmanın geçerliliğini varsaymakla başlar. Ancak bu geçerli bir başlangıç ​​noktası değildir. İlk önce adlandırmanın geçerliliğini çıkarmalıyız. Aşağıdaki teorem kolayca ispatlanabilir ve böyle bir adlandırmayı temsil eder:

Yukarıdaki ifadede A formülü X olarak adlandırılmıştır. Şimdi formülü A için (X → Y) ile somutlaştırmaya çalışın . Ancak bu mümkün değildir, çünkü kapsamının kapsamı içindedir . Niceleyicilerin sırası Skolemization kullanılarak tersine çevrilebilir : ${\görüntüleme stili \var X}$${\ Displaystyle \ için A}$

Ancak, şimdi örnekleme verir

ki bu ispat için başlangıç ​​noktası değildir ve bir çelişkiye yol açmaz. A için paradoksun başlangıç ​​noktasına götüren başka bir örnekleme yoktur.

Küme teorisinde çözünürlük

In Zermelo-Fraenkel küme kuramı (ZFC), sınırsız anlama beliti setleri inşa edilmesine izin aksiyomları bir grup ile değiştirilir. Yani Curry'nin paradoksu ZFC'de ifade edilemez. ZFC, Russell'ın paradoksuna yanıt olarak gelişti.

Ayrıca bakınız

• Russell paradoksu
• Girard'ın paradoksu
• Kleene-Rosser paradoksu
• yalancı paradoks
• paradoksların listesi
• Richard'ın paradoksu
• Zermelo-Fraenkel küme teorisi
• Sabit nokta birleştirici
• Tümdengelimli lambda hesabı
• ifade edelim

Referanslar

Dış bağlantılar

• Beall, JC "Curry'nin paradoksu" . Gelen Zalta, Edward N. (ed.). Stanford Felsefe Ansiklopedisi .
• Cantini, Andrea. "Paradokslar ve Çağdaş Mantık" . Gelen Zalta, Edward N. (ed.). Stanford Felsefe Ansiklopedisi .
• Penguenler Evreni Yönetiyor: Penguenlerin Evreni Yönettiğinin Bir Kanıtı , Curry'nin paradoksunun kısa ve eğlenceli bir tartışması.