Tutarlılık - Consistency

In klasik tümdengelim mantık , bir tutarlı teori mantıksal yol açmaz biridir çelişki . Çelişki olmaması, anlamsal veya sözdizimsel terimlerle tanımlanabilir . Anlamsal tanım, bir teorinin bir modeli varsa tutarlı olduğunu belirtir , yani teorideki tüm formüllerin doğru olduğu bir yorum vardır. Bu, geleneksel Aristoteles mantığında kullanılan anlamdır , ancak çağdaş matematiksel mantıkta bunun yerine tatmin edilebilir terimi kullanılır. Sözdizimsel tanımı bir teori bildiren hiçbir ise tutarlı bir formül , her iki olduğu ve tersi sonuçlarından kümenin elemanları . Izin kümesi olmak kapalı cümle (gayri "aksiyomlar") ve kapalı cümlelerin kümesi dan kanıtlanabilir (muhtemelen dolaylı olarak belirtilen) bazı resmi tümdengelim sistemi altında. Aksiyomların grubu olduğu uygun olduğunda bir formül .

Bu yapı ve anlam tanımlar, belirli bir tümdengelen formüle Herhangi bir teori için eşdeğer olan bir tümdengelen sistem var ise mantık , mantık adlandırılan tam . Tamlığı cümlesel hesabı ile kanıtlanmıştır Paul Bernays'ın 1918 ve Emil mesaj bütünlüğü ise 1921'de yüklem hesabı ile kanıtlanmıştır Kurt Gödel 1930'da, ve benzerleri ile ilgili sınırlı işlemlerinde için kıvam deliller indüksiyon aksiyomu şema Ackermann tarafından kanıtlanmıştır (1924), von Neumann (1927) ve Herbrand (1931). İkinci dereceden mantık gibi daha güçlü mantıklar tam değildir.

Bir tutarlılık kanıtı bir olan matematiksel kanıtı belirli teori tutarlı olduğunu. Matematiksel ispat teorisinin erken gelişimi , Hilbert'in programının bir parçası olarak tüm matematiğin sonlu tutarlılık kanıtlarını sağlama arzusu tarafından yönlendirildi . Hilbert'in programı, yeterince güçlü ispat teorilerinin (aslında tutarlı olmaları şartıyla) kendi tutarlılıklarını ispatlayamadığını gösteren eksiklik teoremlerinden güçlü bir şekilde etkilendi .

Tutarlılık model teorisi aracılığıyla kanıtlanabilse de, genellikle mantığın bazı modellerine atıfta bulunmaya gerek kalmadan tamamen sözdizimsel bir şekilde yapılır. Kesme-eliminasyon (ya da eşit şekilde normalleştirme arasında yatan hesabı varsa) taşı tutarlılık eder: yanlış olması, hiç bir oyuk içermeyen dayanıklı olduğu için, genel olarak herhangi bir çelişki mevcuttur.

Aritmetik ve küme teorisinde tutarlılık ve tamlık

Peano aritmetiği gibi aritmetik teorilerinde , teorinin tutarlılığı ile eksiksizliği arasında karmaşık bir ilişki vardır . Bir teori, kendi dilindeki her φ formülü için φ veya ¬φ'den en az biri teorinin mantıksal bir sonucuysa, tamamlanmış demektir.

Presburger aritmetiği , toplama altındaki doğal sayılar için bir aksiyom sistemidir. Hem tutarlı hem de eksiksiz.

Gödel'in eksiklik teoremleri , yeterince güçlü, özyinelemeli olarak sayılabilir herhangi bir aritmetik teorisinin hem tam hem de tutarlı olamayacağını göstermektedir. Gödel'in teoremi Peano aritmetiği (PA) ve ilkel özyinelemeli aritmetik (PRA) teorileri için geçerlidir , ancak Presburger aritmetiği için geçerli değildir .

Ayrıca, Gödel'in ikinci eksiklik teoremi, yeterince güçlü özyinelemeli olarak sayılabilir aritmetik teorilerinin tutarlılığının belirli bir şekilde test edilebileceğini gösterir. O yok, sadece ve eğer böyle bir teori tutarlı değil , belirli bir cümleyi ispat, teori gerçekten tutarlı olduğunu iddia bir resmiyet ifadesi teorisinin Gödel cümle denir. Bu nedenle, yeterince güçlü, yinelemeli olarak sayılabilir, tutarlı bir aritmetik teorisinin tutarlılığı, bu sistemin kendisinde asla kanıtlanamaz. Aynı sonuç, Zermelo-Fraenkel küme teorisi (ZF) gibi küme teorileri de dahil olmak üzere, yeterince güçlü bir aritmetik parçasını tanımlayabilen yinelemeli olarak sayılabilir teoriler için de geçerlidir . Bu küme teorileri, kendi Gödel cümlelerini kanıtlayamazlar - genel olarak inanıldığı gibi, tutarlı olmaları şartıyla.

