"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 $\sigma$-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 $(\mathbb{N},E)$ formundadır. Burada $E \subseteq \mathbb{N}^2$ rastgele bir simetrik ve "irreflexive" bağıntı. Bu durumda $\mathcal{P}(\mathbb{N}^2)$ kümesini $2^{\mathbb{N}^2}$ özdeşleştirirsek, sayılabilir çizgelerin standart Borel uzayı olarak $2^{\mathbb{N}^2}$ 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ı $\sim \subseteq 2^{\mathbb{N}^2} \times 2^{\mathbb{N}^2}$ 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 \subseteq X^2$ ve $F \subseteq Y^2$ standart Borel uzayları $X$ ve $Y$ üzerinde analitik iki denklik bağıntısı olsun. (Yani çarpım Borel yapısına göre $X^2$ ve $Y^2$'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 \rightarrow Y$ fonksiyonu varsa ki $x E y \Leftrightarrow f(x) F f(y)$ oluyorsa. Bu durumda da $E \leq_B F$ yazıyoruz. Eğer $E \leq_B F$ ve $F \leq_B E$ ise bu durumda $E \sim_B F$ yazıyoruz ve $E$ ile $F$ karşılıklı Borel indirgenebilir (Borel bireducible) diyoruz. $E \leq_B F$ ve $F \nleq_B E$ ise de $E <_B F$ 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ı $\Delta_{{\mathbb{N}}^{\mathbb{N}}}$ bağıntısına indirgenebilir. (Aslında bu bağıntı $\Delta_{\mathbb{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 $\mathbb{Z}^5 \bigoplus \mathbb{Z}_{2^3} \bigoplus \mathbb{Z}_{5^1}$ 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ı $\mathbb{N}^\mathbb{N}$ üzerinde $x E_0 y \Leftrightarrow \exists n\ \forall m\geq n \ x_m=y_m$ denklik bağıntısını tanımlayalım. (Normalde $E_0$ 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 $\Delta_{\mathbb{R}} \leq_B E_0$ olduğu da kolayca kanıtlanabilir. (Öte yandan $\Delta_{\mathbb{R}} <_B E_0$ 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 \leq_B \Delta_{\mathbb{R}}$ olur ya da $E_0 \leq_B E$ olur. Yani $\leq_B$-hiyerarşisinde $E_0$ bağıntısı $\Delta_{\mathbb{R}}$'nin (ya da herhangi bir standart Borel uzayı $X$ için $\Delta_X$'in) ardılı.
Sizin aradığınız şey anladığım kadarıyla $E \leq_B E_0$ 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ı $E_0$ 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 $\Delta_{\mathbb{R}}$ ile karşılıklı indirgenebilir) vs.
Sizin aradığınız şeye örnek olmayan, yani $E_0 <_B E$ olan denklik bağıntıları: $n \geq 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: