Boole Cebirleri İçin Stone Temsil Teoremi

Posted on 26 Nisan 2021 by esrakorkmaz

24 Kasım 1864. George Boole sağanak yağmur altında, evinden üniversiteye kadar yaklaşık 5 km yürümüş ve ıslak giysileriyle ders anlatmıştır. Bir süre sonra ise üşütüp ateşlenir ve akciğerleri hızla enfekte olur. Ancak görece yeni bir disiplin olan homeopatiye inanan eşi Mary Everest Boole (soyadı, Everest dağına ismini veren amcası Albay George Everest’ten gelmektedir), benzer benzeri iyileştirir ilkesi ile George’u ıslak çarşaflara sarar. Bunun üzerinden 1 ay geçmeden zatürreye yakalanan George, 49 yaşında hayata gözlerini yumar. (Bu hikaye bir söylentiden ibaret değildir. Boole’un, babasını öldürdüğünü düşündüğü için annesini hiç affetmeyen kızlarından birinin ifadesine dayanmaktadır.)

Trajik bir başlangıç oldu ama aslında Boole’un hayatı başarılarla doludur. Hayatına yoksul bir ayakkabıcının oğlu olarak başlamasına rağmen, çoğunlukla kendi kendini eğiterek 34 yaşında İrlanda’da yeni kurulan Cork Üniversitesi’nin ilk matematik profesörü olmuştur. Ayrıca kendisi bugün sembolik mantığın babası ve bilgisayar biliminin en önemli figürlerinden biri olarak bilinmektedir. Boole, düşünme işlerimizi bizim yerimize yapabilecek bir makine hayal etmiş ve bunun için düşüncelerimizi matematiksel olarak temsil edebileceğimiz bir dile gereksinim olduğunu düşünmüş olan Leibniz’in hayallerini kısmen de olsa gerçekleştirmiştir. Bunu nasıl yaptığını Cem Say hocamız 50 Soruda Yapay Zeka kitabında gayet açık anlatmış. Kısaca özetlersek:

Gri Kedi söz öbeğini ele alalım. Griyi g, kediyi k, iki kelime arasındaki işlemi de çarpma sembolü “.” ile gösterelim. O halde “gri kedi”, “g.k” biçiminde gösterilir. Bu işlem aslında günümüzde kesişim olarak bilinen işi yapar, yani “gri olan tüm şeyler” ile “tüm kediler” ailelerinin kesişimini elde etmemizi sağlar. İki ailenin aynı seçilmesi durumunda (örneğin, “kedi kedi” ya da “gri gri”) ise anlam aynı kalır, yani bir x kavramı için “x.x=x” olur. Bilinen çarpma işleminde, bu eşitliği sağlayan sadece 0 ve 1 olduğundan, kavramları cebirsel bir dille yazarken sadece 0 ve 1’den oluşan bir sistem kullanmak uygun olur. (Niceleme mantığı ile, bu sembolleştirme işlemini tamamlayan Gottlob Frege’yi de anmadan etmeyelim.)

Bu yazıda Boole cebiriden topolojik uzaylara giden yolu inceleyeceğiz. Bunun için, cebirsel kavramlardan yola çıkılarak elde edilen Stone uzayından ve meşhur Stone Temsil Teoreminden bahsedeceğiz. O zaman işe temel kavramlarla başlayalım.

Tanım: (1) $(L,\leq)$ bir kısmi sıralı küme olsun. Eğer her $a,b\in L$ için $a\vee b$ (a ile b’nin supremumu) ve $a\wedge b$ (a ile b’nin infimumu) varsa, $L$ ‘ye bir latis denir.
(2) $L$ bir latis olsun. Eğer her $a,b,c\in L$ için $a\vee (b\wedge c)=(a\vee b)\wedge (a\vee c)$ oluyorsa $L$ ‘ye bir dağılımlı latis denir.
(3) $L$ latisinin en büyük elemanı ve en küçük elemanı varsa (yani $0,1\in L$ ise), $L$ ‘ye bir sınırlı latis denir.
(4) $L$ bir sınırlı latis ve $a\in L$ olmak üzere, $b\vee a=1$ ve $b\wedge a=0$ olacak şekilde $b\in L$ elemanına, $a$ ‘nın tümleyeni denir ve $b=a^*$ olarak gösterilir. $L$ ‘de her elemanın bir tümleyeni varsa, $L$ ‘ye tümleyenli latis denir.
(5) Tümleyenli dağılımlı bir latis bir Boole Cebiri olarak adlandırılır.

Tanım: $B_1$ ve $B_1$ birer Boole cebiri ve $f:B_1\rightarrow B_2$ olsun. Eğer $f(a\vee b)=f(a)\vee f(b)$ , $f(a\wedge b)=f(a)\wedge f(b)$ , $f(0)=0$ ve $f(1)=1$ koşulları sağlanıyorsa $f$ ‘ye bir Boole cebiri homomorfizması denir. Bire-bir örten bir Boole cebiri homomorfizması, izomorfizma olarak adlandırılır.

Örnek: $X$ bir topolojik uzay ve $\mathcal{B}(X)$ , $X$ ‘in hem açık hem kapalı olan altkümelerinin ailesi olsun. Bu durumda $A,B\in \mathcal{B}(X)$ için $A\vee B= A\cup B, A\wedge B= A\cap B$ ve $A^*=X\setminus A$ olmak üzere, $\mathcal{B}(X)$ bir Boole cebiridir.
$X$ bağlantılı bir küme olsun. Bu durumda, ${\bf{2}}=\{0,1\}$ iki-elemanlı Boole cebirini göstermek üzere $\mathcal{B}(X)$ , ${\bf{2}}$ ‘ye izomorftur. (Çünkü, X uzayının bağlantılı olması için gerek ve yeter koşul o uzayda $X$ ve $\emptyset$ ‘den başka hem açık hem kapalı küme olmamasıdır.)

Tanım: (1) $L$ sınırlı ve dağılımlı bir latis ve $F\subseteq L$ olsun. Eğer
(S1) her $x,y\in F$ için $x\wedge y\in F$
(S2) $x\in F$ , $z\in L$ için $x\vee z\in F$ koşulları sağlanıyorsa $F$ ‘ye bir süzgeç denir.
(2) $F\subseteq L$ bir süzgeç olsun. Her $x,y\in L$ için $x\vee y\in F$ ise $x\in F$ ya da $y\in F$ oluyorsa $F$ ‘ye bir asal süzgeç denir.
(3) $F\subsetneq L$ bir süzgeç olsun. Eğer $F$ kapsama işlemine göre maksimal ise, $F$ ‘ye bir ultrasüzgeç denir.

Önerme 1: $B$ bir Boole cebiri ve $F\subsetneq B$ bir süzgeç olsun. Bu durumda aşağıdakiler denktir:
(i) $F$ bir ultrasüzgeçtir.
(ii) $F$ bir asal süzgeçtir.
(iii) Her $a\in B$ için $a\in F$ ya da $a^*\in F$ dir.

Şimdi, $B$ bir Boole cebiri ve $\mathcal{S}(B)$ , $B$ ‘nin tüm ultrasüzgeçlerinin ailesi olsun. $U_a=\{F\in \mathcal{S}(B) : a\in F\}$ olmak üzere, $\mathcal{S}(B)$ üzerinde $\mathcal{U}=\{U_a : a\in B\}$ ailesinin taban olduğu topolojiyi tanımlayalım. Yukarıdaki önermeyi kullanarak, bu topolojinin aşağıdaki özellikleri sağladığını kolayca gösterebiliriz.

(1) $U_{a\vee b}=U_a\cup U_b$ ve $U_{a\wedge b}=U_a\cap U_b$ dir.
(2) Her $a\in B$ için $U_a$ kapalıdır, yani $U_a$ kümeleri hem açık hem kapalıdır. Çünkü $U_a= \mathcal{S}(B) \setminus U_{a^*}$ eşitliği sağlanır.
(3) Her $F\in \mathcal{S}(B)$ için $\{F\}$ tek nokta kümeleri kapalıdır. Çünkü $\{F\}=\bigcap_{a\in F} U_a$ biçiminde ifade edilebilir.

Tanım: (1) $X$ bir topolojik uzay olsun. Eğer $X$ ‘in tüm bağlantılı alt kümeleri tek nokta kümeleri ise $X$ ‘e tamamen bağlantısız uzay denir.
(2) Tamamen bağlantısız, kompakt, Hausdorff bir uzaya Stone Uzayı denir.

Aşağıda göstereceğimiz gibi, elimizdeki her Boole cebirine bir topolojik uzay karşılık getirebiliriz. Üstelik elde ettiğimiz bu uzay bir Stone uzayı olur.

