Fungsi Scott-continuous: definisi alternatif

Saya benar-benar bergumul dengan properti ini:

Biarkan $X,Y$ menjadi ruang koherensi dan $f: Cl(X) \rightarrow Cl(Y)$ menjadi fungsi monoton. $f$ adalah kontinu jika dan hanya jika $f(\bigcup_{x\in D} x)=\bigcup_{x \in D}f(x)$ , untuk semua $D \subseteq Cl(X)$ sedemikian rupa sehingga $D$ adalah himpunan terarah.

Set yang diarahkan didefinisikan sebagai berikut: $D \subseteq$ POSETadalah himpunan terarah iff $\forall x, x' \in D$ $\exists z \in D$ seperti $x \subseteq z$ dan $x' \subseteq z$ .
$Cl(X)$ adalah klik untuk X: $\{x \subseteq |X| \mid a,b \in x \Rightarrow a$ koheren $b \}$ .

Banyak buku memberikannya sebagai definisi fungsi terus-menerus Scott , tetapi sayangnya bukan guru saya. Dia memberi kita definisi berkelanjutan:

adalah kontinu IFF itu monoton dan ∀ x ∈ C l ( X ) , ∀ b ∈ f ( x ) , ∃ x 0 ⊆ f i n x , b ∈ f ( x 0 ) , di manamonotondidefinisikan sebagai: f adalah monoton iff a $f : Cl(X) \rightarrow Cl(Y)$$\forall x \in Cl(X), \forall b \in f(x), \exists x_0 \subseteq_{fin} x, b \in f(x_0)$
$f$$a \subseteq b \Rightarrow f(a) \subseteq f(b)$

Ini adalah bukti yang diajukan yang saya miliki, tetapi saya tidak dapat memahami persamaan terakhir.

