Cardinality (Sayısallık)

Yazan : Şadi Evren ŞEKER

1. Rasyonel / Tamsayı ilişkisi
2. Sayılabilirlik (Countability)
3. Reel / Tamsayı ilişkisi

Şayet aynı isme sayıp ERD (Entity relationship diagram) üzerindeki sayısallık konusu ile ilgili yazıyı arıyorsanız bu bağlantıdan erişebilirsiniz.

Algoritma analizi (algorithm analysis) ve hesaplama teorisinde (theory of computation) sıkça kullanılan anlamıyla bir kümenin eleman sayısını belirtir.

Ayrıca matematik ve bilgisayar bilimleri açısından önemli bir yönü de kümelerin sonsuz olması durumunda kümeler arasındaki ilişkinin gösterilmesinde işe yaramasıdır.

Bu durumu öncelikle sonsuz iki küme tanımlayarak anlamaya çalışalım.

Tam sayılar kümesini ele alalım. Tam sayılar kümesi sonsuz eleman içermektedir. Eksi sonsuzdan 0’a kadar ve 0’dan da artı sonsuza kadar giden sayılardan oluşur.

Dolayısıyla tam sayılar kümesinde, sonsuz eleman olduğunu söylememiz doğrudur.

Benzer şekilde pozitif tamsayılar kümesi sıfırdan artı sonsuza kadar sonsuz sayıda eleman içerir:

Bu iki kümenin de sonsuz olduğunu söylediğimize göre gerçekten bu iki kümenin sonsuzlukları aynı mıdır? Yoksa kümelerden birisi daha büyük diğeri daha küçük sonsuz mudur?

Bu soru ile kardinallik (sayısallık, cardinality) konusuna başlayabiliriz. Bu soruyu cevaplamadan önce iki küme arasında eşit miktarda eleman bulunmasını tanımlamamız gerekir:

Sayısallık açısından iki küme birbirine bağlanmak istenirse, bunun anlamı bu kümeler arasında birebir (one-to-one) ve üzerine (onto) bağlantı bulunması demektir.

Yukarıdaki örnekte, iki küme arasında bire bir ve örten bir bağlantı gösterilmektedir. Burada birebir olması, birinci kümeden her elemanın ikinci kümeden tek bir elemanı gösteriyor olmasını ve ikinci kümedeki her elemanın da birinci kümede tek elemanı gösteriyor olması demektir. Şayet örneğin “a” elemanı hem 1 hem de 2 ile ilişkilendirilmiş olsaydı bu durumda birebir ilişkiden bahsedilemezdi. Örten olma özelliği (onto) ise boşta hiç eleman kalmamış olması yani bütün elemanların bir şekilde diğer kümede ilişkilendirilmiş olması anlamındadır.

Kümeler teorisi (set theory) ile ilgili bu kısa hatırlatmadan sonra konumuz olan sayısallık ilişkisine dönebiliriz.

Şayet kümelerin ikisi de yukarıdaki örnekte olduğu gibi sonlu değil de yazının başında verildiği gibi sonsuz ise bu durumda sayısallık bağlantısını nasıl kurabiliriz?

Sayısallık açısından, tam sayılar kümesi ve pozitif tam sayılar kümesinin eşit olduğunu söyleyebiliriz. Bunu göstermek için yukarıda bahsettiğimiz üzere, iki küme arasındaki ilişkinin örten ve birebir olduklarını göstermemiz gerekir.

Bunu daha iyi modelleyebilmek için sonsuzluk yönünü aynı tarafa çevirip ardından sayıları sıralayalım:

Tamsayılar kümesini yukarıdaki şekilde çevirecek olursak kümenin elemanlarını aşağıdaki şekilde yazabiliriz:

Yukarıdaki resimde solda gösterilen pozitif tam sayılar (Z+) kümesi ile sağda gösterilen tamsayılar kümesi (Z) arasında birebir ve örten bir ilişki kurulmuş olunur. Bunun sebebi iki kümedeki her eleman diğer kümedeki bir elemana mutlaka ilişkilendirilmiş ve bu ilişki birebir olmuştur.

Yukarıdaki bu görsel ilişkiyi matematiksel olarak aşağıdaki şekilde yazmak da mümkündür:

X e Z ve Y e Z+ olmak üzere X = Y / 2 * ( -1 ) ^{Y mod 2}

Yukarıdaki formülde tam sayı bölmesi yapıldığı kabul edilmiştir. (yani noktadan sonraki değerler göz ardı edilmiştir)

Gerçekten de Y = 1 için X = ½ *1 = 0 sonucu veya Y = 15 için X = 15 / 2 * -1 = -7 sonucu bulunmaktadır.

Bu bağlantının tersini yazmak da mümkündür:

Örneğin X = 0 için Y = -1 * 0 * 2 + 1 = 1 olarak bulunur veya diğer bir örnek olarak X = -7 için Y = -1 * -7 *2 + 1= 15 olarak bulunur.

Görüldüğü üzere iki yönlüde bütün elemanları diğer kümedeki elemanlara bağlayan bir bağlantı yazılması mümkündür.

