Zorlama (özyineleme teorisi) - Forcing (recursion theory) - Wikipedia

Zorlama içinde özyineleme teorisi bir değişikliktir Paul Cohen'in orijinal küme teorik tekniği zorlama etkili endişelerle başa çıkmak için özyineleme teorisi. Kavramsal olarak iki teknik oldukça benzerdir: her ikisinde de inşa etme girişimlerinde genel nesneler (sezgisel olarak bir şekilde 'tipik' olan nesneler) yoğun kümelerle buluşarak. Her iki teknik de bir ilişki olarak tanımlanır (geleneksel olarak ) 'koşullar' ve cümleler arasında. Bununla birlikte, küme-teorik zorlamanın genellikle zemin modelindeki her yoğun koşul kümesini karşılayan nesneler yaratmakla ilgilendiği durumlarda, özyineleme-teorik zorlama, yalnızca aritmetik veya hiperaritmetik olarak tanımlanabilen yoğun kümeleri karşılamayı amaçlar. Bu nedenle, küme teorik zorlamada kullanılan daha zor makinelerin bazıları, yineleme teorisinde zorlamayı tanımlarken ortadan kaldırılabilir veya önemli ölçüde basitleştirilebilir. Ancak, makine biraz farklı olsa da, özyineleme-teorik ve küme-teorik zorlama, aynı tekniğin farklı formül sınıflarına uygulanması olarak kabul edilir.

Terminoloji

Bu yazıda aşağıdaki terminolojiyi kullanıyoruz.

gerçek
bir unsuru . Başka bir deyişle, her bir tamsayıyı 0 veya 1 ile eşleyen bir işlev.
dizi
bir unsuru . Başka bir deyişle, bir gerçek için sonlu bir yaklaşım.
zorlama kavramı
Zorlama kavramı bir kümedir ve bir kısmi sipariş açık , Birlikte en büyük unsur .
şart
Zorlama kavramındaki bir unsur. Bir durum diyoruz bir durumdan daha güçlü tam ne zaman .
uyumlu koşullar
Verilen koşullar şunu söyle ve bir koşul varsa uyumludur ile ve .

anlamına geliyor ve uyumsuz.

Filtrele
Bir alt küme zorlama kavramının eğer bir filtredir , ve . Başka bir deyişle, filtre, koşulların zayıflaması durumunda kapatılan uyumlu bir koşullar kümesidir.
Ultrafiltre
Bir maksimal filtre, yani bir ultrafiltredir eğer bir filtredir ve filtre yoktur uygun şekilde içeren .
Cohen zorlama
Zorlama kavramı koşullar unsurları nerede ve )

Cohen zorlaması için ... tersine çevirmek çevreleme ilişkisinin. Bu, bazı özyineleme teorisyenlerinin kısmi düzenin zorlama yönünü tersine çevirdiği talihsiz bir notasyon karmaşasına yol açar. ile Bu, Cohen zorlaması için daha doğaldır, ancak küme teorisinde kullanılan gösterimle çelişmektedir).

Genel nesneler

Zorlamanın arkasındaki önsezi, koşullarımızın inşa etmek istediğimiz bazı nesneler için sonlu tahminler olduğu ve daha güçlü ne zaman her şeye katılıyor inşa ettiğimiz nesne hakkında söyler ve kendine ait bazı bilgiler ekler. Örneğin, Cohen'de koşulları zorlamak, bir gerçek için sonlu yaklaşımlar olarak görülebilir ve eğer sonra bize gerçeğin değerini daha çok yerde anlatıyor.

Biraz sonra bir ilişki tanımlayacağız (oku kuvvetler ) koşullar arasında kalan ) ve cümleler, ancak önce açıklamamız gerekiyor dil o için bir cümledir. Bununla birlikte, zorlama bir tanım değil tekniktir ve kişinin aklındaki uygulamaya ve seçimine bağlı olacaktır. .

Buradaki fikir, dilimizin zorlayıcı yapımızla inşa etmek istediğimiz nesne hakkındaki gerçekleri ifade etmesi gerektiğidir.

Referanslar

  • Melvin Fitting (1981), Genelleştirilmiş özyineleme teorisinin temelleri.
  • Piergiorgio Odifreddi (1999), Klasik Özyineleme Teorisi, ayet 2.