$\mathbb{N}^{\mathbb{N}}$ kümesinin güçlülüğü

Question

$\mathbb{N}^{\mathbb{N}}$ sembolü ile $\mathbb{N}$'den $\mathbb{N}$'ye giden tüm fonksiyonların kümesini gösterelim. Gösteriniz ki $\mathbb{N}^{\mathbb{N}}$ kümesinin güçlülüğü (cardinality) ile $\mathcal{P}(\mathbb{N})$ kümesinin güçlülüğü aynıdır. Burada $\mathcal{P}(\mathbb{N})$ ile $\mathbb{N}$'nin güç (power) kümesini gösteriyoruz.

Answer 1

(Kardinal sayılarda üs alma kurallarından $(\kappa^{\mu})^\eta=\kappa^{\mu \eta}$ eşitliğini ve üs almanın azalmayan bir fonksiyon olduğunun bilindiğini varsayarsak)

$\aleph_0 \leq 2^{\aleph_0}$ olduğu için

$|\mathbb{N}^{\mathbb{N}}|=\aleph_0^{\aleph_0} \leq (2^{\aleph_0})^{\aleph_0}=2^{\aleph_0 \times \aleph_0}=2^{\aleph_0}=|\mathcal{P}(\mathbb{N})|$

Öte yandan $2 \leq \aleph_0$ olduğu için

$|\mathcal{P}(\mathbb{N})|=2^{\aleph_0} \leq \aleph_0^{\aleph_0}=|\mathbb{N}^{\mathbb{N}}|$

Schröder-Bernstein teoremi ile bu iki küme aynı kardinalitededir.

Comments

                             

---

Bu cevap benimkinden daha şık bir cevap olmuş.

Answer 2

$\mathbb{N}$'den $\mathbb{N}$'ye giden her $f$ fonksiyon, $\mathbb{N}\times\mathbb{N}$'de bir bağıntı tabii ki, dolayısıyla $\mathbb{N}^{\mathbb{N}}\subset \mathcal{P}(\mathbb{N}\times\mathbb{N})$, yani $$|\mathbb{N}^{\mathbb{N}}|\leq |\mathcal{P}(\mathbb{N}\times\mathbb{N})|=|\mathcal{P}(\mathbb{N})|.$$

Diğer taraftan kolayca gösterilebilir ki $\{0,1\}^{\mathbb{N}}$ kümesi ile $\mathcal{P}(\mathbb{N})$ kümesi arasında güzel bir eşleme (bijection) var. $\mathbb{N}$'den $\{0,1\}$ kümesine giden her fonksiyon aynı zamanda $\mathbb{N}$'den $\mathbb{N}$'ye giden bir fonksiyon olduğuna göre $$|\mathcal{P}(\mathbb{N})|=|\{0,1\}^{\mathbb{N}}|\leq|\mathbb{N}^{\mathbb{N}}|.$$

Sonuç olarak $|\mathbb{N}^{\mathbb{N}}|=|\mathcal{P}(\mathbb{N})|$.

Comments

Bu cevap da şık olmuş.

Answer 3

Teorem 1: $\mathbb{N}$ doğal sayılar kümesinin kuvvet kümesinin kardinal sayısı, $\mathbb{R}$ gerçel sayılar kümesinin kardinal sayısına eşittir.

$$(|2^{\mathbb{N}}|=)|\mathcal{P}(\mathbb{N})|=\mathcal{c}$$

İspat: $(2^{\mathbb{N}}=)\mathcal{P}(\mathbb{N})\sim [0,1]$ olduğunu göstermek yeter.

$f:2^{\mathbb{N}}\rightarrow [0,1], \,\ f(A)=0,a_1a_2a_3\ldots \,\,\ \text{birebir} \,\,\,\,\,\ \left( a_i=\left\{\begin{array}{ccc} 1 & , & i\in A \\ 0 & , & i\notin A \end{array}\right.\right)$

$$\Rightarrow$$

$$|2^{\mathbb{N}}|\leq|[0,1]|\ldots (1)$$

$g:[0,1]\rightarrow 2^{\mathbb{N}}, \,\ g((0,c_1c_2c_3\ldots ))=\{m|c_m=1\}\subseteq \mathbb{N} \,\ \text{ birebir}$

$$\Rightarrow$$

$$|[0,1]|\leq |2^{\mathbb{N}}|\ldots (2)$$

O halde 

$$(1),(2)\Rightarrow |2^{\mathbb{N}}|=|[0,1]|$$

elde edilir.

Teorem 2: $\mathbb{N}$ doğal sayılar kümesinden $\mathbb{N}$ doğal sayılar kümesine tanımlı fonksiyonların oluşturduğu kümenin kardinal sayısı, $\mathbb{R}$ gerçel sayılar kümesinin kardinal sayısına eşittir.

$$(\text{Teorem } 1)(\text{Teorem } 2)\Rightarrow |2^{\mathbb{N}}|=\mathcal{c}.$$

Comments

Tabii dikkat edilmesi gereken küçük bir noktayı belirtmekte fayda var. Çözümde eğer sayıların ikilik sisteme göre açılımları kullanılıyorsa [0,1] aralığındaki bazı rasyonel sayılar bir değil de iki tane açılıma sahip olduğu için g fonksiyonu tanımlanırken bu açılımlardan birini sabitleyip ona göre tanımlıyoruz  (mesela $1/2=(0.1)_2$ ve $1/2=(0.011111...)_2$).

f fonksiyonu tanımlanırken de ikilik sisteme göre açılım kullanıldığında f fonksiyonu birebir olmayacağı için $f(A)$'nın mesela 3'lük gösterimdeki hal olduğu varsayılabilir. Bu durumda 0.1000... ve 0.01111... gibi diziler farklı sayıları temsil edecektir.