Teorem 1: $B$ bir Boole cebiri olmak üzere, $\mathcal{S}(B)$ bir Stone uzayıdır.

İspat: $\mathcal{S}(B)$ tamamen bağlantılıdır: $C\subseteq \mathcal{S}(B)$ en az iki elemanlı bir altküme olmak üzere, $C$ ‘nin bağlantılı olmadığını gösterelim. (Bu sayede, tüm bağlantılı kümelerin tek nokta kümeleri olduğunu söyleyebiliriz.) $F\neq G$ olacak şekilde $F,G\in C$ alalım. Bu durumda, $x\in F\setminus G$ olmak üzere, $\{U_x\cap C, U_{x^*}\cap C\}$ , $C$ ‘nin bir ayrışımıdır ve bu nedenle $C$ bağlantılı değildir.

$\mathcal{S}(B)$ kompakttır: Bunun için, $\mathcal{S}(B)$ ‘nin taban elemanlarından oluşan her açık örtünün sonlu bir alt örtüsü olduğunu göstermek yeterlidir. O halde,

“ $\bigcup_{a\in B^\prime} U_a= \mathcal{S}(B)$ olacak şekilde her $B^\prime\subseteq B$ altkümesi için $\bigcup_{a\in B^{\prime \prime}} U_a= \mathcal{S}(B)$ olacak şekilde sonlu bir $B^{\prime \prime} \subseteq B^\prime$ altkümesi vardır”

ifadesinin ya da $\mathcal{S}(B)\setminus U_a=U_{a^*}$ eşitliğini kullanarak elde edeceğimiz, ve yukarıdaki ifadeye denk olan,

“ $\bigcap_{a\in B^\prime} U_a= \emptyset$ olacak şekilde her $B^\prime\subseteq B$ altkümesi için $\bigcup_{a\in B^{\prime \prime}} U_a= \emptyset$ olacak şekilde sonlu bir $B^{\prime \prime} \subseteq B^\prime$ altkümesi vardır”

ifadesinin doğru olduğunu gösterelim.

Notasyon: $A\subseteq B$ olmak üzere, $A$ ‘yı kapsayan en küçük süzgeci $\langle A \rangle$ ile gösterelim.

Bu durumda $\langle A \rangle=\{(a_1\vee b_1)\wedge (a_2\vee b_2) \wedge \ldots \wedge (a_n\vee b_n) : a_i\in A, b_i\in B, n\in \mathbb{N}\}$ olduğunu görebiliriz. Ayrıca, özel olarak $U_a\cap U_b=U_{a\wedge b}=U_ {\langle \{a,b\} \rangle}$ olur.

Şimdi $\bigcap_{a\in B^\prime} U_a= \emptyset$ olduğunu kabul edelim. Bu durumda $\bigcap_{a\in B^\prime} U_a= U_ {\langle B^\prime \rangle}$ olduğundan $0\in B^\prime$ olmalıdır. O halde $0= (a_1\vee b_1)\wedge (a_2\vee b_2) \wedge \ldots \wedge (a_n\vee b_n)$ olacak şekilde $a_i\in B^\prime, b_i\in B$ vardır. $B^{\prime \prime}=\{a_1, a_2, \ldots , a_n\}$ olsun. Bu durumda (S1) ve (S2) özelliklerinden $0\in \langle B^{\prime \prime} \rangle$ ‘dir ve böylece $\bigcap_{a\in B^{\prime \prime}} U_a= \emptyset$ elde edilir.

$\mathcal{S}(B)$ Hausdorff’tur: $F\neq G$ olacak şekilde $F,G\in \mathcal{S}(B)$ alalım. Bu durumda, bir $x\in F\setminus G$ elemanı vardır. $x\notin G$ ve $G$ bir ultrasüzgeç olduğundan $a^*\in G$ ‘dir. Bu durumda, $F\in U_a$ , $G\in U_{a^*}$ ve $U_a \cap U_ {a^*}=\emptyset$ olduğundan istenilen elde edilmiş olur.

Sonuç 1: $C\in \mathcal{S}(B)$ hem açık hem kapalı bir altküme olsun. Bu durumda $C=U_x$ olacak bir $x\in B$ vardır.

İspat: $C\in\mathcal{S}(B)$ hem açık hem kapalı bir altküme olsun. Öncelikle $C$ açık olduğundan $C=\bigcup_{a\in B^\prime} U_a$ biçiminde yazılabilir. Ayrıca $C$ kapalı ve $\mathcal{S}(B)$ kompakt olduğundan $C$ kompakttır. O halde $C=\bigcup_{i=1}^n U_{a_i}$ olacak şekilde bir $\{a_1,a_2,\ldots, a_n\}\subseteq B^\prime$ kümesi vardır. $\bigcup_{i=1}^n U_{a_i}=U_{a_1\vee a_2\vee \ldots a_n}$ olduğundan istenilen elde edilmiş olur.

Teorem 2: $B_1, B_2$ birer Boole cebiri ve $f:B_1\rightarrow B_2$ bir Boole cebiri homomorfizması olsun. Bu durumda $S(f):\mathcal{S}(B_2) \rightarrow \mathcal{S}(B_1), S(f)(F)=f^{-1}(F)$ dönüşümü süreklidir.

İspat: $U_a\in \mathcal{S}(B_1 )$ olsun.

$\begin{aligned} S(f)^{-1}(U_a) &=\{F\in \mathcal{S}(B_2) : S(f)(U_a)=f^{-1}(F)=U_a\} \\ &= \{F\in \mathcal{S}(B_2) : a\in f^{-1}(F) \} \\&=\{F\in \mathcal{S}(B_2) : f(a)\in F\}\\ &=U_{f(a)}\end{aligned}$

olduğundan $S(f)$ süreklidir.

Yukarıda yaptığımız işlerin tersini yapmak da mümkün. Bir $X$ topolojik uzayı verildiğinde, $X$ ‘in hem açık hem kapalı olan altkümelerinin ailesi olan $\mathcal{B}(X)$ ‘in bir Boole cebiri olduğundan bahsetmiştik. Bunun yanı sıra, $X,Y$ topolojik uzayları ve $f: X\rightarrow Y$ sürekli dönüşümü verildiğinde, $\mathcal{B}(f): \mathcal{B}(Y) \rightarrow \mathcal{B}(X)$ , $\mathcal{B}(f)(U)=f^{-1}(U)$ Boole cebiri homomorfizmasını elde ederiz.

Son olarak, Boole cebirleri ile topolojik uzaylar arasında bir köprü kuran Stone Temsil Teoremine bakalım:

Teorem 3: $B$ bir Boole cebiri olsun. Bu durumda $B$ ile $\mathcal{B}( \mathcal{S}(B))$ birbirine izomorftur.

İspat: $F: B\rightarrow \mathcal{B}( \mathcal{S}(B)), F(x)=U_x$ biçiminde tanımlanan dönüşüm bir Boole cebiri izomorfizmasıdır. $F$ ‘in homomorfizma olduğu kolayca gösterilebilir. Bire-bir ve örten olduğu ise Sonuç 1’den açıktır.

Bilindiği gibi, topolojinin ortaya çıkış hikayesi daha çok geometriye dayanır. Cebirde topolojik fikirlerin kullanılması fikrini çoğu matematikçi hoş karşılamamıştır. Mesela Birkhoff’un bu konuda fikri sorulduğunda “Bu yaklaşımı dikkate almıyorum, fakat bu durum, cebircilerin bunu yapamayacağı anlamına gelmez.” diye cevap verdiği rivayet edilir. İşte Stone Temsil Teoremi bu yaklaşımı mümkün kılar ve cebirsel bir yapıdan da ilginç topolojik uzaylar elde edilebileceğini gösterir. Bu sayede geometrik problemlere de latis teorisi yardımıyla çözümler bulmak mümkün olabilir. Son olarak şunu da eklemek gerekir ki, cebirsel kavramları topolojik uzaylara uygulama fikri Stone ile sınırlı değildir. Örneğin Henry Wallman, J. C. C. McKinsey ve A. Tarski gibi matematikçiler de latis teorik ve topolojik kavramlar arasında ilişkiler kurmuşlardır.

Matematik öylesine sırlarla ve mucizelerle doludur ki, çoğu zaman birbiri ile alakasız görünen konular arasında bir solucan deliği bulmak mümkün olur.