Bukti kontinu menyiratkan f ( ⋃ D ) = ⋃ f ( D $f$$f(\bigcup D)=\bigcup f(D)$ :
Misalkan . Dengan definisi kontinuitas, ∃ x 0 ⊂ f i n x ∣ b ∈ f ( x 0 ) . Perhatikan bahwa x 0 adalah gabungan dari { x i ∣ x i ∈ D } .$b \in f(\bigcup D)$$\exists x_0 \subset_{fin} x \mid b \in f(x_0)$$x_0$$\{ x_i \mid x_i \in D\}$
Jika langsung maka: ∃ z ∈ D ∣ x i ⊆ z lalu x 0 ⊆ z . Dengan definisi monoton, f ( x 0 ) ⊆ f ( z ) jadi b ∈ f ( z ) (???) ⊆ ⋃ f ( D ) . Dan bahkan itu benar kita harus menunjukkan bahwa ⋃ f ( D ) = f ( ⋃ $D$$\exists z \in D \mid x_i \subseteq z$$x_0 \subseteq z$$f(x_0)\subseteq f(z)$$b \in f(z)$ $\subseteq \bigcup f(D)$ , bukan hanya ⊆ .$\bigcup f(D) = f(\bigcup D)$$\subseteq$

Bukti dari implikasi lain bahkan lebih buruk sehingga saya tidak dapat menulisnya di sini ... Bisakah Anda menjelaskan kepada saya bagaimana buktinya bisa berfungsi?

Definisi kesinambungan yang digunakan oleh guru Anda adalah definisi yang lebih baik. Ini memberi tahu Anda secara konkret apa arti keberlanjutan.

Misalkan . Itu berarti bahwa mengingat semua informasi x , mungkin set token (atom) yang tak terbatas, fungsinya menghasilkan beberapa elemen yang memiliki informasi atom b . (Ini dapat memiliki informasi lain juga, tetapi kami tidak khawatir dengan itu saat ini.) Definisi guru Anda mengatakan bahwa tidak perlu untuk melihat semua informasi x yang tak terbatas untuk menghasilkan informasi keluaran b . Beberapa subset terbatas x sudah cukup untuk memproduksinya.$b \in f(x)$$x$$b$$x$$b$$x$

(Buku Melvin Fitting, "teori komputasi, semantik, dan pemrograman logika", Oxford, 1987, menyebut properti ini kekompakan dan mendefinisikan fungsi kontinu sebagai sesuatu yang monoton dan kompak.)

Inilah esensi kesinambungan. Untuk mendapatkan sejumlah informasi terbatas tentang output suatu fungsi, Anda hanya memerlukan sejumlah informasi terbatas tentang input. Output yang dihasilkan oleh fungsi untuk input tak terbatas diperoleh dengan mengumpulkan informasi yang dihasilkannya untuk semua perkiraan terbatas dari input tak terbatas. Dengan kata lain, Anda tidak mendapatkan lompatan magis untuk pergi dari pendekatan terbatas ke penyatuan tak terbatas mereka. Apa pun yang Anda dapatkan tanpa batas, Anda harus sudah sampai pada tahap terbatas.

Persamaan standar cukup menarik untuk dilihat, tetapi tidak memberi tahu Anda semua intuisi yang telah saya jelaskan di atas. Namun, secara matematis, itu setara dengan definisi guru Anda.$f(\bigcup_{x \in D} x) = \bigcup_{x \in D} f(x)$

Untuk menunjukkan bahwa , itu sudah cukup untuk menunjukkan bahwa f ( x ) termasuk dalam f ( ⋃ x ∈ D x ) , untuk setiap x ∈ D . Tapi itu mengikuti langsung dari monotonitas f karena x ⊆ ⋃ x ∈ D x . Jadi, ini adalah arah "mudah".$\bigcup_{x \in D} f(x) \subseteq f(\bigcup_{x \in D} x)$$f(x)$$f(\bigcup_{x \in D} x)$$x \in D$$f$$x \subseteq \bigcup_{x \in D} x$

Arah lain, dibuktikan oleh guru Anda, adalah yang menarik: . Untuk melihat ini, gunakan intuisi yang telah saya sebutkan di atas. Setiap potongan informasi atom b di sisi kiri berasal dari pendekatan input yang terbatas: x 0 ⊆ f i n ⋃ x ∈ D x . Yaitu, b ∈ f ( x 0 ) . Sejak x $f(\bigcup_{x \in D} x) \subseteq \bigcup_{x \in D} f(x)$$b$$x_0 \subseteq_{fin} \bigcup_{x \in D} x$$b \in f(x_0)$$x_0$terbatas dan termasuk dalam penyatuan himpunan terarah, harus ada sesuatu dalam himpunan terarah yang lebih besar dari , mungkin x 0 itu sendiri. Sebut elemen itu z . Dengan sifat monoton, f ( x 0 ) ⊆ f ( z ) . Jadi, b ∈ f ( z ) . Karena z ∈ D , f ( z ) ⊆ ⋃ x ∈ D f ( x ) . Jadi, sekarang $x_0$$x_0$$z$$f(x_0) \subseteq f(z)$$b \in f(z)$$z \in D$$f(z) \subseteq \bigcup_{x \in D} f(x)$$b$terlihat di sisi kanan juga. QED.

Seperti yang telah Anda catat, menunjukkan bahwa kontinuitas guru Anda menyiratkan persamaan cantik adalah bagian yang mudah. Bagian yang lebih sulit adalah untuk menunjukkan bahwa persamaan yang cantik, meskipun terlihat seperti itu tidak mengatakan banyak, benar-benar mengatakan segalanya dalam definisi guru Anda.

Terlintas dalam benak saya, setelah saya menulis respons terakhir, bahwa definisi kontinuitas guru yang saya jelaskan dalam respons saya adalah gagasan topologi tentang kontinuitas. The aljabar perumusan kontinuitas yang biasanya disebutkan dalam buku-buku teks Ilmu Komputer menyembunyikan semua intuisi topologi. (Faktanya, Dana Scott sering menulis bahwa dia sengaja menghindari formulasi topologi karena Ilmuwan Komputer tidak mengenalnya.)

Keterkaitan antara formulasi aljabar dan topologis disebut Batu dualitas , dan sekarang menjadi semakin jelas bahwa keterkaitan ini sendiri sangat penting bagi Ilmu Komputer.

Untuk paparan konseptual dari koneksi ini (dan banyak lagi), Lihat Informasi, proses, dan permainan Abramsky .