Apa sebenarnya perbedaan semantik antara set dan tipe?

EDIT: Saya sekarang telah mengajukan pertanyaan serupa tentang perbedaan antara kategori dan set.

Setiap kali saya membaca tentang teori jenis (yang memang agak informal), saya tidak dapat benar-benar memahami perbedaannya dari teori himpunan, secara konkret .

Saya mengerti bahwa ada perbedaan konseptual antara mengatakan "x milik himpunan X" dan "x bertipe X", karena secara intuitif, himpunan hanyalah kumpulan objek, sedangkan jenis memiliki "properti" tertentu. Namun demikian, himpunan sering didefinisikan sesuai dengan sifat juga, dan jika ya, maka saya mengalami kesulitan memahami bagaimana perbedaan ini penting.

Jadi dengan cara yang paling konkrit mungkin, apa sebenarnya yang disiratkan tentang$x$ untuk mengatakan bahwa itu adalah tipe , dibandingkan dengan mengatakan bahwa itu adalah elemen dalam himpunan ?$T$$S$

(Anda dapat memilih jenis dan set apa pun yang membuat perbandingan menjadi paling jelas).

Untuk memahami perbedaan antara set dan tipe, kita harus kembali ke ide pra- matematis tentang "koleksi" dan "konstruksi", dan melihat bagaimana set dan jenis membuat matematisasinya .

Ada spektrum kemungkinan tentang apa itu matematika. Dua di antaranya adalah:

1. Kami menganggap matematika sebagai aktivitas di mana objek matematika dikonstruksi sesuai dengan beberapa aturan (anggap geometri sebagai aktivitas membangun titik, garis, dan lingkaran dengan penggaris dan kompas). Dengan demikian objek matematika diatur sesuai dengan bagaimana mereka dibangun , dan ada berbagai jenis konstruksi. Objek matematika selalu dikonstruksikan dalam beberapa cara unik, yang menentukan tipe uniknya.

2. Kami menganggap matematika sebagai alam semesta luas yang penuh dengan objek matematika yang sudah ada sebelumnya (pikirkan bidang geometris seperti yang diberikan). Kami menemukan, menganalisis, dan berpikir tentang objek-objek ini (kami mengamati bahwa ada titik, garis, dan lingkaran di pesawat). Kami mengumpulkan mereka ke dalam set . Biasanya kita mengumpulkan elemen yang memiliki kesamaan (misalnya, semua garis melewati titik tertentu), tetapi pada prinsipnya satu set dapat menyatukan pemilihan objek yang sewenang-wenang. Satu set ditentukan oleh elemen-elemennya, dan hanya oleh elemen-elemennya. Objek matematika mungkin milik banyak set.

Kami tidak mengatakan bahwa kemungkinan di atas adalah hanya dua, atau bahwa salah satu dari mereka benar-benar menggambarkan apa itu matematika. Namun demikian, masing-masing dapat melihat dapat berfungsi sebagai titik awal yang berguna untuk teori matematika umum yang bermanfaat menggambarkan berbagai kegiatan matematika.

Itu wajar untuk mengambil jenis dan membayangkan koleksi semua hal yang kita dapat membangun menggunakan aturan . Ini adalah ekstensi dari , dan itu bukan itu sendiri. Misalnya, berikut adalah dua jenis yang memiliki aturan konstruksi berbeda, tetapi mereka memiliki ekstensi yang sama:T T $T$$T$$T$ $T$

1. Jenis pasangan mana dibangun sebagai bilangan alami, dan dibangun sebagai bukti yang menunjukkan bahwa adalah bilangan prima genap yang lebih besar dari .n p n $(n, p)$$n$$p$$n$$3$

2. Jenis pasangan mana dibangun sebagai bilangan alami, dan dibangun sebagai bukti yang menunjukkan bahwa adalah bilangan prima ganjil yang lebih kecil dari .m q m $(m, q)$$m$$q$$m$$2$