Son Söz ve Mutlu Son: Mary&George Boole çiftinin beş kızı vardı. Mary Ellen bir matematikçi ile evlendi. Alicia Boole Stott bir matematikçi, Lucy Everest ise ilk kadın kimyacılarından oldu. Margaret’ın oğlu alanında önde gelen bir fizikçi ve matematikçi olurken, Ethel Lilian ünlü bir yazar olup, James Bond’a ilham veren casusla ilişki yaşadı. Ayrıca Boole torunları tırmanma merdivenini (jungle jim) icat edecek, verem tedavisine öncülük edecek, taşınabilir bir röntgen icat edecek, Jüpiter’in Büyük Kırmızı Lekesini modelleyecek, Manhattan projesinde çalışacak ve Meksika’daki birkaç düzine böcek türünü keşfedeceklerdi.

Boole ailesi: Mary Boole, beş kızı ve torunları Julian ve Geoffrey Taylor, Mary Leonard Stott ve George Hinton,

Kaynaklar

(1) https://thonyc.wordpress.com/2012/12/08/killed-by-homeopathy/
(2) https://mathsci.kaist.ac.kr/~htjung/Boolean.pdf
(3) https://sydney4.medium.com/the-extraordinary-life-and-beliefs-of-mary-everest-boole-39eae49f54c9
(4) Peter T. Johnstone, Stone Spaces. Cambridge University Press (1982).
(5) Jorge Picado, Aleš Pultr, Frames and locales: Topology without points. Frontiers in Mathematics, vol. 28, Springer, Basel (2012).
(6) Cem Say, 50 Soruda Yapay Zeka, Bilim ve Gelecek Kitaplığı (2018).

Ev Yapımı İspat: Buffon’un İğneleri ile Pi Sayısı Hesabı

Posted on 18 Nisan 2021 by esrakorkmaz

Cevapla

Mısır’dan Mezopotamya’ya, Çin’den Antik Yunan’a bilimle uğraşan birçok kişinin gözdesi olan $\pi$ sayısını hesaplamak, yani aslında yaklaşık bir değer bulmak için kullanılabilecek yöntemlerden biri de Georges-Louis Leclerc, Comte de Buffon’un iğne problemidir.

L uzunluğunda bir iğnenin, eşit aralıklı paralel çizgilerle kaplı bir kağıt parçasına düştüğünü varsayalım. İğnenin bu çizgilerden birini kesme olasılığı nedir?

Oldukça alakasız görünüyor ama biraz olasılık biraz da integral bilgisi kullanarak, bu problemden $\pi$ ‘nin yaklaşık değerini hesaplamamızı sağlayan bir formül elde edebiliyoruz.

Diyelim ki, elimize L uzunluğunda bir iğne aldık ve paralel doğrular arasındaki uzaklığı da K olarak belirledik. Şimdi kağıdımızı düz bir zemine yerleştirip üzerine iğneyi atalım. İğnenin alt ucu ile üst çizgi arasındaki uzaklığa x diyelim. Daha sonra, iğnenin alt ucundan geçen ve çizgilere paralel olan bir doğru çizelim ve bu doğru ile iğne arasındaki dar açıyı $\theta$ ile gösterelim. (Burada, K ve L sabit iken x ve $\theta$ ‘nın değişken olduğuna dikkat edelim.) Yukarıdaki şekilden görebileceğimiz gibi $L \sin(\theta)> x$ ise iğne çizgilerden birini keser, yani başarılı bir atış yapmış oluruz.

Ayrıca burada $0\leq \theta \leq \frac{\pi}{2}$ ve $0\leq x\leq K$ olduğundan, aşağıdaki dikdörtgen örneklem uzayımızı verir.

K ve L’yi karşılaştırdığımızda iki durum elde ederiz. $K>L$ ya da $K\leq L$ . İlk durumu varsayıp hesaplamaları yaptığımızda $\pi$ ‘nin yaklaşık değerine ulaşabiliyoruz, bu nedenle ikinci durumu incelememize gerek kalmıyor. (Çünkü burada asıl amacımız iğnenin çizgileri kesme olasılığını hesaplamak değil, sadece $\pi$ sayısına bir yaklaşım yapmak.) O halde $K> L$ olduğunu kabul edelim.

Şimdi burada iğne probleminin çözümüne bir es verip biraz olasılık bilgisi ile davam edelim ve klasik olasılık ile ampirik olasılığın ne olduğunu anlamaya çalışalım.

Klasik (veya teorik) olasılık, bir örneklem uzayındaki her bir sonucun eşit olasılıkla ortaya çıkması durumlarında kullanılır. E olayı için klasik olasılık,

formülü ile hesaplanır. Diğer taraftan ampirik (veya istatistiksel) olasılık, olasılık deneylerinden elde edilen gözlemlere dayanır ve

formülü ile hesaplanır. Yazı-tura örneği üzerinden olaya açıklık getirmeye çalışalım. Bir parayı 20 kez attığımızı ve bunlardan 3 tanesinde tura geldiğini varsayalım. Bu durumda tura gelmesinin teorik olasılığı $\frac{1}{2}$ iken, ampirik olasılığı $\frac{3}{20}$ ‘dir. Ayrıca Büyük Sayılar Kanununa göre, deney ne kadar çok tekrar edilirse ampirik olasılık teorik olasılığına o kadar yaklaşır. Yani yine bozuk para örneğini ele alırsak, parayı daha çok atarsak, teorik olasılık değeri olan $\frac{1}{2}$ ‘ye o kadar yaklaşırız.

O zaman sorumuza dönelim ve önce iğnenin paralel çizgilerden birini kesmesi olayının teorik ve ampirik olasılıklarını bulmaya çalışalım. Bunun için $f(\theta)= L \sin(\theta)$ fonksiyonunu tanımlayalım.

$f(\theta)= L \sin(\theta)> x$ olduğunda iğnenin çizgiyi kestiğinden bahsetmiştik. Bu durum, yukarıdaki grafikte taralı kısma denk gelir. O halde iğnenin çizgiyi kesmesi olayının teorik olasılığı, P=taralı bölgenin alanı / tüm dikdörtgenin alanı olur.

Ön izleme(yeni sekmede açılır)

Taralı bölgenin alanı $P=\int_0^ \frac{\pi}{2} L \sin(\theta) \,d\theta=L$ , tüm dikdörtgenin alanı ise $\frac{K \pi}{2}$ olduğundan $P=\frac{2L}{K \pi}$ olarak bulunur.

Diğer taraftan, eğer $\widehat{P}$ , iğnenin çizgiyi kesmesi olayının ampirik olasılığı ise $\widehat{P}\approx \frac{2L}{K \pi}$ yani $\pi \approx \frac{2L}{K \widehat{P}}$ olur.

Formülümüzü elde ettiğimize göre artık deneye başlayabiliriz. L=4 cm, K=6 cm olsun. İğneyi 100 kez atalım ve başarılı atış sayımız da 41 olsun. Bu durumda,

$\pi \approx \frac{2\times 4}{6\times \frac{41}{100}}= 3.25203$ elde edilir.

Burada daha fazla atış yapmış olsaydık Büyük Sayılar Kanununa göre $\pi$ sayısına daha yakın bir değer elde etmiş olurduk. Biraz boş vaktiniz varsa denemek eğlenceli olabilir ama eğer yoksa buraya buyurun.

Kaynaklar

(1) Lee L. Schroeder, Buffon’s needle problem: An exciting application of many mathematical concepts, The Mathematics Teacher, Vol. 67(2), (1974),183–186.
(2) https://acikders.ankara.edu.tr/pluginfile.php/102233/mod_resource/content/0/%C4%B0statistik%20Ders%20Notu%204.pdf

Nicelik mi, Nitelik mi?

Posted on 16 Nisan 2021 by esrakorkmaz

Cevapla

Bir makale yazarken gerçekten üstün çaba sarf ediyoruz. Yani sadece araştırma kısmından değil, onu belli bir formata uygun, güzel bir dille yazılmış kurallar bütünü haline getirmekten bahsediyorum. Özeti, giriş kısmı, kaynakları, atıfları derken “konu neydi ya” diyecek aşamaya geldiğimiz zamanlar bile olabiliyor. Peki söyleyeceğimiz şeyin herkes tarafından anlaşılacağına eminsek neden şunu yapmıyoruz:

Yani bir özet düşünün ki, yazar başına 3 kelime bile düşmüyor. 🙂 Kısa ve öz yazılmış bu özeti, makalenin ismi ile birlikte okuduğunuzda en azından mevzuu anlamış oluyorsunuz. Bir de şunlar var:

Şimdi de en favori özetim geliyor:

Peki acaba en kısa makale kaç kelimeden oluşuyordur? Bir matematikçi olarak her ihtimali göz önünde bulundurmalıyız, bu yüzden iyice düşünelim.

Cevap: 0. Yani, yazar diyor ki,

