Yapıcı küme teorisi - Constructive set theory

Yapıcı küme teorisi, aksiyomatik küme teorisi programını izleyen matematiksel yapılandırmacılığa bir yaklaşımdır . Klasik küme teorisinin " " ve " " ile aynı birinci dereceden dili genellikle kullanılır, bu nedenle bu, yapıcı türler yaklaşımıyla karıştırılmamalıdır . Öte yandan, bazı yapıcı teoriler, tip teorilerindeki yorumlanabilirlikleri tarafından gerçekten motive edilir . ${\görüntüleme stili =}$${\görüntüleme stili \içinde }$

Reddetmeden ek olarak dışlanmış orta yasasını ( ) yapıcı set teorileri genellikle kendi Aksiyomların bazı mantıksal nicelik gerektirir sınırlanmış bağlı sonuçların motive, impredicativity . ${\ Displaystyle {\mathrm {LEM} }}$

Tanıtım

Görünüm

Burada tartışılan küme teorilerinin mantığı, reddetmesi bakımından yapıcıdır , yani ayrım otomatik olarak tüm önermeler için geçerlidir. Bu, güçlü seçim ilkelerinin reddedilmesini ve bazı standart aksiyomların yeniden yazılmasını gerektirir. Örneğin, Seçim Aksiyomu, kişinin benimsediği Ayırma şemasındaki formüller için Diaconescu'nun teoremi tarafından ima eder . Benzer sonuçlar , standart biçimindeki Düzenlilik Aksiyomu için de geçerlidir . Kural olarak, belirli bir ayrılığı kanıtlamak için , ya da kanıtlanması gerekir. Bu durumda, kişi ayrılığın kararlaştırılabilir olduğunu söylüyor. Buna karşılık, yapıcı teoriler, örneğin kanıtlanabilir bir şekilde hesaplama açısından karar verilemez olan birçok klasik özellik kanıtına izin vermeme eğilimindedir . Daha muhafazakar minimal mantığın aksine , burada temel mantık, karar verilebilir yüklemler için çift ​​olumsuzlamanın ortadan kaldırılmasına izin verir ve sonlu yapılarla ilgili teorem formülasyonları, klasik muadillerinden farklı olma eğilimindedir. ${\ Displaystyle {\mathrm {LEM} }}$ ${\displaystyle \phi \lor \neg \phi }$${\ Displaystyle {\mathrm {LEM} }}$${\ Displaystyle P\lor \neg P}$${\görüntüleme stili P}$${\görüntüleme stili \neg P}$

Özellikle, yapıcı mantığa yönelik bir kısıtlama , sınırsız koleksiyonları içeren bir kümenin hangi karakterizasyonlarının bir (matematiksel ve dolayısıyla her zaman toplam anlamına gelen ) bir işlev oluşturduğuna ilişkin daha katı gereksinimlere yol açar . Bunun nedeni genellikle, vaka bazında yapılacak bir tanımdaki yüklemin kararlaştırılamamasıdır. Klasik muadiliyle karşılaştırıldığında, gerçekleştirilemeyen ilişkilerin varlığının kanıtlanması genellikle daha az olasıdır. Bu, aynı zamanda , doğrulukla ifade edilen tüm sıra sayıları gibi toplam sıralar hakkındaki ifadelerin ve ayrımı tanımlayan sıradaki terimlerin olumsuzlanmasının kanıtlanabilirliğini de etkiler . Bu da sıralı analizde tanımlanan ispat teorik gücünü etkiler . ${\displaystyle f\subset X\times Y}$${\displaystyle (\alpha \in \beta )\lor (\alpha =\beta )\lor (\beta \in \alpha )}$

Bununla birlikte, yapıcı matematiksel teoriler genellikle klasik teoremlerin klasik olarak eşdeğer yeniden formüllerini kanıtlama eğilimindedir . Örneğin, Yapıcı analizde , ders kitabı formülasyonunda ara değer teoremi kanıtlanamaz , ancak varsayıldığı anda klasik ifadeye klasik olarak eşdeğer olan algoritmik içerikli teoremler kanıtlanabilir . Aradaki fark, yapıcı kanıtların bulunmasının daha zor olmasıdır. ${\ Displaystyle {\mathrm {LEM} }}$

modellerde

Yapıcı küme teorisinde çalışılan birçok teori, Zermelo-Fraenkel küme teorisinin ( )${\displaystyle {\mathsf {ZF}}}$ aksiyomları ve altta yatan mantıkları bakımından sadece kısıtlamalarıdır . Bu tür teoriler daha sonra herhangi bir modelde de yorumlanabilir . Yapıcı gerçekleşmeler söz konusu olduğunda bir gerçekleştirilebilirlik kuramı vardır ve Aczel'in yapıcı kuramı Zermelo-Fraenkel ( ) aşağıda açıklandığı gibi Martin-Löf tipi kuramlarda yorumlanmıştır . Bu şekilde, ispatlanabilir küme teorisi teoremleri ve daha zayıf teoriler bir bilgisayarda gerçekleştirilmeye adaydır. Daha yakın zamanlarda, yapıcı küme teorileri için ön demet modelleri tanıtıldı. Bunlar , 1980'lerde Dana Scott tarafından geliştirilen sezgisel küme teorisi için yayınlanmamış Presheaf modellerine benzer . ${\displaystyle {\mathsf {ZF}}}$${\displaystyle {\mathsf {CZF}}}$${\displaystyle {\mathsf {CZF}}}$

genel bakış

John Myhill'in , Errett Bishop'un yapıcı matematik programı için biçimsel bir temel sağlamayı amaçlayan, çeşitli türlerde ve sınırlı nicelleştirme olarak da adlandırılan teori üzerindeki çalışmasıyla başlatılan yapıcı küme teorisi (genellikle " ") konusu . Aşağıda, Peter Aczel'in iyi çalışılmış ve ötesine götüren aynı dilde bir dizi teori bulunmaktadır . ayrıca Myhill'in teorisinde de mevcut olan iki özellikle karakterize edilir: Bir yandan, tam, sınırsız Ayırma şeması yerine Tahmini Ayırma kullanıyor, ayrıca bkz . Lévy hiyerarşisi . Sınırlılık, sözdizimsel bir özellik olarak ele alınabilir veya alternatif olarak, teoriler daha yüksek bir sınırlılık yüklemi ve aksiyomları ile muhafazakar bir şekilde genişletilebilir. İkinci olarak, genel olarak ilgili ancak daha zayıf aksiyomlar lehine , tahmin edici Powerset aksiyomu atılır. Güçlü form, klasik genel topolojide çok gelişigüzel kullanılır . Aşağıda ayrıntılı olarak açıklandığı gibi, kurtardığından daha zayıf bir teoriye ekleme . Sezgisel Zermelo–Fraenkel küme teorisi ( ) olarak bilinen sistem, . Buna benzer , ancak daha az muhafazakar veya tahmin edicidir . Belirtilen teori , Toplama Aksiyomu'nun bile sınırlı olduğu klasik Kripke-Platek küme teorisinin yapıcı versiyonudur . ${\displaystyle {\mathsf {CST}}}$${\displaystyle {\mathsf {CST}}}$${\displaystyle {\mathsf {ZF}}}$${\displaystyle {\mathsf {CZF}}}$${\displaystyle {\mathsf {CZF}}}$ ${\ Displaystyle {\mathrm {LEM} }}$${\displaystyle {\mathsf {CZF}}}$${\displaystyle {\mathsf {ZF}}}$${\displaystyle {\mathsf {IZF}}}$${\ Displaystyle {\mathrm {LEM} }}$${\displaystyle {\mathsf {CZF}}}$${\displaystyle {\mathsf {IKP}}}$${\displaystyle {\mathsf {KP}}}$

ZF'nin Alt Teorileri

gösterim

Yunan Aşağıda yer denote bir yüklem değişken aksiyomu şemalar ve kullanım veya belirli yüklemler için. Eşsiz varoluş örn . Niceleyiciler küme üzerinde değişir ve bunlar küçük harflerle gösterilir. ${\görüntüleme stili\phi }$${\görüntüleme stili P}$${\ ekran stili Q}$${\görüntüleme stili \var !xP(x)}$${\görüntüleme stili \x var.\tüm y.\sol(y=x\iff P(y)\sağ)}$

Küme teorilerinin incelenmesinde yaygın olduğu gibi, çoğu bağlamda nesne dilinin bir parçası olmayan ancak kısa tartışma için kullanılan sınıflar için küme oluşturucu notasyonu kullanılır. Özel olarak, bir "ile ilgili sınıfın gösterimi bildirimleri katabileceği eksprese etmek amacıyla," olarak . Aynı sınıfı tanıtmak için mantıksal olarak eşdeğer yüklemler kullanılabilir. Bir de stenografi olarak yazar . ${\displaystyle A=\{z\orta P(z)\}}$${\görüntüleme stili P(a)}$${\ Displaystyle a\in A}$${\displaystyle \{z\B\orta P(z)\}}$${\displaystyle \{z\mid z\inB\land P(z)\}}$