ZF'nin tutarlılığı ZF'de kanıtlanamadığından, daha zayıf olan kavram göreli tutarlılık küme teorisinde (ve yeterince ifade edici diğer aksiyomatik sistemlerde) ilginçtir. EğerTa,teorivebirek olupaksiyomu,T+birtutarlı göre olduğu söylenirT(veya basitçebirtutarlıdırT) o eğer ispat edilebilir ise, Ttutarlıdır sonraT+birtutarlıdır. Eğer her ikiAve ¬birtutarlıdırT, sonra dabirolduğu söylenmektedir, bağımsızbirT.

Birinci dereceden mantık

gösterim

(Turnike sembolü) aşağıdaki matematiksel mantık bağlamında "kanıtlanabilir" anlamına gelir. Yani, okur: b den kanıtlanabilir olan bir (bazı belirli formel sistemde). Bkz . Mantık sembollerinin listesi . Diğer durumlarda turnike sembolü şu anlama gelebilir; türetilmesine izin verir. Bakınız: Matematiksel sembollerin listesi .

Tanım

  • Bir dizi formüller birinci dereceden mantığında olduğu tutarlı (yazılı hiçbir formül ise) olduğu gibi ve . Aksi takdirde ise tutarsız (yazılı ).
  • olduğu söylenir sadece tutarlı bir formül halinde arasında , her ikisi de ve negation arasında bir teoremleridir .
  • dilindeki en az bir formül bir teoremi değilse, mutlak tutarlı veya Post tutarlı olduğu söylenir .
  • her formül için maksimum tutarlı olduğu söylenir , eğer ima ederse .
  • söylenir şahit içeren formun her bir formül için ise bir vardır terimi bu şekilde burada, belirtmektedir ikame , her biri içinde bir göre ; ayrıca bkz. Birinci dereceden mantık .

Temel sonuçlar

  1. Aşağıdakiler eşdeğerdir:
    1. Hepsi için
  2. Her tatmin edilebilir formül kümesi tutarlıdır, burada bir formül kümesi ancak ve ancak böyle bir model varsa tatmin edilebilir .
  3. Hepsi için ve :
    1. değilse , o zaman ;
    2. eğer ve , o zaman ;
    3. eğer , o zaman veya .
  4. Maksimum tutarlı bir formüller dizisi olsun ve bunun tanıklar içerdiğini varsayalım . Hepsi için ve :
    1. eğer öyleyse ,
    2. ya ya da ,
    3. eğer ve sadece eğer veya ,
    4. eğer ve , o zaman ,
    5. ancak ve ancak böyle bir terim varsa .

Henkin teoremi

Let bir olmak sembollerin kümesi . Izin bir maksimum tutarlı seti olmak içeren -formulas tanıkları .

Terimler kümesinde bir denklik ilişkisini if ile tanımlayın , burada eşitliği ifade eder . Let göstermektedirler eşdeğerlik sınıfı ihtiva eden terimler ; ve semboller kümesine dayalı terimler kümesi nerede olsun .

'ye karşılık gelen terim yapısı olarak da adlandırılan - yapıyı over ile tanımlayın :

  1. her biri için -ary ilişki sembolü tanımlayan halinde
  2. her -ary işlev sembolü için tanımlayın
  3. her sabit sembol için tanımlayın

Değişken atama tanımlayın tarafından her bir değişken için . Izin olmak süreli yorumlanması ile ilişkili .

Sonra her -formül için :

ancak ve ancak

Kanıt taslağı

Doğrulanması gereken birkaç şey var. Birincisi, bu aslında bir denklik bağıntısıdır. Daha sonra (1), (2) ve (3)'ün iyi tanımlı olduğu doğrulanmalıdır. Bu , bir denklik bağıntısı olduğu gerçeğinden kaynaklanmaktadır ve ayrıca (1) ve (2)'nin sınıf temsilcilerinin seçiminden bağımsız olduğunun bir kanıtını gerektirir . Son olarak, formüller üzerinde tümevarım yoluyla doğrulanabilir.

model teorisi

In ZFC küme teorisinin klasik ile Birinci derece mantık , bir tutarsız teori kapalı bir cümle vardır böyle olması böyle hem içerdiği ve bunun olumsuzlamayı . Bir tutarlı teori şu bu bir şekildedir mantıksal eşdeğer koşullar tutun

Ayrıca bakınız

Dipnotlar

Referanslar

Dış bağlantılar