“Bu boş sayfa, söylemek istediğim şeyi en iyi biçimde anlatıyor: Söyleyecek hiçbir şeyim yok!” (Sivrisinek Şehirde, Erlom Ahvlediani)

Bu makalenin bir şekilde yayımlanmış olduğunu düşününce Upper’ın Yazar Tıkanmasına Başarısız Müdehalesi pek de başarısızlıkla sonuçlanmış gibi görünmüyor. Makalenin altına iliştirilmiş hakem yorumu da okunmaya değer:

Bu makaleyi limon suyu ve röntgenlerle çok dikkatli inceledim ve ne tasarımda ne de yazı stilinde tek bir kusur tespit etmedim. Revizyon yapılmadan yayınlanmasını öneririm. Açıkçası bu şimdiye kadar gördüğüm en az ama öz yazılmış makale- fakat yine de, diğer araştırmacıların Dr. Upper’ın başarısızlığını tekrar etmesine izin verecek kadar ayrıntı içeriyor. Sizden aldığım, karmaşık ayrıntılar içeren diğer tüm makalelerle karşılaştırıldığında, bunu incelemek bir zevkti.

Şimdi de en kısa matematik makalelerine bir bakalım.

1769 yılında, Leonhard Euler tarafından ortaya konulan ve Fermat teoreminin genel hali olan Euler varsayımı, $n< k$ ise $b^k\neq {a_1}^k+ {a_2}^k+\ldots {a_n}^k$ olduğunu ifade ediyor. 1966 yılında, Lander ve Parkin CDC 6600 üzerinde yaptıkları araştırma ile $k=5$ için bir ters örnek buluyorlar.

Bir diğeri ise, John Conway ve Alexander Soifer’in 2005’de yayımlanan makaleleri:

Soru şu: Kenar uzunluğu $n+\epsilon$ olan bir eşkenar üçgeni, birim eşkenar üçgenlerle kaplamak istiyorsak, en az kaç adet üçgen kullanmamız gerekir? Yazarların cevabı: $n^2+2$ birim üçgen ile bu işi yapabiliriz.

Makalenin gönderildiği American Mathematical Monthly, yazarlara “(…) Makaleniz iyi bir Monthly makalesi olamayacak kadar kısa. Bir veya iki satır açıklama gerçekten yardımcı olur.” cevabını vermiştir. Fakat yazarlar yılmamış ve dergiye “Genel olarak kısa bir makalenin – ve özellikle de bu makalenin – sadece boyutu nedeniyle ‘iyi bir Monthly makalesi olmak için biraz fazla kısa’ olması gerektiğine saygıyla katılmıyorum. Nicelik ve nitelik arasında bir bağlantı var mı? Güzel bir açık bir soru ortaya koyduk ve bunu iki farklı yolla ispatladık. Açıklayacak başka ne var?” yazmışlardır. Hikayenin tümünü okumak isteyenler için, Soifer’in yazmış olduğu yazıyı buraya bırakıyorum. Sürecin yazarların başarısıyla sonuçlandığını zaten biliyoruz.

Kısa ve öz olmak konulu yazımı John Nash’in 26 sayfa ve 2 adet referanstan oluşan doktora tezini ekleyerek sonlandırıyorum. İlham perimizin açık sorularımıza sade ve anlaşılır cevaplar bulmamıza yardım etmesi dileğiyle… 🙂

Kaynaklar

(1) https://www.openculture.com/2018/01/the-shortest-academic-article-ever-written.html
(2) https://paperpile.com/blog/shortest-papers/
(3) http://www.wfnmc.org/mc20101.pdf

#asalsayılarsonsuzdur #topolojiheryerde

Posted on 15 Nisan 2021 by esrakorkmaz

Cevapla

Asal sayıların sonsuz olduğunu gösterirken, genelde aklımıza gelen şu ispat oluyor:

Tersine, asal sayıların sonlu olduğunu kabul edelim ve tüm asal sayıların kümesini $P=\{p_1, p_2, \ldots, p_r\}$ ile gösterelim. $p=p_1 p_2\ldots p_r+1$ olsun. Varsayıma göre $p$ asal olamaz, o halde $p$ ‘nin bir q asal böleni vardır. Ayrıca $q\notin P$ ‘dir, çünkü aksi halde q’nun $p-( p_1 p_2\ldots p_r)=1$ ‘i bölmesi gerekir, ki bu bir çelişkidir. O halde asal sayılar sonsuz olmalıdır.

Çoğu yerde yazanın aksine, bu ispat aslında Öklid’in orijinal ifadesinden farklıdır. Çünkü M.Ö. 330-275 yılları arasında yaşamış olan Öklid’in, şuan gayet doğal kavramlar olarak görülen tamsayıları, bölünebilmeyi ve sonsuzu bizler gibi anlayıp ifade etmesini bekleyemeyiz.

Günümüzdeki yaklaşımdan farklı olarak, Antik Yunan’da tam sayıları soyut nesneler olarak değil, birimlerin sayısı olarak algılamışlar ve doğru parçalarının uzunlukları ile temsil etmişlerdir. Öklid, orijinal ispatta bölünebilme yerine “ölçme” ifadesini kullanmış ve bunu “a uzunluğundaki doğru parçalarının belli sayıdaki toplamı b’ye eşitse, a uzunluğu b’yi ölçer” şeklinde açıklamıştır. Önermenin orijinal ifadesi ve ispatı şöyledir:

Asal sayıların miktarı, belirlenmiş herhangi sayıda asal sayıdan daha fazladır.

İspat: A,B ve C asal sayılar olsun. A,B ve C’den daha fazla asal sayı olduğunu iddia ediyorum. A, B ve C ile ölçülen en küçük sayı olan DE’yi ele alalım. Daha sonra DE’ye DF birimini (yani, bir birim uzunluktaki doğru parçasını) ekleyelim.

EF ya asaldır ya da değildir. İlk olarak asal olduğunu kabul edelim. Bu durumda, A, B, ve C’den daha fazla asal sayı bulmuş olduk. Şimdi de EF’nin asal olmadığını kabul edelim. Bu durumda EF, bazı asal sayılarla ölçülecektir. Diyelim ki EF, G asal sayısı ile ölçülsün. G’nin A, B ve C sayılarından farklı olduğunu iddia ediyorum. Diyelim ki G, bunlardan biriyle aynı olsun. Bu durumda G, DE’yi ölçer. Fakat aynı zamanda EF’yi de ölçtüğünden, DF’yi de ölçmelidir, ki bu saçma bir şeydir. Bu nedenle G; A, B ve C sayılarından herhangi biriyle aynı değildir ve hipoteze göre asaldır. Bu durumda yine, A, B ve C’den daha fazla asal sayı bulmuş olduk.

Bu önermenin birkaç farklı ispatı daha mevcut, fakat burada anlatacağım, Hillel Furstenberg’in 1955 yılında topolojik uzayları kullanarak yapmış olduğu ilginç ve bir o kadar da güzel ispat.

Bunun için öncelikle $\mathbb{Z}$ üzerinde bir topolojik uzay tanımlayacağız. $a,b\in \mathbb{Z}$ ve $b>0$ olmak üzere, $N_{a,b}=\{a+nb : n\in \mathbb{Z}\}$ kümesini tanımlayalım. Şimdi bu kümeyi biraz daha yakından tanıyalım. Bunun için bir $a$ tamsayısı alalım ve bu $a$ sayısından başlayarak, pozitif ve negatif yönde sürekli $b$ birim ilerleyelim. Böylece $N_{a,b}=\{a, b, -b, 2b, -2b, 3b, -3b,\ldots\}$ olacaktır. Ayrıca kümenin tanımından, her $x\in N_{a,b}$ için $N_{x,b}=N_{a,b}$ olduğu da söylenebilir. Şimdi,

$\tau =\{\emptyset\}\cup \{O\subseteq \mathbb{Z} : \forall a\in O, \exists b>0 ; N_{a,b}\subseteq O\}$

olmak üzere, $(\mathbb{Z}, \tau)$ ‘nun bir topolojik uzay olduğunu gösterelim:

$\emptyset, \mathbb{Z} \in \tau$ ve ayrıca açık kümelerin keyfi birleşiminin açık olduğu tanımdan kolayca görülüyor. O halde, $O_1,O_2 \in \tau$ alalım ve keşisimlerinin açık olduğunu görelim. Bu kümelerden en az biri boş küme ise, kesişimleri boş küme olacağı için açıktır. $O_1\neq \emptyset$ , $O_2\neq \emptyset$ olduğunu kabul edelim ve $x\in O_1\cap O_2$ alalım. Bu durumda, $x\in N_{a_1,b_1}\subseteq O_1$ ve $x\in N_{a_2,b_2}\subseteq O_2$ olacak şekilde $a_1,b_1,a_2,b_2 \in \mathbb{Z}$ vardır. Ayrıca yukarıda da belirttiğimiz gibi, $N_{x,b_1}= N_{a_1,b_1}$ ve $N_{x,b_2}= N_{a_2,b_2}$ olduğundan, $x\in N_{x,b_1 b_2}\subseteq N_{x,b_1}\cap N_{x,b_2}\subseteq O_1\cap O_2$ ve böylece $O_1\cap O_2\in \tau$ ‘dir.

