$n$ elemanlı bir küme üzerinde kaç tane primal yazılabilir?

Question

Tanım: $X$ herhangi bir küme ve $\mathcal{P}\subseteq 2^X$ olsun.

$\mathcal{P}, \ X\text{'de primal}:\Leftrightarrow \left\{\begin{array}{l} \mathbf{P_1)} \ X\notin \mathcal{P} \\ \mathbf{P_2)} \ (A\in\mathcal{P})(B\subseteq A) \Rightarrow B\in\mathcal{P} \\ \mathbf{P_3)} \ A\cap B\in\mathcal{P} \Rightarrow (A\in\mathcal{P} \vee B\in\mathcal{P}) \end{array}\right.$ 

 

Teorem: $X$ herhangi bir küme ve $\mathcal{P}\subseteq 2^X$ olsun.

$\mathcal{P}, \ X\text{'de primal}:\Leftrightarrow \left\{\begin{array}{l} \mathbf{P_1)} \ X\notin \mathcal{P} \\ \mathbf{P_2)} \ (B\notin\mathcal{P})(B\subseteq A) \Rightarrow A\notin\mathcal{P} \\ \mathbf{P_3)} \ (A\notin\mathcal{P})(B\notin\mathcal{P})\Rightarrow A\cap B\notin\mathcal{P} \end{array}\right.$ 

Comments

Gözlemler

1) $X$ herhangi bir küme olmak üzere $\mathcal{P}=2^X\setminus \{X\}$ ailesi, $X$ kümesi üzerinde her zaman bir primaldir.

 

2) Aynı küme üzerinde tanımlı iki primalin birleşimi de primaldır. Bunu kanıtlamak çok kolay.

 

3) $X=\emptyset$ kümesi üzerinde sadece 1 tane primal yazılabilir.

$\mathcal{P}=\emptyset$

 

4) Bir elemanlı $X=\{a\}$ kümesi üzerinde 2 tane primal yazılabilir.

$\mathcal{P}_1=\emptyset$

$\mathcal{P}_2=\{\emptyset\}$

 

5) İki elemanlı $X=\{a,b\}$ kümesi üzerinde 4 tane primal yazılabilir.

$\mathcal{P}_1=\emptyset$

$\mathcal{P}_2=\{\emptyset,\{a\}\}$

$\mathcal{P}_3=\{\emptyset,\{b\}\}$

$\mathcal{P}_4=\{\emptyset,\{a\},\{b\}\}$

 

6) Üç elemanlı $X=\{a,b,c\}$ kümesi üzerinde 8 tane primal yazılabilir.

$\mathcal{P}_1=\emptyset$

$\mathcal{P}_2=\{\emptyset,\{a\},\{b\},\{a,b\}\}$

$\mathcal{P}_3=\{\emptyset,\{a\},\{c\},\{a,c\}\}$

$\mathcal{P}_4=\{\emptyset,\{b\},\{c\},\{b,c\}\}$

$\mathcal{P}_5=\{\emptyset,\{a\},\{b\},\{c\}, \{a,b\},\{a,c\}\}$

$\mathcal{P}_6=\{\emptyset,\{a\},\{b\},\{c\},\{a,b\},\{b,c\}\}$

$\mathcal{P}_7=\{\emptyset,\{a\},\{b\},\{c\},\{a,c\},\{b,c\}\}$

$\mathcal{P}_8=\{\emptyset,\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\}\}$

---

$X = \{a,b,c\}$ olsun
$\mathbb{P}(X)$ i soyle kodlayalim.

$\{\} \to 0$
$ \{a\} \to 1 \quad \{b\} \to 2 \quad \{c\} \to 3$

$ \{a,b\} \to 4 \quad \{a,c\} \to 5 \quad \{b,c\} \to 6$

$\{a,b,c\} \to 7$

simdi $\mathbb{P}(\mathbb{P}(X))$ nin bir elemani $k$ yi  $8$ bitlik bir sayi olarak gosterebiliriz. Birinci biti bos kumenin $k$ nin elemani olup olmadigini soyleyecek. Kacinci bitin hangi elemanin kumeye ait oldugunu yukaridaki tablodan okuyabilirsiniz.

Simdi bu kodlama altinda $k$ bir primalsa,
$k$ sayisi cift olmali cunku orjinal kume primalin elemani olmamali,
$k \geq 2^{3-1}$ cunku sanirim bos kume her zaman primalin elemani,
$k \leq 2^{3}-1$ bu acik olmali
Kesisim icin $\text{AND}$ operasyonu var.
Alt kumelik testi icin ise gene $(a \text{AND} b) == b;$ testini kullanabiliriz (burada b a nin alt kumesi mi diye test ediyoruz)
Devam edicem ama suan uykum geldi

---

$n$ elemanli bir $X$ kumesinin, $n-1$ elemanli bir alt kumesi $B_i$ yi alalim.
$\mathbb{P}(B_i)$ bir primaldir. Boyle farkli $n$ tane $B_i$ vardir ve yarattiklari primaller birbirinden farklilar.
Iki primalin birlesimi gene bir primal. demek ki bu $B_i$ leri kullanarak en fazla $2^n$ tane primal yazabilirim.
Her Primal (Tirivial Primal haric) icinde en az bir $B_i$ bulundurmak zorundadiri da ispatlarsak (ki sanirim bu P3 ten cikacak) bu sayinin maksimum $2^n$ oldugunu gosteririz
Iddia: $X$ in kardinalitesi $n-1$ e kucuk esit butun alt kumelerini  $B_i$ lerin kesimi olarak yazabiliriz. Bunun disinda $B_i$ leri orjinal kumeyi ve $B_i$ nin kendisini kullanmadan kesisim olarak ifade edemeyiz. sanirim acik bu
Demek ki her primalde en az bir $B_i$ olmali.

---

oldu bence buyuk ihtimalle. yukarida ufak tefek hatalar var (trivial primalde $B_i$ yok mesela)

ama "morally" dogru bence

---

Iddia: $X$ kumesi uzerine yazilabilecek butun primallerin kumesi, $\mathbb{P}(X)$ kumesi uzerine primaldir

---

Az once verdigim ispat sonlu kumeler icin gecerli. Sonsuz kumeler icin bu onerme dogru olmayabilir. Ispat eger dogru ise $X$ teki butun elemanlari, $\mathbb{P}(X)$ in kesisim altinda asal ( Sadece tum uzay ve kendisini kullarak yazabiliyoruz bu elemani kesisim kullanirken)  kumelerin varolmasi ve bu kumeleri kesistirerek $\mathbb{P}(x)$ in istedigimiz asal olmayan herhangi bir elemanini  bulmamiza dayaniyor. Bu elemanlar var mi varsa ne kadar var sorularinin cevabi reel sayilar kumesinde dramatik bicimde degisebilir (ki bence degisir)

---

degismiyormus

---

7) 4 elemanlı $X=\{a,b,c,d\}$ kümesi üzerinde $16$ tane primal vardır.

$\mathcal{P}_1=\emptyset$

$\mathcal{P}_2=\{\emptyset,\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\},\{a,b,c\}\}$

$\mathcal{P}_3=\{\emptyset,\{a\},\{b\},\{d\},\{a,b\},\{a,d\},\{b,d\},\{a,b,d\}\}$

$\mathcal{P}_4=\{\emptyset,\{a\},\{c\},\{d\},\{a,c\},\{a,d\},\{c,d\},\{a,c,d\}\}$

$\mathcal{P}_5=\{\emptyset,\{b\},\{c\},\{d\},\{b,c\},\{b,d\},\{c,d\},\{b,c,d\}\}$

$\mathcal{P}_6=\{\emptyset,\{a\},\{b\},\{c\},\{d\},\{a,b\},\{a,c\},\{b,c\},\{b,d\},\{c,d\},\{a,b,c\},\{b,c,d\}\}$

$\mathcal{P}_7=\{\emptyset,\{a\},\{b\},\{c\},\{d\},\{a,b\},\{a,d\},\{b,c\},\{b,d\},\{c,d\},\{a,b,d\},\{b,c,d\}\}$

$\mathcal{P}_8=\{\emptyset,\{a\},\{b\},\{c\},\{d\},\{a,b\},\{a,c\},\{a,d\},\{b,c\},\{c,d\},\{a,b,c\},\{a,c,d\}\}$

$\mathcal{P}_9=\{\emptyset,\{a\},\{b\},\{c\},\{d\},\{a,b\},\{a,c\},\{a,d\},\{b,c\},\{b,d\},\{a,b,c\},\{a,b,d\}\}$

$\mathcal{P}_{10}=\{\emptyset,\{a\},\{b\},\{c\},\{d\},\{a,b\},\{a,c\},\{a,d\},\{b,d\},\{c,d\},\{a,b,d\},\{a,c,d\}\}$

$\mathcal{P}_{11}=\{\emptyset,\{a\},\{b\},\{c\},\{d\},\{a,c\},\{a,d\},\{b,c\},\{b,d\},\{c,d\},\{a,c,d\},\{b,c,d\}\}$

$\mathcal{P}_{12}=\{\emptyset,\{a\},\{b\},\{c\},\{d\},\{a,b\},\{a,c\},\{a,d\},\{b,c\},\{b,d\},\{c,d\},\{a,b,c\},\{a,b,d\},\{a,c,d\}\}$

$\mathcal{P}_{13}=\{\emptyset,\{a\},\{b\},\{c\},\{d\},\{a,b\},\{a,c\},\{a,d\},\{b,c\},\{b,d\},\{c,d\},\{a,b,c\},\{a,b,d\},\{b,c,d\}\}$

$\mathcal{P}_{14}=\{\emptyset,\{a\},\{b\},\{c\},\{d\},\{a,b\},\{a,c\},\{a,d\},\{b,c\},\{b,d\},\{c,d\},\{a,b,d\},\{a,c,d\},\{b,c,d\}\}$

$\mathcal{P}_{15}=\{\emptyset,\{a\},\{b\},\{c\},\{d\},\{a,b\},\{a,c\},\{a,d\},\{b,c\},\{b,d\},\{c,d\},\{a,b,c\},\{a,c,d\},\{b,c,d\}\}$

$\mathcal{P}_{16}=\{\emptyset,\{a\},\{b\},\{c\},\{d\},\{a,b\},\{a,c\},\{a,d\},\{b,c\},\{b,d\},\{c,d\},\{a,b,c\},\{a,b,d\},\{a,c,d\},\{b,c,d\}\}$