Bugün öğrendim ki: Robinson aritmetiğinin o kadar zayıf bir matematik sistemi olduğu ki her sayının çift veya tek olduğunu kanıtlayamaz. Ama yine de tüm hesaplanabilir fonksiyonları temsil edecek kadar güçlüdür ve Gödel'in eksiklik teoremlerine tabidir.

---

Matematikte, Robinson aritmetiği, ilk olarak Raphael M. Robinson tarafından 1950 yılında ortaya konulan, birinci dereceden Peano aritmetiğinin (PA) sonlu aksiyomatize edilmiş bir parçasıdır. Genellikle Q ile gösterilir. Q, neredeyse[açıklama gerekli] matematiksel tümevarım aksiyom şemasından yoksun PA'dır. Q, PA'dan daha zayıftır ancak aynı dile sahiptir ve her iki teori de eksiktir. Q, PA'nın özyinelemeli olarak tamamlanamayan ve özünde karar verilemeyen sonlu aksiyomatize edilmiş bir parçası olduğu için önemli ve ilginçtir.

Aksiyomlar

Q'nun arka plan mantığı, infix '=' ile gösterilen özdeşliği içeren birinci dereceden mantıktır. Doğal sayılar olarak adlandırılan bireyler, sıfır olarak adlandırılan ayırt edici bir üye 0'a sahip N olarak adlandırılan bir kümenin üyeleridir. N üzerinde üç işlem vardır:

Önek S ile gösterilen ve ardıl olarak adlandırılan bir birli işlem;

İnfiz + ve · ile sırasıyla gösterilen iki ikili işlem, toplama ve çarpma.

Q için aşağıdaki aksiyomlar, Burgess (2005, s. 42)'deki Q1–Q7'dir (bkz. ayrıca birinci dereceden aritmetiğin aksiyomları). Varoluşsal bir niceleyici tarafından bağlanmayan değişkenler, örtük bir evrensel niceleyici tarafından bağlanır.

Sx ≠ 0

0, hiçbir sayının ardılı değildir.

(Sx = Sy) → x = y

x'in ardılı y'nin ardılı ile özdeş ise, x ve y özdeştir. (1) ve (2), önemsiz olmaması için gereken N (0 tarafından sınırlanmış sonsuz bir kümedir) ve S (bölgesi N olan birebir bir fonksiyondur) hakkında minimum gerçekleri verir. (2)'nin tersi, özdeşliğin özelliklerden gelir.

y=0 ∨ ∃x (Sx = y)

Her sayı ya 0 ya da bir sayının ardılıdır. Q'dan daha güçlü aritmetiklerde bulunan matematiksel tümevarım aksiyom şeması, bu aksiyomu bir teorem haline getirir.

x + 0 = x

x + Sy = S(x + y)

(4) ve (5), toplamanın özyinelemeli tanımını oluşturur.

x·0 = 0

x·Sy = (x·y) + x

(6) ve (7), çarpmanın özyinelemeli tanımını oluşturur.

Değişken aksiyomatizasyonlar

Robinson (1950)'deki aksiyomlar, Mendelson (2015, ss. 202–203)'te (1)–(13)'tür. Robinson'ın 13 aksiyomunun ilk 6'sı, burada olduğu gibi arka plan mantığı özdeşliği içermediğinde gereklidir.

N üzerindeki alışılmış sıkı tam sıralama, "küçük" ( < ile gösterilir), kural aracılığıyla toplama açısından tanımlanabilir x < y ↔ ∃z (Sz + x = y). Denk olarak, <'ı ilkel olarak alarak ve bu kuralı sekizinci aksiyom olarak ekleyerek Q'nun tanımsal korunumlu bir genişlemesini elde ederiz; bu sisteme Boolos, Burgess & Jeffrey (2002, Bölüm 16.4)'te "Robinson aritmetiği R" denir.

<'ı ilkel olarak alıp (son tanımsal aksiyom yerine) aşağıdaki üç aksiyomu Q'nun (1)–(7) aksiyomlarına eklersek, geçici olarak Q+ diyeceğimiz farklı bir Q genişlemesi elde edilir:

¬(x < 0)

x < Sy ↔ (x < y ∨ x = y)

x < y ∨ x = y ∨ y < x

Q+, < sembolünü içermeyen Q+'da kanıtlanabilir herhangi bir formülün zaten Q'da kanıtlanabilir olduğu anlamında, yine de Q'nun korunumlu bir genişlemesidir. (Yukarıdaki üç aksiyomun sadece ilk ikisini Q'ya eklemek, Burgess (2005, s. 56)'nin Q* olarak adlandırdığı şeye eşdeğer olan Q'nun korunumlu bir genişlemesini verir. Ayrıca Burgess (2005, s. 230, dipnot 24)'e bakın, ancak yukarıdaki üç aksiyomun ikincisinin, sadece x < y ↔ ∃z (Sz + x = y) aksiyomunu ekleyerek elde edilen Q'nun "saf tanımsal genişlemesinden" çıkarılamayacağına dikkat edin.)

Q'nun (1)–(7) aksiyomları arasında, aksiyom (3) içsel bir varoluşsal niceleyiciye ihtiyaç duyar. Shoenfield (1967, s. 22), Q'nun aksiyom (3)'ünü ortadan kaldırarak ancak <'ı ilkel olarak ekleyerek yukarıdaki üç aksiyomu ekleyerek yalnızca (örtük) dışsal evrensel niceleyicilere sahip bir aksiyomatizasyon verir. Yani, Shoenfield'ın sistemi Q+ eksi aksiyom (3)'tür ve aksiyom (3), diğer aksiyomlardan bağımsız olduğundan (örneğin, ω ω {\displaystyle \omega ^{\omega }} 'den küçük sıral sayılar, Sv, v + 1 olarak yorumlandığında (3) hariç tüm aksiyomları sağlayan bir model oluşturur) Q+'dan kesinlikle daha zayıftır. Shoenfield'ın sistemi ayrıca Boolos, Burgess & Jeffrey (2002, Bölüm 16.2)'de de görünür, burada "minimum aritmetik" (Q ile de gösterilir) olarak adlandırılır. "<" yerine "≤" kullanan yakından ilgili bir aksiyomatizasyon, Machover (1996, ss. 256–257)'de bulunabilir.

Metamatematik

Q'nun metamatematiği hakkında Boolos, Burgess & Jeffrey (2002, bölüm 16), Tarski, Mostowski & Robinson (1953), Smullyan (1991), Mendelson (2015, ss. 202–203) ve Burgess (2005, §§1.5a, 2.2)'ye bakın. Q'nun amaçlanan yorumu, toplama ve çarpmanın geleneksel anlamına sahip doğal sayılar ve bunların alışılmış aritmetiğidir, özdeşlik eşitliktir, Sx = x + 1 ve 0 doğal sayı sıfırdır.

Muhtemelen aksiyom (3) hariç Q'nun tüm aksiyomlarını sağlayan herhangi bir model (yapı), standart doğal sayılara (N, +, ·, S, 0) izomorfik benzersiz bir alt modele ("standart kısım") sahiptir. (Aksiyom (3)'ün sağlanması gerekmez; örneğin, negatif olmayan tam sayı katsayılarına sahip polinomlar, (3) hariç tüm aksiyomları sağlayan bir model oluşturur.)

Q, Peano aritmetiği gibi, tüm sonsuz kardinalitelerin standart dışı modellerine sahiptir. Ancak, Peano aritmetiğinin aksine, Tennenbaum teoremi Q için geçerli değildir ve hesaplanabilir standart dışı modellere sahiptir. Örneğin, pozitif önde gelen katsayıya sahip tam sayı katsayıları polinomlarından ve sıfır polinomundan oluşan, alışılmış aritmetiğine sahip Q'nun hesaplanabilir bir modeli vardır.

Q'nun dikkate değer bir özelliği, tümevarım aksiyom şemasının yokluğudur. Bu nedenle, genellikle doğal sayılarla ilgili bir gerçeğin her özel örneğini Q'da kanıtlamak, ancak ilişkili genel teoremi kanıtlamak mümkün değildir. Örneğin, 5 + 7 = 7 + 5, Q'da kanıtlanabilir, ancak genel ifade x + y = y + x kanıtlanamaz. Benzer şekilde, Sx ≠ x olduğunu kanıtlayamazsınız. Birçok standart gerçeği karşılamayan bir Q modeli, standart doğal sayılar modeline iki farklı yeni eleman a ve b ekleyerek ve Sa = a, Sb = b, tüm x için x + a = b ve x + b = a, n standart doğal sayı ise a + n = a ve b + n = b, tüm x için x·0 = 0, n sıfır olmayan standart doğal sayı ise a·n = b ve b·n = a, x = a hariç tüm x için x·a = a, x = b hariç tüm x için x·b = b, a·a = b ve b·b = a tanımlayarak elde edilir.

Q, genişlemelilik, boş kümenin varlığı ve ekleme aksiyomundan oluşan Zermelo'nun aksiyomatik küme teorisinin bir parçasına yorumlanabilir. Bu teori, Tarski, Mostowski & Robinson (1953, s. 34)'te S' ve Burgess (2005, ss. 90–91, 223)'te ST'dir. Daha fazla ayrıntı için genel küme teorisine bakın.

Q, Peano aritmetiğinden (PA) oldukça daha zayıf olan ve aksiyomlarında yalnızca bir varoluşsal niceleyici içeren sonlu aksiyomatize edilmiş bir birinci dereceden teoridir. Yine de PA gibi, Gödel'in eksiklik teoremleri anlamında eksik ve tamamlanamaz ve özünde karar verilemezdir. Robinson (1950), her hesaplanabilir fonksiyonun PA'da temsil edilebilir olduğunu kanıtlamak için hangi PA aksiyomlarının gerektiğini belirterek yukarıdaki Q aksiyomlarını (1)–(7)'yi türetmiştir. Bu kanıtın PA tümevarım aksiyom şemasından yaptığı tek kullanım, yukarıdaki aksiyom (3) olan bir ifadeyi kanıtlamaktır ve bu nedenle, tüm hesaplanabilir fonksiyonlar Q'da temsil edilebilirdir. Gödel'in ikinci eksiklik teoreminin sonucu da Q için geçerlidir: Q'nun tutarlı özyinelemeli aksiyomatize edilmiş hiçbir genişlemesi, kanıtların Gödel numaralarını tanımlanabilir bir kesime ek olarak kısıtlasak bile, kendi tutarlılığını kanıtlayamaz.

İlk eksiklik teoremi, gerekli kodlama yapımlarını (Gödel numaralandırmasının bir parçası olan) gerçekleştirmek için yeterli aritmetiği tanımlayan aksiyomatik sistemler için geçerlidir. Q'nun aksiyomları, bu amaç için yeterince güçlü olmalarını sağlamak için özel olarak seçilmiştir. Bu nedenle, ilk eksiklik teoreminin alışılmış kanıtı, Q'nun eksik ve karar verilemez olduğunu göstermek için kullanılabilir. Bu, PA'nın eksikliğini ve karar verilemezliğini, Q'dan ayıran PA'nın tek yönü olan tümevarım aksiyom şemasına bağlayamayacağımızı gösterir.

Gödel'in teoremleri, yukarıdaki yedi aksiyomdan herhangi biri düşürüldüğünde geçerli değildir. Q'nun bu parçaları karar verilemez kalır, ancak artık özünde karar verilemez değildir: tutarlı karar verilebilir genişletmelerin yanı sıra ilgisiz modellere (yani, standart doğal sayıların son genişletmeleri olmayan modeller) sahiptir.[alıntı gerekli]

Ayrıca bakınız

Gentzen'in tutarlılık kanıtı

Gödel'in eksiklik teoremleri

Birinci dereceden teorilerin listesi

Peano aksiyomları

Presburger aritmetiği

Skolem aritmetiği

İkinci dereceden aritmetik

Doğal sayıların küme-teorik tanımı

Genel küme teorisi

Kaynaklar