Bu uzayda;
(i) Boştan farklı her açık küme sonsuz bir kümedir.
(ii) Her $N_{a,b}$ kümesi kapalıdır.

Birinci iddia tanımdan gayet açık. İkincisi için ise $N_{a,b}=\bigcup_{k=1}^{b-1} N_{a+k,b}$ eşitliği sağlandığından, $N_{a,b}$ kapalı bir kümedir diyebiliriz. (Çünkü $N_{a,b}$ , açık bir kümenin tümleyenidir.)

Şimdi bu topolojiyi kullanarak asal sayıların sonsuzluğunu gösterelim.

$\mathbb{P}$ asal sayıların kümesi olmak üzere, $\mathbb{Z}\setminus\{-1,1\}=\bigcup_{p\in \mathbb{P}} N_{0,p}$ eşitliği sağlanır. Çünkü her $x\in \mathbb{Z} \setminus \{-1,1\}$ sayısının bir $p$ asal böleni olduğundan $x\in N_{0,p}$ olur.

Eğer $\mathbb{P}$ sonlu olsaydı, (ii) özelliğinden, $\bigcup_{p\in \mathbb{P}} N_{0,p}$ kapalı kümelerin sonlu birleşimi olarak kapalı bir küme olurdu. Bu durumda $\{-1,1\}$ kümesi açık bir küme olur, ki bu durum (i) özelliği ile çelişir. Demek ki, $\mathbb{P}$ sonsuz olmalıdır.

Kaynaklar
(1) Aigner, Martin; Ziegler, Günter M. (1998). “Proofs from The Book”. Berlin, New York: Springer-Verlag.

Brouwer Hocamızla Sezgiselliğe Doğru…

Posted on 12 Nisan 2021 by esrakorkmaz

Cevapla

“ $a^b$ rasyonel olacak şekilde a ve b irrasyonel sayıları vardır.” İspatı oldukça kolay görünüyor. $\sqrt{2}^{\sqrt{2}}$ sayısını düşünelim. Elimizde iki ihtimal var:

(1) $\sqrt{2}^{\sqrt{2}}$ rasyoneldir. Bu durumda $a=b=\sqrt{2}$ olarak seçebiliriz.
(2) $\sqrt{2}^{\sqrt{2}}$ irrasyoneldir. Bu durumda ise, $a=\sqrt{2}^{\sqrt{2}}$ , $b=\sqrt{2}$ seçeriz ve böylece $a^b= \big(\sqrt{2}^{\sqrt{2}}\big)^ {\sqrt{2}}= (\sqrt{2})^2=2$ rasyonel olur.

Aynı problemi şu şekilde de çözebiliriz: $a=\sqrt{2}, b=log_{2} 9$ olmak üzere, $a^b= (\sqrt{2})^{log_{2} 9}= (\sqrt{2})^{log_{2} {3^2}}=(\sqrt{2})^{2log_{2} 3}=2^{log_{2} 3}=3$ bir rasyonel sayıdır. (Burada, b bir irrayonel sayıdır. Tersine, b bir rasyonel sayı olsaydı, $b= log_{2} 9=\frac{p}{q}$ olacak şekilde p ve q tamsayıları olurdu. Buradan, $2^ \frac{p}{q} =9$ ve böylece $2^p=9^q$ olur. Fakat bu bir çelişkidir, çünkü $2^p$ bir çift sayı iken, $9^q$ bir tek sayıdır.)

Yukarıdaki ilk ispat yapıcı olmayan ispat (non-constructive proof) tekniğine bir örnektir. Burada ispatı yaparken elimizde iki ihtimal olduğunu söyleyip, hangisinin doğru olduğu hakkında bir bilgi sunmadan sonuca ulaştık. Bu ispat tekniği karşımıza oldukça sık çıkmıştır. Matematik bölümlerinde, daha ayağımızın tozuyla öğrendiğimiz Ara Değer, Rolle, Ortalama Değer ve Monoton Yakınsaklık Teoremleri bunun en güzel örnekleridir. Örneğin bir polinomun $\mathbb{R}$ ‘de bir kökü olduğunu gösterirken, belli koşulları kontrol edip, Ara Değer Teoreminden bu koşullar altında bir kök bulmanın mümkün olduğu sonucuna ulaşırız fakat bu kökün ne olduğu açıkça ifade etmeyiz.

İkincisi ispat ise yapıcı ispat (constructive proof) tekniğine bir örnektir. Bunun diğerinden farkı, kabaca, çözümü inşa etmemizdir. Yapıcı ispat, var olduğunu iddia ettiğimiz nesneyi nasıl bulacağımızı bize tarif eder.

Yapıcı olmayan ispatlar seçme prensibinden ve daha da önemlisi ara değeri dışlama (Law of excluded middle-kısaca LEM) kanunundan kaynaklanır. Klasik mantığın temel kurallarından biri olan LEM, bir önermenin ya kendisinin ya da değilinin doğru olduğunu (yani üçüncü bir ihtimalin olmadığını) ifade eder.

Şimdi buradan, Bertrand Russell’ın 1901 yılında keşfettiği meşhur Russell paradoksuna bir geçiş yapıyoruz. $R=\{A: A\notin A\}$ , “kendisini içermeyen kümelerin” kümesi olsun. Bu noktada biraz daha açıklama gerekiyor sanırım. Örneğin, 3’ten fazla elemanı olan kümelerin kümesi, (kendisi de 3’ten fazla elemana sahip olacağı için) kendisini içerir. Fakat doğal sayılar kümesi, (kendisi bir doğal sayı olmadığından) kendisini içermez. Aynı şekilde, tüm karelerin kümesi de kendisini içermeyen bir kümedir. Burada paradoksa neden olan soru şudur: Acaba $R$ kümesi kendini içerir mi, yoksa içermez mi? Elimizde iki olasılık var:

(1) $R$ kendini içerir, yani $R\in R$ ‘dir. Bu durumda kümenin tanımı gereği $R\notin R$ olmalıdır, ki bu bir çelişkidir.
(2) $R$ kendini içermez, yani $R\notin R$ ‘dir. Yine tanım gereği, $R\in R$ çelişkisini elde ederiz.

(Matematik sevmeyenler için, bu paradoksun diğer bir versiyonu şöyledir: Diyelim ki, bir berber, yalnızca kendini tıraş etmeyenleri tıraş ediyor, kendini tıraş edenleri tıraş etmiyor. Peki bu berber kendini tıraş eder mi? Soruyu cevaplarken, aynı yukarıda olduğu gibi, önce kendini tıraş eder, daha sonra da etmez deyip, her iki durumda da çelişkiye varıyoruz.)

“Eğer öyle olsaydı, öyle olabilirdi; ola ki öyle olsaydı, öyle olacaktı; ama öyle olmadığından öyle değil. İşte işin mantığı bu. –*Alice Harikalar Diyarında*

Burada aslında, “ $R$ kümesi kendisini içerir” önermesini ele alıp, “bu önerme ya doğrudur ya da değili doğrudur” yaklaşımıyla ispata başlayıp, sonrasında işin içinden çıkamıyoruz. Belli ki bu önerme, bu yasayı ihlal ediyor. Demek ki LEM aslında vazgeçilemez bir kanun değildir, yani bu yasanın (ya da genel olarak klasik mantık yasalarının) geçerli olmadığı mantık türleri tanımlamak da mümkündür. Bu örnek için, bu kuralı kaldırmak paradoksun ortadan kalkmasına yetmiyor maalesef. Çünkü bu kez de, birbirini olumsuzlayan iki önermenin aynı anda doğru olamayacağını söyleyen çelişki yasası (law of non-contradiction) yolumuza taş koyuyor. Russell bu paradoksu ortadan kaldırmak için, Principia Mathematica‘da tipler kuramını (theory of types) ortaya atmıştır. Burada birkaç kelime ile özetlendiği gibi;

“Tipler kuramı kümeleri derecelendirir. Örneğin, dördüncü dereceden bir kümeyi tanımlamak için ancak birinci, ikinci ve üçüncü dereceden kümeler kullanılabilir. Böylece “tüm kümeler kümesi” diye bir küme matematikte yasaklanmış olur ve Russell’ın paradoksu paradoks olmaktan çıkar. Yani Russell akla gelen her nesnenin küme olmasını yasaklayarak, matematiği değiştirmiş, (şimdilik) çelişkisiz bir matematik yaratmıştır. Ünlü Fransız matematikçisi Poincaré’nin de dediği gibi, kurtlardan korumak için sürünün çevresine bir çit çekilmiştir.”

Konudan konuya atlama uzmanı olarak, Cem Say’ın (şiddetle tavsiye ettiğim) 50 Soruda Yapay Zeka isimli kitabında Principia Mathematica ile ilgili yazdıklarını da eklemeden edemeyeceğim.

Bertrand Russell, matematiğin mantık temeline oturtulması bayrağını Frege’den devraldıktan sonra bu konuda insanüstü bir çaba gösterdi. Russell’ın meslektaşı Alfred North Whitehead’le birlikte bu amaçla yazmaya giriştiği Principia Mathematica, tarihin en zor kitaplarından biridir. Her kavramı, en ama en temel parçacıklarına ayırıp, hiçbir kuşkuya, Frege’nin düş kırıklığına yol açandaki gibi hiçbir paradoksa meydan vermeyecek şekilde yazma çabası, Whitehead’le Russell’ın yıllarına, neredeyse akıl sağlıklarına ve Russell’ın evliliklerinden birine mal oldu. Çok çetrefilli bir notasyonla yazılan kitabın 1912’de basılan ikinci cildinin 86. sayfasında nihayet 1+1’in 2’ye eşit olduğunun kanıtı tamamlanıyor ve hemen ardından “Yukarıdaki önerme bazen yararlı olur” cümlesi yer alıyordu! Üçüncü ciltten sonra halleri kalmayan ikili, geometrinin temellerini işlemesini öngördükleri dördüncü cildi yazmaktan vazgeçtiler. (Eski bir mantıkçı bilmecesi: “Principia Mathematica’yı kaç kişi okumuştur? Cevap: İki. Russell’ın yazdığı yerleri Russell, Whitehead’inkileri de Whitehead”)

Şimdi asıl meseleye dönüp, yukarıda bahsettiğimiz ara değeri dışlama kanununa ek olarak çifte olumsuzlama elemesi ( $\sim\sim p \equiv p$ ) de çıkarılarak elde edilen sezgisel mantık (Intuitionistic Logic), ya da diğer adıyla Yapıcı Mantığa (Constructive Logic) bir bakalım.

Sezgiselciler, matematiksel bir nesnenin var kabul edilebilmesi için bu nesnenin nasıl inşa edildiğine dair bir kural ya da işlemin ortaya konması gerektiğini savunurlar. Bu görüşü ortaya atan Luitzen Egbertus Jan Brouwer, formalize eden ise Arend Heyting olmuştur. Tabi her yenilikte olduğu gibi bunun da kabul görmesi öyle kolay olmamıştır. Bunu, Brouwer ile David Hilbert arasındaki tartışmada Hilbert’in

“Matematikçiden ara değeri dışlama kanununu almak, astronoma teleskopu ya da boksöre yumruklarını kullanmayı yasaklamakla aynıdır. Varlık ifadelerini ve ara değeri dışlama kanununu yasaklamak, matematik bilimden vazgeçmekle aynı şeydir”

sözlerinden anlamak mümkün. Sezgisel mantık ile, oldukça işe yarayan iki aracı kaybetmiş oluruz; fakat uygulanabilirliğinin fazla olması onu değerli kılar. Elde ettiğimiz yapıcı ispatları birer algoritma olarak kullanmamız mümkündür ve böylece bunları doğrulamak ve belki de daha kapsamlı çözümler üretmek için “kanıt asistanları” kullanma şansımız olur. Mizar, Isabelle, Coq gibi kanıt asistanları sayesinde bizler için oldukça karmaşık olan ya da belki de mümkün görünmeyen durumları yazılım temelli ispatlar ile elde edebiliriz. Örneğin buradan Mizar kullanılarak yazılmış birçok makaleye ulaşabilirsiniz. Bir yazılım yardımıyla ispatlanan en önemli problemlerden biri, Dört Renk Problemidir:

Bir harita, komşu ülkelerin farklı renklerde olması koşuluyla, dört renk kullanılarak boyanabilir.

1852 yılında ortaya atılan ve uzun yıllar ispatlanamayan problem, en sonunda, 1976 yılında bilgisayarların yardımıyla çözüme kavuşmuştur. (Günümüzde bilgisayarlara olan güvenimiz sonsuz, ama o zamanlar bu ispat büyük kuşku ile karşılanmış olmalı.)

Sezgisel mantığı anlatırken, Arend Heyting’in tanımladığı Heyting cebirlerinden bahsetmemek olmaz. Nasıl Boole cebirleri klasik mantığın cebirsel modelleri ise, Heyting cebirleri de sezgisel mantığın modelleridir.

$L$ sınırlı bir latis olmak üzere, eğer her $a,b,c\in L$ için

$c\leq a\rightarrow b \Leftrightarrow c\wedge a\leq b$

koşulunu sağlayan bir $\rightarrow : L\times L \rightarrow L$ ikili işlemi varsa, $L$ ‘ye bir Heyting Cebiri (ya da Brouwer Latis ya da Frame) denir.

Son olarak, Heyting Cebirleri ile topoloji arasındaki ilişkiye bir bakalım:

$X$ bir topolojik uzay olsun (En sevdiğim başlangıç cümlesi 🙂 ). $U,V, U_\alpha (\alpha \in \Delta)$ açık kümeler olmak üzere, supremum, infimum, Heyting operatörü ve tümleyen işlemini, sırasıyla, aşağıdaki gibi tanımlayalım:

$\bigvee_{ \alpha \in \Lambda} U_\alpha = \bigcup_{ \alpha \in \Lambda} U_\alpha$ , $\bigwedge_{ \alpha \in \Lambda} U_\alpha = \big (\bigcap_{ \alpha \in \Lambda} U_\alpha \big)^\circ$ ,
$U\rightarrow V= (U^c\cup V)^\circ$ , $U^c= U \rightarrow 0=(U^c)^\circ$ .
(Burada $^\circ$ iç operatörünü, $^c$ ise tümleyeni gösterir.)

Bu durumda $X$ ‘in tüm açık kümelerinin ailesi bir Heyting cebiridir. İşte bize açılan bu pencereden nokta-bağımsız topoloji olarak da bilinen Frame ve Lokal Teorisine bir geçiş yaparız. Frame’ler topolojik uzaylar teorisine cebirsel bir bakış açısı sunar. Topolojik uzaylar teorisinde bilinen (Stone-Čech kompaktlaştırma gibi) bazı yapılar için yapıcı ispatlar elde edilmesine olanak sağlar. Ayrıca, kompakt uzayların çarpımının kompakt olması gibi, seçme aksiyomuna bağlı ispatların yapıcı versiyonlarına sahip olmamızı sağlar. Konu hakkında daha fazla bilgi sahibi olmak isteyenler için, bu teori üzerine yazılmış en kapsamlı kaynağı buraya bırakıyorum.

Bu yazıda sadece sezgisel mantıktan kısaca bahsetmiş olduk. Tabii mantık türleri bununla sınırlı değil ve hepsinden biraz bahsetmek bile sayfalar sürer. Daha sonraki yazılar ve daha derin konularda görüşmek üzere.

Kaynaklar
1)https://web.stanford.edu/~bobonich/glances%20ahead/IV.excluded.middle.html
2) https://en.wikipedia.org/wiki/Heyting_algebra
3) https://plato.stanford.edu/entries/logic-intuitionistic/
4) https://plato.stanford.edu/entries/russell-paradox/

Hausdorff Metriğinden Fraktal Görüntü Sıkıştırma Teknolojisine

Posted on 5 Nisan 2021 by esrakorkmaz

Cevapla

Nesneler arasındaki uzaklıktan anladığımız şey genelde onlar arasındaki en kısa mesafedir. Örneğin bir doğrunun bir düzleme ya da iki düzlemin birbirine olan uzaklığını bulurken, bu iki kümenin noktaları arasındaki minimum uzaklığı elde etmeye çalışırız. Peki bu, iki nesnenin birbirine yakın olduğunu söylemek için yeterince iyi bir yöntem midir? Yani, bu nesneler birbirlerine oldukça yakın birer noktaya sahip olmalarına rağmen, diğer noktalar için bu durum geçerli olmayabilir mi?

Örneğin yukarıdaki şekilde, iki üçgen arasındaki uzaklık değeri küçük olabilir, fakat şeklin geneline bakıldığında, bu değerin, mavi noktaların birbirine oldukça uzak olduğu gerçeğini yansıtmadığı açıktır. Şimdi yukarıdaki üçgenleri, aralarındaki uzaklık değişmeyecek şekilde, aşağıdaki gibi yeniden konumlandıralım.

Burada, konum değişmesine rağmen uzaklığın aynı kaldığını, dolayısıyla en kısa uzaklık kavramının nesnelerin konumundan tamamen bağımsız olduğu görebiliriz. Konu uygulamaya geldiğinde bu pek de istenilen bir özellik değildir. Neyse ki bu eksikliği ortadan kaldırmaya yardımcı olacak Hausdorff metriği vardır.

Hausdorff metriğin tanımını vermeden önce, bu metriğin neyi ölçtüğüne bir bakalım. İlk olarak çalışacağımız kümelerin kompakt olduğunu kabul edelim. $A\subseteq \mathbb{R}^2$ için, bu kümeyi $\delta > 0$ kadar genişleterek elde edilen $A_\delta$ kümesini tanımlayalım:

$A_\delta = \{x\in \mathbb{R}^2 : |x-y|<\delta, y\in A\}$

$A, B\subseteq \mathbb{R}^2$ için $B\subseteq A_\delta$ ve $A\subseteq B_\delta$ olacak şekilde bir $\delta$ elde etmeye, hatta bu özelliği sağlayan $\delta$ ‘ların en küçüğünü bulmaya çalışalım. (Kümeler kompakt olduğundan sınırlılar, dolayısıyla böyle bir $\delta$ ‘nın varlığından eminiz.) İşte elde ettiğimiz bu $\delta$ bize A ve B arasındaki Hausdorff uzaklığı verecektir. Şimdi yine aynı örnek üzerinden, bu metriği nasıl tanımlayabileceğimize bakalım.

İlk olarak, $A$ ‘nın $B$ ‘yi kapsayan bir genişlemesini yani, $B\subseteq A_{\delta_A}$ olacak şekilde bir $\delta_A$ bulmaya çalışalım. Bunun için, önce $A$ kümesinin her bir noktasının $B$ kümesine olan (en kısa) uzaklığını, yani $d(a,B)=inf_{b\in B} d(a,b)$ ‘yi buluruz. $A$ ‘nın $\delta_A$ genişlemesinin $B$ ‘yi kapsaması için ise bu uzaklıkların en büyüğünü seçeriz. Bu durumda $\delta_A= sup_{a\in A} d(a,B)$ olur.

Benzer şekilde, $\delta_B= sup_{b\in B} d(b,A)$ için $A\subseteq B_{\delta_B}$ olduğunu da görebiliriz. Fakat amacımız $A$ ve $B$ kümeleri için ortak bir $\delta$ elde etmek olduğundan

$\delta=\textrm{maks}\{\delta_A, \delta_B\}=\textrm{maks}\{ sup_{a\in A} d(a,B), sup_{b\in B} d(b,A) \}$

olarak seçeriz.

Hausdorff metriğinin en bilinen uygulamalarından biri, görüntü analizi, robotların görsel navigasyonu, bilgisayar destekli ameliyatlar gibi alanlarda kullanılan görüntü eşlemedir.

Yukarıdaki şekilde, solda verilen şablonun, sağdaki resimde olup olmadığını, varsa nerede olduğunu araştırırken Hausdorff metriği kullanılabilir. En iyi eşleşmeyi elde etmek için uzaklığın yeterince küçük olması gerekir.

Şimdi, asıl konumuza dönelim ve Hausdorff metriğin fraktal görüntü işleme alanında nasıl kullanıldığına bakalım.

Bir bilgisayarda görüntü depolarken karşılaşılan en temel sıkıntılardan biri depolama alanının kısıtlı olmasıdır. Görüntüyü depolarken, onu bir şekilde (sonlu bir) sıfırlar ve birler dizisine çevirmemiz gerekir. Bunu yapmak için görüntünün üzerine bir piksel ağı yerleştirdiğimizi ve bilgisayarın her pikselin değerini belleğine kaydettiğini düşünelim. Bir pikselin değeri, o noktadaki görüntünün siyah veya beyaz olmasına bağlı olarak 0 ya da 1 olsun. Bu yöntemde, görüntünün çözünürlüğü piksellerin büyüklüğüne bağlı olacaktır. Kullandığımız piksel sayısı depolama alanı ile sınırlıdır ve bu durum görüntünün netliğini ve ne kadar detaya sahip olup olmayacağını doğrudan etkiler. Bu sorunu çözmek fraktal sıkıştırma yöntemi kullanılabilir. Bunun için, işlemek istediğimiz görüntüye A diyelim ve $A_n=f(A_{n-1})$ ve $\lim A_n=A$ olacak şekilde bir $f$ prosesi bulmaya çalışalım. Hausdorff metriği işte tam burada devreye giriyor, çünkü $\lim A_n=A$ olması

$\forall \epsilon >0$ için, $\exists N\in \mathbb{N} ; n\geq N$ ise $H(A_n,A)<\epsilon$

koşulunun sağlanması anlamına gelir. (Burada H Hausdorff metriği gösterir.) Bu yöntem sayesinde, tüm görüntüyü depolamak yerine $f$ ‘yi depolamak yeterli olacaktır.

Yukarıda Sierpinski üçgeni ve onu elde etmek için kullanılan ilk üç iterasyonu görüyoruz. Bu üçgeni saklamak yerine, iterasyon kuralını saklamak tabii ki daha az yer kaplayacaktır.

Şimdi yukarıda anlatılanların matematiksel boyutuna bir bakalım.

$(X,d)$ bir tam metrik uzay olmak üzere, $\mathcal{H}(X)=\{A\subset X : A\neq \emptyset, A\hspace{0.1cm} \textrm{kompakt}\}$ kümesini tanımlayalım. Biliyoruz ki, $B\in \mathcal{H}(X)$ için $x$ ile $B$ kümesi arasındaki (en kısa) uzaklık $d(x,B)=\textrm{min} \{d(x,y) : y\in B\}$ biçiminde tanımlıdır. Burada B kümesi kompakt ve metrik fonksiyonu sürekli olduğundan minimum değerin varlığından söz edebiliriz. Çünkü kompakt bir küme üzerinde sürekli bir fonksiyonun maksimum ve minimum değerlerini aldığını biliyoruz.

Şimdi de $A, B\in \mathcal{H}(X)$ için $h(A,B)=\textrm{maks}\{d(x,B) : x\in A\}$ uzaklığını tanımlayalım. Dikkat edersek, h fonksiyonu $\mathcal{H}(X)$ üzerinde bir metrik değildir, çünkü simetri özelliğini sağlamaz. Örneğin, d standart metrik olmak üzere, $(\mathbb{R},d)$ tam metrik uzayında, $A=[3,4], B=[4,6]$ kompakt kümelerini düşünelim. $h(A,B)=1, h(B,A)=2$ olur, dolayısıyla $h(A,B)\neq h(B,A)$ ‘dir.

Teorem: $(X,d)$ bir tam metrik uzay ve $H: \mathcal{H}(X) \rightarrow \mathcal{H}(X)$ , $H(A,B)=\textrm{maks}\{h(A,B),h(B,A)\}$ olmak üzere $( \mathcal{H}(X) ,H)$ bir metrik uzaydır. (Bu metrik, $\mathcal{H}(X)$ üzerinde Hausdorff metriğidir.)

Bir görüntüyü $X=\mathbb{R}^2$ tam metrik uzayının kompakt bir alt kümesi olarak düşünebiliriz. Bu yaklaşımdan yola çıkarak, her bir görüntüyü $\mathcal{H}(X)$ uzayının bir noktası olarak kabul edip, bu uzayı “fraktallar uzayı” olarak adlandıralım.

Teorem: $(X,d)$ bir tam metrik uzay olsun. Bu durumda, $( \mathcal{H}(X) ,H)$ bir tam metrik uzaydır. Ayrıca $(A_n)$ , $\mathcal{H}(X)$ ‘de bir Cauchy dizisi olmak üzere, $\lim A_n=\{ x\in X : x_n \rightarrow x, x_n\in A_n, \hspace{0.1cm} \textrm{olacak \c{s}ekilde bir} \hspace{0.1cm} (x_n) \hspace{0.1cm} \textrm{Cauchy dizisi vard{\i}r.} \}$ biçiminde tanımlıdır.

Şimdi, $( \mathcal{H}(X) ,H)$ ‘in bir tam metrik uzay olmasından ve Banach sabit nokta teoreminden yararlanarak yakınsak bir dizi elde etmeye çalışalım. Bunun için önce daraltma dönüşümünün tanımını ve sabit nokta teoreminin ifadesini verelim.