Böylelikle yukarıdaki şartımızı sağlamış ve iki küme arasında eşit miktarda eleman bulunduğunu göstermiş oluyoruz.

Bu konuyu anlatırken sorulmuş bir soruyu cevaplamak istiyorum: “Kümelerin venn diyagramlarında da, denklemlerin her ikisinde de Z kümesi, Z+ kümesine göre daha yavaş ilerliyor. Yani Y için 16 sayısına ulaşıldığında X için henüz 8 sayısına yeni ulaşılmış olunuyor. Bu durumda tam sayılar kümesi, pozitif tam sayılar kümesinden daha büyük değil midir?”

Bu soru ilk başta mantıklı gibi görülse de cevabı kesin olarak hayırdır. Bunun sebebi kümelerin sonsuz oluşudur. Yani sonsuzun sonu yoktur J Bu durumu şöyle açıklayalım, yukarıdaki formülde yazılan X ve Y sayıları arasında neredeyse X=Y/2 veya Y = 2*X gibi bir bağlantı vardır. Bu durumda yukarıdaki soruya temel teşkil eden düşünceyi cevaplamak için sonsuzdaki bir sayıya n diyerek X=n için Y = 2n ‘dir sonucuna ulaşmak ve dolayısıyla n sonsuz ise 2n sonsuzdan daha büyük bir sonsuzdur gibi bir hataya düşmek mümkündür. Ancak buradaki hata iki türlü cevaplanabilir,

1. Örnekteki n bir sayı olmak üzere, kümelerdeki son sayının n olduğunu söyleyemeyiz
2. Sayı kümesindeki n, sonsuzda bir sayı olmak şartıyla 2n’in sonsuzda olmadığını söyleyemeyiz.

Dolayısıyla bu iki kümede de eşit sayıda eleman bulunur denilebilir.

Rasyonel sayılar (kesirli sayılar, rational numbers) ile pozitif tam sayılar kümesi arasındaki sayısallık ilişkisi

Yukarıdaki bu yaklaşım kullanılarak, kesirli sayılar ( rational numbers) kümesinin, tam sayılar kümesi ile aynı miktarda sonsuz eleman içerdiğini de ispatlayabiliriz. İhtiyacımız olan tek şey yukarıdaki örnekte bahsedildiği üzere pozitif tam sayılar kümesi, veya tam sayılar kümesi ile, kesirli sayılar (rasyonel sayılar) arasında bir bağlantı kurabilmek ve bu bağlantıyı modellemektir.

Öncelikle kesirli sayıları, iki boyutlu uzayda modellemekle işe başlayabiliriz. Kesirli sayılar kümesini aşağıdaki tabloda olduğu gibi yazmak mümkündür:

	1	2	3	.	n
1	1/1	1/2	1/3	.	1/n
2	2/1	2/2	2/3	.
3	3/1	3/2	3/3	.
.	.	.	.	.
n	.	.	.	.	n/n

Yukarıdaki tabloda görüldüğü üzere ilk satır ve ilk sütun birer pozitif tam sayı içermek üzere, tablonun diğer elemanları bu iki sayının (üsttekinin soldakine) bölümüdür. Dolayısıyla aslında problemi aşağıdaki şekilde pozitif tamsayılar olarak modellemiş oluruz:

Diğer bir deyişle şimdilik elimizde (Z+ x Z+) <-> Q+ şeklinde bir bağlantı bulunmaktadır. Bu bağlantıyı biraz daha ilerleterek Z <-> Q şeklinde çevirmeye çalışalım. Çünkü bu şekilde bir bağlantı bizim bu iki kümedeki eleman sayılarının eşit olduğunu kardinallik açısından ispatlamamız olacaktır.

Yukarıdaki şekilde gösterilen ok yönlerinde bu sayıları, pozitif tam sayılar kümesi ile ilişkilendirirsek hem bir bağlantı yakalamış hem de birebir ve örten bir ilişki elde etmiş oluruz. Bu durumda sayılarımızı aşağıdaki şekilde ilişkilendireceğiz:

Z+	Q+
1	1/1
2	2/1
3	1/2
4	3/1
5	1/3
6	4/1
7	3/2
…	…

Yukarıda görüldüğü üzere, tam sayılar kümesindeki bütün sayılar, rasyonel sayılar kümesi ile ilişkilendirilmiştir. Ayrıca dikkat edilmesi gereken bir husus, 2/2 veya 3/3 gibi tam sayı karşılığı 1 olan ve aslında eşit olan sayıların bu ilişkide yer almamasıdır. Bu sayıların ilişkiye yerleştirilmesi durumunda birebir olma özelliği bozulacaktır.

Yukarıdaki gösterim sayesinde, bu iki kümenin, yani rasyonel sayılar kümesi ile tam sayılar kümesi arasında bir ilişki birebir ve örten olarak kurulmuş ve bu sayede bu iki kümenin eleman sayısının eşit olduğu ve dolayısıyla bu iki kümenin sayısallık (kardinallik, cardinality) açısından eşit olduğu söylenebilir.

Sayılabilirlik (countability)

Diğer bir deyişle rasyonel sayılar kümesi sayılabilir bir kümedir (countable set) denilebilir. Aslında sayılabilirliğin (countability) tanımı, bir kümenin pozitif tam sayılar kümesi ile aynı kardinalliğe getirilebilmesidir. Yani herhangi bir kümeyi, yukarıdaki örneklere benzer şekilde pozitif tam sayılar ile birebir ve örten bir şekilde ilişkilendirebiliyorsak bu küme sayılabilir kümedir, aksi halde sayılamaz bir kümedir (uncountable set).

Bu sayılamazlık durumunu ve dolayısıyla kardinallik açısından eşit olmayan iki sonsuz kümeyi aşağıda örneklemeye çalışalım. Bu sefer kullanacağımız örnek gerçek sayılar (real numbers, reel sayılar) ile tam sayılar kümesi (integers) olsun.

Tam sayılar ve Reel sayılar arasında sayısallık ilişkisi

Bu örnekte, tam sayılar kümesi ve reel sayılar kümesi arasında sayısallık açısından eşitlik olmadığını ispatlamaya çalışalım.

Öncelikle ispatımızı, olmayana ergi (proof by contradiction) olarak modelliyoruz. Yani öncelikle reel sayılar kümesinin sayılabilir olduğunu kabul edip, bu sayı kümesi ile pozitif tam sayılar kümesi arasında bir ilişki kuracağız. Ardından bu ilişkinin kurulamayacağını ispatlamaya çalışacağız.

Öncelikle ilişki gösterimini ve ispatı daha iyi anlayabilmek için bu ispatta ikilik tabanda sayılar kullanalım. Yani 2 sayısı ikilik tabanda 10 olarak gösterilir. Dolayısıyla 0.2 sayısı 0.10 olarak gösterilir. Benzer şekilde 0.15438 sayısı 0.11110001001110 olarak gösterilecektir. Aslında bu gösterimin herhangi özel bir önemli olmamakla birlikte ispatı daha görülür kılmak için kullanacağız.

Şimdi doğru çalışan bir ilişkimiz olduğunu kabul edelim ve aşağıdaki şekilde gösterildiği gibi, tam sayılar ile reel sayılar kümesini ilişkilendirelim:

Z+	Q+
1	0.110101010100101…
2	0.010101010110101…
3	0.100100100101110…
4	0.001010101010001…
5	0.111110101010000…
6	0.111000011111111…
…	…

Yukarıdaki şekilde görüldüğü üzere, Z+ <-> Q+ ilişkisi kurulmuştur. Bu ilişkide herhangi bir matematiksel bağlantı bulunmadığı gibi sonuçta bütün ilişkilerde yukarıdakine benzer bir tablo ortaya çıkacaktır. Okuyucu birazdan yapacağımız ispatı, farklı sayılar veya herhangi bir matematiksel bağlantı için de deneyebilir sonuç değişmez.

Yukarıdaki şekilde tamsayılar ve reel sayılar arasında bir ilişki kurduktan sonra, kantor (Georg Cantor) tarafından ilk kez ispatlanan sayılamazlık durumu, köşegende (diagon) bulunan sayıların ters çevrilmesi ile elde edilir.

Yukarıdaki her sayının kaçıncı satırdaysa, o bitini alarak yeni bir sayı oluşturuyoruz.

Z+	Q+
1	0.110101010100101…
2	0.010101010110101…
3	0.100100100101110…
4	0.001010101010001…
5	0.111110101010000…
6	0.111000011111111…
…	…

Yukarıda, siyah renkle gösterilen bu sayılardan oluşan yeni sayımız: 0.110010… olarak belirlenebilir. Şimdi bu sayıdaki bütün bitlerin tersini alalım : 0.001101… olarak yeni bir sayı bulunacaktır.

Şimdi bu iki kümenin eşit olmadığını gösteren sorumuzu sorabiliriz, bulduğumuz bu yeni sayı, acaba yukarıdaki ilişkide hangi satırda yer almaktadır?

Cevap: Hiçbir satırda.

Bunun sebebi, her satırdan 1 bit alınarak oluşturulan yukarıdaki örnek sayının, tersi alındığında, her satırdan alınan bu bitin tersi alınmış ve dolayısıyla her satıra denk gelen bitin tersinden oluşan yeni bir sayı üretilmiş olmasıdır. Dolayısıyla hiçbir satırda ürettiğimiz bu yeni sayı bulunamaz.

Öyleyse, Z+ kümesi ile Q+ kümesini bağlamak için hangi bağlantı kullanılırsa kullanılsın, nasıl bir sayma yöntemi geliştirilirse geliştirilsin sonuçta yukarıdakine benzer bir durum olacak ve bu ilişkide bulunmayan bir reel sayı üretilerek iki küme arasındaki örten (onto) bağlantısı bozulacak ve reel sayılar kümesinde, tam sayılar kümesi ile ilişkilendirilmemiş bir eleman bulunacaktır.

Bu durumda reel sayılar kümesinin, tam sayılar kümesinden daha büyük olduğunu ve dolayısıyla sayılamaz olduğunu söyleyebiliriz.