Ya, ini adalah contoh sepele konyol, tetapi intinya adalah: kedua jenis tidak memiliki dalam ekstensi mereka, tetapi mereka memiliki aturan konstruksi yang berbeda . Sebaliknya, set dan yang sama karena mereka memiliki unsur yang sama.{ m ∈ N ∣ m  adalah bilangan prima yang lebih kecil dari  2

$$\{ n \in \mathbb{N} \mid \text{$n$ is an even prime larger than $3$} \}$$ $$\{ m \in \mathbb{N} \mid \text{$m$ is an odd prime smaller than $2$} \}$$

Perhatikan bahwa teori tipe bukan tentang sintaks. Ini adalah teori konstruksi matematika, seperti teori himpunan adalah teori koleksi matematika. Kebetulan bahwa presentasi yang biasa dari teori tipe menekankan sintaksis, dan akibatnya orang akhirnya berpikir teori tipe adalah sintaksis. Ini bukan kasusnya. Untuk membingungkan objek matematika (konstruksi) dengan ekspresi sintaksis yang mewakilinya (istilah sebelumnya) adalah kesalahan kategori dasar yang telah membingungkan para ahli logika untuk waktu yang lama, tetapi tidak lagi.

Untuk memulai, set dan jenis bahkan tidak di arena yang sama. Set adalah objek dari teori orde pertama, seperti teori set ZFC. Sedangkan tipe seperti jenis ditumbuhi. Dengan kata lain, teori himpunan adalah teori tingkat pertama dalam logika tingkat pertama. Teori tipe adalah perpanjangan dari logika itu sendiri. Teori Tipe Martin-Löf, misalnya, tidak disajikan sebagai teori tingkat pertama dalam logika tingkat pertama. Tidak umum berbicara tentang set dan tipe pada saat yang sama.

Seperti status kadal Diskrit, jenis (dan jenis) melayani fungsi sintaksis. Semacam / tipe berperilaku sebagai kategori sintaksis . Ini memberi tahu kita ekspresi apa yang terbentuk dengan baik. Untuk contoh sederhana menggunakan macam, katakanlah kita menggambarkan teori ruang vektor di atas bidang arbitrer sebagai teori 2-diurutkan. Kami memiliki semacam untuk skalar, , dan semacam untuk vektor, . Di antara banyak hal lainnya, kami akan memiliki operasi untuk skala: . Ini memberi tahu kita bahwa sama sekali bukan istilah yang dibentuk dengan baik. Dalam konteks teori tipe, ekspresi seperti membutuhkan untuk memiliki tipeV s c a l e : S × V → V s c a l e ( s c a l e ( s , v ) , v ) f ( x ) f X → Y X Y f f ( x ) ( x : X $\mathsf S$$\mathsf V$$\mathsf{scale}:\mathsf S\times \mathsf V\to \mathsf V$$\mathsf{scale}(\mathsf{scale}(s,v),v)$$f(x)$$f$$X\to Y$ untuk beberapa jenis dan . Jika tidak memiliki tipe fungsi, maka sama sekali bukan ekspresi yang terbentuk dengan baik. Apakah suatu ekspresi memiliki semacam atau memiliki beberapa jenis adalah pernyataan meta-logis. Tidak masuk akal untuk menulis sesuatu seperti: . Pertama, sama sekali bukan formula, dan kedua, bahkan secara konseptual tidak masuk akal karena jenis / tipe adalah apa yang memberi tahu kita formula mana yang terbentuk dengan baik. Kami hanya mempertimbangkan nilai kebenaran dari formula yang dibentuk dengan baik, jadi pada saat kami mempertimbangkan apakah beberapa formula berlaku, lebih baik kita sudah tahu bahwa formula tersebut telah terbentuk dengan baik!$X$$Y$$f$$f(x)$x : $(x:X)\implies y=3$$x : X$

Dalam teori himpunan, dan khususnya ZFC, satu-satunya simbol yang tidak logis sama sekali adalah simbol relasi untuk set keanggotaan, . Jadi adalah formula yang terbentuk dengan nilai kebenaran. Tidak ada istilah selain variabel. Semua notasi yang biasa tentang teori himpunan adalah perpanjangan definisi untuk ini. Misalnya, rumus seperti sering dianggap sebagai singkatan untuk yang dengan sendirinya dapat dianggap sebagai singkatan untuk yang merupakan kependekan dari Bagaimanapun, set apa pun dapat mengambil tempat dan semuanya sudah diatur!x ∈ y f ( x ) = y ( x , y ) ∈ f ∃ p . p ∈ f ∧ p = ( x , y ) ∃ p . p ∈ f ∧ ( ∀ z . z ∈ $\in$$x\in y$$f(x)=y$$(x,y)\in f$$\exists p.p\in f\land p=(x,y)$f π ( 7 ) = 3 π f ( x ) = { N , jika  x = 1 7 , jika  x = Q x ∩ R R , jika  x = ( Z , N

$$\exists p.p\in f\land(\forall z.z\in p\iff [z = x\lor(\forall w.w\in z\Leftrightarrow w = y)])$$ $f$Seperti yang saya tunjukkan dalam pertanyaan yang berbeda baru-baru ini, mana adalah bilangan real adalah benar-benar sah dan bermakna (dan bahkan mungkin benar) menetapkan ekspresi teoretis. Pada dasarnya, apa pun yang Anda tulis yang diuraikan dalam teori himpunan dapat diberi makna. Ini mungkin makna yang sepenuhnya palsu, tetapi memiliki satu makna. Set juga merupakan objek "kelas satu" dalam teori set. (Mereka lebih baik seperti mereka adalah satu - satunya objek biasanya.) Fungsi seperti$\pi(7)=3$$\pi$ $$f(x)=\begin{cases}\mathbb N, &\text{if }x=1\\7,&\text{if }x=\mathbb Q\\x\cap \mathbb R^\mathbb R,&\text{if }x=(\mathbb Z,\mathbb N)\end{cases}$$ adalah fungsi yang sepenuhnya sah dalam teori himpunan. Tidak ada yang bahkan analog dengan teori tipe ini. Yang terdekat adalah dengan menggunakan kode untuk alam semesta Tarskian. Himpunan adalah objek dari teori himpunan; tipe bukan objek dari teori tipe.

Suatu tipe bukanlah kumpulan dari hal-hal (tidak ada satu set pun dalam hal ini ...), dan itu tidak didefinisikan oleh properti. Tipe adalah kategori sintaksis yang memungkinkan Anda mengetahui operasi apa yang berlaku untuk istilah tipe itu dan ekspresi mana yang terbentuk dengan baik. Dari perspektif proposisi-sebagai-tipe, tipe apa yang mengklasifikasikan adalah bukti valid dari proposisi yang sesuai dengan tipe tersebut. Yaitu, istilah yang dibentuk dengan baik (yaitu diketik dengan baik) dari jenis yang diberikan sesuai dengan bukti yang valid (yang juga merupakan objek sintaksis) dari proposisi yang sesuai. Tidak ada yang seperti ini yang terjadi dalam teori himpunan.

Teori himpunan dan teori jenis benar-benar tidak sama.

Dalam prakteknya, mengklaim bahwa menjadi tipe biasanya digunakan untuk menggambarkan sintaks , sementara mengklaim bahwa adalah di set yang biasanya digunakan untuk menunjukkan semantik properti. Saya akan memberikan beberapa contoh untuk menjelaskan perbedaan dalam penggunaan tipe dan set ini. Untuk perbedaan dalam apa jenis dan set sebenarnya adalah , saya lihat jawaban Andrej Bauer .T x $x$$T$ $x$$S$

Sebuah contoh

Untuk memperjelas perbedaan ini, saya akan menggunakan contoh yang diberikan dalam catatan kuliah Herman Geuvers . Pertama, kita melihat contoh menghuni suatu tipe:

$$3+(7*8)^5:\mathrm{Nat},$$ dan contoh menjadi anggota dari set: $$3\in \{n\in\mathbb{N}\mid \forall x,y,z\in\mathbb{N}^+ (x^n+y^n\neq z^n)\}$$

Perbedaan utama di sini adalah untuk menguji apakah ekspresi pertama adalah bilangan alami, kita tidak harus menghitung makna semantik, kita hanya harus 'membaca' fakta bahwa semua literal bertipe Nat dan semua operator ditutup pada tipe Nat.

Namun, untuk contoh kedua dari himpunan, kita harus menentukan makna semantik dari dalam konteks himpunan. Untuk set khusus ini, ini cukup sulit: keanggotaan untuk set ini setara dengan membuktikan teorema terakhir Fermat! Perhatikan bahwa, seperti yang dinyatakan dalam catatan, perbedaan antara sintaksis dan semantik tidak selalu dapat digambarkan dengan jelas. (dan Anda bahkan mungkin berpendapat bahwa bahkan contoh ini tidak jelas, seperti yang disebutkan Programmer2134 dalam komentar)$3$$3$

Algoritma vs Bukti

Untuk meringkas, tipe sering digunakan untuk klaim 'sederhana' pada sintaksis beberapa ekspresi, sehingga keanggotaan tipe dapat diperiksa oleh suatu algoritma , sementara untuk menguji keanggotaan set, kita biasanya membutuhkan bukti .

Untuk melihat mengapa perbedaan ini bermanfaat, pertimbangkan kompiler dari bahasa pemrograman yang diketik. Jika kompiler ini harus membuat bukti formal untuk 'memeriksa jenis', kompiler diminta untuk melakukan tugas yang hampir mustahil (pembuktian teorema otomatis, secara umum, sulit). Jika di sisi lain kompiler hanya dapat menjalankan algoritma (efisien) untuk memeriksa jenis, maka secara realistis dapat melakukan tugas.

Motivasi untuk interpretasi yang ketat

Ada beberapa interpretasi makna semantik set dan tipe. Sementara di bawah perbedaan yang dibuat di sini tipe dan tipe ekstensional dengan pemeriksaan tipe yang tidak dapat dipastikan (seperti yang digunakan dalam NuPRL, seperti yang disebutkan dalam komentar) tidak akan menjadi 'tipe', yang lain tentu saja bebas untuk memanggilnya seperti itu (sama seperti gratis karena mereka akan memanggil mereka sesuatu yang lain, asalkan definisi mereka sesuai).

Namun, kami (Herman Geuvers dan saya), lebih suka untuk tidak membuang penafsiran ini dari jendela, yang saya (bukan Herman, meskipun dia mungkin setuju) memiliki motivasi berikut:

Pertama-tama, maksud interpretasi ini tidak jauh dari Andrej Bauer. Maksud dari sintaks biasanya untuk menggambarkan bagaimana membangun sesuatu dan memiliki algoritma untuk benar-benar membangunnya umumnya bermanfaat. Selain itu, fitur dari set biasanya hanya diperlukan ketika kita menginginkan deskripsi semantik, yang memungkinkan ketidakpastian.

Jadi, keuntungan dari deskripsi kami yang lebih ketat adalah untuk menjaga pemisahan tetap sederhana , untuk mendapatkan perbedaan yang lebih langsung terkait dengan penggunaan praktis umum. Ini berfungsi dengan baik, selama Anda tidak perlu atau ingin melonggarkan penggunaan Anda, seperti yang Anda lakukan, misalnya NuPRL.

Saya percaya bahwa salah satu perbedaan paling konkret tentang set dan tipe adalah perbedaan dalam cara "hal-hal" dalam pikiran Anda dikodekan ke dalam bahasa formal.

Baik set dan tipe memungkinkan Anda untuk berbicara tentang hal-hal, dan koleksi hal-hal. Perbedaan utama adalah bahwa dengan set, Anda dapat mengajukan pertanyaan yang Anda inginkan tentang berbagai hal dan itu mungkin benar, mungkin tidak; sementara dengan tipe, Anda harus terlebih dahulu membuktikan bahwa pertanyaan itu masuk akal.

$\mathbb B=\{\operatorname{true},\operatorname{false}\}$$\mathbb N=\{0, 1,\dots \}$$\operatorname{true}=1$

Salah satu cara untuk menafsirkan ini adalah bahwa dengan set, semuanya dikodekan menjadi satu koleksi: koleksi semua set. dikodekan sebagai , dikodekan sebagai dan dan can dikodekan oleh dua set berbeda. Jadi sebenarnya masuk akal untuk menanyakan apakah , karena dapat dipahami dengan menanyakan apakah "pengodean yang dipilih untuk sama dengan pengkodean yang dipilih untuk ". Tetapi jawaban untuk pertanyaan ini bisa berubah jika kita memilih pengkodean lain: ini adalah tentang pengkodean dan bukan tentang hal-hal itu.$0$$[0]=\{\}$$n+1$$[n+1]=\{[n]\}\cup [n]$$\operatorname{true}$$\operatorname{false}$$\operatorname{true}=1$$\operatorname{true}$$1$

Anda kemudian dapat memikirkan jenis sebagai menggambarkan pengodean dari hal-hal di dalamnya. Dengan tipe, untuk mengajukan pertanyaan apakah , pertama-tama Anda harus menunjukkan bahwa dan memiliki tipe yang sama, yaitu bahwa mereka dikodekan dengan cara yang sama, yang melarang pertanyaan seperti . Anda masih bisa ingin memiliki tipe besar di mana dan dapat dikodekan, dan kemudian diberi dua pengkodean dan , Anda bisa bertanya apakah$a=b$$a$$b$$\operatorname{true}=1$$S$$\mathbb B$$\mathbb N$$\iota_\mathbb B:\mathbb B\to S$$\iota_\mathbb N:\mathbb N\to S$$\iota_\mathbb B(\operatorname{true})=\iota_\mathbb N(1)$ tetapi fakta bahwa pertanyaan ini tergantung pada pengkodean (dan pilihan pengkodean) sekarang eksplisit.

Perhatikan bahwa dalam kasus-kasus itu, apakah pertanyaan itu masuk akal sebenarnya mudah dilihat tetapi bisa lebih sulit seperti dalam, misalnya, .$(\operatorname{if} \text{very_hard_question} \operatorname{then} 1 \operatorname{else} \operatorname{true})=1$

Singkatnya, set memungkinkan Anda mengajukan pertanyaan apa pun yang Anda inginkan, tetapi tipe memaksa Anda untuk membuat penyandian secara eksplisit ketika jawabannya mungkin bergantung pada mereka.