Tanım: $(X,d)$ bir metrik uzay, $f:X\rightarrow X$ bir dönüşüm ve $0\leq s<1$ olsun. Eğer her $x,y\in X$ için $d(f(x),f(y))\leq s d(x,y)$ oluyorsa, $f$ ‘ye bir daraltma dönüşümü denir.

Teorem (Banach sabit nokta teoremi): $(X,d)$ bir tam metrik uzay ve $f:X\rightarrow X$ bir daraltma dönüşümü olsun. Bu durumda $f$ ‘nin tek bir sabit noktası vardır (Yani, $f(x_f)=x_f$ olacak şekilde tek bir $x_f\in X$ vardır). Ayrıca bu sabit nokta, her $x\in X$ için $f(x)=x, f^n(x)=(f\circ f^{n-1})(x)$ biçiminde elde edilen $(f^n(x))$ dizisinin limitidir, yani her $x\in X$ için $\lim f^n(x)=x_f$ ‘dir.

Demek ki, $( \mathcal{H}(X) ,H)$ üzerinde bir $f$ daraltma dönüşümü bulabilirsek, her $A\in \mathcal{H}(X)$ için, bu dönüşümün sabit noktasına yakınsayan bir $(f^n(A))$ dizisi de elde etmiş oluruz. Bu dönüşümü bulurken, X üzerinde tanımlı bir daraltma dönüşümlerinden yararlanabiliriz.

Lemma: $(X,d)$ bir tam metrik uzay olsun.
1) $w:X\rightarrow X$ sürekli bir fonksiyon ise, her $A\in \mathcal{H}(X)$ için $w(A)\in \mathcal{H}(X)$ olur.
2) $w:X\rightarrow X$ , $0\leq s<1$ faktörü ile bir daraltma dönüşümü ise, $w: \mathcal{H}(X) \rightarrow \mathcal{H}(X)$ , $\mathcal{H}(X)$ üzerinde $0\leq s <1$ faktörü ile bir daraltma dönüşümüdür, yani her $A,B\in \mathcal{H}(X)$ için $H(w(A),w(B))\leq s H(A,B)$ sağlanır.

Bu Lemma ile, X üzerinde tanımlı her daraltma dönüşümünün aynı zamanda $\mathcal{H}(X)$ üzerinde de bir daraltma dönüşümü olduğunu görmüş olduk. Şimdi $\mathcal{H}(X)$ üzerinde daha kapsamlı bir daraltma dönüşümü elde edeceğiz.

Lemma: $(X,d)$ bir tam metrik uzay ve her $n=1,2,\ldots N$ için $w_n$ , $s_n$ faktörüyle bir daraltma dönüşümü olsun. Bu durumda $W: \mathcal{H}(X) \rightarrow \mathcal{H}(X)$ , $W(B)=w_1(B)\cup w_2(B)\cup \ldots w_N(B)$ , $s=\textrm{maks}\{s_1, s_2,\ldots, s_N\}$ faktörü ile bir daraltma dönüşümüdür.

Tanım: $(X,d)$ bir tam metrik uzay ve her $n=1,2,\ldots N$ için $w_n$ , $s_n$ faktörüyle bir daraltma dönüşümü olmak üzere, $\{X; w_1,w_2,\ldots, w_N\}$ sistemine bir “Yinelemeli Fonksiyon Sistemi (Iterated Function System)” ya da kısaca bir IFS denir. Bu sistemin daraltma faktörü ise $s=\textrm{maks}\{s_1, s_2,\ldots, s_N\}$ ‘dir.

Eğer $W(B)=w_1(B)\cup w_2(B)\cup \ldots w_N(B)$ ise, yukarıdaki Lemma gereğince $W$ ‘nin $\mathcal{H}(X)$ üzerinde bir daraltma dönüşümü olduğunu söyleyebiliriz. O halde Banach Sabit Nokta Teoreminden, $W$ ‘nin tek bir $A\subset X$ sabit noktası ve her $B\in \mathcal{H}(X)$ için, $\lim W^n(B)=A$ olacak şekilde bir $(W^n(B))$ dizisi vardır. Burada $A$ kümesi, IFS’nin atraktörü olarak adlandırılır.

İşlemek istediğimiz bir görüntüyü, $\mathbb{R}^2$ ‘nin kompakt bir altkümesi olarak düşünebileceğimizden bahsetmiştik. Amacımız, $\mathbb{R}^2$ ‘de bir A görüntüsü verildiğinde, A’yı atraktör kabul eden bir IFS elde etmektir. Bu sayede, A görüntüsü yerine, içerisinde A’ya ulaşmak için gereken tüm bilgiler bulunan bir IFS’yi depolamış oluruz.

Şimdi bir $A\in \mathcal{H}(X)$ kümesi alalım ve her $B\in \mathcal{H}(X)$ için $c_A(B)=A$ olacak şekilde bir $c_A:\mathcal{H}(X) \rightarrow \mathcal{H}(X)$ dönüşümü tanımlayalım. Bu durumda her $B,D\in \mathcal{H}(X)$ için $H(c_A(B),c_A(D))=H(A,A)=0$ olduğundan $c_A$ bir daraltma dönüşümüdür ve dönüşümün tanımdan $c_A(A)=A$ ‘dir. O halde, $\{X,c_A\}$ , atraktörü $A$ olan bir IFS’dir. Tabii ki burada $c_A$ ‘yı depolamakla $A$ ‘yı depolamak aynı şey olduğundan, $c_A$ yeterince işe yarar bir dönüşüm değildir. Ama en azından verilen her $A$ görüntüsü için, atraktörü $A$ olan (iyi ya da kötü) bir IFS bulunabileceğini görmüş olduk.

Son olarak aşağıdaki teorem ile, her görüntü için daha basit, yani bir anlamda depolanması daha kolay olacak bir IFS bulmanın mümkün olduğu görelim.

Teorem (Kolaj Teoremi): $(X,d)$ bir tam metrik uzay olsun. $T\in \mathcal{H}(X)$ ve $\epsilon >0$ verilsin.

$H(T,\bigcup_{n=1}^N w_n(T))\leq \epsilon \hspace{3cm} (*)$

olacak şekilde, $0\leq s<1$ daraltma faktörüne sahip bir $\{X;w_1,w_2\ldots w_N\}$ seçelim. Bu durumda, $A$ bu IFS’nin atraktörü olmak üzere, $H(T;A)\leq \frac{\epsilon}{1-s}$ eşitsizliği sağlanır. Denk olarak, her $T\in \mathcal{H}(X)$ için

$H(T;A)\leq (1-s)^{-1} H(T, \bigcup_{n=1}^N w_n(T) )$ ‘dir.

Dolayısıyla, atraktörü, elimizdeki görüntüye yakın olan bir IFS bulmak için, yukarıdaki teoremde verilen (*) koşulunu sağlayan daraltma dönüşümleri bulmak gerekir. Bu teorem, belirli bir fraktal için bir IFS bulma problemini hemen çözmese de, probleme nasıl yaklaşılması gerektiği konusunda rehberlik eder.

Yukarıda kısaca anlattığımız, verilen bir görüntüyü, bir IFS ile temsil etme yöntemi “Fraktal Görüntü Sıkıştırma” olarak adlandırılır.

Son olarak, burada Kolaj Teoremi kullanılarak üretilmiş bir fraktal örneği bulabilirsiniz. Burada ise, Kolaj Teoreminin sahibi Michael Barnsley’in “Fractals Everywhere (Fraktallar Her Yerde)” adlı kitabında tanımladığı Barnsley Eğrelti otu isimli fraktalı elde etmek için kullanılan ve dört afin dönüşümden oluşan IFS’yi inceleyebilirsiniz.

Fraktallar her yerde olabilir, tamam, ama matematik de her yerdedir! 🙂

Kaynaklar
1)https://www.math.arizona.edu/~flaschka/Topmatter/527files/termpapers/mcmillen.pdf
2)https://www.youtube.com/watch?v=zGKfU91-hU0
3)http://cgm.cs.mcgill.ca/~godfried/teaching/cg-projects/98/normand/main.html

Topolojik bir oluşum!

Monthly Archives: Nisan 2021

Boole Cebirleri İçin Stone Temsil Teoremi

Ev Yapımı İspat: Buffon’un İğneleri ile Pi Sayısı Hesabı

Nicelik mi, Nitelik mi?

#asalsayılarsonsuzdur #topolojiheryerde

Brouwer Hocamızla Sezgiselliğe Doğru…

Hausdorff Metriğinden Fraktal Görüntü Sıkıştırma Teknolojisine