Yaygın olduğu gibi, kişi tarafından kısaltılabilir ve alt sınıf iddiası , yani , ile ifade edilebilir . ${\displaystyle \forall z.(z\in A\P(z) anlamına gelir)}$${\displaystyle \forall (z\in A).P(z)}$${\displaystyle \forall (z\ A'da).z\B'de}$${\displaystyle \forall z.(z\in A\in z\in B)}$${\görüntüleme stili A\altküme B}$

Bir özellik için , önemsiz bir şekilde . Ve bunu takip eder . ${\görüntüleme stili P}$${\displaystyle \forall z.{\big (}(z\in B\land P(z))\in B{\big )}}$${\displaystyle \{z\in B\mid P(z)\}\altküme B}$

Ortak aksiyomlar

Neredeyse her zaman tartışmasız kabul edilen ve bu makalede ele alınan tüm teorilerin bir parçası olan aksiyomların bir başlangıç ​​noktası . ${\displaystyle {\mathsf {ZF}}}$

İki sınıfın tam olarak aynı öğelere sahip olduğunu ifade eden ifade ile belirtin , yani , veya eşdeğer olarak . ${\ Displaystyle A\simeq B}$${\displaystyle \forall z.(z\in A\iff z\inB)}$${\ Displaystyle (A\subset B)\land (B\subset A)}$

Aşağıdaki aksiyom , iki kümenin " " eşitliğini kanıtlamak için bir araç verir , böylece ikame yoluyla, herhangi bir yaklaşık yüklemi ' den birine çevrilir . ${\görüntüleme stili =}$${\görüntüleme stili x}$${\görüntüleme stili y}$

Genişletilebilirlik ${\displaystyle \tüm x için.\tüm y için.\ \ x\simeq y\implies x=y}$

Eşitliğin mantıksal özellikleriyle, ters yön otomatik olarak tutar.

Yapıcı yorumda, bir alt sınıfın elemanları arasında olanlar daha fazla bilgi ile donatılmış olabilir yargıç edememek anlamında, yargılamak mümkün ediliyor . Ve Brouwer-Heyting-Kolmogorov yorumunda (bütün ayrım aksiyomlardan gelmediği sürece) , bu, onu kanıtlamış veya reddetmiş olmak anlamına gelir . Olarak Karar verilebilen olmayabilir tüm elemanları , iki sınıf önsel ayırt edilmelidir. ${\displaystyle A=\{z\in B\orta Q(z)\lor \neg Q(z)\}}$${\görüntüleme stili B}$${\görüntüleme stili B}$${\ Displaystyle b\ A'da}$${\görüntüleme stili Q(b)\lor \neg Q(b)}$${\görüntüleme stili Q(b)}$${\ ekran stili Q}$ ${\görüntüleme stili B}$

Bir kümenin tüm öğeleri için geçerli olduğu kanıtlanan bir özellik düşünün , böylece sol taraftaki sınıfın bir küme olarak kurulduğunu varsayalım. Soldaki bu küme gayri resmi olarak tüm öğelerin geçerliliği hakkında kanıtla ilgili bilgilere de bağlansa bile, Genişletme aksiyomu, küme teorimizde sol taraftaki kümenin eşit olarak değerlendirildiğini varsayar. biri sağ tarafta. ${\görüntüleme stili P}$${\görüntüleme stili y}$${\displaystyle \{z\in y\mid P(z)\}\simeq y}$${\görüntüleme stili P}$

Modern tip teorileri bunun yerine talep edilen eşdeğerliği " " fonksiyonlar açısından tanımlamayı hedefleyebilir, örneğin tip eşdeğerliğine bakınız . İlgili fonksiyon genişleme kavramı genellikle tip teorisinde benimsenmez. ${\görüntüleme stili \simeq }$

Yapıcı matematik için diğer çerçeveler, bunun yerine , tartışılan her kümenin öğeleri için eşitlik veya ayrıklık için belirli bir kural talep edebilir . O zaman bile, yukarıdaki tanım alt kümelerin eşitliğini karakterize etmek için kullanılabilir ve . ${\displaystyle z\in x}$${\görüntüleme stili x}$ ${\görüntüleme stili u\alt küme x}$${\görüntüleme stili v\alt küme x}$

Diğer iki temel aksiyom aşağıdaki gibidir. İlk önce,

Eşleştirme ${\displaystyle \forall x.\forall y.\ \ \ p.\forall z.{\big (}(z=x\lor z=y)\implies z\in p{\big )}}$

herhangi iki ve kümesi için , en az bu iki kümeyi ( ) tutan en az bir küme olduğunu söyleyerek . ${\görüntüleme stili x}$${\görüntüleme stili y}$${\görüntüleme stili p}$${\görüntüleme stili z}$

Ve daha sonra,

birlik ${\displaystyle \forall x.\ \ \ u.\forall y var.{\big (}(\exists zy\in z\land z\in x)\ y\in u{\big )}}$

Herhangi seti söyleyerek , en az bir set var bütün üyeleri tutan, bir, bireyin üyeleri . ${\görüntüleme stili x}$${\görüntüleme stili u}$${\görüntüleme stili y}$${\görüntüleme stili x}$${\görüntüleme stili z}$

İki aksiyom ayrıca " " açısından daha güçlü formüle edilebilir , örneğin Ayırma bağlamında bu gerekli değildir. ${\görüntüleme stili \iff }$${\displaystyle {\mathsf {BCST}}}$

Birlikte, bu iki aksiyom, iki sınıfın ikili birliğinin varlığını ve ne zaman küme olmak üzere kurulduğunu ima eder ve bu, veya ile gösterilir . Ayrışmalar yoluyla sonlu elemanlar için sınıf gösterimini tanımlayın, örneğin, diyor ve ardıl kümesini olarak tanımlayın . Eşleştirme ve birleşme arasında bir tür karışım, halef ile daha kolay ilişkili bir aksiyom , ek aksiyomudur . Tek tek Neumann sıra sayılarının standart modellemesi ile ilgilidir . Bu aksiyom da kolayca kabul edilebilir, ancak aşağıdaki daha güçlü aksiyomlar bağlamında geçerli değildir. Standart sıralı çift modeli ile belirtin . ${\görüntüleme stili bir}$${\görüntüleme stili b}$${\displaystyle \bigcup \{a,b\}}$${\ Displaystyle a\cup b}$${\displaystyle c\in \{a,b\}}$${\görüntüleme stili (c=a)\lor (c=b)}$ ${\ Displaystyle Sx}$${\displaystyle x\cup \{x\}}$${\görüntüleme stili \langle x,y\rangle }$${\displaystyle \{\{x\},\{x,y\}\}}$

Herhangi bir küme için false olan özellik, veya sıfır, 0 ile gösterilen boş sınıfa karşılık gelir. Bunun bir küme olduğu, aşağıdaki Sonsuzluk Aksiyomu gibi diğer aksiyomlardan kolaylıkla gelir. Ancak, örneğin, kişi kendi çalışmasında sonsuz kümeleri hariç tutmakla açıkça ilgileniyorsa, bu noktada boş küme aksiyomunu kabul edebilir. ${\görüntüleme stili \{\}}$

${\görüntüleme stili \x var.\tüm y.\,\neg (y\in x)}$

BCST

Aşağıdaki, aksiyom şemalarını , yani bazı yüklemler koleksiyonu için aksiyomları kullanır. Belirtilen aksiyomu şemalar bazı genellikle belirlenmiş olan ölçülere sunulmasını Not yanı, yani ekstra evrensel kapanışları ile varyantları böyle 'ın parametrelere bağlı olabilir. ${\görüntüleme stili v}$${\görüntüleme stili \forall v}$${\görüntüleme stili\phi }$

Temel yapıcı küme teorisi , standart küme teorisinin bir parçası olan birkaç aksiyomdan oluşur, ancak Ayırma aksiyomu zayıflatılmıştır. Yukarıdaki üç aksiyomun ötesinde, ${\displaystyle {\mathsf {BCST}}}$

Yüklemlik ayrılık Axiom şema : Herhangi İçin sınırlı yüklemi ile onun içinde değil özgür, ${\görüntüleme stili\phi }$${\görüntüleme stili y}$ ${\displaystyle \forall y.\ \ \ s.\forall x var.{\Big (}x\in s\iff {\big (}x\in y\land \phi (x){\big )}{ \Büyük )}}$

Aksiyom , herhangi bir kümenin ve öngörücü olarak tanımlanmış herhangi bir sınıfın kesişimiyle elde edilen bir kümenin varlığını varsaymak anlamına gelir . Yüklem olarak alındığında için bir set setleri ve yazma biri edinir ikili kavşak olduğu kanıtlanmıştır . ${\görüntüleme stili s}$${\görüntüleme stili y}$${\displaystyle \{x\mid \phi (x)\}}$${\displaystyle x\in z}$${\görüntüleme stili z}$${\displaystyle s=y\kap z}$

Şema, yalnızca set- sınırlı niceleyiciler için Ayırma'da olduğu gibi, Sınırlı Ayırma olarak da adlandırılır . Yüklemlerin sözdizimsel yönlerine gönderme yapan aksiyom şemasıdır. Sınırlı formüller ayrıca , aritmetik hiyerarşiye benzer şekilde, küme teorik Lévy hiyerarşisinde ile gösterilir . (Ancak, aritmetik sınıflandırmanın bazen sözdizimsel olarak değil, doğalların alt sınıfları cinsinden ifade edildiğine dikkat edin. Ayrıca, alt düzeyin, bazıları bazı toplam işlevlerin kullanımına izin vermeyen birkaç ortak tanımı vardır. Ayrım, düzeyle ilgili değildir veya Daha yüksek.) Aksiyomdaki kısıtlama aynı zamanda tahmin edici tanımların kapı bekçiliğidir : Varlık, en iyi ihtimalle, açıkça tanımlanamayan veya tanımı kendilerini içeren veya uygun bir sınıfa atıfta bulunan nesneler için iddia edilmemelidir, örneğin kontrol edilecek bir özelliğin aşağıdakileri içermesi gibi. evrensel niceleyici Bu nedenle , güç kümesi aksiyomu olmayan yapıcı bir teoride , olarak tanımlanan bir sınıf beklenmemelidir . ${\displaystyle \Delta _{0}}$${\displaystyle \Delta _{0}^{0}}$${\görüntüleme stili \Sigma _{1}^{0}}$${\görüntüleme stili s}$

${\displaystyle \{x\in y\mid \forall (t\in {\mathcal {P}}y).Q(x,t)\}}$

yani

${\displaystyle \{x\in y\mid \forall t.{\big (}\forall (z\in t).(z\in y)\Q(x,t){\big )}\} anlamına gelir }$

bir küme olmak, burada bazı 2-ary yüklemi ifade eder. Bu alt sınıf kanıtlanabilir bir küme ise, bu şekilde tanımlanan terimin aynı zamanda değişken terimin sınırsız kapsamında olduğuna ve kendisini tanımlamak için kullanılan parantez içindeki yüklemi yerine getirdiğine dikkat edin . Tahmini Ayırma, verilen sınıf tanımlarının daha az küme olmasına yol açarken, klasik olarak eşdeğer olan birçok sınıf tanımının, kendini yapıcı mantıkla sınırlandırırken böyle olmadığı vurgulanmalıdır. Böylece bu şekilde, yapıcı bir şekilde daha geniş bir teori elde edilir. Genel yüklemlerin potansiyel karar verilemezliği nedeniyle , alt sınıf kavramı, yapıcı küme teorilerinde klasik olanlara göre daha ayrıntılıdır. ${\ ekran stili Q}$${\görüntüleme stili s}$${\görüntüleme stili t}$${\görüntüleme stili t}$

Belirtildiği gibi, Ayrılma ve herhangi bir kümenin varlığından (örneğin aşağıdaki Sonsuzluk) ve herhangi bir kümenin yanlış olan yüklemi boş kümenin varlığını izleyecektir.

Salt mantıksal teorem sayesinde , Russel'in yapısı , Tahmini Ayrımın tek başına bunu ima ettiğini gösterir . Özellikle, hiçbir evrensel küme yoktur. ${\displaystyle \forall x.{\big (}xRs\Leftrightarrow (xRy\land \neg xRx){\big )}\implies \neg sRy}$${\displaystyle \{x\in y\orta x\x değil\}\y değil}$

Bu tutucu bağlamda , Sınırlı Ayırma şeması aslında Boş Küme artı herhangi iki küme için ikili kesişimin varlığına eşdeğerdir. Aksiyomatizasyonun ikinci çeşidi bir şema kullanmaz. Gibi alt tiplemesi gerekli bir özelliği değildir yapıcı tip teorisi oldukça bu çerçeve farklı olmasına, yapıcı küme teorisi söylenebilir. ${\displaystyle {\mathsf {BCST}}}$

Sonraki

Değiştirmenin aksiyom şeması : Herhangi bir yüklem için , ${\görüntüleme stili\phi }$ ${\displaystyle \forall d.\ \ \forall (x\in d).\vardır !y.\phi (x,y)\vardır \r.\forall y.{\big (}y\in r\ iff \vardır (x\in d).\phi (x,y){\big )}}$

Etki alanları aracılığıyla elde edilen fonksiyon benzeri yüklemler dizisinin kümeler olarak varlığını bahşeder.

Değiştirme şeması ile bu teori, denklik sınıflarının veya indekslenmiş toplamların kümeler olduğunu kanıtlar . Özellikle, iki kümenin tüm eleman çiftlerini tutan Kartezyen ürün bir kümedir.

Değiştirme ve Küme İndüksiyonunun aksiyomu (aşağıda tanıtılmıştır), kalıtsal olarak sonlu kümeleri yapıcı bir şekilde aksiyomlamak için yeterlidir ve bu teori de Sonsuz olmadan çalışılır. Karşılaştırma için, doğal sayılar sınıfını ve onların aritmetiğini sadece Genişleme, Ekleme ve tam Ayırma yoluyla yorumlayan Genel küme teorisi olarak adlandırılan çok zayıf klasik teoriyi düşünün .

'de , Değiştirme çoğunlukla yüksek dereceli kümelerin varlığını kanıtlamak için önemlidir , yani nispeten küçük kümeleri daha büyük kümelerle ilişkilendiren aksiyom şeması örnekleri aracılığıyla . ${\displaystyle {\mathsf {ZF}}}$${\görüntüleme stili \phi (x,y)}$${\görüntüleme stili x}$${\görüntüleme stili y}$

Yapıcı küme teorileri genellikle, bazen sınırlı formüllerle sınırlı olan Değiştirme Aksiyom şemasına sahiptir. Bununla birlikte, diğer aksiyomlar bırakıldığında, bu şema aslında genellikle güçlendirilir - ötesinde değil , bunun yerine sadece bir miktar kanıtlanabilirlik gücü kazanmak için. ${\displaystyle {\mathsf {ZF}}}$

Değiştirme bir anlama biçimi olarak görülebilir. Yalnızca , Değiştirmenin zaten tam Ayrılık anlamına geldiği varsayıldığında . ${\ Displaystyle {\mathrm {LEM} }}$

AKST

Endüktif özellik ile belirtin , örn . Sınıfın altında yatan bir yüklem açısından bu, . Burada jenerik bir set değişkenini belirtir. Yazın için . Bir sınıf tanımlayın . ${\displaystyle \mathrm {Ind} (A)}$${\displaystyle 0\A\land\içinde (n\A'da).Sn\A'da}$${\görüntüleme stili P}$${\displaystyle P(0)\land \forall n.{\big (}P(n)\P(Sn) anlamına gelir{\big )}}$${\görüntüleme stili n}$${\displaystyle \bigcap A}$${\displaystyle \{x\mid \forall y.(y\in A\x\in y anlamına gelir)\}}$${\displaystyle \omega =\bigcap \{x\mid \mathrm {Ind} (x)\}}$

Bazı sabit yüklem için , deyim ifade eden bütün setleri arasında en küçük kümesidir kendisi için de geçerlidir. Temel yapıcı Küme Teorisi , aksiyomunun yanı sıra ${\görüntüleme stili P}$${\displaystyle P(a)\land \forall xP(x)\bir\altküme x} anlamına gelir$${\görüntüleme stili bir}$${\görüntüleme stili x}$${\görüntüleme stili P(x)}$${\displaystyle {\mathsf {ECST}}}$${\displaystyle {\mathsf {BCST}}}$

Güçlü Sonsuzluk ${\displaystyle \var w.{\Big (}\mathrm {Ind} (w)\,\land \,{\big (}\forall x.\mathrm {Ind} (x)\w\subset x{ anlamına gelir) \büyük )}{\Büyük )}}$

Evrensel olarak nicelleştirilmiş ikinci bağlaç , söylem evrenindeki herkes için , yani kümeler için matematiksel tümevarımı ifade eder . yüklemler için gerçekten kümeleri tanımlıyorlarsa . Bu şekilde, bu bölümde tartışılan ilkeler, bazı yüklemlerin en azından tüm öğeleri için geçerli olduğunu kanıtlamanın yollarını sunar . Tam matematiksel tümevarımın (aşağıda tartışılan herhangi bir yüklem için tümevarım) oldukça güçlü aksiyomunun bile, bir küme oluşturduğunu varsaymadan benimsenebileceğini ve kullanılabileceğini unutmayın . ${\görüntüleme stili x}$${\görüntüleme stili x}$${\ Displaystyle \ omega }$${\ Displaystyle \ omega }$

Sonsuzluk aksiyomlarının zayıf biçimleri formüle edilebilir, tümü ortak doğal sayı özelliklerine sahip bazı kümelerin var olduğunu varsayar. Daha sonra, bu tür "seyrek" kümeyi, doğal sayılar kümesini elde etmek için tam Ayırma kullanılabilir. Aksi halde daha zayıf aksiyom sistemleri bağlamında, kendi başına böyle bir seyrek kümenin varlığını ima etmek için bir sonsuzluk aksiyomu güçlendirilmelidir. Infinity'nin daha zayıf bir biçimi okur

${\displaystyle \exists w.\forall m.{\Big (}m\in w\iff {\big (}m=0\lor (\exists n\in w).\forall k.(k\in m) \iff k\in n\lor k=n){\büyük )}{\Büyük )}}$

kullanılarak daha özlü bir şekilde yazılabilir . Bu şekilde var olduğu varsayılan küme, genellikle , en küçük sonsuz von Neumann sıra sayısı ile gösterilir . Bu kümenin elemanları için, iddiaya karar verilebilir. ${\görüntüleme stili S}$${\ Displaystyle \ omega }$${\görüntüleme stili n,m}$${\görüntüleme stili n=m}$

Bununla, sınırlı formüllerle verilen tüm yüklemler için tümevarımı ispatlar . Sıfırla ilgili beş Peano aksiyomunun ikisi ve sonsuzluk aksiyomlarından oldukça doğrudan takip etmekle ilgili kapalılık ile ilgili bir . Son olarak, bir enjeksiyon işlemi olduğu kanıtlanabilir. ${\displaystyle {\mathsf {ECST}}}$${\görüntüleme stili S}$${\ Displaystyle \ omega }$${\görüntüleme stili S}$

Doğal sayılar ayırt edilebilir, yani bunların eşitliği (ve dolayısıyla eşitsizliği) belirlenebilir. Temel düzen, bu modelde üyelik tarafından yakalanır. Standart gösterim adına, boş küme de dahil olmak üzere herhangi biri için doğal sayıların bir ilk bölümünü gösterelim . ${\görüntüleme stili \{0,1,\noktalar,n-1\}}$${\displaystyle \{k\in \omega\orta k<n\}}$${\görüntüleme stili k\in \omega }$

Fonksiyonlar

Doğal olarak varoluş iddialarının mantıksal anlamı, sezgici mantığın ilgilendiği bir konudur. Burada odak toplam ilişkiler üzerindedir .

Yapıcı bir matematiksel çerçevede, aşağıdaki gibi ifadelerin ispat hesabı

${\displaystyle \forall (a\in A).\vardır (c\in C).P(a,c)}$

temsil edilen alanlardaki programlar açısından kurulabilir ve muhtemelen iddiaya tanık olmak zorunda kalabilir . Bu gayrı, konuşma, anlamında anlaşılmalıdır , nerede belirtildiği gibi bir programın değerini ifade eder, ancak bu sorularına içine alır gerçeklenebilirlik teorisi . Daha güçlü bir bağlam için, eğer önerme geçerliyse ve ne zaman olursa olsun, bunun her zaman tam bir özyinelemeli işlev tarafından gerçekleştirilmesiyle mümkün olacağını talep etmek , sonuç olarak kesinlikle klasik olmayan Rus yapılandırmacılığında benimsenen olası bir Kilise tez postülatıdır . Önceki paragrafta, "fonksiyon"un hesaplanabilir özyineleme teorisi anlamında anlaşılması gerekir - bu ara sıra belirsizliğe aşağıda da dikkat edilmelidir. ${\displaystyle \forall (a\in A).P(a,c_{a})}$${\ Displaystyle c_{a}}$${\ Displaystyle A=C=\omega }$${\displaystyle a\mapsto c_{a}}$

Buna bağlı olarak, bir önceki sayı varlığı iddiasının yerine tam matematiksel tümevarım şemasını koyan klasik bir aritmetik teorisi olan Robinson aritmetiğini düşünün . Bu teorinin , kanıtlanabilir bir toplam işlevsel ilişkiler olan yüklemleri tanımlama anlamında tam olarak özyinelemeli işlevleri temsil ettiği bir teoremdir.${\görüntüleme stili P}$

${\displaystyle \forall (a\in {\mathbb {N} }).\vardır !(c\in {\mathbb {N} }).P(a,c)}$.

Şimdi kapsayan mülkiyet wdefine akımı ayarlanan teorik yaklaşımı, içinde fonksiyon uygulama parantez, gibi bir fonksiyonun konuşmak ve ne zaman kanıtlanabilir ${\görüntüleme stili f(a)=c}$${\displaystyle \langle a,c\rangle \in f}$${\displaystyle f\subset A\times C}$

${\displaystyle \forall (a\in A).\,\vardır !(c\inC).f(a)=c}$,

yani

${\displaystyle \forall (a\in A).\,\vardır (c\in C).\,\forall (c'\CinC).{\big (}c'=c\iff \langle a, c'\rangle \in f{\büyük )}}$,

ki bu özellikle varoluşsal bir niceleyici içerir. Bir alt sınıfın bir fonksiyon olarak yargılanıp yargılanamayacağı, teorinin gücüne, yani birinin benimsediği aksiyomlara bağlı olacaktır.

Özellikle, genel bir sınıf, ürünün bir alt sınıfı olmaksızın yukarıdaki yüklemi karşılayabilir , yani özellik, girdilerden daha fazla veya daha az işlevsellik ifade etmiyor . Etki alanı ve kod alanı kümelerse, yukarıdaki yüklem yalnızca sınırlı niceleyicileri içerir. Çoğu matematiksel çerçevede kullanılan "fonksiyon" terminolojisine dikkat edilmelidir, çünkü bazıları bir fonksiyon teriminin kendisini belirli bir kod alanına bağlamaktadır. Fonksiyonel yüklem tanımının setoidler üzerindeki ayrıklık ilişkilerini kullanan varyantları da tanımlanmıştır. ${\ Displaystyle A\time C}$${\görüntüleme stili A}$

Bu tür küme fonksiyonlarının sınıfını (ayrıca ) gösterelim. Standart sınıf terminolojisini kullanarak, etki alanları bir küme olduğu göz önüne alındığında, işlevler serbestçe kullanılabilir. Bir bütün olarak işlevler, kod etki alanları ise ayarlanacaktır. Fonksiyonlar yukarıdaki gibi sadece fonksiyon grafikleri olarak anlaşıldığında üyelik önermesi de yazılır . Aşağıda yazabiliriz için sıra üs ayırd edici uğruna. ${\görüntüleme stili C^{A}}$${\görüntüleme stili {}^{A}C}$${\ Displaystyle f\in C^{A}}$${\displaystyle f\kolon A\to C}$${\görüntüleme stili x\'den y'ye}$${\görüntüleme stili y^{x}}$

Ayırma , en azından sınırlı bir şekilde tanımlandıklarında , ürünlerin kesilmiş alt kümelerinin kullanılmasına izin verir . Yazın için . Herhangi biri verildiğinde, artık aşağıdaki gibi sınıflar hakkında akıl yürütmeye yönlendirilir: ${\ Displaystyle A\time C}$${\görüntüleme stili 1}$${\görüntüleme stili S0}$${\görüntüleme stili B\alt küme A}$

${\displaystyle \{\langle x,y\rangle \in A\times \{0,1\}\mid (x\in B\land y=1)\lor (\neg (x\in B)\land) y=0)\}.}$

Boolean değerli karakteristik fonksiyonlar bu sınıflar arasındadır. Ancak genel olarak karar verilemeyebileceğini unutmayın . Başka bir deyişle, herhangi bir yapıcı olmayan aksiyomun yokluğunda, her iki ayrılığın da açık bir kanıtı gerektiğinden, ayrım kanıtlanabilir olmayabilir. Ne zaman ${\displaystyle \chi _{B}\iki nokta üst üste A\to \{0,1\}}$${\görüntüleme stili bir\B'de}$${\ Displaystyle a\in B\lor a\notin B}$

${\displaystyle \vardır (y_{a}\in \{0,1\}).f(a)=y_{a}}$

herkes için tanık olunamaz veya bir terimin benzersizliği kanıtlanamazsa, kavranan koleksiyonun işlevsel olduğu yapıcı bir şekilde yargılanamaz. ${\ Displaystyle a\in A}$${\görüntüleme stili y_{a}}$

için ve herhangi bir doğal , var ${\displaystyle I=\{n\in \omega \orta Q(n)\}}$${\ Displaystyle n\ omega'da }$

${\displaystyle Q(n)\lor \neg Q(n)\n\in I\veya n\notin I'i ima eder}$.

Böylece , tanımdaki önermelerin kararlaştırılabilir olduğu klasik küme teorisinde, alt sınıf üyeliği de öyledir. Küme sonlu değilse, klasik olarak sayıları atlayarak tüm sayıları art arda "listelemek" artan bir surjective dizisi oluşturur . Orada, bir bijective işlevi elde edilebilir . Bu şekilde, klasik işlevler sınıfı kanıtlanabilir bir şekilde zengindir, çünkü aynı zamanda etkili bir şekilde hesaplanabilir olduğunu bildiğimizin ötesinde veya praksiste programlı olarak listelenebilir nesneleri de içerir . ${\ Displaystyle {\mathrm {LEM} }}$${\ ekran stili Q}$${\görüntüleme stili I}$${\görüntüleme stili n\ben değil}$${\displaystyle a:\omega \twoheadrightarrow I}$

Bunun aksine, referans bölgesi Hesaplama teorisi , hesaplanabilir setleri seviyesinde, (yinelemeli anlamda) toplam fonksiyonları azalmayan aralıkları olan bir aritmetik hiyerarşisi ve daha yüksek olmayan. Bu düzeyde bir yüklem karar vermek, sonunda üyeliği doğrulayan veya reddeden bir sertifika bulma görevini çözmek anlamına gelir. Her yüklem hesaplanabilir bir şekilde kararlaştırılabilir olmadığından, tek başına teori , tüm sonsuzların etki alanı ile bazı bijektif fonksiyonların aralığı olduğunu iddia etmeyecek (kanıtlamayacaktır) . ${\displaystyle \Sigma _{1}^{0}\cap \Pi _{1}^{0}=\Delta _{1}^{0}}$${\ ekran stili Q}$${\displaystyle {\mathsf {CZF}}}$${\displaystyle I\altküme\omega }$${\ Displaystyle \ omega }$

Sonlu olmak, doğal olanın bijektif bir işlevi olduğu anlamına gelir. Alt sonlu olmak, sonlu bir kümenin alt kümesi olmak demektir. Sonlu bir küme olmanın alt sonlu olmaya eşdeğer olduğu iddiası . ${\ Displaystyle {\mathrm {LEM} }}$

Ancak, ile uyumlu olarak , bu bölümdeki gelişme aynı zamanda her zaman "üzerinde işlev "in yasaya benzer bir dizi olarak verilmesi gerekmeyen bir nesne olarak yorumlanmasına da izin verir . Olasılıkla ilgili iddialar için yaygın modellerde uygulamalar bulunabilir, örneğin bitmeyen bir rastgele yazı tura dizisi "verilme" kavramını içeren ifadeler. ${\displaystyle {\mathsf {ZF}}}$${\ Displaystyle \ omega }$

Tercih

• Sayılabilir seçim aksiyomu : Eğer , bir-çok ilişki kümesi oluşturulabilir . Sayılabilir seçim aksiyomu, her bir sayıyı benzersiz bir değere eşleyen bir fonksiyon oluşturulabilir. Sayılabilir seçim ayrıca, örneğin aralığında kümelerin olası kardinalitelerini sınırlayarak veya sözdizimsel hiyerarşilerdeki yerleriyle ilgili tanımı sınırlayarak daha da zayıflatılabilir .${\displaystyle g\kolon \omega\to z}$${\displaystyle \{\langle n,u\rangle \mid n\in \omega \land u\in g(n)\}}$${\displaystyle \forall (n\in \omega ).\vardır uu\in g(n)}$${\görüntüleme stili g}$

• Bağımlı seçim aksiyomu : Daha genel bir bağımlı seçim aksiyomu tarafından ima edilir, yerleşik bir kümedeki herhangi bir tüm ilişkiden bir işlev çıkarır. Sayılabilir seçim, yapıcı Kilise'nin tezinin bir örneğine benzer ve aslında bağımlı seçim birçok gerçekleştirilebilirlik modelinde geçerlidir ve bu nedenle birçok yapıcı okulda benimsenmiştir.

• Göreceli bağımlı seçim: Daha güçlü göreli bağımlı seçim ilkesi, bunun bir çeşididir - fazladan bir yüklem değişkeni içeren bir şema. Sadece sınırlı formüller için bu benimseyen , teori zaten kanıtlar - indüksiyon , aşağıda daha ayrıntılı olarak tartışılmıştır.${\displaystyle {\mathsf {ECST}}}$${\görüntüleme stili \Sigma _{1}^{0}}$

• Seçim aksiyomu : Genel alanlardaki fonksiyonlarla ilgili seçim aksiyomu. Bağımlı seçim anlamına gelir.

Tam seçim gücünü ve konularında olan ilişkisini vurgulamak için amaçlılığının , tek subfinite sınıfları düşünmelisiniz

${\displaystyle x=\{u\in \{0,1\}\mid u=0\lor (u=1\land P)\}}$

${\displaystyle y=\{u\in \{0,1\}\mid u=1\lor (u=0\land P)\}}$

Burada ve tanımlarında yer alan yüklemler kadar olumsaldır. Şimdi kümeler olarak kuruldukları bir bağlamı varsayalım, bu da öyle. Burada, Seçim Aksiyomu, ayırt edilebilir öğelere sahip bir haritanın varlığını verir . Bu şimdi aslında şunu ima ediyor . Dolayısıyla genel seçim fonksiyonlarının varlık iddiası yapıcı değildir. Bu fenomeni daha iyi anlamak için , vb. gibi mantıksal çıkarımları dikkate almak gerekir . Bazı doğal sayıların ayrık kod alanı ile alan arasındaki fark, ikincisi hakkında a priori çok az şey bilinmesi gerçeğinde yatmaktadır. Bu durumda ve , ne olursa olsun , muhtemelen bir seçim işlevi için bir yarışmacı yapıyor . Ama durumunda arasında sağlamasının da anlaşıldığı üzere, tek vardır sadece, şimdi extensionally bir seçim seçim işlevine yalnızca bir olası fonksiyon girişi olacak şekilde , seçim mutessekkil veya . Bu nedenle, işlevsel atama düşünüldüğünde, koşulsuz olarak bildirmek tutarlı olmaz. Seçim, aksi takdirde güçlü bir küme teorisinde benimsenmeyebilir, çünkü yalnızca fonksiyon varlığının iddiası belirli bir fonksiyonu gerçekleştirmez. Alt sınıf anlama (ayırmak için kullanılan ve gelen tarif edilen şekilde, ayar eşitliğe içinde yer bağları yüklemler'ıN ve bu fonksiyonları ile ilgili bilgiler ile ilgilidir, yani bunları tanımlar). ${\görüntüleme stili x}$${\görüntüleme stili y}$${\görüntüleme stili \{x,y\}}$${\displaystyle f\colon \{x,y\}\to \{0,1\}}$${\displaystyle f(z)\in z}$ ${\ Displaystyle P\lor \neg P}$${\displaystyle P\implies x=y}$${\görüntüleme stili \{x,y\}}$${\displaystyle 0\in x}$${\ekran stili 1\y}$${\görüntüleme stili P}$${\displaystyle \{\langle x,0\rangle ,\langle y,1\rangle \}}$${\görüntüleme stili x=y}$${\görüntüleme stili P}$${\displaystyle \{x,y\}=\{x\}}$${\displaystyle \{x\}\to \{0,1\}}$${\displaystyle \{\langle x,0\rangle \}}$${\displaystyle \{\langle x,1\rangle \}}$${\görüntüleme stili f(x)=0}$${\görüntüleme stili f(y)=1}$${\görüntüleme stili x}$${\görüntüleme stili y}$${\görüntüleme stili \{0,1\}}$

Yapıcı gelişme genellikle tartışılan seçim ilkelerinden bağımsız bir tarzda ilerler.

Aritmetik

Bir aritmetik teorisi elde etmek için gerekli varsayımlar, ispat teorisinde etraflıca incelenir . Bağlam için, burada buradaki sınıflandırmalar hakkında bir paragraf: Sınırlı aritmetik ile başlayan klasik teoriler, farklı muhafazakar tümevarım şemalarını benimser ve belirli işlevler için semboller ekleyerek Robinson- ve Peano aritmetiği arasındaki teorilere yol açabilir . Bununla birlikte, bu tür teorilerin çoğu, bazı daha hızlı büyüyen işlevler için bütünlük kanıtı konusunda nispeten zayıftır . En temel örneklerden bazıları , bir ispat teorik ordinali (en az kanıtlanabilir özyinelemeli iyi sıralama ) ile temel fonksiyon aritmetiğini içerir . olan sıralı , teori anlamı (diyelim (bu sıra analiz anlamda) daha zayıf biri kodlamak sıra sayılarını teorilerini sağlayan , sadece naturals üzerinde özyinelemeli ilişki olarak küme teorisi açısından) . -İnduction şema, relativized bağımlı seçim ima örn gibi araçlar ilişkisiz (sonlu) çalışma zamanı ile arama yerlilerde hesaplanabilir aracılığıyla sonlu olanlar alt sınıfları için indüksiyon. Şema aynı zamanda -indüksiyon şemasına eşdeğerdir . Bu şemayı benimseyen nispeten zayıf klasik birinci mertebeden aritmetik gösterilir . -İnduction de klasik benimsenmiştir ikinci dereceden ters matematik bir taban sisteminin . Bu ikinci mertebeden teori - ilkel özyinelemeli aritmetik üzerinde tutucudur , bu nedenle tüm ilkel özyinelemeli işlevlerin toplamını kanıtlar . En son bahsedilen aritmetik teorilerin hepsinin sıra sayıları vardır . Bahsedilen yüksek mertebeden aritmetik, dili sadece aritmetik kümeleri ifade etmediği sürece, bu tartışmanın ilgili bir referans noktasıdır , oysa teorinin varlığını kanıtladığı tüm doğal kümeler sadece hesaplanabilir kümelerdir . ${\displaystyle {\mathsf {PA}}}$ ${\displaystyle {\mathsf {EFA}}}$${\görüntüleme stili \omega ^{3}}$${\displaystyle {\mathsf {PA}}}$${\displaystyle \varepsilon _{0}}$${\displaystyle \langle \omega ^{3},\in \rangle}$${\ Displaystyle \ langle \ omega , E \ rangle }$${\görüntüleme stili \Sigma _{1}^{0}}$${\görüntüleme stili \Pi _{1}^{0}}$${\displaystyle {\mathsf {I\Sigma }}_{1}}$${\görüntüleme stili \Sigma _{1}^{0}}$${\displaystyle {\mathsf {RCA}}_{0}}$${\displaystyle \Pi _{2}^{0}}$ ${\displaystyle {\mathsf {PRA}}}$${\görüntüleme stili \omega ^{\omega }}$

Bütün bunlarla birlikte , küme teorisi aslında tam ilkel özyinelemeyi bile yorumlamaz. Aslında, Değiştirme aksiyomuna sahip olmasına rağmen, teori, toplama fonksiyonunun bir küme fonksiyonu olduğunu kanıtlamaz. Öte yandan, bu teoride bireysel küme başına birçok ifade kanıtlanabilir (örneğin, bir tümevarım ilkesiyle kullanılabilen evrensel bir niceleyici içeren ifadelerin aksine) ve matematiksel ilgi nesneleri sınıf düzeyinde kullanılabilir. bireysel bazda. Bu nedenle, şimdiye kadar listelenen aksiyomlar, temel matematiğin iyi bir kısmı için temel çalışma teorisi olarak yeterlidir. Ötesine geçerek aritmetik açısından, aksiyomu tanımını verilmesi iterasyon aşamalı set fonksiyonları vasıtasıyla ayarlanan fonksiyonlar eklenmesi gerekir. Gerekli olan, bir doğal sayılar nesnesinin küme teorik eşdeğeridir . Bu daha sonra bir yorumunu sağlayan Heyting Aritmetik , . Bununla rasyonel sayıların aritmetiği de tanımlanabilir ve teklik ve sayılabilirlik gibi özellikleri kanıtlanabilir. Bununla bir küme teorisi, aynı zamanda, herhangi bir doğal ve , fonksiyon uzayları için kanıtlayacaktır.${\displaystyle {\mathsf {ECST}}}$${\displaystyle {\mathsf {ECST}}}$${\displaystyle {\mathsf {HA}}}$${\displaystyle {\mathbb {Q} }}$${\görüntüleme stili n}$${\görüntüleme stili m}$

${\displaystyle {\{0,1,\dots ,n-1\}}\to {\{0,1,\dots ,m-1\}}}$

kümelerdir.

Tersine, aranan yineleme ilkesinin bir kanıtı, bir kişinin yazmak isteyeceği işlevlerin toplanmasına dayanabilir ve bunun varlığı, sonlu alanlardaki bireysel işlev uzaylarının kümeler biçiminde kümeler oluşturduğu varsayılarak ima edilir . Bu açıklama, aritmetik ilkeleri teorimize doğrudan yerleştirmek yerine, daha yerleşik bir teorik lezzet aksiyomunun benimsenmesini motive etmelidir. Bununla birlikte, bir sonraki, daha set teorik aksiyom aracılığıyla elde edilen yineleme ilkesi, yine de tam matematiksel tümevarım şemasını kanıtlamayacaktır . ${\displaystyle \cup _{n\in \omega}y^{\{0,1,\dots ,n-1\}}}$${\görüntüleme stili y}$

üs alma

Ayırma şemasının zayıflatılmış bir biçimi zaten benimsenmiştir ve daha tahmin edici ve yapıcı bir teori için standart aksiyomların çoğu zayıflatılacaktır. Bunlardan ilki , aslında teorinin karar verilebilir alt kümeleri için benimsenen Powerset aksiyomudur . ${\displaystyle {\mathsf {ZF}}}$

Bir kümenin tüm alt kümelerinin sınıfının karakterizasyonu , yani sınırsız evrensel nicelemeyi içerir . İşte yukarıda üyelik yüklemi açısından tanımlanmıştır . Deyim kendisi olduğunu . Dolayısıyla, bir matematiksel küme teorisi çerçevesinde, güç sınıfı, bileşenlerinden (bir listedeki bir algoritma gibi, örneğin haritalar gibi ) aşağıdan yukarıya bir yapıda değil, tüm kümeler üzerinde bir kavrayış yoluyla tanımlanır. ${\ Displaystyle {\Mathcal {P}}x}$${\görüntüleme stili x}$${\displaystyle \forall uu\subset x\iff u\in {\mathcal {P}}x}$${\görüntüleme stili\altküme }$${\görüntüleme stili \içinde }$${\displaystyle y={\matematiksel {P}}x}$${\görüntüleme stili \Pi _{1}}$${\displaystyle \langle a,b\rangle \mapsto \langle \langle \rangle ,\langle a\rangle ,\langle b\rangle ,\langle a,b\rangle \rangle }$

Orta hariç bir teoride güç sınıfının zenginliği, en iyi, klasik olarak küçük sonlu kümeler dikkate alınarak anlaşılabilir. Herhangi bir formül için sınıf , reddedilebildiğinde 0'a ve kanıtlanabildiğinde 1'e eşittir , ancak hiç karar verilebilir olmayabilir. Bu görüşe göre, singleton'un güç sınıfına, yani sınıf veya anlamlı olarak " " ve genellikle ile gösterilen , doğruluk değeri cebiri olarak adlandırılır. Bir kümedeki -değerli işlevler, onun karar verilebilir alt kümelerine enjekte edilir ve dolayısıyla bunlara karşılık gelir. ${\görüntüleme stili P}$${\displaystyle \{x\mid (x=0)\land P\}}$${\görüntüleme stili P}$${\görüntüleme stili P}$${\görüntüleme stili P}$${\görüntüleme stili \{0\}=1}$${\ Displaystyle {\Mathcal {P}}1}$${\görüntüleme stili \{0,\noktalar,1\}}$${\görüntüleme stili\Omega }$${\görüntüleme stili \{0,1\}}$${\görüntüleme stili x}$${\görüntüleme stili \Omega ^{x}}$

Öyleyse bir sonraki aksiyomu düşünün . ${\displaystyle {\mathrm {Exp} }}$

üs alma ${\displaystyle \forall x.\forall y.\ \ \var hh=y^{x}}$

Buradaki formülasyon, fonksiyon uzayları için uygun gösterimi kullanır. Aksi takdirde aksiyom daha uzundur ve toplam fonksiyon yüklemi ile sınırlanmış bir niceleyici içerir . Aksiyom, iki küme verildiğinde , tüm fonksiyonların sınıfının aslında bir küme olduğunu söyler . Bu kesinlikle, örneğin, gibi bir dahili hom-functor nesne haritasını resmileştirmek için gereklidir . Üstelleştirme aksiyomlarının kullanımı, işlev uzaylarının küme olması, işlevleri üzerinde nicelleştirmenin sınırlı bir kavram olması ve Ayırma'nın kullanılmasına olanak sağlaması gerçeğinden kaynaklanmaktadır. Kayda değer çıkarımları vardır: Bunu benimsemek , belirli fonksiyon sınıflarının elemanları üzerindeki nicelemenin , fonksiyon uzayları klasik olarak sayılamayan bile olsa, sınırlı bir kavram haline geldiği anlamına gelir . Örneğin bütün fonksiyonların koleksiyonu yani seti, altta yatan noktalarının Cantor alanı ile, sayılamayan olan Cantor köşegen argüman ve en iyi olmak için alınabilecek subcountable . (Bu bölümde , kardinal- ile sıralı üslerin birleştirilmesini önlemek için, ya da yazma gibi ifadelerde doğal sayıların yarı halkalanması için sembolü kullanmaya başlıyoruz .) ${\görüntüleme stili x\kez y}$${\görüntüleme stili x,y}$${\görüntüleme stili y^{x}}$${\displaystyle {\mathrm {hom} }({\mathbb {N} },-)}$${\displaystyle \forall f}$${\displaystyle f\colon \omega \to \{0,1\}}$${\displaystyle \{0,1\}^{\mathbb {N} }}$${\ Displaystyle y^{\Mathbb {N}}}$${\ Displaystyle \ omega \ y'ye}$

Üslü küme teorisi artık , kümedeki küme işlevleri gibi , doğallar üzerinde herhangi bir ilkel özyinelemeli işlevin varlığını da kanıtlıyor . Buna bağlı olarak, olarak nitelendirilebilecek sıralı -üslü sayıyı elde edin . Daha genel olarak ifade edilirse, Üs, sayılabilir bir küme üzerindeki tüm sonlu dizilerin birleşiminin sayılabilir bir küme olduğunu kanıtlar. Ve gerçekten de, herhangi bir sayılabilir sayma fonksiyonu ailesinin aralıklarının birleşimleri sayılabilir. ${\ Displaystyle \ omega }$${\ Displaystyle \ omega \ to \ omega }$${\görüntüleme stili \omega ^{\omega }}$${\displaystyle \bigcup _{n\in \omega }\omega ^{n}}$

Anlayış söz konusu olduğunda, teori şimdi herhangi bir kümenin tüm sayılabilir alt kümelerinin (koleksiyon, güç sınıfının bir alt sınıfıdır) koleksiyonunun bir küme olduğunu kanıtlıyor. Ayrıca güvercin deliği prensibi kanıtlanabilir.

Orijinal güç sınıfı değerlendirmesine geri dönersek: Tüm formüllerin karar verilebilir olduğu varsayıldığında , yani varsayıldığında , sadece bunun bir küme olduğu değil, daha somut olarak bunun bu iki elemanlı küme olduğu gösterilebilir. Sınırlı formülleri varsayarsak , Ayırma, herhangi bir güç sınıfının bir küme olduğunu göstermeye izin verir. Alternatif olarak, tam Güç Kümesi, yalnızca tüm alt kümelerin sınıfının bir küme oluşturduğunu varsaymaya eşdeğerdir . Tam Ayırma, öğesinin her bir alt sınıfının bir küme olduğunu varsaymaya eşdeğerdir . ${\ Displaystyle {\mathrm {LEM} }}$${\görüntüleme stili\Omega }$${\ Displaystyle {\mathrm {LEM} }}$${\görüntüleme stili 1}$${\görüntüleme stili 1}$

Kategori ve tip teorik kavramlar

Dolayısıyla, bu bağlamda, Üstelleştirme ile, üstel nesnelerde olduğu gibi, işlev uzaylarına alt küme sınıflarından daha erişilebilir . kategori teorisinde alt nesneler . Olarak kategori teorik açıdan, teori esas yapıcı tekabül iyi sivri kapalı Kartezyen Heyting ön toposes (Sonsuz kabul edilir her) bir ile doğal sayılar nesne . Güç kümesinin varlığı, bir Heyting pretoposunu temel bir toposa dönüştürecek olan şeydir . Yorumlayan bu tür her topos , elbette bu daha zayıf teorilerin bir modelidir, ancak yerel olarak Kartezyen kapalı pretopozlar tanımlanmıştır, örneğin teorileri Üs ile yorumlayan, ancak tam Ayırma ve Güç Kümesini reddeden. ${\displaystyle {\mathsf {BCST}}+{\mathrm {Exp} }}$ ${\displaystyle {\mathsf {ZF}}}$

Tip teorisinde, " " ifadesi kendi başına vardır ve ilkel bir kavram olan işlev uzaylarını belirtir . (Küme teorisi, sınıflar veya takım ya da,) Bu tür, doğal olarak türü olarak, örneğin, görünür tımar arasında bir eşleşme ve bir birleşim . Genel programlama yeteneğine sahip tipik bir tür teorisi - ve kesinlikle yapıcı bir küme teorisi olarak kabul edilen modelleyebilenler - bir tür tamsayıya ve 'yi temsil eden işlev uzaylarına sahip olacaktır ve bu nedenle sayılabilir olmayan türleri de içerir. Bu sadece, fonksiyon terimleri arasında hiçbirinin bijeksiyon olma özelliğine sahip olmadığını ima eder ve bu anlama gelir . ${\görüntüleme stili x\'den y'ye}$${\görüntüleme stili (z\times x)\to y}$${\displaystyle z\to y^{x}}$${\displaystyle {\mathsf {CZF}}}$${\displaystyle {\mathbb {Z} }\to {\mathbb {Z}}}$${\displaystyle f\colon {\mathbb {Z} }\to ({\mathbb {Z} }\to {\mathbb {Z} })}$

Yapıcı küme teorileri, uygulamalı aksiyomlar bağlamında da incelenir .

analiz

Bu bölümde, birinin gücü detaylandırılmıştır. Bağlam için, klasik olması gerekmeyen ve ayrıca genel olarak yapıcı kabul edilmeyen olası başka ilkelerden bahsedilmiştir. Burada genel bir uyarı yapılması gerekir: Hesaplanabilir bağlamda önerme denklik iddialarını okurken, kişi her zaman hangi seçim , tümevarım ve anlama ilkelerinin sessizce varsayıldığının farkında olmalıdır . Ayrıca ilgili Yapıcı analiz ve Hesaplanabilir analize bakın . ${\displaystyle {\mathsf {ECST}}+{\mathrm {Exp} }}$

gerçeklere doğru

Üs, özyineleme ilkelerini ima eder ve böylece , diziler hakkında veya içindeki küçülen aralıklar hakkında akıl yürütebilir ve bu aynı zamanda Cauchy dizilerinden ve bunların aritmetiğinden bahsetmeyi sağlar . Herhangi bir Cauchy gerçek sayısı, dizilerin bir koleksiyonudur, yani üzerindeki bir dizi işlevin alt kümesidir . Bu tür dizilerin eşdeğerlik sınıflarının tamlığını her zaman sağlamak için daha fazla aksiyom gerekir ve tüm Cauchy dizileri için bir yakınsama modülünün varlığını ima etmek için güçlü ilkelerin varsayılması gerekir . Zayıf sayılabilir seçim genellikle Cauchy gerçeklerinin tam (sözde) sıralı alan olarak benzersizliğini kanıtlama bağlamıdır . "Sözde-" burada, düzenin her durumda yapıcı bir şekilde her zaman karar verilebilir olmayacağını vurgular. ${\displaystyle {\mathsf {ECST}}+{\mathrm {Exp} }}$${\displaystyle \omega \to {\mathbb {Q}}}$${\displaystyle \omega \to ({\mathbb {Q} }\times {\mathbb {Q} })}$${\ Displaystyle \ omega }$

Klasik teoride olduğu gibi, Dedekind kesimleri cebirsel yapıların alt kümeleri kullanılarak karakterize edilir : Yerleşim, yukarıda sayısal olarak sınırlı, "aşağıya kapalı" ve "yukarı açık" özelliklerinin tümü, cebirsel yapının altında yatan verilen kümeye göre sınırlı formüllerdir. yapı. Standart bir kesim örneği, gerçekten bu özellikleri sergileyen ilk bileşen, verilen temsilidir.${\displaystyle {\mathbb {Q} }}$${\displaystyle {\sqrt {2}}}$

${\displaystyle {\big \langle }\{x\in {\mathbb {Q} }\mid x<0\lor x^{2}<2\},\,\{x\in {\mathbb {Q } }\mid 0<x\land 2<x^{2}\}{\big \rangle }\,\ \in \,\ {{\mathcal {P}}{\mathbb {Q} }}\times {{\mathcal {P}}{\mathbb {Q} }}}$

(Kesme sözleşmesine bağlı olarak, buradaki gibi iki parçadan biri veya hiçbiri işareti kullanamaz .) ${\görüntüleme stili \leq }$

Şimdiye kadar aksiyomlar tarafından verilen teori , aynı zamanda Arşimet ve Dedekind tam olan sözde sıralı bir alanın , eğer varsa, bu şekilde, izomorfizme kadar benzersiz bir şekilde karakterize edildiğini doğrular. Bununla birlikte, gibi sadece fonksiyon uzaylarının varlığı bir küme olmayı sağlamaz ve dolayısıyla bunların tüm alt kümelerinin sınıfı da adlandırılmış özellikleri karşılamaz. Dedekind gerçelleri sınıfının bir küme olabilmesi için gerekli olan, bir alt kümeler kümesinin varlığına ilişkin bir aksiyomdur. ${\displaystyle \{0,1\}^{\mathbb {Q} }}$${\displaystyle {{\mathcal {P}}{\mathbb {Q} }}}$${\displaystyle {\mathbb {Q} }}$

Her iki durumda da, klasik teoriye kıyasla , gerçeklerin aritmetiği hakkında daha az sayıda ifadeye karar verilebilir .

yapıcı okullar

Yapıcı analiz çalışmasında değerli olan yapıcı olmayan iddialar , genel olarak tüm ikili diziler, yani fonksiyonlar ile ilgili olarak formüle edilir . Başka bir deyişle, tarafından nicelenen talepler . ${\displaystyle f\colon \omega \to \{0,1\}}$${\displaystyle \forall (f\in \{0,1\}^{\mathbb {N} })}$

En belirgin örnek, -cümleler veya işlevler düzeyinde olduğu gibi , ayırıcı bir özelliği varsayan sınırlı her şeyi bilme ilkesidir. ( Örnek fonksiyonlar ham olarak oluşturulabilir, öyle ki, eğer tutarlıysa, rekabet eden ayrıklar -kanıtlanamaz.) İlke, örneğin aşağıda tanıtılandan bağımsızdır . Bu yapıcı küme teorisinde, De Morgan yasasının sınırlı bir varyantı olarak belirtilen "daha küçük" versiyonunu ima eder . Ayrıca, Markov ilkesini , bir çelişki yoluyla ispat biçimini ve fan teoreminin -versiyonunu ima eder . Cümleler için geçerli olan bu tür ilkelerin belirtilmesi, genellikle , gerçeklerin ayrılığına karar vererek, diziler açısından eşdeğer formülasyonlara işaret eder . Sayılabilir bir seçim ile yapıcı bir analiz bağlamında , örneğin, her gerçeğin ya rasyonel ya da irrasyonel olduğu iddiasına eşdeğerdir - yine her iki ayrılığa tanık olma şartı olmadan. ${\görüntüleme stili {\mathrm {LPO}}}$${\ Displaystyle {\mathrm {LEM} }}$${\görüntüleme stili \Pi _{1}^{0}}$${\displaystyle {\mathsf {PA}}}$${\displaystyle {\mathsf {PA}}}$${\displaystyle {\mathsf {PA}}}$${\displaystyle {\mathsf {CZF}}}$${\görüntüleme stili {\mathrm {LPO}}}$${\görüntüleme stili {\mathrm {LLPO}}}$ ${\görüntüleme stili {\mathrm {MP}}}$${\görüntüleme stili \Pi _{1}^{0}}$${\görüntüleme stili \Pi _{1}^{0}}$${\görüntüleme stili {\mathrm {LPO}}}$

Bu nedenle, yalnızca temel sezgisel mantık kullanılarak kanıtlanamayan yapıcı analiz teorilerinde kullanılan bazı önermeler için, klasik olmayan yapıcı Church'ün tezine veya özyinelemeli matematik ( veya ) üzerindeki bazı sonuçlarına ve ayrıca Kripke'nin şemasına bakın. ( sayılabilir tüm alt sınıfları döndürme ), bar indüksiyon , karar verilebilir fan teoremi ve hatta klasik olmayan süreklilik ilkesi , Brouwerian sezgici tarafta ( ) sonlu başlangıç ​​segmentleri aracılığıyla bitmeyen diziler üzerinde işlev görür . Her iki okul da çelişir , bu nedenle bu tür yasaları benimsemeyi seçmek, teoriyi klasik analizdeki teoremlerle tutarsız hale getirir. ${\görüntüleme stili {\mathrm {MP}}}$ ${\görüntüleme stili {\mathrm {CT}}}$${\displaystyle {\mathsf {RUSS}}}$${\displaystyle {\mathsf {CRM}}}$${\ Displaystyle \ omega }$${\displaystyle {\mathrm {FAN} }_{\Delta }}$ ${\displaystyle {\mathsf {INT}}}$${\görüntüleme stili {\mathrm {LPO}}}$

sonsuz ağaçlar

Hesaplanabilirlik ve aritmetik hiyerarşi arasındaki ilişki aracılığıyla, bu klasik çalışmadaki içgörüler de yapıcı düşünceler için ortaya çıkıyor. Tersine matematiğin temel bir kavrayışı, hesaplanabilir sonsuz, son derece dallanan ikili ağaçlarla ilgilidir. Böyle bir ağaç, örneğin sonsuz bir sonlu kümeler kümesi olarak kodlanabilir.

${\displaystyle T\,\subset \,\cup _{n\in \omega }\{0,1\}^{\{0,1,\dots ,n-1\}}}$,

karar verilebilir üyelik ile ve bu ağaçlar daha sonra kanıtlanabilir şekilde keyfi büyük sonlu boyutta elemanlar içerir. Weak Kőnigs lemması şunu belirtir: Bunun için , içinde her zaman sonsuz bir yol vardır , yani tüm ilk segmentleri ağacın bir parçası olacak şekilde sonsuz bir dizi. Ters matematikte, ikinci dereceden aritmetik kanıtlamaz . Bunu anlamak için, içinden hesaplanabilir böyle bir yolun bulunmadığı hesaplanabilir ağaçlar olduğuna dikkat edin . Bunu kanıtlamak için , kısmi hesaplanabilir diziler numaralandırılır ve ardından tüm toplam hesaplanabilir diziler tek bir kısmi hesaplanabilir dizide köşegenleştirilir . Daha sonra , her yerin hala olası değerleriyle tam olarak uyumlu olan ve yapım gereği herhangi bir toplam hesaplanabilir yol ile uyumsuz olan belirli bir ağaç açılabilir . ${\displaystyle {\mathrm {WKL} }}$${\görüntüleme stili T}$${\displaystyle \omega \to \{0,1\}}$${\displaystyle {\mathsf {RCA}}_{0}}$${\displaystyle {\mathrm {WKL} }}$${\görüntüleme stili K}$${\görüntüleme stili d}$${\görüntüleme stili K}$${\görüntüleme stili d}$

'de , ilke, her şeyi bilmenin yapıcı olmayan daha az sınırlı ilkesini ima eder . Daha muhafazakar bir bağlamda, - (çok zayıf sayılabilir bir seçim) varsayımıyla eşdeğerdirler . Aynı zamanda Brouwer sabit nokta teoremi ve gerçekler üzerindeki sürekli fonksiyonların değerleriyle ilgili diğer teoremlere eşdeğerdir . Sabit nokta teoremi de ara değer teoremini ima eder , ancak klasik teoremlerin yapıcı bir bağlamda ifade edildiğinde farklı varyantlara çevrilebileceğini unutmayın. ${\displaystyle {\mathsf {CZF}}}$${\displaystyle {\mathrm {WKL} }}$ ${\görüntüleme stili {\mathrm {LLPO}}}$${\görüntüleme stili \Pi _{1}^{0}}$${\ Displaystyle {\mathrm {AC} }_{\omega ,2}}$

Kaygılar sonsuz grafikler ve dolayısıyla ona olumlu çelişki sonluluğu için bir koşul verir. Aşırı klasik aritmetik teorisi , bu denklik verir Borel kompakt reel birim aralığının sonlu subcovers ilgili. Sonsuz bir bağlamda sonlu dizileri içeren yakından ilişkili bir varoluş iddiası, karar verilebilir fan teoremidir . üzerinde, aslında eşdeğerdirler. Gelen bu farklıdır, ancak yine bazı seçim varsayarak, ima . ${\displaystyle {\mathrm {WKL} }}$${\displaystyle {\mathsf {RCA}}_{0}}$${\displaystyle {\mathrm {FAN} }_{\Delta }}$${\displaystyle {\mathsf {RCA}}_{0}}$${\displaystyle {\mathsf {CZF}}}$${\displaystyle {\mathrm {WKL} }}$${\displaystyle {\mathrm {FAN} }_{\Delta }}$

İşlev boşluklarını kısıtlama

Aşağıdaki yorumda fonksiyon ve onlar hakkında ileri sürülen iddialar yine hesaplanabilirlik teorisi anlamındadır. Μ operatörün tüm kısmi sağlayan genel yinelemeli fonksiyonları , örneğin temel olmayan ama da dahil olmak üzere (bunlar hesaplanabilir Turing anlamda veya programları,), örneğin, -toplam, Ackermann fonksiyonu . Operatörün tanımı, doğallar üzerindeki yüklemleri içerir ve bu nedenle fonksiyonların ve bunların bütünlüğünün teorik analizi , eldeki resmi çerçeveye bağlıdır. Her iki durumda da, hesaplanabilirlik teorisinde, toplam olan hesaplanabilir fonksiyonların indeksleri olarak düşünülen doğal sayılar , aritmetik hiyerarşidedir . Yani hala doğalların bir alt sınıfıdır. Ve orada, bütün programların bir yüklemi olarak bütünlük, ünlü bir şekilde hesaplanamaz bir şekilde karar verilemez . ${\görüntüleme stili {\mathrm {PA}}}$${\displaystyle \Pi _{2}^{0}}$

Klasik olmayan bir yapıcı Kilise'nin tezi , öncülündeki varsayıma göre, kanıtlanabilir şekilde bütün olan yüklem tanımlarıyla (ve dolayısıyla burada küme işlevleriyle) ilgilidir ve bunların hesaplanabilir programlara karşılık geldiğini varsayar. Postülatın benimsenmesi, klasik küme teorisinden görüldüğü gibi "seyrek" bir kümeye dönüşür. Bkz. alt sayılabilirlik . ${\görüntüleme stili {\mathrm {CT}}}$${\ Displaystyle \ omega \ to \ omega }$

Postüla hala tutarlı sezgisel aritmetik veya seçimdir. Ancak , sıklıkla tartışılan en zayıf ilkeler arasında yer alan ve gibi klasik olarak geçerli ilkelerle çelişir . ${\görüntüleme stili {\mathrm {CT}}}$${\görüntüleme stili {\mathrm {LLPO}}}$${\displaystyle {\mathrm {FAN} }_{\Delta }}$

indüksiyon

matematiksel tümevarım

Önceki bölümlerde, sınırlı Ayırma, sınırlı tanımlar için tümevarımın geçerliliğini zaten oluşturmuştu. Belirlenmiş dilde, tümevarım ilkeleri, yukarıda tanımlanan öncül ile okunabilir . Bir önerme olduğunu gözlemlemek öğreticidir , sonucu gibi birçok aksiyomlar uygulamak alışkanlık anlamı - - burada bir dizi teşkil olmayabilir Alt sınıf kapsayan sınıf notasyonu kullanılarak ifade ve düz (bir aynı istenen iddiayı formüle sadece iki yolu vardır Burada özellikle istemlerin indekslenmiş birleşimi.) Böylece, henüz sınırlandırılmış Ayırma ile bir dizi teorik çerçeve, sınırsız yüklemler için aritmetik tümevarım şemaları yoluyla güçlendirilebilir. ${\displaystyle \mathrm {Ind} (A)\implies \omega \subset A}$ ${\displaystyle \mathrm {Ind} (A)}$${\displaystyle \omega \subset \{n\in \omega \mid y^{\{0,1,\dots ,n-1\}}{\text{ bir kümedir}}\}}$${\displaystyle \forall (n\in \omega ).y^{\{0,1,\dots ,n-1\}}{\text{ bir kümedir}}}$${\görüntüleme stili n}$

Daha önce bahsedilen küme fonksiyonları için yineleme ilkesi, Üstelleştirmeye alternatif olarak, doğalları modelleyen kişinin yapısı üzerindeki tam tümevarım şemasıyla da ima edilir (örn . Bu aynı zamanda, olduğundan daha fazla fonksiyonun toplamını kanıtlamak için birinci dereceden aritmetik ilkesidir . Genellikle aşağıdaki gibi doğrudan yüklemler cinsinden formüle edilir. Şemayı düşünün - : ${\ Displaystyle \ omega }$${\displaystyle {\mathsf {PRA}}}$${\ Displaystyle \ omega }$${\ Displaystyle {\mathrm {Ind} }}$

Tam matematiksel tümevarımın aksiyom şeması : Herhangi bir yüklem için , ${\görüntüleme stili\phi }$${\ Displaystyle \ omega }$ ${\displaystyle {\Big (}\phi (0)\ \land \ \forall (k\in \omega ).{\big (}\phi (k)\implies \phi (Sk){\big )}{\ \Big )}\her şey için (n\in \omega ).\phi (n)}$

Burada 0, yukarıdaki gibi anlamına gelir ve küme , ile ardıl kümesini belirtir . Yukarıdaki Sonsuzluk Axiom'a göre, yine . ${\görüntüleme stili \{\}}$${\ Displaystyle Sn}$${\ Displaystyle n\ omega'da }$${\ Displaystyle n\ Sn'de}$${\ Displaystyle \ omega }$

Seçim bölümünde belirtildiği gibi, tümevarım ilkeleri aynı zamanda çeşitli seçim ilkeleri biçimleriyle ima edilir. Tam tümevarım şeması, tam Ayırma şeması tarafından ima edilir.

'ye göre her küme için bir geçişli kapanışın varlığını kanıtlamak için en azından sınırlı bir yineleme şemasına ihtiyaç vardır. Tahmini aritmetik programında, doğal sayılar bu şemayı yerine getiren nesne olarak tanımlandığında , tam matematiksel tümevarım şemasının muhtemelen tahmin edici olduğu için eleştirilmiş olduğunu belirtmekte fayda var . ${\görüntüleme stili \içinde }$

İndüksiyonu Ayarla

Full Set Induction in , doğal sayılar üzerinde tam matematiksel tümevarımı kanıtlar. Gerçekten de, sıra sayıları ve sıra aritmetiği üzerinde tümevarım verir. Doğal kümeler üzerinde tümevarımı kanıtlamak için değiştirme gerekli değildir, ancak küme teorisi içinde modellenen aritmetikleri içindir. ${\displaystyle {\mathsf {ECST}}}$

Daha güçlü aksiyom - aşağıdaki gibi okur: ${\görüntüleme stili \içinde }$${\ Displaystyle {\mathrm {Ind} }}$

Set indüksiyonunun aksiyom şeması : Herhangi bir yüklem için , ${\görüntüleme stili\phi }$ ${\displaystyle {\Big (}\forall s.\,{\big (}\forall (x\in s).\ \phi (x){\big )}\implies \phi (s){\Big ) }\tüm y için\phi (y)} ima eder$

Burada önemsizdir ve standart çerçevedeki "alt duruma" karşılık gelir. Aksiyomun sadece sınırlı formüller için varyantı da bağımsız olarak incelenir ve diğer aksiyomlardan türetilebilir. ${\displaystyle \forall x\in \{\}.\phi (x)}$

Aksiyom, sınır ötesi özyineleme ile sınıf fonksiyonlarının tanımlarına izin verir . Tümevarım yoluyla küme tanımları, yani tümevarımsal tanımlar veren çeşitli ilkelerin incelenmesi, yapıcı küme teorisi ve bunların nispeten zayıf güçlü yönleri bağlamında ana konudur . Bu aynı zamanda tip teorisindeki benzerleri için de geçerlidir .

Düzenlilik aksiyomu birlikte sınırlı / sınırsız Ayırma da sınırsız / sınırlı set indüksiyon anlamına gelir fakat bu Düzenlilik yapıcı olmayan, bu yüzden. Tersine, Set Induction ile birlikte Düzenlilik anlamına gelir. ${\ Displaystyle {\mathrm {LEM} }}$${\ Displaystyle {\mathrm {LEM} }}$

metalolojik

Bu şimdi sekiz Zermelo-Fraenkel aksiyomunun tüm çeşitlerini kapsar . Genişletme, Eşleştirme, Birleştirme ve Değiştirme gerçekten aynıdır. Sonsuzluk güçlü bir formülle ifade edilir ve klasik durumda olduğu gibi Emty Kümesini ifade eder. Klasik olarak gereksiz olarak ifade edilen ayırma, Değiştirme ile yapıcı olarak ima edilmez. Hariç Tutulan Orta Yasası olmadan , buradaki teori, klasik biçiminde, tam Ayırma, Güç Kümesi ve Düzenlilikten yoksundur.

Teori tutarlılığı gücünü aşmayacak Heyting aritmetik ama ekleyerek bu aşamada tipik gücü ötesinde bir teoriye yol açacak tip teorisi : o zaman ekleyerek, sınırsız formda Ayrımı varsayarsak için aynı teoremleri kanıtlayan bir teori verir eksi Düzenlilik! Böylece bu çerçeveye Ayrılık ve Düzenlilik eklemek tam verir ve ona Seçim eklemek . ${\displaystyle {\mathsf {ECST}}+{\mathrm {Exp} }}$${\ Displaystyle {\mathrm {LEM} }}$${\ Displaystyle {\mathrm {LEM} }}$${\displaystyle {\mathsf {ECST}}+{\mathrm {Exp} }}$${\displaystyle {\mathsf {ZF}}}$${\displaystyle {\mathsf {ZF}}}$${\displaystyle {\mathsf {ZFC}}}$

Yapıcı bağlamda İndüksiyon ile elde edilen ilave teorik ispat gücü, bağlamında Düzenliliği düşürmek ispat teorik gücünü azaltmasa bile önemlidir . Aczel ayrıca , bu son aksiyomu reddeden ana geliştiricilerden veya sağlam temelli olmayan küme teorisinden biriydi . ${\displaystyle {\mathsf {ZF}}}$

Güçlü Koleksiyon

Tüm zayıflatılmış aksiyomlar ve şimdi Myhill'in daktilo yaklaşımında da görülen bu aksiyomların ötesine geçerek, şimdi toplama şemasıyla güçlendirilen Üslü teoriyi düşünün . Birinci dereceden formülasyonunda bir şekilde tekrarlayan bir biçime yol açan ilişkiler için bir özellik ile ilgilidir. ${\displaystyle {\mathsf {ZF}}}$

Strong Collection'ın aksiyom şeması: Herhangi bir yüklem için , ${\görüntüleme stili\phi }$ ${\displaystyle \forall a.\ \ {\Big (}\forall (x\in a).\vardır.\phi (x,y){\Big )}\implies \vardır b.{\Big (} \forall (x\in a).\vardır (y\in b).\phi (x,y)\ \land \ \forall (y\in b).\vardır (x\in a).\phi ( x,y){\Büyük )}}$

Belirli bir tanım kümesi üzerinde toplam olan kümeler arasında bir bağıntı varsa (yani, kümedeki her öğe için en az bir görüntü değerine sahipse), her kümenin altında en az bir görüntü içeren bir kümenin var olduğunu belirtir . etki alanı öğesi. Ve bu formülasyon ayrıca, yalnızca bu tür görüntülerin o kod alanı kümesinin öğeleri olduğunu belirtir. Son madde aksiyomu - bu yapıcı bağlamda - Koleksiyon'un standart formülasyonundan daha güçlü kılar. Bunun kod alanını aşmadığını garanti ediyor ve bu nedenle aksiyom bir Ayırma prosedürünün bir gücünü ifade ediyor. ${\görüntüleme stili\phi }$${\görüntüleme stili bir}$${\görüntüleme stili b}$${\görüntüleme stili\phi }$${\görüntüleme stili b}$${\görüntüleme stili\phi }$

Aksiyom, Değiştirme şemasına bir alternatiftir ve ikili ilişki tanımının işlevsel olmasını gerektirmediği için gerçekten onun yerini alır .

Kural olarak, orta düzeyde kardinalite soruları yapıcı bir ortamda daha inceliklidir. Aritmetik burada iyi bir şekilde mevcut olduğundan, teorinin bağımlı ürünleri vardır, doğal sayıların tüm alt kümelerinin sınıfının alt sayılabilir olamayacağını ve ayrıca sayılabilir kümelerin fonksiyon uzaylarının sayılabilir birleşimlerinin sayılabilir kaldığını kanıtlar.

metalolojik

Bu teori , sınırsız ayırma ve "naif" Güç kümesi olmadan çeşitli güzel özelliklere sahiptir. Örneğin, Varoluş Özelliğine sahiptir : Herhangi bir özellik için teori, o özelliğe sahip bir kümenin var olduğunu kanıtlarsa, yani teori ifadeyi kanıtlarsa, böyle bir küme örneğini benzersiz olarak tanımlayan bir özellik de vardır . Yani, teori o zaman da kanıtlıyor . Bu, teoremlerin somut doğal sayılarla gerçekleştirildiği ve bu özelliklere sahip olduğu Heyting aritmetiği ile karşılaştırılabilir . Küme teorisinde rol, tanımlanmış kümeler tarafından oynanır. Buna karşılık, içinde Seçim Aksiyomu'nun İyi sıralama teoremini ima ettiğini hatırlayın , böylece kümelerin alt kümeleri için en az elemana sahip toplam sıralamaların varlığı, böyle bir sıralama açıklanamasa bile, resmi olarak kanıtlanır. ${\ Displaystyle {\mathrm {LEM} }}$${\görüntüleme stili\Phi }$${\görüntüleme stili \x var.\Phi (x)}$${\görüntüleme stili \Psi }$${\görüntüleme stili \var !x.\Psi (x)\land \Phi (x)}$${\displaystyle {\mathsf {ZFC}}}$${\displaystyle \mathbb {R} }$

Yapıcı Zermelo-Fraenkel

Bir tür teorik yorumunu kaybetmeden Güç kümesine daha fazla yaklaşılabilir. Olarak bilinen teori , yukarıdaki aksiyomlar artı daha güçlü bir Üstelleştirme biçimidir. Yine Güç kümesi aksiyomunun yapıcı bir versiyonu olarak görülebilecek olan aşağıdaki alternatifi benimseyerek yapılır : ${\displaystyle {\mathsf {CZF}}}$

Subset Collection'ın aksiyom şeması: Herhangi bir yüklem için , ${\görüntüleme stili\phi }$ ${\displaystyle \forall a.\forall b.\ \ \\vardır u.\forall z.{\big (}\forall (x\in a).\vardır (y\in b).\phi (x,y ,z){\big )}\vardır (v\in u).{\big (}\forall (x\in a).\vardır (y\in v).\phi (x,y,z) )\;\land \;\forall (y\in v).\vardır (x\in a).\phi (x,y,z){\big )}}$

Bu Alt Küme Toplama aksiyomu şeması, tek ve biraz daha net bir alternatif Doluluk Aksiyomu'na eşdeğerdir. Bu amaçla, a ve b arasındaki tüm toplam ilişkilerin sınıfı olsun, bu sınıf olarak verilmiştir. ${\görüntüleme stili a\Sigma {b}}$

${\displaystyle r\in a\Sigma {b}\iff {\big (}\forall (x\in a).\vardır (y\in b).\langle x,y\rangle \in r{\big )}\,\land \,{\big (}\forall (p\in r).\vardır (x\in a).\vardır (y\in b).p=\langle x,y\rangle { \büyük )}}$

Bununla, Subset Collection'a bir alternatif belirtin . İstenen ilişkilerin iyi bir miktarını tutan en azından bir kümenin var olduğunu garanti eder . Daha somut olarak, her iki set arasında ve , bir dizi olduğu toplam alt ilişkisini içeren bir toplam ilişki için gelen için . ${\displaystyle {\mathrm {Doluluk}}}$${\displaystyle c\subset a\Sigma {b}}$${\görüntüleme stili bir}$${\görüntüleme stili b}$${\görüntüleme stili c}$${\görüntüleme stili s}$${\görüntüleme stili r}$${\görüntüleme stili bir}$${\görüntüleme stili b}$

Doluluk Aksiyomu:

${\displaystyle \forall a.\forall b.\ \ \ var (c\subset a\Sigma {b}).\forall (r\in a\Sigma {b}).\vardır (s\in c). s\altküme r}$

Doluluk aksiyomu, bölümler hakkında Sunum Aksiyomu olarak adlandırılan ve kategori teorik olarak da formüle edilebilen tarafından ima edilir .

Doluluk, Dedekind kesimlerinin sınıfının bir küme olduğunu kanıtlamak için gerekli olan ikili iyileştirme özelliğini ifade eder. Bu, İndüksiyon veya Toplama gerektirmez.

Ne doğrusallık ait ordinals , ne de sonlu kümelerin güç kümelerinin varlığı bu teoride derive bulunmaktadır. Her ikisinin de bu bağlamda Güç setini ima ettiğini varsayarsak.

metalolojik

Bu teori, Şema nedeniyle var olma özelliğinden yoksundur, ancak 1977'de Aczel , Martin-Löf tipi teoride ( tipler olarak önermeler yaklaşımını kullanarak) hala yorumlanabileceğini gösterdi , şimdi tip teorisinde standart bir model olarak görülen şeyi sağladı. . Bu, küme teorisinin dilini korurken, işlevlerinin görüntüleri ve oldukça doğrudan yapıcı ve tahmin edici bir gerekçelendirme açısından yapılır. Bu alt sayılabilir model birçok seçim ilkesini doğrular . Bir tür teorik model ile, mütevazı bir kanıt teorik gücüne sahiptir, bakınız : Bachmann-Howard ordinal . ${\displaystyle {\mathsf {CZF}}}$${\displaystyle {\mathsf {CZF}}}$${\displaystyle {\mathsf {CZF}}}$ ${\displaystyle {\mathsf {IKP}}}$

Not: ZF ile kırma

Ayrıca, tüm kümelerin bir aksiyom olarak alt sayılabilir olduğu şeklindeki klasik olmayan iddia da eklenebilir . O zaman bir kümedir (Sonsuzluk ve Üs ile), sınıf veya hatta kanıtlanabilir bir şekilde bir küme değildir, Cantor'un köşegen argümanına göre . Dolayısıyla bu teori, mantıksal olarak Powerset ve . ${\ Displaystyle \ omega \ to \ omega }$${\ Displaystyle {\Mathcal {P}}\omega }$${\görüntüleme stili {\matematiksel {P}}\{0\}}$${\ Displaystyle {\mathrm {LEM} }}$

1989 yılında Ingrid Lindström gösterdi olmayan sağlam temelli setleri eşdeğer değiştirerek elde Vakfı Axiom içinde (İndüksiyon) ile Aczél karşıtı vakıf aksiyomuna ( ) ayrıca Martin-Löf tipi teoride yorumlanabilir. ${\displaystyle {\mathsf {CZF}}}$${\displaystyle {\mathsf {CZFA}}}$

Sezgisel Zermelo-Fraenkel

Teori , standart Ayırma ve Güç seti ile ilgilidir . ${\displaystyle {\mathsf {IZF}}}$${\displaystyle {\mathsf {CZF}}}$

Burada, aksiyom değiştirme şeması yerine ,

Toplama aksiyom şeması : Herhangi bir yüklem için , ${\görüntüleme stili\phi }$ ${\displaystyle \forall z.{\big (}\forall (x\in z).\vardır.\phi (x,y){\big )}\implies \w.\forall (x\in z) ).\vardır (y\in w).\phi (x,y)}$

Değiştirme aksiyomu ilişkisini gerektirir iken olmaya işlevsel kümesi üzerinden (her için, olduğu gibi de tam olarak bir tane ilişkilidir ), Koleksiyon aksiyomu değildir. Yalnızca en az bir tane ilişkilendirilmiş olmasını gerektirir ve her biri için en az bir tane toplayan bir kümenin varlığını ileri sürer . Koleksiyon ile birlikte Değiştirme anlamına gelir. ${\görüntüleme stili\phi }$${\görüntüleme stili z}$${\görüntüleme stili x}$${\görüntüleme stili z}$${\görüntüleme stili y}$${\görüntüleme stili y}$${\görüntüleme stili y}$${\görüntüleme stili x}$${\ Displaystyle {\mathrm {LEM} }}$

Bu nedenle, olmadan en yalındır varyantı olarak görülebilir . ${\displaystyle {\mathsf {IZF}}}$${\displaystyle {\mathsf {ZF}}}$${\ Displaystyle {\mathrm {LEM} }}$

Teori, sayı teorik fonksiyonlar için Church'ün tezinin yanı sıra alt sayılabilir olma ile de tutarlıdır . Ancak, yukarıda ima edildiği gibi, teorinin bir küme olduğu kanıtlandığında, alt sayılabilirlik özelliği tüm kümeler için kabul edilemez. ${\ Displaystyle \ omega \ to \ omega }$${\ Displaystyle {\Mathcal {P}}\omega }$

metalolojik

Değiştirme Aksiyom şemasını Toplama Aksiyom şemasıyla değiştirerek, ortaya çıkan teori Sayısal Varolma Özelliğine sahiptir .

Hatta olmadan , ispat teorik gücü ait Bunun eşittir . ${\ Displaystyle {\mathrm {LEM} }}$${\displaystyle {\mathsf {IZF}}}$${\displaystyle {\mathsf {ZF}}}$

Klasik mantıktan ziyade sezgiye dayalı olmasına rağmen , tahmin edilemez olarak kabul edilir . Sınırlı olmayan niceleyiciler içerenler de dahil olmak üzere herhangi bir önerme ile Ayrılık Aksiyomu kullanılarak kümelerin oluşturulmasına izin verir . Böylece tüm kümelerin evreni cinsinden yeni kümeler oluşturulabilir. Ek olarak, güç kümesi aksiyomu, bir dizi doğruluk değerinin varlığını ima eder . Dışlanan ortanın varlığında, bu küme vardır ve iki elemanı vardır. Bunun yokluğunda, doğruluk değerleri kümesi de tahmin edici olarak kabul edilir. ${\displaystyle {\mathsf {ZF}}}$

Tarih

1973'te John Myhill , en yaygın temeli alan ve seçim Aksiyomunu ve hariç tutulan ortanın yasasını atarak , diğer her şeyi olduğu gibi bırakarak sezgisel mantığa dayalı bir küme teorisi sistemi önerdi . Bununla birlikte, klasik ortamda eşdeğer olan bazı aksiyomların farklı formları , yapıcı ortamda eşdeğerdir ve bazı formlar . Bu durumlarda, daha sonra yapıcı küme teorisi için sezgisel olarak daha zayıf formülasyonlar benimsendi. ${\displaystyle {\mathsf {ZFC}}}$${\displaystyle {\mathsf {ZFC}}}$${\ Displaystyle {\mathrm {LEM} }}$

Sezgisel Z

Yine daha zayıf ucunda, tarihsel muadili gibi Zermelo grubu teori , tek tarafından belirtebilir gibi ayarlanır sezgisel teori ama değiştirilmesi, Collection veya İndüksiyon olmadan. ${\displaystyle {\mathsf {IZ}}}$${\displaystyle {\mathsf {IZF}}}$

Sezgisel KP

Araştırılan başka bir çok zayıf teoriden, yani Sezgisel (veya yapıcı) Kripke-Platek küme teorisinden bahsedelim . Teoride sadece Ayırma değil, aynı zamanda Toplama da sınırlandırılmıştır, yani tam Değiştirme yerine Tümevarım ile benzerdir . Infinity olmadan çalışıldığında özellikle zayıftır. Teori, yukarıda sunulduğu gibi hiyerarşiye uymaz, çünkü başlangıçtan itibaren Küme İndüksiyonunun Aksiyom şemasına sahiptir . Bu, sıra sayıları sınıfını içeren teoremleri mümkün kılar. ${\displaystyle {\mathsf {IKP}}}$${\displaystyle {\mathsf {BCST}}}$

sıralanmış teoriler

Yapıcı küme teorisi

Sunduğu gibi, Myhill'in sistemi , özdeşlik ve üç tür , yani kümeler, doğal sayılar , işlevler ile yapıcı birinci mertebeden mantığı kullanan bir teoridir . Aksiyomları şunlardır: ${\displaystyle {\mathsf {CST}}}$

• Kümeler için olağan Genişletme Aksiyomu ve ayrıca işlevler için bir Aksiyom ve olağan birleşim Aksiyomu .
• Sınırlı veya yüklem, aksiyomu ayrılması zayıflatılmış bir şeklidir, ayırma aksiyomu herhangi gerektiren klasik grubu teoriden sayımsal tartışıldığı gibi, bir dizi sınırlı olsun.
• Sonsuzluk Aksiyomu'nun bir biçimi, doğal sayılar koleksiyonunun (ki bunun için bir sabit verir ) aslında bir küme olduğunu iddia eder .${\ Displaystyle \ omega }$
• Herhangi iki küme için, etki alanı birinci küme ve aralığı ikinci küme olan tüm (ve yalnızca) işlevleri içeren üçüncü bir küme olduğunu öne süren Üs aksiyomu. Bu, klasik küme teorisindeki kuvvet kümesi aksiyomunun büyük ölçüde zayıflatılmış bir biçimidir ve Myhill'in diğerlerinin yanı sıra, kendi öngörüsüzlüğü temelinde itiraz ettiği .

Ve ayrıca:

• Doğal sayılar için olağan Peano aksiyomları .
• Bir fonksiyonun etki alanı ve aralığının her ikisinin de küme olduğunu iddia eden aksiyomlar . Ek olarak, bir seçimsizlik aksiyomu , seçimin zaten yapılmış olduğu durumlarda bir seçim fonksiyonunun varlığını ileri sürer. Bunlar birlikte klasik küme teorisindeki olağan Değiştirme aksiyomu gibi hareket eder .

Bu teorinin gücü , önceki bölümlerle karşılaştırıldığında, yapıcı bir alt teori ile kabaca tanımlanabilir . ${\displaystyle {\mathsf {ZF}}}$

Ve nihayet teori benimser

• Her zamanki seçim aksiyomundan çok daha zayıf olan bir bağımlı seçim aksiyomu .

Piskopos stili küme teorisi

Errett Bishop'un yapılandırmacı okulunun tadındaki küme teorisi, Myhill'inkini yansıtır, ancak kümelerin ayrıklıklarını yöneten ilişkilerle donatıldığı bir şekilde kurulur. Genellikle, Bağımlı Seçim benimsenir.

Bu bağlamda pek çok analiz ve modül teorisi geliştirilmiştir.

Kategori teorileri

Kümelerin tüm biçimsel mantık teorilerinin ikili üyelik yüklemini " " doğrudan aksiyomlaştırması gerekmez . Ve Küme Kategorilerinin Temel Teorisi ( ), örneğin nesneler arasında birleştirilebilir eşleme çiftlerini yakalamak, yapıcı bir arka plan mantığı ( ) ile de ifade edilebilir . Kategori teorisi , oklar ve nesneler teorisi olarak kurulabilir, ancak birinci dereceden aksiyomizasyonlar sadece oklar açısından mümkündür. ${\görüntüleme stili \içinde }$${\displaystyle {\mathsf {ETCS}}}$${\ Displaystyle {\mathsf {CETCS}}}$

Kategori teorisindeki yapıcı küme teorilerinin iyi modelleri, Üsleme bölümünde bahsedilen ön varsayımlardır - muhtemelen yeterli projektif gerektirir, kümenin surjektif "sunuları" hakkında bir aksiyom, Sayılabilir Bağımlı Seçimi ima eder.

Bunun ötesinde, topoi'nin ayrıca sezgici olabilen ve bir küme kavramını yakalayan dahili dilleri vardır .

Ayrıca bakınız

• yapıcı matematik
• Sezgisel tip teorisi
• sıralı analiz
• tahmin edilemezlik
• Varlık Özelliği
• Hariç tutulan orta yasası
• alt sayılabilirlik

Referanslar

daha fazla okuma

• Troelstra, Anne ; van Dalen, Dirk (1988). Matematikte Yapılandırmacılık, Cilt. 2 . Mantık Çalışmaları ve Matematiğin Temelleri. P. 619 . ISBN'si 978-0-444-70358-3.
• Aczel, P. ve Rathjen, M. (2001). Yapıcı küme teorisi üzerine notlar . Teknik Rapor 40, 2000/2001. Mittag-Leffler Enstitüsü, İsveç.

Dış bağlantılar

• Laura Crosilla, Küme Teorisi: Yapıcı ve Sezgisel ZF , Stanford Felsefe Ansiklopedisi , 20 Şubat 2009
• Benno van den Berg, Yapıcı küme teorisi – genel bakış , Heyting dag'dan slaytlar, Amsterdam, 7 Eylül 2012