"Sınıflandırma problemlerinin (classification problems) ne kadar
zor olduğunu matematiksel olarak ölçmek mümkün müdür?"
Son otuz yılda betimsel kümeler kuramının (descriptive set theory) teknikleriyle bu soruya pozitif yanıt vermenin mümkün olduğu anlaşıldı. Matematikteki sınıflandırma problemleri çoğu zaman bir standart Borel uzayı üzerindeki tanımlanabilir denklik bağıntıları olarak ifade edilebiliyor. (Standart Borel uzayı demek şu demek: Bir ayrılabilir tam metrik uzay alın, daha sonra bu uzayı üzerindeki metriği ve topolojiyi "unutarak" sadece ilgili Borel σ-cebiri yapısıyla göz önüne alın.)
Örnek vereyim. Diyelim ki sayılabilir çizgelerin sınıflandırma problemini incelemek istiyorsunuz. Genelliği bozmadan varsayabiliriz ki her sayılabilir çizge (N,E) formundadır. Burada E⊆N2 rastgele bir simetrik ve "irreflexive" bağıntı. Bu durumda P(N2) kümesini 2N2 özdeşleştirirsek, sayılabilir çizgelerin standart Borel uzayı olarak 2N2 uzayının bir alt uzayı olarak alabiliriz. Bu uzayın her elemanı bir sayılabilir çizge kodlar ve her sayılabilir çizge bu uzayın bir elemanıyla kodlanabilir. Sayılabilir çizgeler üzerindeki eşyapısallık bağıntısı ∼⊆2N2×2N2 da çarpım uzayının analitik bir alt kümesi olur. (Analitik küme demek bir boyut üstte yaşayan Borel bir kümenin izdüşümü demek.)
Bunu pek çok kategori için yapmak mümkün. Sayılabilir grupların, cisimlerin, doğrusal sıralamaların (genel olarak bağıntısal sayılabilir bir dille ifade edilebilen sayılabilir yapıların) uzayları, Cantor uzayının homeomorfizmlerinin uzayı, AF-cebirlerin uzayı vs.
Bunu yaptıktan sonra sınıflandırma problemlerinin değişmezlerini (invariant) ilgili uzaylardaki denklik sınıfları kümeleri olarak görebiliriz ve sınıflandırma problemlerinin göreli karmaşıklıklarını Borel indirgenebilirlik (Borel reducibility) altında kıyaslamak mümkün. Borel indirgenebilirliğin tanımını yapayım:
E⊆X2 ve F⊆Y2 standart Borel uzayları X ve Y üzerinde analitik iki denklik bağıntısı olsun. (Yani çarpım Borel yapısına göre X2 ve Y2'nin analitik alt kümeleri.) Bu durumda E denklik bağıntısı, F denklik bağıntısına Borel indirgenebilirdir diyoruz ancak ve ancak öyle bir Borel f:X→Y fonksiyonu varsa ki xEy⇔f(x)Ff(y) oluyorsa. Bu durumda da E≤BF yazıyoruz. Eğer E≤BF ve F≤BE ise bu durumda E∼BF yazıyoruz ve E ile F karşılıklı Borel indirgenebilir (Borel bireducible) diyoruz. E≤BF ve F≰BE ise de E<BF yazıyoruz.
Bunun sezgisel olarak anlamı şu: Eğer elimizde iki objenin F-denk olup olmadığını söyleyen bir kahin olsaydı, bu kahini ve f fonksiyonunu kullanarak iki objenin E-denk olup olmadığına karar verebilirdik. Bu durumda E'nin kodladığı sınıflandırma probleminin karmaşıklığının F'nin kodladığı sınıflandırma probleminin karmaşıklığından küçük eşit olduğunu söyleyebiliriz.
Burada f fonksiyonunun Borel olmasını istiyoruz çünkü Borel kümeleri açıkça ifade edilebilir (explicit) fonksiyonlar gibi düşünüyoruz. Aksi halde, eğer Borel olma koşulunu koymazsak, seçim belitini kullanarak denklik sınıfı sayısı aynı her bağıntıyı birbirine indirgeyebilirdik ama seçim beliti bize büyük ihtimalle "patolojik" kümeler üretirdi.
Örnek verelim: Değişmeli sonlu üretilebilir grupların eşyapısallık bağıntısı ΔNN bağıntısına indirgenebilir. (Aslında bu bağıntı ΔN ile karşılıklı indirgenebilirdir.) Zira sınıflandırma teoremini kullanarak her grubun direkt toplamı olduğu döngüsel grupların ilgili datasını doğal sayı dizileri olarak kodlayabiliriz. Mesela grubunuz Z5⨁Z23⨁Z51 ile eşyapısal ise grubu (5,3,0,1,0,0,) dizisine götürelim vs.
Yazıyı çok uzatmamak için örnekleri şimdilik kesip sorduğunuz sorunun cevabına geçeyim:
Baire uzayı
NN üzerinde
xE0y⇔∃n ∀m≥n xm=ym denklik bağıntısını tanımlayalım. (Normalde
E0 Cantor uzayı üzerinde tanımlanır ama bu bağıntılar birbiriyle karşılıklı indirgenebilirdir.)
Bu denklik bağıntısının Borel olduğunu kanıtlamak zor değil. Ayrıca
ΔR≤BE0 olduğu da kolayca kanıtlanabilir. (Öte yandan
ΔR<BE0 olduğu biraz daha uğraş isteyen bir şey.) Harrington-Kechris-Louveau'nun
hiç de aşikar olmayan bir teoremi şunu söyler:
Her Borel denklik bağıntısı E için ya E≤BΔR olur ya da E0≤BE olur. Yani ≤B-hiyerarşisinde E0 bağıntısı ΔR'nin (ya da herhangi bir standart Borel uzayı X için ΔX'in) ardılı.
Sizin aradığınız şey anladığım kadarıyla E≤BE0 olan denklik bağıntıları. Bunun örnekleri: Torsion eleman barındırmayan 1-dereceli değişmeli grupların (torsion-free abelian group of rank 1) eşyapısallık bağıntısı (ki bu bağıntı E0 ile karşılıklı indirgenebilir), sayılabilir bölünebilir (countable divisible) grupların eşyapısallık bağıntısı (ki bu bağıntı aslında ΔR ile karşılıklı indirgenebilir) vs.
Sizin aradığınız şeye örnek olmayan, yani E0<BE olan denklik bağıntıları: n≥2 için torsion eleman barındırmayan n-dereceli değişmeli grupların eşyapısallık bağıntısı, sonlu üretilebilir grupların eşyapısallık bağıntısı (bu iki sonuç da Simon Thomas'ın önemli sonuçları), sayılabilir grupların, çizgelerin, doğrusal sıralamaların eşyapısallık bağıntıları (bunlar da Friedman ve Stanley'in sonuçları), Cantor uzayının homeomorfizmalarının eşleniklik ilişkisi (Gao ve Camerlo'nun bir sonucu) vs.
Bunlar aşikar teoremler değil. O yüzden bunları kanıtlamak yerine konuya giriş niteliğinde bir referans verip bu uzun cevabı noktalayım: